Courses/ALGA

From LRDE

Revision as of 11:49, 4 February 2020 by Edwin Carlinet (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Titre

Algorithmique Avancée

Sigle

ALGA

Enseignant

Edwin Carlinet

Période

S2, App1

Public

Apprentis

Contrôle

Partiel

Durée

12h

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