Comment pouvons-nous être certains qu'un objet répondant à certaines exigences existe ? Une façon de le démontrer est de passer en revue tous les objets et de vérifier si au moins l'un d'entre eux répond aux exigences. Cependant, dans de nombreux cas, l'espace de recherche est énorme. Un ordinateur peut aider, mais un raisonnement qui réduit l'espace de recherche est important à la fois pour la recherche informatique et pour le travail "à mains nues". Dans ce module, nous apprendrons diverses techniques pour montrer qu'un objet existe et qu'il est optimal parmi tous les autres objets. Comme d'habitude, nous nous entraînerons à résoudre de nombreuses énigmes interactives. Nous montrerons également quelques programmes informatiques qui nous aideront à construire un exemple.

Nous découvrirons deux méthodes puissantes pour définir des objets, prouver des concepts et mettre en œuvre des programmes : la récursivité et l'induction. Ces deux méthodes sont très utilisées en mathématiques discrètes et en informatique. En particulier, vous les verrez fréquemment dans les algorithmes - pour analyser la correction et le temps d'exécution des algorithmes ainsi que pour mettre en œuvre des solutions efficaces. Pour certains problèmes informatiques (par exemple, l'exploration de réseaux), les solutions récursives sont les plus naturelles. L'idée principale de la récursivité et de l'induction est de décomposer un problème donné en problèmes plus petits du même type. Être capable de voir de telles décompositions est une compétence importante à la fois en mathématiques et en programmation. Nous perfectionnerons cette compétence en résolvant ensemble divers problèmes.

La logique mathématique joue un rôle crucial et indispensable dans la création d'arguments convaincants. Nous utilisons les règles et le langage de la logique mathématique lorsque nous écrivons du code, lorsque nous raisonnons et prenons des décisions, et lorsque nous utilisons des programmes informatiques. Cette semaine, nous apprendrons les bases de la logique mathématique et nous pratiquerons des aspects délicats et apparemment contre-intuitifs, mais pourtant logiques, de la logique mathématique. Cela nous aidera à écrire un code lisible et précis, et à formuler nos pensées de manière rigoureuse et concise.

"Il y a des choses qui ne changent jamais". Au-delà d'une simple déclaration philosophique, cette phrase s'avère être une idée importante en mathématiques discrètes et en informatique. Une propriété qui est préservée au cours d'un processus est appelée un invariant. Les invariants sont très utilisés dans l'analyse du comportement des algorithmes, des programmes et d'autres processus. Être capable de trouver le bon invariant est une compétence importante que nous développerons ensemble dans ce module.

Dans ce module, nous considérons un puzzle à 15 bien connu où il faut rétablir l'ordre parmi 15 pièces carrées dans une boîte carrée. Il s'avère que le comportement de ce puzzle est déterminé par les mathématiques : il est résoluble si et seulement si la permutation correspondante est paire. Pour comprendre ce que cela signifie et pourquoi c'est vrai, nous apprendrons les propriétés de base des permutations paires et impaires - une notion importante en algèbre et en mathématiques discrètes. Ensemble, nous mettrons en œuvre un certain nombre de méthodes simples pour travailler avec les permutations. Vous les utiliserez ensuite comme blocs de construction pour mettre en œuvre un programme qui résout n'importe quelle configuration de ce jeu en un clin d'œil !