Remerciez-le!

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

Chapitre 1 Introduction Ce cours est un cours sur les fondements de l’informati

Chapitre 1 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, cer- tains 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 affecter les choix d’affectations 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’est- ce 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 fa- cilement 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- 1 2 CHAPITRE 1. 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 d’avoir compris ces difﬁcultés. D’autres domaines sont fortement impactés par la complexité. Un des premiers qui l’a été historiquement est la cryptographie : dans la plupart des domaines, on cherche plutôt à privilégier les problèmes faciles à résoudre aux problèmes difﬁciles. La crypto- graphie est originale de ce point de vue, car elle recherche plutôt les problèmes difﬁciles à résoudre que les problèmes simples, car un code secret doit être dur à casser sans la clé secrète. On peut aussi se demander : pourquoi autant de logique dans un cours sur les fon- dements de l’informatique ? Une première raison est parce que les programmes informatiques et les langages informatiques sont essentiellement basés sur la logique. Les processeurs sont d’ailleurs essentiellement composés de portes logiques. Les programmes sont essentiellement faits d’instructions logiques, et de tests logiques. Comprendre cette logique permet de bien comprendre ce que font les programmes informatiques. De façon plus fondamentale, les programmes et les systèmes informatiques obligent bien souvent à décrire très précisément les objets sur lesquels ils travaillent : pour résoudre un problème d’emploi du temps, le système va obliger à décrire toutes les contraintes. Pour faire une requête sur une base de données, le système va obliger à formuler très précisément cette requête. Il s’avère que la logique mathématique est un outil très naturel pour décrire le monde qui nous entoure, et à vrai dire, le modèle le plus naturel que nous connaissons pour le faire. Comprendre les concepts de la logique, permet de bien comprendre nombre de concepts informatiques. Par exemple, pour dé- crire le système d’information d’une entreprise, ou tout système complexe, le meilleur outil reste bien souvent la logique mathématique. Une troisième raison est historique, et au cœur en fait de la naissance de l’infor- matique. Durant la première moitié du siècle dernier, des mathématiciens comme Kurt Gödel, Alonzo Church ou Alan Turing ont découvert que certains problèmes ne pou- vaient pas se résoudre par des dispositifs informatiques ou automatiques comme les ordinateurs. Par exemple, le problème de déterminer si un énoncé mathématique est vrai ou non. Cette tâche, qui est le quotidien du mathématicien, ne peut pas être résolue par aucun ordinateur, quelle que soit sa puissance. Les conséquences de ces résultats profonds ont permis la naissance d’idées sur des modèles d’ordinateurs qui ont mené à la conception des ordinateurs actuels. Au cœur de ces découvertes sont des liens très forts qui unissent algorithmes et dé- monstrations : une démonstration logique correspond à un algorithme. A partir d’hypo- thèses, on déduit des nouvelles assertions à l’aide de règles logiques. Réciproquement, un programme correspond à une démonstration dans un certain sens. Ce sont ces liens forts entre algorithmes et démonstrations qui ont fait naître l’infor- matique et ses concepts et ce bien avant l’existence même de machines aussi puissantes que celles que nous connaissons actuellement. Historiquement, la première question était : “qu’est-ce qu’une démonstration” ? Elle est maintenant devenue : “qu’est-ce 1.1. CONCEPTS MATHÉMATIQUES 3 qu’un ordinateur” ? Ils ont par ailleurs révolutionné notre conception des mathématiques, de l’informa- tique, et plus généralement du monde qui nous entoure. En mathématiques, ces liens ont mené à une crise des fondements, avec le retour sur des questions aussi fondamentales que celle-ci : qu’est-ce qu’un ensemble, qu’est-ce qu’une démonstration ? Que peut-on prouver ? L’ambition de ce document est plutôt de se focaliser sur l’informatique. Nous es- timerons que ce cours aura atteint son but si notre lecteur change au ﬁnal la réponse qu’il aurait pu faire à priori sur des questions aussi simples que celle-ci : – qu’est-ce qu’un ordinateur ? – qu’est-ce qu’une preuve ? – qu’est-ce qu’un algorithme ? – qu’est-ce qu’un bon algorithme ? Si tel est le cas, sa façon de programmer, ou d’appréhender un problème informa- tique ne devrait plus être la même. Remerciements L’auteur de ce document souhaite remercier vivement Johanne Co- hen, Bruno Salvy et David Monniaux pour leurs retours sur des versions préliminaires de ce document. Je remercie par ailleurs les promotions 2011-2012, 2012-2013 pour leurs retours. Des remerciements particuliers à Carlo Ferrari, Stéphane Lengrand et Ar- naud Lenoir pour des retours détaillés et des suggestions précises d’améliorations sur les versions antérieures de ce polycopié. Tous les commentaires (mêmes typographiques, orthographiques, etc.) sur ce do- cument sont les bienvenus et à adresser à bournez@lix.polytechnique.fr. Sur les exercices Certains des exercices sont corrigés. Les corrections se trouvent en ﬁn du polycopié dans un chapitre consacré à des solutions. Les exercices marqués d’une étoile nécessitent plus de réﬂexions. 1.1 Concepts mathématiques 1.1.1 Ensembles, Fonctions Soit E un ensemble, et e un élément. On note e∈E pour signiﬁer que e est un élément de l’ensemble E. Si A et B sont deux ensembles, on note A ⊂B pour signiﬁer que tout élément de A est un élément de B. On dit dans ce cas que A est une partie de B. Lorsque E est un ensemble, les parties de E constituent un ensemble que l’on note P(E). On notera A ∪B, A ∩B pour respectivement l’union et l’intersection des ensembles A et B. Lorsque A est une partie de E, on notera Ac pour le complémentaire de A dans E. Exercice 1.1. Soient A, B deux partie de E. Prouver les lois de Morgan : (A∪B)c = Ac ∩Bc et (A ∩B)c = Ac ∪Bc. Exercice 1.2. Soient A, B, C trois partie de E. Prouver que A ∩(B ∪C) = (A ∩ B) ∪(A ∩C) et A ∪(B ∩C) = (A ∪B) ∩(A ∪C). 4 CHAPITRE 1. INTRODUCTION Exercice 1.3. Soient A, B, C trois partie de E. Montrer que A ∩Bc = A ∩Cc si et seulement si A ∩B = A ∩C. On appelle produit cartésien, de deux ensembles E et F, noté E × F, l’ensemble des couples formés d’un élément de E et d’un élément de F : E × F = {(x, y)|x ∈E et y ∈F}. Pour n ≥1 un entier, on note En = E × · · · × E le produit cartésien de E par lui même n fois. En peut aussi se déﬁnir 1 récursivement par E1 = E, et En+1 = E×En. Intuitivement, une application f d’un ensemble E vers un ensemble F est un ob- jet qui associe à chaque élément e d’un ensemble E un unique élément f(e) de F. Formellement, une fonction f d’un ensemble E vers un ensemble F est une partie Γ de uploads/Philosophie/ introduction 3 .pdf