L'informatique à Polytechnique

Les deux premières années

1. l'hétérogénéité des élèves dans ce domaine à l'entrée de l'école et pour une majorité d'entre eux, leur quasi-analphabétisme en informatique ;
2. la particularité de l'informatique d'être à la fois comme les mathématiques, une science et un art de l'artificiel, mais d'avoir aussi comme la physique, la chimie ou la biologie des aspects très concrets ;
3. le problème de la masse d'élèves ;
4. et bien sûr les contraintes de l'emploi du temps.

En quoi consiste ce niveau : Il inclut la compréhension des fondements de l'algorithmique, la programmation, la théorie de la calculabilité ; une connaissance de base du fonctionnement et de l'architecture des systèmes informatiques ; et, cela va de soi, une maîtrise d'outils essentiels comme le traitement de texte, le réseau (courrier et recherche d'information), les tableurs. Il faut insister sur le spectre très large de cette connaissance qui va, en caricaturant, du théorème d'incomplétude de Goedel à savoir publier une page sur le Web.

Pour arriver à ce niveau, nous proposons une voie rapide et une voie plus progressive. (Voir schéma). Les différents cours de ces deux premières années sont :

1. Informatique 1A : Introduction à l'informatique
2. Informatique 1B : Les bases de la programmation et de l'algorithmique
3. Informatique 2A : Les bases de la programmation et de l'algorithmique
4. Informatique F: Fondements de l'Informatique

Bien sûr, on ne peut garantir dans l'emploi du temps actuel que tous les élèves iront jusqu'à Informatique F. Tous auront au moins fait Informatique 1 (A ou B), et d'autres 2A ou 2B. Les cours 1B et 2A sont presque identiques. Le cours 2B devrait permettre à un nombre encore plus important d'élèves de se familiariser avec l'informatique à leur propre vitesse.

Informatique 1A

