COURS // INF5130 Algorithmique
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
Objectifs
Introduire aux principes fondamentaux de la conception et de l'analyse des algorithmes.
Sommaire du contenu
Introduction à la théorie de l'information. Entropie, information mutuelle et conditionnelle. Codes de longueur fixe/variable, théorème fondamental du codage de source. Détection et correction d'erreurs, distance de Hamming, codes linéaires.
Rappels sur la notation asymptotique. Complexité temporelle et spatiale, analyse probabiliste. Équations de récurrence et théorème fondamental. Algorithmes de force brute et voraces. Principe «diviser pour régner». Programmation dynamique. Algorithmes randomisés. Algorithmes à retour arrière. Méthode de séparation et d'évaluation progressive (Branch-and- bound). Heuristiques.
Machine de Turing : le problème de l'arrêt, la question P=NP. Réductions et NP-complétude.
Modalité d'enseignement
Ce cours comporte une séance obligatoire de laboratoire (2 heures).
Préalables académiques
[INF3105 Structures de données et algorithmes]
Horaire - Été 2024
Enseignant |
|
Horaire et lieu
Jour | Date | Heure | Lieu | Type |
---|---|---|---|---|
Lundi |
Du 29 avril 2024 au 9 août 2024 |
De 13h30 à 16h00 | PK-1780 | Campus de Montréal | Atelier |
Mercredi |
Du 29 avril 2024 au 9 août 2024 |
De 13h30 à 16h30 | PK-1780 | Campus de Montréal | Cours magistral |
Horaire - Automne 2024
Enseignant |
|
Horaire et lieu
Jour | Date | Heure | Lieu | Type |
---|---|---|---|---|
Lundi |
Du 3 septembre 2024 au 18 décembre 2024 |
De 13h30 à 16h30 | SH-3620 | Campus de Montréal | Cours magistral |
Mercredi |
Du 3 septembre 2024 au 18 décembre 2024 |
De 09h30 à 11h30 | SH-3620 | Campus de Montréal | Atelier |
Horaire - Hiver 2025
Enseignant |
|
Horaire et lieu
Jour | Date | Heure | Lieu | Type |
---|---|---|---|---|
Lundi |
Du 6 janvier 2025 au 25 avril 2025 |
De 13h30 à 16h30 | Cours magistral | |
Mardi |
Du 6 janvier 2025 au 25 avril 2025 |
De 13h30 à 15h30 | Atelier |