IMG_1643.jpeg

# IFT 3355 ## Algorithmes et structures de données ### Automne 2023 ### Notes de cours ### Gilles Brassard Département d'informatique et de recherche opérationnelle Université de Montréal. ift3355\@iro.umontreal.ca http://www.iro.umontreal.ca/\~{}brassard/ift3355 version du 21 août 2023 ##...

# IFT 3355 ## Algorithmes et structures de données ### Automne 2023 ### Notes de cours ### Gilles Brassard Département d'informatique et de recherche opérationnelle Université de Montréal. ift3355\@iro.umontreal.ca http://www.iro.umontreal.ca/\~{}brassard/ift3355 version du 21 août 2023 ## Table des matières 1 Introduction 5 1. 1 Préliminaires...................................... 5 2. 2 Les algorithmes, c'est quoi?.............................. 6 3. 3 Petit historique de l'algorithmique.......................... 7 4. 4 Correction et terminaison.............................. 7 5. 5 Analyse de la complexité.............................. 9 2 Les listes chaînées 11 6 Chaînes de caractères 13 7 Les arbres 15 8 Les arbres binaires de recherche 17 9 Les tas 19 10 Le tri 21 10. 1 Tri par insertion................................... 21 11 Tables de hachage 23 12 Graphes 25 12. 1 Définitions...................................... 25 13. 2 Représentation des graphes............................. 26 13 Parcours de graphes 27 13. 1 Parcours en largeur.................................. 27 14. 2 Parcours en profondeur................................ 28 14 Arbres couvrants minimums 29 15 Plus courts chemins 31 16 Diviser pour régner 33 17 Programmation dynamique 35 18 Algorithmes gloutons 37 19 Recherche textuelle 39 20 Structures de données avancées 41 21 NP-Complétude 43 Index 45