Descriptif
Computer Science does not live without algorithms, and furthermore, ‘good’ algorithms, and thus, their analysis is crucial. The successful students after this class should understand why big industrial players now put a lot of efforts into the algorithm analysis and should be able to perform such analysis by themselves.
In the context of the CSN program we will tackle the network related classical and non-classical problems in computer communications and will study how to perform their analysis.
The main objective of the course is therefore the study of the design and analysis of algorithms, including the proofs of their correctness and their complexity estimation.
Lecturers: Drs. Natalia Kushik and Jorge López (TSP)
Format des notes
Numérique sur 20Littérale/grade européenPour les étudiants du diplôme M2 Systèmes Radio
Le rattrapage est autorisé (Max entre les deux notes)- Crédits ECTS acquis : 2.5 ECTS
La note obtenue rentre dans le calcul de votre GPA.
La note obtenue est classante.
L'UE est évaluée par les étudiants.
Pour les étudiants du diplôme Informatique pour les Réseaux
Le rattrapage est autorisé (Max entre les deux notes)- le rattrapage est obligatoire si :
- Note initiale < 10
- Crédits ECTS acquis : 2.5 ECTS
La note obtenue rentre dans le calcul de votre GPA.
La note obtenue est classante.
L'UE est évaluée par les étudiants.
Programme détaillé
Turing Machines. Computability. Decision problems. Decidable and undecidable problems. The Halting Problem (Lecture and exercises).
Algorithm and Problem Complexity. Complexity classes. Time and Space Complexity. Hardness and completeness of (decision) problems (Lecture and exercises).
SAT-problem (Lecture and exercises).
Algorithm analysis for “very known” problems (e.g., sorting) – where to start and how to proceed.
Hamiltonian path, Hamiltonian cycle problems, Clique problem (Lecture and exercises).
Data structures as a complexity reduction strategy.
Greedy algorithms as tempting ideas: how often do they lies and what is the price?
Algorithms and their analysis in related fields of Communication Networks:
– Complexity issues in information security (Lecture, discussion and students’ presentations) – background for the guaranteed secrecy.
– Complexity issues in software testing (Lecture, discussion and students’ presentations) – background for software certification.
Discussions and debates on open (Millennium) problems:
i) P =? NP.
ii) Alternative complexity definitions?
iii) Improving the performance of an implementation? ‘Classical’ compiler optimizations and beyond that; from high to low level programming languages?
Individual laboratories on the listed subjects will be performed. The algorithm analysis will be supported by the experimental evaluation of software quality parameters, such as performance, disc load, energy consumption, etc.
Evaluation
The evaluation includes a 3 hour written exam (1/2 of the final grade).
The class also contains the continuous evaluation represented as homework, laboratories and students’ presentations (1/2 of the final grade).