Conception des structures de données et des algorithmes

Aperçu

ABOUT THE COURSE:

The modern economy is run by algorithms. This a first-level course to introduce the students to the world of algorithm design, data structures, analysis, and programming.

We'll start with the asymptotics notation which captures time and space of algorithms in the worst-case.The basic data structures covered are -- array, list, queue, stack, matrix, tree, heap, set, and graph. The algorithmic paradigms covered are -- induction/recursion, divide-conquer, hashing, greedy-method, and dynamic-programming.In the lectures, the theory will be backed up by numerous practical CS examples.

The content is suitable for anyone who is mathematically inclined or computationally curious.INTENDED AUDIENCE:

Computer Science & Engineering, Mathematics, Electronics, Physics, & similar disciplines.PREREQUISITES:

Very good analytical skills.INDUSTRY SUPPORT:

Discrete Optimization, Cryptography/ Cyber Security, Coding theory, Computer Algebra, Symbolic Computing Software, Artificial Intelligence, Learning Software

Programme

• Introduction au cours
Vue d'ensemble des algorithmes et des structures de données
Importance et applications dans l'économie moderne
• Notation asymptotique
Notations Big O, Big Ω, et Big Θ
Analyse de la complexité temporelle et spatiale
• Structures de données de base
Tableaux et listes
Piles et files d'attente
Matrices
Arbres
Arbres binaires
Arbres AVL
Arbres de recherche binaire
Tas
Min-tas et max-tas
Tri par tas
Ensembles
Opérations et mises en œuvre
Graphes
Représentation (Matricielle/Liste d'adjacence)
Algorithmes de parcours (DFS, BFS)
• Paradigmes algorithmiques
Induction et récursion
Induction mathématique
Algorithmes récursifs
Diviser pour régner
Tri par fusion
Tri rapide
Exponentiation rapide
Méthode gloutonne
Principes et stratégies
Applications : Algorithmes de Kruskal et Prim
Programmation dynamique
Mémorisation vs. tabulation
Problèmes classiques : Problème du sac à dos, Suite de Fibonacci
Hachage
Fonctions de hachage
Techniques de résolution de collisions
• Applications pratiques et exemples
Scénarios réels en informatique
Études de cas et résolution de problèmes
• Revue du cours et applications industrielles
Revue des concepts clés
Application en optimisation discrète, cryptographie, IA, etc.
Directions futures et exploration dans la conception d'algorithmes

---

Enseigné par

Prof. Nitin Saxena

---

Matières

Computer Science