Enseignements à l'École Nationale des Ponts et Chaussées (2001/2002)

Je suis l'enseignant du groupe 3 dans le modules Algorithmique et Programmation en première année de l'ENPC.

Module Programmation

Les sujets des séances:

• Séance 1: Environnement, compilation, principaux termes et composants d'un programme, structures de contrôle, arguments sur la ligne de commande.
  Corrigés de la séance 1
• Séance 2: Les types primitifs et les tabeaux. Déclaration, allocation, accès et utilisation.
  Corrigés de la séance 2
• Séance 3: Méthodes statiques (c'est-à-dire fonctions): déclaration, utilisation. Définitions récursives.
  Corrigés de la séance 3
• Séance 4: Rappels sur les premières séances, réponses aux questions, corrections des exercices.
  
• Séance 5 : Classes et objets, instances, méthodes et attributs.
  Corrigés de la séance 5
• Séance 6 (et 7) : Héritage, redéfinition, masquage.
  Corrigés de la séance 6
• Séance 7 : Redéfinition, typage et type dynamique, interfaces.
  Corrigés de la séance 7
• Séance 8 : Classes abstraites, interfaces. Exemple des piles et leur implémentation.
  Corrigés de la séance 8
• Séance 9 : Les collections de java.util.*.
  Corrigés de la séance 9
• Séance 10 : Les flots (package java.io.*.
  Corrigés de la séance 10 (à venir...)

Le sujet du devoir de programmation (à rendre le 15 Mars 2002 au plus tard):

Module Algorithmes

Les thèmes des séances:

• Séance 1: introduction à la notion de code. L'exemple du code ASCII et rappels sur les représentations binaires et les bases binaires et hexadécimales. Exemple du codage de Huffman et sa structure de données de file de priorité. Notion de code correcteur et détecteur d'erreurs.
• Séance 2: problèmes de recherche et complexités dans les structures de données: recherche séquentielle et dichotomique dans un tableau trié. Le problème de l'insertion: la structure de liste. Les arbres binaires étiquetés et les arbres binaires de recherche. Le hachage et ses variantes. La structure de tas comme implémentation des files de priorités.
• Séance 3: les graphes. Représentation en mémoire (matrice ou liste d'adjacence), les différentes familles (arbres, DAG...) et leurs parcours: en profondeur ou en largeur.
• Séance 4: les algorithmes gloutons. L'exemple des algorithmes de Prim et Kruskal. Le problème du rendu de monnaie comme exemple d'algorithme glouton avec retour arrière (backtrack) (indications pour le devoir de programmation).
• Séance 5: la programmation dynamique. L'exemple de l'algorithme de Floyd-Warshall. Comparaison au problème de la mutltiplication de matrice.
• Séance 6: l'approche « diviser pour régner ». Les exemples du tri fusion et du tri rapide.

[page d'accueil]