Home – Research – Teaching

Divers

Informations générales

• Cours : INF5130, Algorithmique
• Session : hiver 2025
• Groupe : 10
• Professeur : Samuele Giraudo
• Coordinatrice : Louise Laforest

Plan du cours

Accessible ici.

Entente d’évaluation

Accessible ici.

Calendrier des séances

Séance 1

• Lundi 6 janvier 2025, 13 h 30 à 16 h 30, salle PK-R310.
• Cours 1.
• Thèmes abordés : notion de problème ; notion d’algorithme ; exemples de problèmes ; complexité temporelle ; manipulation des sommations.

Séance 2

• Lundi 13 janvier 2025, 13 h 30 à 16 h 30, salle PK-R310.
• Cours 2
• Thèmes abordés : opérations barométriques ; croissance des fonctions ; fonctions polynomiales.

Séance 3

• Lundi 20 janvier 2025, 13 h 30 à 16 h 30, salle PK-R310.
• Cours 3
• Thèmes abordés : démonstrations de comportement asymptotique de fonctions ; rappels sur les logarithmes, somme des termes d’une suite arithmétique ou géométrique, fonctions plafond et plancher ; récurrences aux différences finies ; récurrences aux divisions finies ; théorème général (“Master Theorem”).

Séance 4

• Lundi 27 janvier 2025, 13 h 30 à 16 h 30, salle PK-R310.
• Cours 4
• Thèmes abordés : théorème général dans le cas où \(f\) est une fonction polynomiale ; méthode diviser pour régner ; exponentiation à la russe ; méthode efficace du calcul des nombres de Fibonacci ; somme maximale d’intervalle d’un tableau ; multiplications de grands nombres.

Séance 5

• Lundi 3 février 2025, 13 h 30 à 16 h 30, salle PK-R310.
• Cours 5
• Thèmes abordés : multiplication de matrices et algorithme de Strassen ; tri rapide ; tris en place ; statistique de rang \(i\) ; calcul de la médiane et sélection rapide de Hoare ; bases de la programmation dynamique ; calcul des coefficients binomiaux ; multiplication chaînée de matrices et parenthésages optimaux.

Séance 6

• Lundi 10 février 2025, 13 h 30 à 16 h 30, salle PK-R310.
• Cours 6
• Thèmes abordés : arbres binaires de recherche statiques optimaux ; sous-suite commune de longueur maximale.

Séance 7

• Lundi 17 février 2025, 13 h 30 à 16 h 30, salle PK-R310.
• Cours 7
• Thèmes abordés : distance de Leveshtein ; problème du voyageur de commerce (approche dynamque) ; révisions.

Séance 8 — Examen 1

• Lundi 24 février 2025, 13 h 30 à 16 h 30, salle PK-R310.
• Il porte sur toute la matière vue lors des 7 premières séances de cours.

Séance 9

• Lundi 10 mars 2025, 13 h 30 à 16 h 30, salle PK-R310.
• Cours 8
• Thèmes abordés : principes généraux des algorithmes gloutons ; problème de la monnaie ; problème du sac alpin ; problème des tâches ; codes et codage de Huffman.

Séance 10

• Lundi 17 mars 2025, 13 h 30 à 16 h 30, salle PK-R310.
• Cours 9
• Thèmes abordés : graphes (orientés, non orientés, pondérés) ; algorithmes de parcours de graphes (parcours en profondeur, parcours en largeur); algorithmes d’arbres couvrants maximaux (algorithmes de Prim et de Kruskal).

Séance 11

• Lundi 24 mars 2025, 13 h 30 à 16 h 30, salle PK-R310.
• Cours 10
• Thèmes abordés : algorithme de Ford-Fulkerson ; analyse amortie (méthode de l’agrégat, du comptable et du potentiel).

Séance 12

• Lundi 31 mars 2025, 13 h 30 à 16 h 30, salle PK-R310.
• Cours 11
• Thèmes abordés : files binomiales ; algorithmes à retour arrière (version générique et application au problème des \(8\) dames) ; questions/réponses au sujet du devoir 2.

Séance 13

• Lundi 7 avril 2025, 13 h 30 à 16 h 30, salle PK-R310.
• Cours 12
• Thèmes abordés : classes de problèmes : P, NP et NPC ; réductions polynomiales ; problèmes SAT et apparentés.

Séance 14

• Lundi 14 avril 2025, 13 h 30 à 16 h 30, salle PK-R310.
• Cours 13
• Thèmes abordés : exemples de réduction de problèmes ; révisions.

Séance 15 — Examen 2

• Mardi 22 avril 2025, 13 h 30 à 16 h 30, salle PK-R310.
• Il porte sur toute la matière vue lors de la 2e partie du cours (à partir de la séance 9), avec utilisation de notions vues depuis le début du cours.

Devoirs

Devoir 1

• Le sujet est disponible sur la page Moodle du cours depuis le 2025-01-28 à 9 h 10.
• À rendre sur la zone de dépôt du Moodle avant le lundi 17 février 2025, 23 h 59.

Devoir 2

• Le sujet est disponible sur la page Moodle du cours depuis le 2025-03-24 à 13 h 10.
• À rendre sur la zone de dépôt du Moodle avant le mardi 15 avril 2025, 23 h 59.

Examens

Il est fortement recommandé de bien prendre connaissance des modalités des examens qui figurent dans le plan du cours.

Démonstrations

• Les mardis (à partir de la semaine du 13 janvier 2025), 13 h 30 à 16 h 30, salle PK-R310.
• Auxiliaire de démonstrations : Amanda Boatswain Jacques.