UE INFO: Algorithmique 2

Code de l'ECUE : SLUF501

Ce cours donne droit à 6.0 ECTS.

Structure

PORTAIL SCIENCES ET TECHNOLOGIES

Domaine disciplinaire

Informatique

Lieu d'enseignement

Campus Valrose

Niveau du cours

Licence 3

Semestre

Semestre impair

Langue

Français

PRESENTATION

Ce cours vise à développer votre pensée algorithmique en l'appliquant à différents types d'objets tels que les graphes, les objets géométriques ainsi que les séquences de lettres et de nombres. Les exemples choisis sont des problèmes naturels qui apparaissent en pratique dans le traitement des données provenant de contextes variés. Le cours illustre plusieurs techniques algorithmiques classiques qui permettent de résoudre ces problèmes, et beaucoup d'autres, avec de bonnes performances en termes de ressources de calcul. Les compétences développées dans ce cours vous permettront dans votre vie professionnelle de développeur d'être capable de mettre en œuvre des solutions efficaces pour stocker des données, les manipuler et effectuer des calculs sur ces données.

Responsable(s) du cours

, Christophe Crespelle

Présentiel

24h de cours magistral
36h de travaux dirigés

PREREQUIS

Avant le début du cours, je dois ...

Faire le test de positionnement disponible sur l'espace Moodle
connaître et savoir utiliser les structures de données de base: tableaux et listes chaînées.
connaître et savoir utiliser les structures de données plus avancées: piles, files, tas binaires, arbres binaires de recherche.

OBJECTIFS

A la fin de ce cours, je devrais être capable de...

Modéliser un problème pratique par une question algorithmique (c.à.d. à laquelle on peut répondre par un calcul) sur un objet mathématique
Formuler des problèmes algorithmiques classiques et de décrire des algorithmes pour les résoudre.
Expliquer pourquoi un algorithme fourni la solution correcte.
Analyser la complexité temporelle d'un algorithme.
Analyser la complexité spatiale d'un algorithme.
Justifier le choix d'une représentation des données.

CONTENU

Parcours de graphes

Parcours en largeur
Parcours en profondeur
Plus courts chemins

Algorithme de Dijkstra

Algorithme de Bellman-Ford

Algorithme de Floyd-Warshall
Arbre couvrant de poids minimum

Algorithme de Prim

Algorithme de Kruskal
Flot maximum / coupe minimum

Algorithme de Ford-Fulkerson

Algorithme d'Edmonds-Karp
Enveloppe convexe

Algorithme de Jarvis

Algorithme de Graham

Approche diviser pour regner

Master theorem

Accéder au Syllabus complet (Authentification requise)

Important

Ce syllabus n’a aucune valeur contractuelle. Son contenu est susceptible d’évoluer en cours d’année : soyez attentifs aux dernières modifications.