Table des matières

• Complexité des algorithmes
  • Borne asymptotique supérieure
  • Mesure de temps d'exécution
    • Algorithmes en temps constant, $\mathcal {O}(1)$
    • Algorithmes de complexité linéaire, $\mathcal {O}(n)$
    • Algorithmes de complexité logarithmique, $\mathcal {O}(log n)$
    • Algorithmes de complexité quadratique $\mathcal {O}(n^2)$
    • Algorithmes de complexité $\mathcal {O}(n.log n)$
    • Algorithmes de complexité exponentielle $\mathcal {O}(k^n), k > 1$
    • Algorithmes de complexité polynomiale $\mathcal {O}(n^k)$, $k$ fixé
  
  
• Algorithmes itératifs
  • Invariants de boucle
    • Le principe
    • Exemple
  • Terminaison
    • Le principe
    • Fin de l'exemple
    • Un autre exemple
  • Complexité
  
  
• Récursivité
  • Sous-programmes récursifs
    • Factorielle
  • Sous-programmes récursifs terminaux
    • Factorielle
    • Exponentiation
    • Itérateurs
  • Listes chaînées
    • Notations et conventions
    • Rédaction
  • Exemple de calcul de complexité d'un algorithme récursif
    • L'algorithme
    • Résolution exacte
    • Vérification par récurrence
  • Problèmes
  • L'heure du code
  
  
• Arbres
  • Définitions par induction
    • Définition
    • Exemple
    • Expressions arithmétiques
    • Application aux arbres binaires
  • Preuves par induction
    • Lien avec les preuves par récurrence
    • Application aux EATPs
  • Algorithmique dans les arbres
  • Arbres $n$-naires
  
  
• Files de priorité
  • Implémentations naïves
  • Tas
    • Définition
    • Extraction du minumum
    • Insertion
    • Suppression du minimum
    • Implémentation
  • Tas binomial
    • Arbre binomial
    • Fusion
    • Tas binomial
    • Implémentation
    • Extraction du minimum
    • Fusion
  
  
• Hachage
  • Principe
  • Collisions
    • Gestion des collisions par chaînage
    • Gestion des collisions par adressage ouvert
  
  
• AVL
  • Arbres binaires de recherche
  • Complexité dans le pire de cas
  • Rotations
  • AVLs
    • Rééquilibrage
    • Insertion
    • Suppression
    • Compléments
  
  
• Modélisation
  • Définition
  • Exemple
    • Données
    • Contraintes
    • Question
  • Sensibilisation à la complexité
    • Le tour de la table
    • De la terre à la Lune
    • En bref
  • Terminologie
    • Difficulté
    • Rappels de théorie des graphes
    • Définition d'un problème
    • Problèmes d'optimisation
  • Problèmethèque
    • Arbre couvrant de poids minimal
    • Ensemble stable maximal
    • Circuit eulérien
    • Circuit hamiltonien
    • Voyageur de commerce
    • SAT
    • Couverture
    • Coloration
    • Plus court chemin
    • Sac à dos
  • Exercices
  
  
• Programmation linéaire
  • Exemple
  • Algorithme du simplexe en bref
  • Modéliser un programme linéaire
  • GLPK
    • Qu'est-ce que c'est ?
    • Où le trouver ?
    • La documentation
    • Les fonctions
  
  
• Théorie de la complexité
  • Terminologie et rappels
    • Problèmes de décision
    • Instances
    • Algorithme polynomial
  • Les classes P et NP
    • La classe P
    • La classe NP
    • Relations d'inclusion
  • Réductions polynomiales
    • Définition
    • Exemple
    • Application
  • Les problèmes NP-complets
    • Courte méditation
    • 3-SAT
    • Conséquences déprimantes
    • Un espoir vain
  
  
• Introduction à la cryptographie
  • Définitions
  • La stéganographie
  • Les chiffres symétriques sans clé
  • Les chiffres symétriques à clé
    • Le chiffre de Vigenère
    • Enigma
  • Les algorithmes asymétriques
    • Un peu d'histoire[1]
    • Le principe
    • Programmation en C
  
  
• GnuPG
  • Présentation
  • Utilisation
    • Génération d'une clé privée
    • Exportation de la clé publique
    • Importation
    • Liste des clés
    • Chiffrement
    • Déchiffrement
    • Signature
    • Bref
  
  
• GMP
  • Présentation
  • Quelques points délicats
    • Compilation
    • Initialisation
    • Les fonctions
    • Affichage
    • Exemple
    • Pour terminer
    • Vigenere
  
  
• Arithmétique
  • Divisibilité
  • Division euclidienne
  • $pgcd$
  • Nombres premiers
  • Nombres premiers entre eux
  • Décomposition en produit de facteurs premiers
    • Application à la divisibilité
    • Application au calcul du PGCD
  • Théorème de Bezout
    • Théorème de Gauss
  • Algorithme d'Euclide
    • Algorithme d'Euclide pour le PGCD
    • Algorithme d'Euclide étendu (avec tableau)
    • Algorithme d'Euclide étendu (sans tableau)
  • Exercices
    • Morceaux choisis
    • Programmation en C
    • Applications avec GMP
  
  
• Arithmétique modulaire
  • Congruences
  • Espace quotient $Z/nZ$
    • Opposé d'un élément de $Z/nZ$
    • Inverse d'un élément de $Z/nZ$
    • Eléments inversibles et fonction $\phi$ d'Euler
  • Pratique de l'inversion
    • Petit théorème de Fermat
    • Théorème d'Euler
  
  
• RSA
  • Principe
    • Chiffrement
    • Déchiffrement
  • Résistance aux attaques
  • Applications directes du cours
  • 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 $n$-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
    • Définition
    • Opérations ensemblistes
    • Cardinal
    • $n$-uplets
    • Parties
    • Définition
    • Composition
    • Classification des applications
    • Application réciproque
  • Raisonnements par récurrence
    • Principe
    • Exemple
    • Exercices
  • Analyse combinatoire
    • Factorielles
    • Arrangements
    • Combinaisons
    • Triangle de Pascal
    • Liens avec les ensembles
  • Exercices récapitulatifs
    • Echauffement
    • Formule de Poincaré
    • La moulinette à méninges
  
  
• Bibliographie