Notes et plan de cours

Le tableau ci-dessous énumère les sujets touchés. Les ouvrages de référence principaux :

S Sedgewick, Robert. Algorithmes en Java (Pearson, 2004) ou Algorithms in Java: Parts 1–4, 3rd edition (Pearson, 2003).

SW Sedgewick, Robert et Wayne, Kevin. Algorithms, 4th edition (Addison-Wesley, 2011).

La connaissance des sujets marqués par * est exigée pour un «B/A-». Les sujets marqués par ** correspondent plutôt à un niveau «A+/A».

 

Sujets Notes Livres Liens
Plan de cours № 0
Principes de l’analyse de l’algorithms S 2, SW 1.4
* Principes de base : pire cas, meilleur cas, moyen cas № 1 S2.1,2.2,2.7
* Croissance de fonctions communes : constantes, logarithmiques, polynomiales,
exponentielles. Factorielle, approximation de Stirling, nombres Fibonacci, nombres harmoniques.
S2.3
* Notation asymptotique : définitions de grand O(f), petit o(f), Θ(f) et Ω(f).
Asymptotiques exactes f ∼ g. Expressions avec O() ou o(), règles d’arithmétique : O(f ) + O(g), O(f ) · O(g). Relations avec la limite
№ 4 S2.4 wikipedia-globe
* Application directe de la définition pour de ́montrer f = O(g) ou f = o(g).
* Détermination du temps de calcul et d’usage de mémoire pour algorithmes (itératifs) simples, et pour algorithmes récursifs (comme expression récursive).
* Récurrences simples: f(n) = f(n−1) + O(1); f(n) = f(n−1) + O(n); f(n) = f(n/2) + O(1); f(n) = f(n/2) + O(n) S2.5,S2.6
** Preuve par induction pour crooissance asymptotique d’une récurrence.
* Notion de temps amorti.
** Preuves de résultats sur le coût amorti d’opérations.
Principe d’analyse crédit/débit.
wikipedia-globe
* Validation expérimentale de temps de calcul.
Structures élémentaires et types abstraits S3, S4; SW 1.1, SW 1.2, SW 1.3
* Blocs de construction pour programmes Java. S3.1, SW 1.1
* Notion de type abstrait, interface, implantation, client. № 2 S3.3,S3.4
* Liste chaînée. Variations: listes circulaires, doublement chaînées. Sentinelles pour la tête et/ou la queue. Manipulation d’éléments sur la liste, insertion et suppression. Parcours d’une liste. S3.3,S3.4 wikipedia-globe
wikipedia-globe
wikipedia-globe
* Tableaux. № 3 S3.2 wikipedia-globe
* Types abstraits de files généralisées, piles et queues/files FIFO. S4.2,S4.7 wikipedia-globe
wikipedia-globe
* Implantations de pile et de queue par tableaux ou listes chaînées. Efficacité d’implantations différentes (temps de calcul pour les opérations standardes). Débordement. S4.4,4.5,4.7; SW 1.3
Intra
Tableau de hachage S14; SW 3.4, SW 3.5
* Notions de base pour tableaux de hachage: facteur de charge/remplissage, collisions № 6 S14.1
* Fonctions de hachage: méthodes de la division et de la multiplication.
* Résolution de collisions par chaînage séparé. Coût moyen des opérations de l’interface (table de symboles) en fonction de la facteur de charge. S14.2
* Addressage ouvert: notion de sondage/test. Procédures de recherche et d’insertion avec addressage ouvert. Suppression paresseuse et hachage dynamique. Sondage linéaire, grappe forte. Double hachage. S14.3-S14.6
** Coût moyen des opérations de l’interface avec sondage linéaire et double hachage en fonction de la facteur de charge
Appartenance-union S1.2-1.3; SW 1.5
* Problème de connexité,opérations d’appartenance-union. № 7 S1.2
* Structure Union-Find. Astuces: union-par-rang/union-par-taille, compression de chemin. S1.3, SW1.5
** Coût amorti d’opérations: O(\alpha(m,n)) pour Union-Find avec union équilibrée et compression de chemin.
Arbres S4.3, 5.4-5.7
* Terminologie pour structures arborescentes: arbre k-aire, hauteur, niveau, profondeur. Implémentation d’un arbre. № 8 S5.4
* Propriétés d’arbres binaires (relations entre le nombre de
noeuds internes et externes ou la hauteur)
S5.5
* Parcours d’un arbre: préfixe/préordre, infixe/dans l’ordre, postfixe/postordre, ordre de niveau S5.6
* Arbre syntaxique. Conversions d’expressions arithmétiques: notations infixe, postfixe et préfixe. S4.3
* Algorithmes récursifs sur les arbres: calcul de taille, hauteur ou profondeur de sous-arbres S5.7
Publicités