Algorithmique et structures de données ISC_14 / sISC_12

Informations sur le cours

• mardi A501 18h30 — 20h

Plan du cours

• Semaine 01 – Présentation
• Semaine 01 – L’algorithmique
• Semaine 01 – Les structures de contrôle
• Semaine 02 – Les tableaux
• Semaine 02 – Exercice 1 – Premiers algorithmes
• Semaine 03 – L’aléatoire
• Semaine 03 – La complexité algorithmique
• Semaine 03 – Exercice 2 – Structures de contrôle
• Semaine 04 – Représentation des nombres
• Semaine 04 – Exercice 3 – Représentation des nombres
• Semaine 04 – Matrices et chaines de caractères
• Semaine 05 – La récursivité
• Semaine 06 – Introduction au backtracking
• Semaine 06 – Les piles statiques
• Semaine 07 – Les tris
• Semaine 08 – Évaluation
• Semaine 09 – Évaluation
• Semaine 10 – Fin tris et piles
• Semaine 11 – Exemples d’usages de piles
• Semaine 11 – La liste chainée
• Semaine 12 – FAQ
• Semaine 13 – Les files d’attente Ajouter une partie sur comment faire une pile avec une liste chainée
• Semaine 14 – Les listes triées
• Semaine 15 – Évaluation
• Semaine 16 – Évaluation
• Semaine 17 – DLL
• Semaine 18 – Les tables de hachage Ajouter une partie sur les suppressions d’élements
• Semaine 19 – Les arbres
• Semaine 20 – Les arbres, suite et fin
• Semaine 20 – Le tri par tas
• Semaine 21 – Arbres AVL
• Semaine 22 – Évaluation
• Semaine 23 – Arbres quaternaires
• Semaine 24 – Compression et rotation d’image
• Semaine 25 – Graphes
• Semaine 26 – (https://gitedu.hesge.ch/algorithmique/cours/-/blob/main/slides_2024/cours_23.md) + algorithme plus court chemin (24) + arbre couvrant (25)
• Semaine 24 – Compression et rotation d’image (https://gitedu.hesge.ch/algorithmique/cours/-/blob/main/slides_2024/cours_19.md) => Compression d’image
• Semaine 20 – B-arbres (https://gitedu.hesge.ch/algorithmique/cours/-/blob/main/slides_2024/cours_21.md + https://gitedu.hesge.ch/algorithmique/cours/-/blob/main/slides_2024/cours_22.md)

Objectifs d’apprentissage

À la fin du cours, l’étudiant·e doit être capable de :

• savoir analyser et concevoir des algorithmes simples et des structures de données de base ;
• savoir mettre en oeuvre, en pratique, les différentes étapes nécessaires à l’élaboration d’algorithmes plus compliqués, notamment les algorithmes récursifs ;
• savoir analyser et concevoir des structures de données statiques et dynamiques les plus courantes ainsi que les algorithmes permettant de les manipuler ;
• savoir mettre en oeuvre, en pratique, les différentes étapes nécessaires à l’élaboration d’une application exigeant des structures de données et des algorithmes appropriés.

Contenus

• Méthodologie de la programmation : structures de contrôle, structures de données de base, récursivité, …
• Algorithmes de base : tris, hachage, recherche dans une table, algorithmes sur les structures linéaires statiques
• Structures de données de base : tableaux, enregistrements, pointeurs
• Structures de données linéaires dynamique : listes, piles, files d’attente, anneaux
• Structures d’arbres : arbres binaires, B-arbres, arbres quadratiques, arbres AVL
• Théorie des graphes : modélisation et structures de données, parcours en largeur et en profondeur, plus court chemin, coloration, recouvrement
• Notions de calcul de complexité

Les ressources

Le langage C

• The C Book, de Mike Banahan, Declan Brady & Mark Doran, janvier 1991
• Le C en 20 heures, d’Eric Berthomier & Daniel Schang, juin 2013
• A tutorial on pointers and arrays in C, de Ted Jensen, v1.2 septembre 2003
• C Traps and Pitfalls, d’Andrew Koenig

Les débogeurs

• Debugging with GDB, de Richard Stallman, Roland Pesch, Stan Shebs, et al.
• Decouverte du débogueur DDD, de Hiko Seijuro, août 2007

Aide-mémoires

• Bite Size Command Line, par Julia, 2018
• VIM — Carte de référence rapide, de Laurent Grégoire, v1.7 2003
• Aide mémoire sur les Makefiles

Me contacter

• Gregory Trolliet
• gregory.trolliet@hesge.ch
• @gregory.trolliet:matrix.org

Informations de compilation

Latex svg

Il faut avoir le paquet librsvg2-bin.

Évaluations

Examen d’automne

• Structures de contrôle
• Tableaux et chaines de caractères
• Tableaux à plusieurs dimensions
• Tris
• Représentation binaire

Examen d’hiver

En plus du champ de l’examen d’automne, rajouter :

• Opérations binaire
• Le backtracking
• Les piles
• Les opérations infix et postfix
• Les listes chainées

Examen de printemps

• Les arbres binaires
• Les tables de hachage
• Les arbres AVL
• Le tri par tas
• Les listes chainées (simples et doubles)

Examen d’été

• Les graphes
• Les tables de hachage
• Les arbres quaternaires

À modifier