• Une partie des cours consistera en une introduction générale à l'informatique, aux logiciels, matériels, environnements informatiques et à la science sous-jacente.
• Une autre partie (60% environ) consistera à établir les bases de la programmation et de l'algorithmique, en enseignant un langage de programmation, la programmation de structures de données non dynamiques (scalaires, chaînes de caractères, tableaux) et les structures de contrôles élémentaires (itération, récursivité). Cela correspondra approximativement à la semaine d'initiation démarrée en mai 1999 (http://w3.edu.polytechnique.fr/informatique/Init0/semaine0.html)
• La partie par nature un peu "salon" des premiers 40% sera compensée par des travaux pratiques très concrets sur les outils de base (traitement de texte, courrier, recherche d'information, tableur).
• Ce cours demandera beaucoup de travail personnel car typiquement l'apprentissage d'un langage de programmation et la maîtrise de ce genre d'outils prend du temps. Il pourra être demandé, par exemple, de réaliser un document sous Word, une présentation utilisant Powerpoint et Excel, une page personnelle sur le Web, etc.

Informatique 1B

• Une première partie d'introduction générale à l'informatique est commune avec Informatique 1A.
• La partie programmation et algorithmique consistera à aller jusqu'aux structures de données dynamiques non destructives (listes et arbres non modifiables). L'effort sera porté sur la programmation plus que sur l'algorithmique. Dans la structure actuelle, on va grosso modo jusqu'au chapitre 4 (inclus) du cours Algorithmes et Programmation du Tronc Commun.
• On vérifiera aussi rapidement que les élèves ont les connaissances des environnements informatiques au moins au niveau d'Informatique 1A.

Informatique 2A

Informatique 2B

• option A: refaire 2A
• option B: autre chose mais quoi?

Informatique F

• Une moitié du cours sera dédié à des aspects plus complexes de l'algorithmique et de la programmation (structures de données dynamiques, éventuellement destructives; graphes; programmation dynamique, bactracking; diviser pour régner; modularité, calcul de dépendances, gestion de versions) [Cette partie de cours correspond à la fin du cours Algorithmes et Programmation du Tronc Commun actuel.]
• Une autre partie est plus thématique (programmation orientée-objet et interfaces graphiques; analyse lexicale et syntaxique avec un minimum d'automates finis; concurrence, sections critiques et sémaphores; systèmes digitaux et logiques, calcul propositionnel).
• Un aspect fondamental de ce cours est la réalisation d'un projet informatique d'envergure en binôme, dont une partie est faite en TD. Ce projet devrait exiger beaucoup de travail personnel.

La troisième année

• ce sont des cours généraux de niveau license/maîtrise, nécessaires pour une bonne compréhension de l'informatique par un élève intéressé par l'informatique.
• les élèves peuvent aussi ajuster leur cursus en choisissant des cours optionnels plus avancés ou spécialisés.
• les élèves doivent avoir une idée claire de ce que nous demandons, et pourquoi nous le demandons.
• nos cours sont des cours standards existant dans les meilleures universités. A part peut-être de rares cours d'approfondissements, il ne s'agit pas de cours orientés recherche.
• il n'y a pas de pré-requis entre 3A et 3B, mais l'enchainement est conseillé.
• ces cours préparent à des études informatiques complémentaires en école d'ingénieur ou à l'université.

Majeure 3A (1er semestre de 3ème année)

• [AR] Architecture des ordinateurs
• [AT] Automates, langages formels et calculabilité.

• [PL] Langages de programmation
• [DC] Informatique distribuée

• [CS1] Un cours parmi ceux listés plus bas

Majeure 3B (2ème semestre de 3ème année)

• [OS] Principes et Programmation des Systèmes d'exploitation
• [AA] Algorithmique avancée

• [DB] Bases de données
• [CO] Compilation

• [CS2] Un cours parmi ceux listés plus bas

Comme référence pour ces cours, on peut à la fois se repérer Curriculum 91 de l'ACM, ou à la liste suivante (non exhaustive) de liens:

• Computer Organization and Design, Stanford,
• Introduction to Computer Systems and Assembly Language Programming, Stanford,
• Operating Systems and Systems Programming, Stanford,
• Compilers, Stanford,
• Logic and Automated Reasoning, Stanford,
• Introduction to Automata and Complexity Theory, Stanford,
• Introduction to Databases, Stanford,
• Programming Languages, Stanford,
• Introduction to Computer Graphics, Stanford,

Contenus des cours

[AR] Architecture Von Neumann, etc
Référence: Hennessy/Patterson

[AT] Automates finis, automates à piles, classification de Chomsky, machines de Turing, exemples de problèmes indécidables, fonctions récursives de Kleene, théorèmes de récursion, théorème de Rice, thèse de Church, machines non-déterministes, classe NP, P-space, exemples élémentaires de réductions.
Référence: Kozen, Hopcroft/Ullman
JJ: autre manière de faire ce cours, prendre Pascal/Java à la place des machines de Turing, mais ca risque de ne pas être facile

[PL] Machines virtuelles, représentation des types de données, contrôle, typage, partage, données modifiables, gestion mémoire, sémantique, paradigmes de programmation.
Références: Sethi, Gunter, Mitchell, Reynolds, Tennent, Winskel
JJ: il me faut plus de réflexion pour comprendre l'articulation entre apprentissage d'un langage (ML) et une théorie simple suffisamment générale pour s'appliquer à d'autres langages; aller vers Prolog me parait demander un investissement théorique dément... pour l'intéret que ca représente..

[DC] Protocoles et généraux byzantins...
Références: Tannenbaum, Lynch
JJ: help, help!!

[OS] Allocation de ressources,
Références: Tannenbaum, Silberchatz
JJ: faut regarder ces livres

[AA] Algorithmes NP,
Références: Cormen, Garrey/Graham
JJ: help, tout en étant assez précis!!

[DB] SQL, langages de requêtes, modèle relationnel, et quoi??
Références: Abiteboul1, Abiteboul2, Ullman
JJ: help, help, help, objets + tableaux 2D!!

[CO] langage machine, analyse lexicale, analyse syntaxique, syntaxe abstraite, portée des variables, blocs d'activation, génération de code à 3 adresses, blocs de base, allocation de registres, ordonnancement et sélection des instructions.
Références: Aho/Sethi/Ullman, Appel
JJ: demander à Didier