suivant: Table des matières Table des matières

Algorithmique

http://alexandre-mesle.com

5 août 2010

Version pdf : algav.pdf
Version archive : algoAvance.tgz
Les autres cours : http://alexandre-mesle.com/?/Enseignement/
Les annales 2008/2009 : annales/

Table des matières
Complexité des algorithmes
- Borne asymptotique supérieure
- Mesure de temps d'exécution
Algorithmes itératifs
- Invariants de boucle
  - Le principe
  - Exemple
- Terminaison
- Complexité
Récursivité
- Sous-programmes récursifs
  - Factorielle
    - Exercice 1 - Opérations arithmétiques entières
    - Exercice 2 - La fonction
- Sous-programmes récursifs terminaux
- Listes chaînées
  - Notations et conventions
  - Rédaction
    - Exercice 8 - Prise en main
    - Exercice 9 - Tris
- Exemple de calcul de complexité d'un algorithme récursif
- Problèmes
- L'heure du code
Arbres
- Définitions par induction
- Preuves par induction
  - Lien avec les preuves par récurrence
  - Application aux EATPs
    - Exercice 1 - Opérandes et opérateurs
- Algorithmique dans les arbres
- Arbres -naires
  - L'heure du code
    - Exercice 5 - Arbres binaires et -aires
    - Exercice 6 - Arbres syntaxiques
Files de priorité
- Implémentations naïves
- Tas
- Tas binomial
Hachage
- Principe
- Collisions
  - Gestion des collisions par chaînage
  - Gestion des collisions par adressage ouvert
    - Exercice 1 - Résolution par chaînage
    - Exercice 2 - Temps moyen de recherche d'un noeud
AVL
- Arbres binaires de recherche
- Complexité dans le pire de cas
  - Exercice 7 - complexité moyenne d'une recherche
- Rotations
- AVLs
Modélisation
- Définition
- Exemple
- Sensibilisation à la complexité
- Terminologie
- Problèmethèque
- Exercices
Programmation linéaire
- Exemple
- Algorithme du simplexe en bref
- Modéliser un programme linéaire
- GLPK
Théorie de la complexité
- Terminologie et rappels
- Les classes P et NP
- Réductions polynomiales
- Les problèmes NP-complets
Introduction à la cryptographie
- Définitions
- La stéganographie
- Les chiffres symétriques sans clé
  - Exercice 1 - Chiffrement par transposition
  - Exercice 2 - La barrière de la langue
- Les chiffres symétriques à clé
  - Le chiffre de Vigenère
  - Enigma
- Les algorithmes asymétriques
GnuPG
- Présentation
- Utilisation
GMP
- Présentation
- Quelques points délicats
Arithmétique
- Divisibilité
- Division euclidienne
  - Exercice 4
- - Exercice 5
- Nombres premiers
  - Exercice 6
  - Exercice 7
- Nombres premiers entre eux
- Décomposition en produit de facteurs premiers
- Théorème de Bezout
- Algorithme d'Euclide
- Exercices
Arithmétique modulaire
- Congruences
- Espace quotient
- Pratique de l'inversion
  - Petit théorème de Fermat
  - Théorème d'Euler
    - Exercice 16 - Espaces quotient et GMP
RSA
- Principe
  - Chiffrement
  - Déchiffrement
- Résistance aux attaques
- Applications directes du cours
  - Exercice 17
- Exercices
Corrigés des programmes
- Fonctions récursives
- Fonctions récursives terminales
- Itérateurs et applications
- Tours de Hanoï
- Suite de Fibonacci
- Pgcd
- Pavage avec des L
- Complexes
- Listes chaînées
- Tri fusion
- Tri par insertion
- Transformée de Fourier
- Polynômes
- Arbres binaires et -aires
- Arbres syntaxiques
- Tas binomiaux
- AVL
- Knapsack par recherche exhaustive
- Prise en main de GLPK
- Le plus beau métier du monde
- Vigenere
- Changement de base
- Prise en main de GMP
- Vigenere
- Algorithme d'Euclide étendu sous forme de tableau
- Algorithme d'Euclide étendu avec GMP
- Espaces Quotients
- Test de primarité
Rappels mathématiques
- Sommations
  - Exercices
- Ensembles
- Raisonnements par récurrence
- Analyse combinatoire
- Exercices récapitulatifs
Bibliographie
À propos de ce document...

klaus 2010-08-05