|
NOUS AVONS LU Fondements de l'Informatique : Logique, modèles, calculs INF 412 - Cours d'Olivier Bournez à l'École Polytechnique.
Tous ces domaines sont reliés par la question suivante : quelles sont les capacités et les limites des ordinateurs ? Même un téléphone est maintenant capable de résoudre très rapidement certains problèmes, comme trier un répertoire de plus d'un million d'entrées. Par contre, certains problèmes s'avèrent beaucoup plus lents et difficiles `a résoudre : par exemple, résoudre un problème d'emploi du temps, ou affecter les choix d'affectations des élèves de l'école polytechnique en fonction de leurs préférences ordonnées. Au coeur de ce cours est la compréhension de ce qui fait qu'un problème, comme le tri, est simple à résoudre informatiquement, alors qu'un problème comme un problème d'emploi du temps peut prendre des siècles à résoudre avec seulement un millier de données en entrées. Autrement dit, au coeur de nos interrogations est aussi la question suivante : qu'est-ce qui rend certains problèmes difficiles, et d'autres faciles ? C'est la question centrale de la complexité, et de la calculabilité. https://hal.archives-ouvertes.fr/hal-00760775/ ___________________
|
Ce cours est un cours sur les fondements de l'informatique : il se focalise sur trois domaines centraux en informatique : la logique, les modèles de calculs et la complexité.