UE 4M017 Algorithmique et Complexité - automne 2020
Master de Sciences et Technologies

cours les mardis de 08h30 à 10h30 de la semaine du 07/09/2019 à la semaine du 30/11/2020
emploi du temps

-   Semaine du 07 Septembre -   Semaine du 14 Septembre -   Semaine du 21 Septembre -   Semaine du 28 Septembre
-   Semaine du 05 Octobre -   Semaine du 12 Octobre -   Semaine du 19 Octobre -   Semaine du 26 Octobre
-   Semaine du 02 Novembre -   Semaine du 09 Novembre -   Semaine du 16 Novembre -   Semaine du 23 Novembre
-   Semaine du 30 Novembre -   Semaine du 07 Décembre

travaux dirigés les vendredis de 13h45 à 16h45 de la semaine du 14/09/2020 à la semaine du 07/12/2020

Examen de première session la semaine du 04/01/2021
Examen de deuxième session la semaine du 24/05/2021 (le jeudi 27 mai de 09H00 à 11h00 très probablement)

Thèmes abordés :
  1. Tri et Recherche. Tas binomiaux et tas de Fibonacci. Arbres binaires de recherche randomisés.
  2. Gestion des partitions.
  3. Parcours de graphes. Arbres couvrants optimaux. Chemins optimaux.
  4. Calculabilité. Complexité. Classes P, NP et #P.
Mots clés :
Support de cours :