TCSS6AC - Info II

Algorithmes et complexité

Tronc Commun d'Informatique

Responsables :

Xavier GOAOC, Professeur (Xavier.Goaoc@univ-lorraine.fr)

Pierre-Etienne MOREAU, Professeur (Pierre-Etienne.Moreau@univ-lorraine.fr)

Cédric ZANNI, Maitre de Conférences (Cedric.Zanni@univ-lorraine.fr)

Durée du module : 30 heures

Crédits ECTS : 3.5

Objectif général : apprendre à concevoir des algorithmes et à les programmer

Syllabus : TCSS6AC

Contenu

  • modèles et programmation

  • les objets

  • algorithmique et récursivité

  • arbres et graphes

  • robots, questions autour du temps

  • réseaux et communications

Support

Polycopié des séances 1-4 (version papier distribuée à la première séance) et sa liste d'errata (au 19 février).

Support du cours Python

Nous utilisons les environnements de programmation Wing 101 qui est bien adapté à l'enseignement à un public débutant.

A titre personnel, vous pouvez utiliser l'outil Spyder qui permet d'éditer, d'exécuter, de déboguer et de visualiser les variables dans un même environnement.


Partie 1 : séances 1 à 4 en mode débranché

  1. Marriages stables – XG - 05/02/2021 - en présentiel le matin

    • Cours : transparents.

    • Notions abordées : problème d'affectation, algorithme de Gale-Shapley et son analyse, plateforme parcoursup

    • TD sur papier : sujet, corrigé.

  2. Récursion– XG - 12/02/2021 - en présentiel l'après midi

    • Cours : transparents.

    • Notions abordées : récursion, recherche dichotomique, diviser pour régner, recherche par retour arrière

    • TD sur papier : sujet , corrigé.

  3. Complexité - XG - 19/02/2021 - en présentiel le matin

    • Cours : transparents.

    • Notions abordées : complexité asymptotique pire-cas, arbres d'exécution, théorème maître, algorithme de Karatsuba

    • TD sur papier : sujet, corrigé.

  4. Cas d'étude – XG - 12/03/2021

    • Cours : transparents (à venir)

    • Notions abordées : conception d'un algorithme avancé, sélection en temps linéaire ("median of medians")

    • TD sur papier : sujet (à venir), corrigé (à venir)


Test intermédiaire le 19/03/2021

  • durée : 1h

  • modalité : sur table

  • programme : les 4 premières séances


Partie 2 : séances 5 à 9 en mode branché

(le programme des séances 5 à 9 est en cours de finalisation et peut encore changer)

  1. Arbres – PEM - 26/03/2021

  2. Hachage - PEM - 02/04/2021

  3. Graphes – PEM - 09/04/2021

  4. Structures de données spatiales – CZ - 16/04/2021

  5. Structures de données spatiales – CZ - 30/04/2021


Test final le 21/05/2021

  • durée : 2h

  • modalité : sur machine

  • programme : les 5 dernières séances


Cours 8h30-9h30 et 13h30-14h30

TD 9h45-11h45 - Présentiel ou Teams

  • Groupe B1 : Pierre Lermusiaux

  • Groupe B2 : Clélie Amiot

  • Groupe B3 : Fabienne Thomarat-Buffet

  • Groupe B4 : Yoann Fleytoux

TD 14h45-16h45 - Présentiel ou Teams

  • Groupe A1 : Fabienne Thomarat-Buffet

  • Groupe A2 : Dominique Benmouffek

  • Groupe A3 : Pierre Lermusiaux

  • Groupe A4 : Yoann Fleytoux

  • Groupe A5 : Paul Caillon