Objectives
Deepen students' knowledge of analysis, algorithms, resolution methods, performance and programming. Among the course objectives, it is important to give students the knowledge and the practical methods and tools necessary for the implementation of the activity of modeling solutions and/or designing algorithms and their programming. The study of problems known to be complex and their solutions are proposed as well to complete this course.
Palabras clave
Algorithm, Algorithm analysis, Complexity, Graph, Problem Solving, Resolution strategy
Programme
- Analysis and the complexity computation of recursif algorithms (cf. CAML).
- Short introduction to TDAs and notable data types algorithmic solving strategies.
- Divide and Conquer Strategy, Dynamic Programming.
- Greedy approach (greedy / gradient approach).
- Algorithms with depth/breath first search , Back Tracking (AES and BT).
- Branch and Bound (B&B).
- Resolution of the characteristic equation for the complexity computation.
- Examples of complexity calculation.
- Proof methods (optional).
- Introduction to NP theory (optional).
- Algorithms on number theory with complexity (optional), optimization (in the sense of operation research).
- Graph as modeling tools, Graph algorithms, Graph theory.
Learning Outcomes
- The resolution of non-trivial problems in Computer Science requires a rigorous Mathematical approach. Once the problem has been posed, the research phases for a model, the algorithmic study of the solution and the calculation of its complexity are the important elements of this approach. The proof phase (and accuracy of the proposed solution) which completes this approach is not detailed in this course even if references will be given. Proving the correctness of what is written is nevertheless addressed.
- For the sake of a balanced theoretical / practical relationship, the objective of this course is to give students the knowledge and the practical methods and tools necessary for the implementation of the activity of designing algorithms and their programming. The study of examples of problems known to be complex and the solutions proposed in Computer Science will complete this course.
- To approach the definition of an algorithm from its statement anf to take into account the feasibility (computability) and the complexity of the algorithms.
- Study some well classified complex algorithm and their resolution strategies. Study of major data structures: graphs and tree. Realization of TDs and mini-projects with various strategies.
Assesment
Practical marks and final exam mark (50%-50%)