Aller au contenu

Portail:Informatique théorique

Le projet « Informatique théorique » lié à ce portail
Une page de Wikipédia, l'encyclopédie libre.

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 112 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.


Lumière sur…

Certains comportements des fourmis sont à l'origine d'algorithmes d’optimisation (ici, des fourmis légionnaires du genre Dorylus).
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.

Autres articles sélectionnés au sein du portail informatique théorique


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.

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

Logique mathématique

Calcul des propositionsCalcul des prédicatsLogique d'ordre supérieurSkolémisationThéorie des modèlesThéorie des typesThéorème d'incomplétude de GödelCorrespondance de Curry-Howard

Théorie des graphes

GrapheArbreArêteCliqueDegré

Familles de graphes

Graphe planaireGraphe completGraphe bipartiGraphe expanseur

Problèmes classiques

Coloration de grapheColoration équitableProblème du voyageur de commerceTriangulation de grapheRecherche de cheminProblème d'affectationCodes identifiants dans les graphesProblème de couverture de sommetsProblème SATThéorème de Robertson-Seymour

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

Mode de calcul

Calcul séquentielCalcul parallèleOrdinateur à ADNCalculateur quantique

Théorie des langages et systèmes de réécriture

Théorie des langagesCompilationExpression rationnelleThéorème de KleeneGrammaire formelleLangage rationnelLangage algébriqueLangage contextuelTransduction rationnelle

Intelligence artificielle

Généralités

Intelligence artificielleHistoire de l'intelligence artificiellePhilosophie de l'intelligence artificielle

Recherche localeRecherche tabouRecuit simulé

Algorithme génétiqueProgrammation génétique

Réseau de neurones artificielReconnaissance de formesApprentissage non-superviséApprentissage superviséClassification automatiqueReconnaissance optique de caractèresApprentissage profond

Algorithme de colonies de fourmisSystème multi-agentsOptimisation par essaims particulaires

Éthique de l'intelligence artificielleIntelligence artificielle amicaleAlignement des intelligences artificielles


Optimisation

Algorithme minimaxÉlagage alpha-bêtaDilemme du prisonnier

Retour sur trace (ou backtrack) • Séparation et évaluation (ou Branch & Bound) • Algorithme A*Programmation par contraintes

Optimisation linéaire : Algorithme du simplexeBranch and cut
Théorie des graphes : Algorithme de DijkstraAlgorithme de KruskalAlgorithme de Prim

Sémantique des programmes

Sémantique dénotationnelleSémantique axiomatiqueSémantique opérationnelleSémantique des langages de programmation

Algorithmique

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

Personnalités

Portails connexes

2 112 articles sont actuellement liés au portail.