/
Français
English
Parcours en largeur
Parcours en profondeur
UE INFO: Algorithmique 2
ECUE's code : SLUF501
PORTAIL SCIENCES ET TECHNOLOGIES
Informatique
Campus Valrose
Licence 3
Semestre impair
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.
Course's manager(s)
, Christophe Crespelle
In class
- 24h of lectures
- 36h of directed studies
PREREQUISITES
Before the start of the course, I must ...
-
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.
OBJECTIVES
By the end of this course, I should be able to...
- 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.
CONTENT
-
Parcours de graphes
-
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
Access to complete Syllabus (Authentification required)
Important
This syllabus has no contractual value. Its content is subject to change throughout this year: be aware to the last updates