TCSS6AC - Info II

Tronc Commun d'Informatique

Responsables :

Xavier GOAOC, Professeur (Xavier.Goaoc@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)

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

   • Cours : Algorithmique, hachage et dictionnaires

   • TD sur machine : Hachage ouvert, corrigé

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

   • Cours : Arbres

   • TD sur machine : Arbres et Expressions, corrigé

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

   • Cours : transparents

   • Préparation du TD : Installation de lark, basic_parser.py

   • TD sur machine : Arbres et Interprétation, corrigé

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

   • Cours: transparents

   • TD sur machine : KdTree, corrigé

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

   • Cours: transparents

   • TD sur machine : Reconstruction de surface, corrigé

Test final le 21/05/2021

• durée : 1h

• modalité : sur machine

• programme : les 5 dernières séances

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

• téléphones, navigateurs, fichiers, anciens programmes interdits

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