Portail:Informatique théorique

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)
2 024 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…

  • 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

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

Modifier

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

Königsberg graph.svg 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

Nuvola apps password.png 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 • Cryptage

Modifier

Xy icon.svg Mode de calcul

Calcul séquentiel • Calcul parallèle • Ordinateur à ADN • Calculateur quantique

Modifier

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

Brain mechanism.svg 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

Intelligence artificielle distribuée

Algorithme de colonies de fourmis • Système multi-agents • Optimisation par essaims particulaires

Modifier

Nuvola apps kmplot.svg 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

Nuvola apps edu miscellaneous.svg Sémantique des programmes

Sémantique dénotationnelle • Sémantique axiomatique • Sémantique opérationnelle • Sémantique des langages de programmation

Modifier

Nuvola apps ipo.svg 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

Portails connexes
2 024 articles sont actuellement liés au portail.

Médias utilisés sur cette page

Max-cut.svg
Auteur/Créateur: Miym, Licence: CC BY-SA 3.0
Maximum cut
Xy icon.svg
x/y icon.
Nuvola apps password.png
Auteur/Créateur: David Vignoni / ICON KING, Licence: LGPL
Icône du thème d'icônes Nuvola pour KDE 3.x.
Nuvola apps edu miscellaneous.svg
Auteur/Créateur: David Vignoni, traced User:Stannered, Licence: LGPL
Icon from Nuvola icon theme for KDE 3.x.
Gcalctool.svg
Auteur/Créateur: David Vignoni / ICON KING, Licence: LGPL
Icône du thème d'icônes Nuvola pour KDE 3.x / GNOME 2.
BandeauPortailLogiqueSmall.png
Auteur/Créateur: Original téléversé par Jmtrivial sur Wikipédia français., Licence: FAL
Source : File:BandeauPortailLogique.jpg
HSVissteduatt.svg
Auteur/Créateur: Jsdo1980, Licence: CC BY-SA 3.0
Did you know?
HSutvald2.svg
Auteur/Créateur: , Licence: LGPL
Shrunken, colored version created for ClockworkSoul's Coffee Roll template theme. part of the featured stars seriesCscr-featured.svg If anyone is interested in the original vector/3d files you may contact en:User:Avsa.
Blue-bg rounded stretched.svg
Une ligne présentant un dégradé du bleu vers le transparent
Nuvola apps keyboard layout.png
Auteur/Créateur: David Vignoni / ICON KING, Licence: LGPL
Icône du thème d'icônes Nuvola pour KDE 3.x.
Königsberg graph.svg
Auteur/Créateur: unknown, Licence: CC-BY-SA-3.0
Water gaz electricity Dudeney.jpg
Dessin original de Henry Dudeney pour l'énigme des trois maisons, tiré du livre Amusements in mathematics
Nuvola apps kmplot.svg
Auteur/Créateur: David Vignoni, Licence: LGPL
Image from the Nuvola icon theme for KDE 3.x
Crystal Clear kdm user female.svg
Auteur/Créateur: Ftiercel, Licence: GFDL
Une icône du thème Crystal Clear.
Crystal Clear app database.png
Auteur/Créateur: Everaldo Coelho and YellowIcon;, Licence: LGPL
Une icône du thème Crystal Clear
Brain mechanism.svg
Auteur/Créateur: Alexander Krainov, Licence: CC BY-SA 3.0
A human brain, a gear and an eye make up this icon.
Venn A subset B.svg
Venn diagram for "A is a subset of B". Modification of Image:Venn A intersect B.svg based on w:en:Image:Venn A subset B.png
Nuvola apps edu mathematics blue-p.svg
Auteur/Créateur: David Vignoni (original icon); Flamurai (SVG convertion); bayo (color), Licence: GPL
Square root of x formula. Symbol of mathematics.
Nuvola apps ipo.svg
Auteur/Créateur: , Licence: LGPL
Icon from Nuvola icon theme for KDE 3.x.
Nuvola apps package development.png
Auteur/Créateur: David Vignoni / ICON KING, Licence: LGPL
Icône du thème d'icônes Nuvola pour KDE 3.x.
Desktop computer clipart - Yellow theme.svg
Auteur/Créateur: AJ from openclipart.org, Licence: CC0
Nouvelle version de l'image refaite par Niridya sur Inkscape.