Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Introduction 2 Chapitre Introduction 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é Tous ces domaines sont reliés par la question s

Chapitre Introduction 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é 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 dif ?ciles à résoudre par exemple résoudre un problème d ? emploi du temps ou a ?ecter les choix d ? a ?ectations des élèves de l ? école polytechnique en fonction de leurs préférences ordonnées Au c ?ur 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ée Autrement dit au c ?ur de nos interrogations est aussi la question suivante qu ? estce qui rend certains problèmes dif ?ciles et d ? autres faciles C ? est la question centrale de la théorie de la complexité et de la calculabilité Pourquoi s ? intéresser à comprendre les problèmes dif ?ciles plutôt que d ? essayer de résoudre des problèmes très concrets Premièrement parce que des problèmes très simples et concrets et aux enjeux économiques considérables s ? avèrent faire partie des problèmes dif ?ciles Deuxièmement parce que comprendre qu ? un problème ne peut pas être résolu facilement est utile Cela signi ?e que le problème doit être simpli ?é ou modi ?é pour pouvoir être résolu Ce cours permet réellement de comprendre les pistes pour éviter les problèmes dif ?ciles à résoudre informatiquement En ?n et surtout parce que les problèmes dif ?ciles ont réellement des implications dans la conception de nombreux systèmes actuels Par exemple pour la véri ?cation l ? analyse et la conception de systèmes lorsqu ? on conçoit un système on souhaite en général qu ? il se comporte au minimum selon la spéci ?cation avec laquelle on l ? a conçu On aimerait que le processus de véri ?cation puisse s ? automatiser c ? est-à-dire que l ? on puisse garantir informatiquement qu ? un système donné véri ?e une sa spéci ?cation Surtout lorsque le système en question est d ? une complexité énorme comme les pro- C CHAPITRE INTRODUCTION cesseurs actuels et qu ? un unique être humain n ? est plus capable d ? en comprendre seul tous les composants Les résultats de ce cours montrent précisément que le processus de véri ?cation ne peut pas s ? automatiser facilement Tout l ? art de la véri ?cation de systèmes et donc de la conception de systèmes est de tenter d ? éviter ces dif ?cultés pour la rendre praticable ce qui nécessite