1I2AB2 | Advanced algorithmics | Computer Science | 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. - Provide notions of theoretical computer science about undecidability and the complexity of problems. |
|
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. - Fundamentals of theoretical computer science: undecidability problems, Turing machines, complexity of problems, examples of NP-complete problems. |
|
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. - Knowledge of the existence of intractable problems in a reasonable (polynomial) time. |
|
Bibliographie | |
- 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 )