Digital educational booklet 2016/2017
| 1IAG2 | Advanced algorithmics | Computer Science - Apprentissage | S6 | ||||||
|---|---|---|---|---|---|---|---|---|---|
| Cours : 15 h | TD : 14 h | TP : 14 h | Projet : 0 h | Total : 43 h | |||||
| Responsable : Christine Porquet | |||||||||
| Pré-requis | |
|---|---|
| Course "Programming and C language" Course "Basics of algorithmics" Course "Software development tools" |
|
| Objectifs de l'enseignement | |
| - Go in depth into the basics of algorithmics learnt during the first semester by studying abstract data types for trees and graphs and the main algorithms to manipulate them. |
|
| Programme détaillé | |
| - Study of the search / insert / delete algorithms in binary search trees, balanced trees, B-trees and n-ary trees. - Representation of union-find sets by a forest of trees. - Study of basic algorithms on directed graphs and undirected graphs: depth-first and breadth-first traversals, strongly connected components, minimum weight spanning tree (Prim and Kruskal), shortest path (Moore-Dijkstra). All algorithms are analyzed and compared in terms of their complexity. |
|
| Applications (TD ou TP) | |
| Examples of practical work : - Depth-first and breadth-first traversal of binary search trees. - Search / insertion / traversal of an n-ary tree of words. - Depth-first and breadth-first traversal of undirected graphs and computing of their connected components. - Topological sort. - Scheduling of tasks by the Metra Potential Method (MPM). |
|
| Compétences acquises | |
| - Mastery of the main abstract data types and their implementation in C language. - Knowledge of algorithms on trees with analysis of their complexity. - Mastery of some graph algorithms. |
|
| Bibliographie | |
| - Introduction à l'algorithmique. T. Cormen et al., Dunod (1994) - Types de données et algorithmes. C. Froidevaux et al., Mc Graw-Hill (1990) - Algorithmes et structures de données en langage C. L. Ammeraal, InterEditions (1996) - Algorithmes de graphes. P. Lacomme et al., Eyrolles (2003) - Programmation en langage C. 3ème édition. S. Kochan, Pearson Education (2005) - Le langage C, norme Ansi. B. Kernigham, Dunod (2000) |
© 2024 - ENSICAEN ( Legal Notices - Credits )