| jeudi 17 septembre 2020 à 16h15 |
Problème du tri par comparaison
Tri insertion. Spécification d'un algorithme. Terminaison (variant), complexité, correction (invariant). Tri en place. Tri fusion. Arbre d'appel. Algorithmique récursif. Programmation fonctionnelle. Code Python
==> Problèmes conduisant à une modélisation par des suites ou par des fonctions (complexité du tri fusion)
|
| jeudi 1er octobre 2020 à 16h15 |
Suite de Fibonacci
Algorithme récursif exponentiel. Algorithme en temps quadratique. Complexité linéaire d'une addition. Algorithme sur représentation matricielle.Code Python
Complexité quadratique d'une multiplication avec l'algorithme naïf. Complexité en O(n^2 log n).
|
| jeudi 15 octobre 2020 à 16h15 |
La complexité qu'on a vu : du O(m(n) log n) pour le calcul du n-ème terme où m(n) est la complexité de la multiplication de nombres à n bits. En fait, c'est en O(m(n)).
Algorithme de Karatsuba pour multiplier deux nombres.
Complexité quadratique d'une division euclidienne. Algorithme d'Euclide.
|
| jeudi 17 octobre 2020 à 14h |
Algorithme sur les nombres (suite)
Algorithme d'Euclide. Analyse de complexité. Théorème de Lamé. Algorithme d'Euclide étendue. Exponentiation rapide modulo N. RSA.
Code Python
==> leçon sur les nombres premiers, PGCD, etc.
==> leçon sur un+1 = f(un). Applications.
|
| jeudi ? octobre 2019 à 16h |
TP
Fractales?
|
| jeudi 24 octobre 2019 à 14h |
Nombres premiers et factorisation
Algorithme naïf de test de primalité. Test de primalité de Fermat.
Factorisation de nombres entiers: Algorithme de Floyd pour détecter un cycle dans une suite un+1 = f(un) ; Algorithme rho de Pollard.
Code Python
==> leçon sur les nombres premiers, PGCD, etc.
==> leçon sur un+1 = f(un). Applications.
|
| jeudi 7 octobre 2019 à 14h |
Pile et file
Code Python pour une pile
Code Python pour une file
Algorithmes sur les graphes
Représentation des graphes (matrice d'adjacence, liste d'adjacence).
Parcours en largeur. File.
Code Python
Algorithme de Dijkstra. File de priorité (implémentations naïves).
Code Python
==> leçon sur les algorithmes
|
| ?? ??/12/2019 – ??h |
TERMINAL : sujet
|