Ce site regroupe les présentations pour le cours d’algorithmes et structures de données 1 (ASD1) du département des Technologies de l’Information et de la Communication (TIC) de la HEIG-VD.

Ces présentations sont basées sur les jupyter notebooks que vous trouverez dans le repository github associé à ces pages.

Pour imprimer ces slides, utilisez Google Chrome et ouvrez les présentations depuis la page d’impression. Il est probablement plus pertinent d’imprimer les notebooks correspondant dans nbviewer.

Pour certains sujets, vous trouverez des demos sur le site ASD1-Labs.

Introduction

1. Introduction à Python
   • Classes et objets

Récursivité

1. Multiplication russe

Tris

1. Tri à bulles
   • Stabilité
   • Complexité
2. Tri par sélection
3. Tri par insertion
4. Tri de Shell
5. Tri par fusion
6. Tri rapide
   • Sélection rapide
7. Tris en C et C++

Structures linéaires

1. Tableaux
   • de taille fixe
   • de capacité fixe
   • circulaire
   • de capacité variable
2. Listes
   • simplement chainée
   • doublement chainée
   • tri de Listes
3. Tableaux (suite)
   • Deque (Double Ended QUEue)
   • Tas (Heap)
4. Types de données abstraits
   • pile, file et file de priorité
5. Structures linéaires en C++
   • Sequence containers: array, vector, forward_list, list, deque
   • Container adaptors: stack, queue, priority_queue
   • Heaps

Arbres

1. Arbres généraux
2. Arbres binaires
   • Arbres à partir de 2 parcours
   • Expressions arithmétiques
3. Arbres binaires de recherche (ABR)
   • Itérer
   • Accès aléatoire
   • Complexité
   • Linéarisation et équilibrage
4. Types de données abstraits
   • Ensemble (set)
   • Tableau associatif (map)
5. Arbres binaires de recherche en C++
6. Arbres AVL (ASD2)
   • Complexité (ASD2)

Graphes