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)
824 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…

Problème du sac à dos

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


Le saviez vous ?

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

824 articles sont actuellement liés au portail.

Autres portails.

Avertissement