Algorithmique 2

• Analyse d'algorithmes et étude de cas : la structure de données Union-find
• Tri fusion, tri rapide
• Files de priorité et tri par tas
• Arbres binaires de recherche équilibrés
• Graphes : parcours et cycles
• Composantes fortement connexes
• Arbres couvrants
• Plus courts chemins
• Programmation dynamique
• Algorithmes de flots
• Introduction à la programmation linéaire

A l’issue de cette unité d’enseignement, un étudiant sera capable de conceptualiser des méthodes et structures algorithmiques, d'optimiser des algorithmes et des structures de données et de résoudre avec des algorithmes appropriés des problèmes fondamentaux de théorie des graphes.

Cours pré-requis

Cours ayant celui-ci comme pré-requis

Cours ayant celui-ci comme co-requis

Cours, séances d'exercices et réalisation d'un projet.

Références, bibliographie et lectures recommandées

• Robert Sedgewick et Kevin Wayne, Algorithms 4th Edition, Addison-Wesley.
• Thomas Cormen, Charles Leiserson, Ronald Rivest et Clifford Stein. Introduction à l'algorithmique : cours et exercices corrigés. Seconde édition. Dunod.
   

Support(s) de cours

• Université virtuelle
• Syllabus

Contacts

Emmanuel Filiot
Campus de la Plaine, Bâtiment NO
 

Campus

Plaine

Méthode(s) d'évaluation

• Autre

Autre

Examen écrit avec entre autres des questions ouvertes, ainsi qu'un projet à réaliser en binôme.

Note importante: A chaque session d'examen, un.e étudiant.e pourra être contacté.e par le responsable du cours afin de justifier ses réponses à l'examen écrit. La date à laquelle des étudiant.es pourraient être convoqué.es au bureau du responsable sera communiquée à l'avance à toute la cohorte, en début de session. Les étudiant.es convoqué.es seront contacté.es au minimum un jour avant cette date, par email. En cas de non-présentation, la note pour le cours sera un zéro.

Construction de la note (en ce compris, la pondération des notes partielles)

Première session:

L'examen écrit comporte une question qui porte sur le projet. Si l'étudiant.e obtient au moins 50% des points à cette question, le projet compte pour 1/4 de la note finale. Sinon, le projet ne compte pas. La note est donc construite selon la règle suivante:

SI note_question_projet > 0.5 x note_max_question_projet 
ALORS note_cours := MAX(note_examen, (3 x note_examen + note_projet) / 4)
SINON note_cours := note_examen

où
- note_question_projet : note de l'étudiant à la question de l'examen écrit portant sur le projet
- note_max_question_projet : note maximale possible à cette question
- note_cours : note finale du cours
- note_projet : note du projet
- note_examen : note à l'examen écrit

Remarque 1: note_question_projet compte pour calculer note_examen, il est donc fortement recommandé de réaliser le projet afin d'obtenir des points à cette question. 
Report de note de projet: une note de projet ne peut PAS être reportée d'une année n à une année n+1

Deuxième session:

La deuxième session consiste également en un examen écrit (il n'y a pas de deuxième session projet). Il ne comporte pas de question sur le projet. 
La note de projet ne comptera pour 1/4 de la note de deuxième session, que si la question projet a été réussie à au moins 50% à l'examen écrit de première session.  

SI note_question_projet > 0.5 x note_max_question_projet 
ALORS note_cours := MAX(note_examen_2eme_session, (3 x note_examen_2eme_session + note_projet) / 4)
SINON note_cours := note_examen_2eme_session

Langue(s) d'évaluation

• français