Portail:Informatique théorique

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 100 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

Portail

Projet

Discussion

Lumière sur… Certains comportements des fourmis sont à l'origine d'algorithmes d’optimisation (ici, des fourmis légionnaires du genre Dorylus). Les algorithmes de colonies de fourmis sont des algorithmes inspirés du comportement des fourmis et qui constituent une famille de métaheuristiques d’optimisation. Initialement proposé par Marco Dorigo et al. dans les années 1990, pour la recherche de chemins optimaux dans un graphe, le premier algorithme s’inspire du comportement des fourmis recherchant un chemin entre leur colonie et une source de nourriture. L’idée originale s'est depuis diversifiée pour résoudre une classe plus large de problèmes et plusieurs algorithmes ont vu le jour, s’inspirant de divers aspects du comportement des fourmis. En anglais, le terme consacré à la principale classe d’algorithme est « Ant Colony Optimization » (abrégé ACO). Les spécialistes réservent ce terme à un type particulier d'algorithme. Il existe cependant plusieurs familles de méthodes s'inspirant du comportement des fourmis. En français, ces différentes approches sont regroupées sous les termes : algorithmes de colonies de fourmis, optimisation par colonies de fourmis, fourmis artificielles, ou diverses combinaisons de ces variantes. Lire la suite Autres articles sélectionnés au sein du portail informatique théorique Modifier - Propositions & Archives		Le saviez vous ? Problème NP-complet: En théorie de la complexité, un problème NP-complet est un problème de décision qui satisfait les propriétés suivantes : Il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette propriété est notée NP. Tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de la classe NP....http://fr.wikipedia.org/wiki/NP-difficile 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 100 articles sont actuellement liés au portail.

Autres portails thématiques

Autres projets thématiques