Cours INF5130 – Algorithmique
1er cycle
3 crédits
Informatique
Magistral
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).