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 du 6 mars) et sa liste d'errata (au 6 mars).

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 - en présentiel l'après midi

    • Cours : transparents

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

    • TD sur papier : sujet, corrigé


Test intermédiaire le 19/03/2021 de 13h30 à 14h30

  • durée : 1h.

  • modalité : sur table, en présentiel.

  • programme : les 4 premières séances.

  • documents autorisés : polycopié + une feuille manuscrite (A4, recto-verso) personnelle portant votre nom.

  • tous systèmes électroniques (ordinateurs, téléphones, calculatrices, ... ) interdits. Pas même pour servir de montre.


Partie 2 : séances 5 à 9 en mode branché (utilisation de Python sur votre machine)

  1. Hachage – PEM - 26/03/2021 - en présentiel

  2. Arbres - PEM - 02/04/2021 - en présentiel

  3. Compilation – PEM - 09/04/2021 - en présentiel

  4. KDTree – CZ - 16/04/2021 - en présentiel

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

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