Courses/ALGA

From LRDE

Titre

Algorithmique Avancée

Sigle

ALGA

Enseignant

Etienne Renault

Période

S1, App1

Public

Apprentis

Contrôle

Partiel

Durée

20h

Optionnel

non

Module

Informatique Fondamentale

Prérequis

ALSD

Objectifs

Ce cours étudie la façon de construire un algorithme et présente plusieurs classes d'algorithmes particulières ainsi que la façon de calculer les complexité dans chaque cas. Des exemples d'algorithmes de programmation dynamique permettent d'aborder la théorie des graphe sur la fin du cours.

Plan
  • Algorithmes récursifs, l'intérêt de la récursion terminale
  • Algorithmes diviser pour régner (ex. tri fusion, Karatsuba)
  • Programmation dynamique (ex.: distance de Levenshtein, chaîne de multiplications de matrices, plus longue sous-séquence commune)
  • Algorithmes gloutons (ex.: distributeur de monnaie, codage de Huffman)
  • Exponentiation rapide (et application à tous les monoïdes)
  • Calculs des plus courts chemins dans un graphe
  • Utilisation de l'exponentiation rapide de matrices pour les calculs
Documentation
  • Introduction to algorithms. Cormen, Leiserson, Rivest and Stein.
Support
Journaux