Difference between revisions of "Courses/ALGA"

From LRDE

Line 4: Line 4:
 
|teacher=Adl
 
|teacher=Adl
 
|period=S1, App1
 
|period=S1, App1
  +
|audience=Apprentis
 
|optional course=non
 
|optional course=non
 
|module=Informatique Fondamentale
 
|module=Informatique Fondamentale

Revision as of 16:06, 10 June 2014

Titre

Algorithmique Avancée

Sigle

ALGA

Enseignant

Alexandre Duret-Lutz

Période

S1, App1

Public

Apprentis

Contrôle
Durée
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