Portail Informatique théorique

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…

Problème du sac à dos
Crédit image:
licence CC BY-SA 2.5 🛈

Le problème du sac à dos, aussi noté KP (en anglais, Knapsack Problem) est un problème d’optimisation combinatoire. Il modélise une situation analogue au remplissage d’un sac à dos, ne pouvant supporter plus d’un certain poids, avec tout ou partie d’un ensemble d’objets ayant chacun un poids et une valeur. Les objets mis dans le sac à dos doivent maximiser la valeur totale, sans dépasser le poids maximum.

Le problème du sac à dos est l’un des 21 problèmes NP-complets de Richard Karp, de son article de 1972. Il est intensivement étudié depuis le milieu du siècle dernier. La formulation du problème est fort simple, mais sa résolution est plus complexe. Les algorithmes existants peuvent résoudre des instances pratiques de taille conséquente. Cependant, la structure singulière du problème, et le fait qu’il soit présent en tant que sous-problème d’autres problèmes plus généraux, en font un sujet de choix pour la recherche.

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

Portails connexes

2 113 articles sont actuellement liés au portail.
Autres projets thématiques
Portail:Informatique théorique (14)
    Droit d'auteur : le texte de l'article est disponible sous la licence CC BY-SA 3.0.
    Les détails concernant les licences et crédits des images sont disponibles en cliquant sur l'image.
    Le site Wikimonde est un agrégateur d'articles encyclopédiques, il n'est pas à l'origine du contenu des articles, ni des images.
    Le contenu de cet article est une copie de l'article d'origine (//fr.wikipedia.org/wiki/Portail%3AInformatique_th%C3%A9orique) publié sur Wikipédia (wiki collaboratif publié sous licence libre).
    Le contenu des articles n'est pas garanti.
    Le texte des articles n'est pas modifié par Wikimonde. Des modifications mineures de mise en page et des liens internes (pour faciliter la navigation) peuvent être effectués automatiquement.
    Des crédits concernant les images peuvent être ajoutés automatiquement selon les informations fournis par le site d'origine.
    Les images sont chargées depuis des sites externes, certaines peuvent ne pas s'afficher.
    Auteurs de cet article « Portail:Informatique théorique » :
    Binabik, Nouill, (:Julien:), Ju gatsu mikka, Romainhk, Léna, Erasmus.new, PierreSelim, Outs, Mrmw, 1 utilisateur non enregistré.