Portail:Informatique théorique

Une page de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Max-cut.svg 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)
827 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…

Résoudre l’énigme consiste à relier chacune des trois maisons du bas à chaque usine du haut par des chemins. Cette illustration est l’œuvre de Henry Dudeney qui présente cette énigme en 1917 dans son livre Amusements in mathematics.

L’énigme des trois maisons, aussi appelée l’énigme de l’eau, du gaz et de l’électricité, est un jeu mathématique dont l’analyse utilise un théorème de topologie ou de théorie des graphes. Ce problème n’a pas de solution. Georges Perec le cite en 1978 dans son livre Je me souviens : « Je me souviens des heures que j’ai passées, en classe de troisième je crois, à essayer d’alimenter en eau, gaz et électricité, trois maisons, sans que les tuyaux se croisent (il n’y a pas de solution tant que l’on reste dans un espace à deux dimensions ; c’est un des exemples élémentaires de la topologie, comme les ponts de Königsberg, ou le coloriage des cartes) ».

Cette énigme est déjà posée par H. E. Dudeney en 1917 dans son livre Amusements in mathematics. Il précise qu’« il existe une demi-douzaine d’énigmes aussi vieilles que les collines, qui réapparaissent perpétuellement ». Celle de l’article en est une, qu’il appelle eau, gaz, et électricité. Elle est popularisée par M. Gardner, qui la présente dans ses Six livres de jeux mathématiques

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


Le saviez vous ?

Edsger Dijkstra n'aimait pas les logiciels de traitement de texte et calligraphiait avec son stylo plume ses articles qu'il numérotait séquentiellement en les précédant des trois initiales de son nom, à savoir EWD. Ces documents qui constituent une contribution majeure à l'informatique sont accessibles en ligne sur le site des archives Dijkstra de l'Université du Texas.

Thèmes

Gcalctool.svg 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

Venn A subset B.svg 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

Konigsburg graph.svg Théorie des graphes

Lexique en 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

Nuvola apps password.png Information et cryptologie

Théorie de l'information

Théorie de l'information • Combinatoire des mots * Codage • Codage de l'information • Compression de données

Cryptologie

Cryptologie • Cryptographie • Cryptanalyse • Cryptage

Xy icon.svg Mode de calcul

Calcul séquentielCalcul parallèleOrdinateur à ADNCalculateur quantique

Nuvola apps keyboard layout.png 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

Brain mechanism.svg Intelligence artificielle

Méta-heuristique

Recherche localeRecherche tabouRecuit simulé

Algorithme évolutionniste

Algorithme génétiqueProgrammation génétique

Apprentissage automatique

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

Intelligence artificielle distribuée

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

Nuvola apps kmplot.svg Optimisation

Théorie des jeux

Algorithme minimaxÉlagage alpha-betaDilemme 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 simplexeBranch and cut
Théorie des graphes: Algorithme de DijkstraAlgorithme de Dantzig-FordAlgorithme de KruskalAlgorithme de Prim

Nuvola apps edu miscellaneous.svg Sémantique des programmes

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

Nuvola apps ipo.svg Algorithmique

Théorie de la complexité

Théorème de Cook • Réduction polynomiale • Complexité algorithmique • 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

827 articles sont actuellement liés au portail.

Autres portails.

Avertissement