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 113 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… Les hypercubes, ou n-cubes, forment une famille de graphes. Dans un hypercube $Q_{n}$, chaque sommet porte une étiquette de longueur $n$ sur un alphabet $A=\{0,1\}$, et deux sommets sont adjacents si leurs étiquettes ne diffèrent que d'un symbole. C'est le graphe squelette de l'hypercube, un polytope n-dimensionnel, généralisant la notion de carré (n = 2) et de cube (n = 3). Dans les années 1980, des ordinateurs furent réalisés avec plusieurs processeurs connectés selon un hypercube : chaque processeur traite une partie des données et ainsi les données sont traitées par plusieurs processeurs à la fois, ce qui constitue un calcul parallèle. L'hypercube est couramment introduit pour illustrer des algorithmes parallèles, et de nombreuses variantes ont été proposées, soit pour des cas pratiques liés à la construction de machines parallèles, soit comme objets théoriques. Lire la suite Autres articles sélectionnés au sein du portail informatique théorique Modifier - Propositions & Archives		Le saviez vous ? L'algorithme de Knuth-Morris-Pratt (qui devrait peut-être s'appeler l'algorithme de Knuth-Matiyasevich-Morris-Pratt) et le théorème de Cook-Levin partagent la particularité d'avoir été découverts vers 1970 indépendamment aux États-Unis et en Union soviétique. 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 113 articles sont actuellement liés au portail.

Autres portails thématiques

Autres projets thématiques