Complexité des algorithmes et graphes

Complexité des algorithmes et graphes  GIN3202

Enseignant: Email: Durée totale du cours: 45 H Semestre : 2 Nombre de crédits : 3

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