Complexité des algorithmes et graphes GIN3202
Enseignant: Email: Durée totale du cours: 45 H Semestre : 2 Nombre de crédits : 3
| Modules spécialisés | Modules de base | Sciences et techniques de l’ingénierie | Préparation à la carrière professionnelle |
| X |
| Nombre d’heures | Activités hors classe |
| 45 | 38 |
| Code | GIN3202 | Complexité des algorithmes et graphes |
Volume Horaire : 1h:30 Cours intégrés + 1h:30 travaux pratiques (par semaine)
Objectifs d’apprentissage et compétences visées
- Présenter les techniques d’évaluation de performances d’algorithmes.
- Analyser un problème pour évaluer sa difficulté algorithmique (au sens de la théorie de la complexité),
- Montrer comment améliorer la performance d’un algorithme, et ceci en utilisant des paradigmes et techniques avancées de conception d’algorithmes
- Étudier les graphes avec une concentration sur les arbres. L’idée est que les arbres seront des cas d’application de la partie complexité.
Contenu du cours
- Chapitre 1 (3h) : Introduction et motivation : Théorie de la calculabilité et théorie de la complexité
- Chapitre 2 (3h) : Préliminaires : rappels mathématiques et algorithmique
- Chapitre 3 (4h30) : Complexité temporelle (1) :
- Motivation et objectif : « Benchmarking »
- Le pire, le meilleur et le moyen cas
- Complexité : définition, propriétés, classe de complexité
- Chapitre 4 (3h) : Complexité temporelle (2) : Analyse des structures de contrôle
- Chapitre 5 (4h30) : Théorie de la NP-Complétude et Méthodes de résolution pratique de problèmes difficiles (NP-Complets, NP-Difficiles) : diviser pour régner, heuristique, algorithme glouton, programmation dynamique, etc
- Chapitre 6 (3h) : Les arbres
- Chapitre 7 (3h) : Les ABR
- Chapitre 8 (3h) : Les AVL
- Chapitre 9 (3h) : Les graphes
Méthodes d’enseignement et d’apprentissage
– Enseignement frontal (magistral) avec des exemples à résoudre en commun. – Exercices théoriques et études de cas (présentation et discussion).
Connaissances et compétences pré-requises
- Algorithmique et structures de données 1
- Types de données abstraits (Listes, piles, files)
Références bibliographiques
- Un polycopié (Notes du cours) de l’enseignant sera
Modalité d’évaluation
- 40% Contrôle continu (Test, Assiduité, Devoir surveillé)
- 60% Examen semestriel
Résultats d’apprentissage :
A l’issue de cette matière, l’étudiant doit être capable de :
- Concevoir, manipuler et raisonner sur une variété de techniques pour résoudre des problèmes de tri, de recherche et de représentation graphique
- Écrire des algorithmes et des structures de données efficaces pour une variété de problèmes fondamentaux
- Mener un raisonnement formel sur la complexité du problème et l’efficacité algorithmique
- Reconnaître les techniques de conception des algorithmes standard et appliquer ces techniques pour développer de nouvelles solutions informatiques aux problèmes
Compétences génériques Au terme de cette matière, les étudiants doivent avoir les compétences suivantes :
- Application des connaissances des principes fondamentaux de la science et de l’ingénierie
- Communication efficace sur l’efficacité de calcul
- Capacité à raisonner et à résoudre des problèmes
- Capacité à entreprendre l’identification, la formulation et la solution des problèmes
- Capacité de créativité et d’innovation
- Profond respect de la vérité et de l’intégrité intellectuelle, ainsi que de l’éthique de l’érudition