Calculabilité
Modèles de calcul
modifier
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
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 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
Théorie des graphes
Graphe • Arbre • Arête • Clique • Degré
Familles de graphes
modifier
Graphe planaire • Graphe complet • Graphe biparti • Graphe expanseur
Problèmes classiques
modifier
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
Information et cryptologie
Théorie de l'information
modifier
Théorie de l'information •
Combinatoire des mots •
Codage de l'information •
Compression de données
Cryptologie •
Cryptographie •
Cryptanalyse •
Chiffrement
Mode de calcul
Calcul séquentiel • Calcul parallèle • Ordinateur à ADN • Calculateur quantique
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
|