L'informatique est d'une part une discipline scientifique à part entière, d'autre part un puissant outil, exploité par toutes les disciplines, y compris l'informatique elle-même.
Ce cours constitue une introduction approfondie aux notions fondamentales de l'informatique, aussi bien scientifiques que techniques. Il s'adresse à ceux qui s'intéressent à l'informatique pour elle-même comme à ceux qui s'y intéressent en tant qu'outil.
Ce cours enseigne d'abord l'algorithmique, c'est-à-dire la science de la résolution systématique des problèmes et de l'organisation efficace des données. L'accent est mis sur la conception des algorithmes et sur l'analyse de leur efficacité. Un petit nombre de concepts et de techniques fondamentaux, qui sont exploités dans de nombreuses situations, sont présentés.
De plus, ce cours est conçu comme un approfondissement de la pratique de la programmation. Le langage Java est utilisé tout au long du cours, pour les travaux dirigés sur machine et pour un projet de programmation réalisé en binôme. Ceci se double d'une réflexion à propos de la programmation: on propose une introduction au test et à la preuve de programmes ainsi qu'une introduction à la programmation concurrente.
La description officielle du cours se trouve dans le catalogue des cours, en français et en anglais.
Voici un plan prévisionnel:
La vidéo. Transparents en pdf: animations, impression (en grand), impression 4 par feuille.
Matériel bibliographique: Mariages Stables de Donald Knuth. L'article original de 1962.
Transparents en pdf: animations.
Voici le sujet du DM01 à propos du problème des mariages stables. Vous pouvez déposer ici votre solution.
Il est normal que le compilateur avertisse Note: StableMatchingTest.java uses or overrides a deprecated API ou bien warning: [deprecation] stop() in java.lang.Thread has been deprecated. En principe, cela ne devrait pas empêcher le code de test de fonctionner.
Students who would prefer English-speaking PC and TD teachers are invited to enroll in group 4 or 8.
Les sujets et corrigés des pales précédentes sont disponibles ici. Toutefois, rappelons que le contenu du cours a en partie évolué depuis.