Portail:Informatique théorique

Portail

Projet

Discussions

Suivi

Portail de l' Informatique théorique

« L'informatique n'est pas plus la science des ordinateurs que l'astronomie n'est celle des télescopes.  » Michael R. Fellows et Ian Parberry (souvent attribué à Edsger Dijkstra) 2 114 articles sont actuellement liés au portail.

L'informatique théorique (aussi appelée informatique mathématique) est l'étude des fondements logiques et mathématiques de l'informatique. Plus généralement, le terme est utilisé pour désigner des domaines ou sous-domaines de recherche centrés sur des vérités universelles (axiomes) en rapport avec l'informatique. L'informatique théorique se caractérise par une approche par nature plus mathématique et moins empirique de l'informatique et ses objectifs ne sont pas toujours directement reliés à des enjeux technologiques. De nombreuses disciplines peuvent être regroupées sous cette dénomination diffuse dont la théorie de la calculabilité, l'algorithmique et la théorie de la complexité, la théorie de l'information, l'étude de la sémantique des langages de programmation, la théorie des graphes, la théorie des automates et des langages formels, etc.

Modifier

Lumière sur… Le problème du sac à dos, aussi noté KP (en anglais, Knapsack Problem) est un problème d’optimisation combinatoire. Il modélise une situation analogue au remplissage d’un sac à dos, ne pouvant supporter plus d’un certain poids, avec tout ou partie d’un ensemble d’objets ayant chacun un poids et une valeur. Les objets mis dans le sac à dos doivent maximiser la valeur totale, sans dépasser le poids maximum. Le problème du sac à dos est l’un des 21 problèmes NP-complets de Richard Karp, de son article de 1972. Il est intensivement étudié depuis le milieu du siècle dernier. La formulation du problème est fort simple, mais sa résolution est plus complexe. Les algorithmes existants peuvent résoudre des instances pratiques de taille conséquente. Cependant, la structure singulière du problème, et le fait qu’il soit présent en tant que sous-problème d’autres problèmes plus généraux, en font un sujet de choix pour la recherche. Lire la suite Autres articles sélectionnés au sein du portail informatique théorique Modifier - Propositions & Archives		Le saviez vous ? La grammairien Panini qui a vécu en Inde au Ve avant J-C avait inventé pour décrire le sanskrit une forme proche des notations de Backus-Naur. Modifier
Thèmes Calculabilité Modèles de calcul Automate fini • Automate sur les mots infinis • Transducteur fini • Automate à pile • Automate linéairement borné • Automate cellulaire • Machine de Turing • Lambda-calcul • Fonction récursive • Random access machine • Parallel random access machine  Problématiques Thèse de Church • Décidabilité • Problème de l'arrêt • Ensemble récursif • Ensemble récursivement énumérable Modifier Logique mathématique Calcul des propositions • Calcul des prédicats • Logique d'ordre supérieur • Skolémisation • Théorie des modèles • Théorie des types • Théorème d'incomplétude de Gödel • Correspondance de Curry-Howard Modifier Théorie des graphes Lexique en théorie des graphes Graphe • Arbre • Arête • Clique • Degré Familles de graphes Graphe planaire • Graphe complet • Graphe biparti • Graphe expanseur Problèmes classiques Coloration de graphe • Coloration équitable • Problème du voyageur de commerce • Triangulation de graphe • Recherche de chemin • Problème d'affectation • Codes identifiants dans les graphes • Problème de couverture de sommets • Problème SAT • Théorème de Robertson-Seymour Modifier Information et cryptologie Théorie de l'information Théorie de l'information • Combinatoire des mots • Codage de l'information • Compression de données Cryptologie Cryptologie • Cryptographie • Cryptanalyse • Chiffrement Modifier Mode de calcul Calcul séquentiel • Calcul parallèle • Ordinateur à ADN • Calculateur quantique Modifier Théorie des langages et systèmes de réécriture Théorie des langages • Compilation • Expression rationnelle • Théorème de Kleene • Grammaire formelle • Langage rationnel • Langage algébrique • Langage contextuel • Transduction rationnelle Modifier Intelligence artificielle Généralités Intelligence artificielle • Histoire de l'intelligence artificielle • Philosophie de l'intelligence artificielle Méta-heuristique Recherche locale • Recherche tabou • Recuit simulé Algorithme évolutionniste Algorithme génétique • Programmation génétique Apprentissage automatique Réseau de neurones artificiel • Reconnaissance de formes • Apprentissage non-supervisé • Apprentissage supervisé • Classification automatique • Reconnaissance optique de caractères • Apprentissage profond Intelligence artificielle distribuée Algorithme de colonies de fourmis • Système multi-agents • Optimisation par essaims particulaires Intelligence artificielle digne de confiance Éthique de l'intelligence artificielle • Intelligence artificielle amicale • Alignement des intelligences artificielles Modifier Optimisation Théorie des jeux Algorithme minimax • Élagage alpha-bêta • Dilemme du prisonnier Optimisation combinatoire Retour sur trace (ou backtrack) • Séparation et évaluation (ou Branch & Bound) • Algorithme A* • Programmation par contraintes Recherche opérationnelle Optimisation linéaire : Algorithme du simplexe • Branch and cut Théorie des graphes : Algorithme de Dijkstra • Algorithme de Kruskal • Algorithme de Prim Modifier Sémantique des programmes Sémantique dénotationnelle • Sémantique axiomatique • Sémantique opérationnelle • Sémantique des langages de programmation Modifier Algorithmique Théorie de la complexité Théorème de Cook • Réduction polynomiale • Problèmes NP-complet Paradigmes algorithmique Diviser pour régner • Algorithme glouton • Programmation dynamique • Algorithme probabiliste • Algorithme génétique • Heuristique Problèmes algorithmiques Théorie des graphes • Géométrie algorithmique • Structure de données • Optimisation Modifier
Personnalités Alonzo Church Kurt Gödel Alan Turing J. Barkley Rosser Stephen Cole Kleene Richard Stallman Ronald Rivest Adi Shamir Leonard Adleman
Portails connexes Portail de l'informatique Portail des mathématiques Portail de la logique Portail de la cryptologie Portail des bases de données Portail de la programmation informatique

2 114 articles sont actuellement liés au portail.

Autres portails thématiques

Autres projets thématiques