Université Claude Bernard - Département Informatique Lyon 1
Algorithmique, Programmation et Complexité - LIF9

Licence Sciences et Technologies - L3
  2015-2016 - Semestre automne

 

Algorithmique, Programmation

et Complexité


Nouvelles récentes :




Prérequis Cours TD et TP Phrases clés BibliographieInformationsEnseignants

Prérequis :

Cet enseignement nécessite de connaître et d'avoir intégré le contenu des UEs LIF1 et LIF5. Il est également préférable d'avoir suivi LIF3 et LIF7. Voici ici une liste non exhaustive des notions sur lesquelles vous rafraîchir la mémoire avant d'aborder l'UE :

Plus de précisions sur le(s) langage(s)

Le langage utilisé est une extension du langage C (ANSI89-ISO90) auquel sont ajoutés certains éléments C++ (ISO98), à l'exclusion des éléments relatifs à la programmation objet (au programme de LIF13).  On pourra également choisir de programmer en C pur  (on peut dans ce cas utiliser une normalisation plus récente que ISO90).

Transparents de cours :

Cours 1 - Paradigmes de programmation, prérequis

Cours 2 - Généricité

Cours 3 - Preuve d'algorithme, classes de complexité, preuve et complexité des algorithmes itératifs (resp. récursifs),

Cours 4 - Complexité des algorithmes récursifs, tri par partition (Quick-sort), TAD Séquence (ou Liste)
Cours 5 - TAD Ensemble et TAD Table, Table de hachage

Cours 6 -  Table de hachage (fin), Arbre binaire (AB)

Cours 7 -  Analyseur syntaxique, Arbre binaire de Recherche (ABR), AVL (Adelson-Velsky et Landis)

Cours 8 -  AVL, Graphes

Cours 9 -  Graphes

Cours 10 :  Réseaux, Méthodes de conception

Les phrases clé du cours :

.

Informations concernant les TDs :

Les feuilles de TD sont distribuées pendant les séances. 

Informations concernant les TPs :

Les feuilles de TP sont distribuées pendant les séances. Il pourra arriver que vous ayez à rapatrier des fichiers sources sur ce site.

Spécificateurs de format de printf
Spécificateurs de format de scanf

Concernant les outils de gestion de projet, de compilation et de déboggage (gcc, valgrind), vous pouvez vous rafraîchir la mémoire en  consultant  les prérequis de LIF7 ainsi que les liens suivants :

- Compilation avec gcc sous Linux
- Mise au point de programmes avec GDB
- Gestion de projet : Make et Makefile, ou Comment écrire un Makefile


Séance de TP1 : 

Séance de TP en autoformation :

    Fin du TP1

Séance de TP 2 : 

Séance de TP 3 et 4

Séance de TP 5 :

Séance de TP 6 :

Séance de TP  7 et 8:

Séance de TP 9 et 10 

Séance de TP 11 :


Contrôle continu Intégral

Rendu de TPs 
Interro de cours : au début de certaines séances de TD
Contrôle terminal
 (exemple annale contrôle final)

Il est vivement conseillé :

L'assiduité des étudiants entre également dans l'évaluation du contrôle continu.

Bibliographie C++ :

      1. The C++ Programming Language,
        Bjarne Stroustrup, 3. Auflage, Addison-Wesley, 1997, (existe en version française)
      2. Le langage et la bibliothèque C++, Norme ISO
        Henri Garetta, Ellipse, 2000
      3. C++ Primer, Lippman & Lajoie,
        Third Edition, Addison-Wesley, 1998
      4. Effective C++
        Scott Meyers, Second Edition, 1998
      5. The Design and Evolution of C++
        Bjarne Stroustrup, 1994
      6. The ISO/IEC C++ standard,
        American National Standards Institute,  First Edition, 1998

Bibliographie C :

    1. The C Programming Language (Ansi C)
      B.W. Kernighan - D.M. Ritchie
      Ed. Prentice Hall, 1988
      Le langage C - C ANSI 
      B.W. Kernighan - D.M. Ritchie
      Ed. Masson - Prentice Hall, 1994
    2. Langage C - Manuel de référence
      Harbison S.P., Steele Jr. G.L.
      Masson, 1990
      (traduction en français par J.C. Franchitti)
    3. Méthodologie de la programmation en langage C,
      Principes et applications
      Braquelaire J.P.
      Masson, 1995
    4. N'oubliez jamais de vous servir du man!

Bibliographie Algorithmique :

    1. Introduction to Algorithms
      Cormen T., Leiserson C., Rivest R.
      MIT Press, Cambridge, 1990
      Introduction à l'algorithmique
      Cormen T., Leiserson C., Rivest R.
      Dunod, 1994
    2. Structures de données et algorithmes
      A. Aho, J.Hoptcroft, J. Ullman,
      InterEditions
    3. Types de données et algorithmes
      C. Froideveaux, M.C. Gaudel, M. Soria,
      Ediscience
    4. The Art of Computer Programming
      D. Knuth, Vol. 1 et 3, Addison-Wesley
    5. Algorithmes de graphes
      C. Prins,
      Eyrolles

Sites web

Unix and Internet Fundamentals HOW TO ( VO, VF )
 

Informations pratiques et enseignants:


Cours magistral :

    Mercredi 10h à 11h30 -- 10 séances (ne correspondant pas forcément à des semaines consécutives)

TD :

    10 séances de 1h30 (ne correspondant pas forcément à des semaines consécutives) le mercredi de 8h15 à 9H45 

TP :

    10 +1 séances de 3h00, le mercredi de 14h30 à 17h30

Soutien :
     (voir calendrier)