COURS // INF4100 Conception et analyse d'algorithmes
Mes cours favoris
Ce système permet de sélectionner vos cours favoris en prévision de votre inscription qui se fait sur le portail étudiant.
| Trimestre | Cours | Groupe |
|---|
Description du cours
- Cycle : 1
- Type de cours : Magistral
- Nombre de crédits : 3
- Discipline : Informatique
Description
Connaître les algorithmes de base de l'informatique. Être capable d'analyser leur complexité temporelle et spatiale. Connaître les grands principes de la conception des algorithmes et la programmation dynamique. Être capable d'appliquer ces principes. Comprendre la notion de problème NP-complet. - Notations asymptotiques - Opérations sur les notations asymptotiques - Équations de récurrence asymptotiques - Résolution de récurrence - Algorithmes et heuristiques voraces - Applications au problème de l'arbre de recouvrement minimal et à l'ordonnancement des travaux - Principe «diviser pour régner» (sélection en temps linéaire, arithmétique des grands entiers, calcul des nombres de Fibonacci etc.) - Principe de la programmation dynamique (multiplication chaînée de matrices, arborescences de fouilles optimales, etc.) - Exploration de graphes - Algorithmes à retour arrière - Introduction aux graphes de recherche de chaînes - Introduction à la NP-complétude
Modalité d'enseignement
Ce cours comporte une séance hebdomadaire de deux heures de travaux en laboratoire.
Préalables académiques
[INF3105 Structures de données et algorithmes]
