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

Licence Sciences et Technologies - L3
  2020-2021 - Semestre automne

 

Algorithmique, Programmation

et Complexité

Calendrier prévisionnel :

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 LIFAP1 et LIFAP3. Il est également préférable d'avoir suivi LIFASR3, LIFAP2 et LIFAP4. 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 le langage C++ sans recourir à l'héritage ni aux éléments les plus avancés de la norme C++11 (et normes postérieures). On pourra également être amené à programmer en C pur.

Cours magistraux :

Contenu fourni à titre indicatif

Cours 1  - Présentation du cours, rappel sur les prérequis

Fichiers de l'exemple de Module donné en exemple sur les slides : ici.

Cours 2 et 3 - Preuve d'algorithme, classes de complexité, analyse asymptotique, preuve et complexité des algorithmes itératifs
                

Cours 4 - Complexité des algorithmes récursifs, Tri fusion, TAD Séquence (ou Liste)
Cours 5Tri par partition (Quick-sort), Récursivité

Cours 6 -  TAD Ensemble et TAD Table,Table de hachage, Pointeurs de fonction

Cours 7-   Arbre binaire, Analyseur syntaxique

Cours 8  -  Arbre binaire de Recherche (ABR), AVL (Adelson-Velsky et Landis), Arbres 2-3-4, Arbres Rouge Noir

Cours 9  -  Graphes

Cours 10 -  Graphes, Méthodes de conception

 Cours  : Méthodes de conception (approfondis en TD10)

         Généricité


Liens utiles :

Liens utiles :
Spécificateurs de format de printf
Spécificateurs de format de scanf

Des exemples simples de lecture écriture sur fichier (ascii ou binaire) :  readwritescanfprintblablabla .

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


Informations concernant les TDs :

Feuilles de TD : fournies sous forme papier dans les TDs en présentiel.

Informations concernant les TPs :

Il pourra arriver que vous ayez à rappatrier des fichiers sources sur ce site.

La description suivante peut-être sujette à des modifications et est juste fournie à titre indicatif.

Séance de TP1

Séance de TP 2

Séance de TP 3 :

Séance de TP 4 :

Séance de TP 5 :

Séance de TP 6 :

Séance de  TP 7:

Séance de TP 8:

Séance de TP 9  

Séance de 10:  



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 -- 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  

TP :

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

Soutien :
     Voir les possibilités offertes par les tuteurs