Cet enseignement est constitué de 12 semaines de cours (2 heures) et de 14 semaines de TD ou de TP (3 heures), dont les contenus sont :

TD / TP Cours
Introduction : 
  • présentation de l'enseignement (plan),
  • définition de l'informatique,
  • fonctionnement d'un ordinateur (présentation matérielle et logicielle, système d'exploitation, gestionnaire de fenêtres),
  • notions de base d'un langage de programmation (algorithmes, langages informatique et machine, interpréteur/compilateur) ;
  • présentation du premier travail pratique.
1. Introduction au langage Pascal : 
  • définition d'un programme, d'un identificateur, d'un bloc, des déclarations de constantes et de variables, des instructions d'affectation et des appels de procédure d'entrée/sortie ;
    importance de l'ordre (déclarations de variables à la fin) ;
  • présentation des types de base (opérateurs et valeurs) et de la notion de variable en informatique (nom + valeur + type + adresse) ;
  • exemples de programmes simples avec entrée/sortie, possibilité d'utiliser les redirections en Unix.
TP 1 : 

introduction à Unix, X, Emacs et Pascal ;
ennoncé (PDF, 298 kO) et fichier fourni.

2. Conditionnelles, itérations : 
  • présentation des conditionnelles (if ... then ... [else], case rapidement) ;
  • définition des déclarations de types, exemples avec types énumérés et intervalles.
TD 1 : 

instructions d'entrée/sortie, conditionnelles, itérations, tableaux ;
ennoncé (PDF, 215 kO).

3. Tableaux et fonctions : 
  • présentation formelle des tableaux, exemples d'utilisation (classique + fonction) ;
  • présentation des déclarations de fonctions et de procédures.
TD / TP : 

calcul du jour de la semaine (cf. TD 1).

4. Fonctions, récursivité et preuves; : 
  • notion d'environement (un environement pour chaque bloc Pascal) ;
  • problème des variables globales et du passage par valeur/référence ;
  • présentation de la récursivité et des preuves.
TD 2 : 

récursivité et preuves ;
ennoncé (PDF, 199 kO).

5. Complexité : 
  • fonction de coût (temps, mémoire, échanges, ...), évaluations pratique et théorique ;
  • difficulté de l'évaluation exacte, intérêt de l'ordre de grandeur, formules de récurrence ;
  • exemples d'évaluation théorique (xn, Fibbonacci).
TD 3 : 

complexité et tris ;
ennoncé (PDF, 78 kO).

6. Algorithmes de tri : 
  • généricité des tris (les objets à trier doivent pouvoir être comparés et échangés) ;
  • arbre des méthodes de tri :  simples = sélection (direct ou à bulles) ou insertion (séquentielle ou dichotomique), complexes = division (tri rapide ou fusion) ou tri par tas ;
  • présentation complète des tris simples (algorithme, complexité résultante), présentation rapide des tris complexes (revus au TD suivant).
TD 4 : 

révisions pour un partiel ;
ennoncé (PDF, 216 kO).

7. Produits cartésien, pointeurs : 
  • présentation du produit cartésien entre type, ou enregistrement (record), et de la notion de pointeurs ;
  • implantation de listes chaînées.
TD 5, application en TP : 

tri rapide d'un tableau ;
ennoncé (PDF, 207 kO).

8. Listes : 
  • présentation des principales implantations de listes (tableau et liste chaînée) ; avantages et inconvénients de ces implantations ;
  • applications aux files et aux piles ; tableau ou liste chaînée pour pile, tableau avec deux indices ou liste doublement chaînée pour files ;
  • applications aux listes triées ; nécessité d'un autre type (les arbres).
TD 6, application en TP : 

enregistrements, pointeurs et récursivité ;
ennoncé (PDF, 193 kO) et fichiers fournis :  listes_rec.p, listes_iter.p et hanoi.p.

9. Arbres binaires : 
  • présentation des principales implantations d'arbres binaires (tableau et arbre chaîné) ; isomorphisme entre l'ensemble des arbres et celui des arbres binaires ;
  • applications aux expressions arithmétiques (à la traduction).
TD 7, application en TP : 

Flocon de von Koch (fractal) ;
ennoncé (PDF, 81 kO), fichiers fournis :  flocon.p, flocon2.plot, flocon3.plot, flocon4.plot, flocon6.plot.

10. Arbres binaires : 
  • applications des arbres binaires à la recherche (tri par insertion dichotomique) ;
  • définition des tas (arbres partiellement ordonnés), présentation du tri par tas.
TD 8, application en TP : 

tris et arbres binaires ;
ennoncé (PDF, 194 kO) et fichiers fournis :  insert.p et tas.p.

11. Graphes : 
  • présentation des principales implantations d'arbres binaires (liste de sommets et d'arcs, liste de sommets et matrice d'adjacence, liste de couples sommet-liste de successeurs) ;
  • applications des graphes à la résolution de problèmes (problème du voyageur de commerce, plus court chemin, etc.).
TD 9, application en TP : 

expressions arithmétiques ;
ennoncé (PDF, 190 kO) et fichier fourni :  expr.p.

12. Graphes : 
  • manipulation de graphes (parcours, tri topologique, fermeture transitive, etc.) ;
  • automates à états finis ; programmation par automates ; application à la complexité (notion de P/NP complétude).
TD 10, application en TP : 

automate de recherche ;
ennoncé (PDF, 53 kO).

 

Révisions.