Algorithmique 2

Semestre 2 - L1 mathématiques et informatique

Cours

- Version 2017 (langage python)

(Se référer au moodle pour tous les documents : pb de compatibilité entre notebook python et site joomla)

- Version 2016 (langage algorithmique)

Diapos	Thème	Notions	Exemples
s1	Introduction	Notations et rappels	Permuter, doubler
s2	Sous-programmes	Fonctions, procédures, en-tête, appel, corps, paramètres formels et effectifs, variables locales vs. paramètres, modes de passage de paramètres
s3	Tableaux 1D	Tableaux 1D de nombres (surtout), de caractères	Lire, stocker, calculer la moyenne, minimum et maximum : valeur, indice, tri insertion
s4	Tableaux 2D et plus	Tableaux 2D, images et matrices Boucles imbriquées Tableaux 3D, notions d'enregistrements	Traitement d'image : initialisation, niveaux de gris, transformations (miroir, contraste, ...) Matrices et algorithmes : vérification (identité, symétrie), calcul (produit de matrices, ...), génération de formes particulières (transposée, ...)
s5	Complexités	Analyse de complexité en temps : modèle, pire cas, fonctions de complexité, complexité vs. mesures de temps d'exécution. Complexité en espace mémoire. Notations asymptotiques.	Sommer un tableau de n entiers, arithmétique matricielle, multiplier 2 entiers de taille n, recherche séquentielle, recherche dichotomique
s6	Exemples de traitements et de complexités	Evaluation de polynômes	Algorithmes classique, de Horner.
s7	Récursion	Fonctions récursives, preuves, piles/arbre des apples, environnements. Complexité, récurrences et efficacité. Boucles : récursion, dé-récursivation.	Factorielle, Fibonacci, exponentiations naïve et rapide, recherche dichotomique (version récursive), tours de Hanoi
s8	Rechercher	Recherche séquentielle : algo, preuve, complexité. Recherche dichotomique : algos itératif et récursif, preuve, complexité.
s9	Terminaison et correction	Terminaison : variants Correction : invariants de boucle
s10	Trier	Tris par comparaisons, algorithmes quadratique et semi-linéaire.	Tris sélection, insertion, fusion, rapide.
s61	Correction contrôle continu	Structures de contrôle, fonctions, tableaux 1D-2D, complexité (estimation basique).

Travaux dirigés

Objectifs pédagogiques. Chaque feuille comporte deux parties.

La partie 1 “Objectif 10” propose des exercices très proches du cours et des révisions du semestre 1. Avec les QCM en ligne (ENT), cette partie a pour objectif l’assimilation des connaissances de base, en particulier tout ce qui a été vu au semestre 1. Ces notions pleinement acquises permettent d’obtenir la moyenne lors des contrôles de connaissances (contrôle continu et sessions d’examens).
La partie 2 “Objectif 20” propose des exercices de difficulté croissante sur des notions plus avancées ou des formulations plus abstraites. Les étudiant-e-s informaticien-e-s, et les étudiant-e-s mathématicien-e-s qui souhaitent continuer au delà de la Licence, doivent impérativement traiter cette partie 2.

Méthode de travail.

Les exercices Objectif 20 sont traités après que ceux de l'Objectif 10 aient été résolus correctement en un temps raisonnable (10 minutes au plus par question).
Ne pas hésiter à résoudre d'autres exercices Objectifs 10 que ceux traités en TD (et listés ci-après) avant de passer à l'Objectif 20.

Feuille 1 : tableaux 1D et traitements simples, sous-programmes et tableaux, un peu de complexité.

Feuille 2 : tableaux 2D et traitements associés, images, matrices, complexité.

Feuille 3 : récursivité, recherches séquentielle et dichotomique, complexité, tris récursifs.

Feuille 4 : terminaison et correction.

Sujets et corrections des épreuves de contrôle continu et d'examen

2015 : sujet CC, correction CC, sujet session 1, correction session 1, sujet session 2, correction session 2
2016 : sujet CC, correction CC, sujet session 1, correction session 1, sujet session 2, correction session 2
2017 : sujet CC , correction CC , sujet devoir printemps, correction devoir printemps

template joomla