# ALGO1 :rocket:
## Bienvenue au cours d'algorithmique :smiley: !


## $\hookrightarrow$ :pencil: Remplissez le sondage svp :pray: --- # Objectifs du cours - Étude de l'**algorithmique** = science des algorithmes Étude **théorique** et **empirique** - *Pas* une étude de la calculabilité (cf. autre cours) - Maîtriser différents axes : + types abstraits & structures de données + des algorithmes "importants" et typiques + paradigmes de conception d'algorithmes + spécifications : correction… + garanties : terminaison, complexités (temps & mémoire)… - **Algorithmes** : en pseudo-code et implémentations en Python :snake: --- # Organisation du cours - :scroll: Page web du cours [`perso.crans.org/besson/teach/info1_algo1_2019`](https://perso.crans.org/besson/teach/info1_algo1_2019/) - 10 séances de cours + 10 séances de TD (planning sur ADE) - Votre travail : + attentif⋅ve⋅s en cours :pencil: + actif⋅ve⋅s en TD :weight_lifting_woman: + lire les implémentations proposées pour chaque cours + finir les TD à la maison :house: + un DM & un DS :pencil: + lire les références :books: - :warning: ==Présence obligatoire== aux CM et TD ! --- # Organisation des *Cours Magistraux* - :wave: *Par* : [Lilian Besson](https://GitHub.com/Naereen/slides/) $\hookrightarrow$ `Lilian.Besson @ Inria.fr` :email: - :school: *Lieu* : ENS de Rennes, salle 07 ou autre (à voir sur ADE) - :date: *Date* : les mardis + 14h - 16h généralement + ou 13h30 - 15h30 *quand il y a un séminaire du département* (17 sept., 01 & 15 oct., 05 & 12 & 26 nov.) :warning: ==Présence obligatoire aux séminaires (en amphi)== - :alarm_clock: *Durée* : 2 heures, 5-10 minutes de pause au milieu

- Support de cours *pas mis en ligne* : :warning: prenez des notes ! --- # Organisation des *Travaux Dirigés* - :wave: *Par* : Raphaël Truffet $\hookrightarrow$ `Raphael.Truffet @ IRISA.fr` :email: - :school: *Lieu* : Beaulieu (salles à voir sur ADE) - :date: *Date* : les jeudis, 16h15 - 18h15 - :alarm_clock: *Durée* : 2 heures, 5-10 minutes de pause au milieu


- Feuille de TD distribuée pendant le TD - A terminer pour le TD suivant --- # :mortar_board: Évaluations 1. :warning: **Présence obligatoire à tous les cours *et* les TD** :warning:
2. Un DM écrit $\Longrightarrow$ ==**1/3 de la note**== + :warning: seul (pas de travail de groupe) + sujet donné mi octobre, à rendre début novembre (après Toussaint) + des preuves à rédiger sur papier libre (ou en LaTeX/…) + un peu de code à écrire (Python / OCaml)
3. Un DS écrit $\Longrightarrow$ ==**2/3 de la note**== + pendant les examens mi décembre + des preuves à rédiger sur papier libre (ou en LaTeX) + un peu de code à écrire (pseudo-code, ou Python / OCaml) --- # :books: Des références bibliographiques ? - **Introduction à l'algorithmique**, Cormen et al ; Dunod. - **Éléments d'algorithmique**, Beauquier, Berstel, Chrétienne ; Masson. (en libre accès sur Internet !) - **Types de données et algorithmes**, Froidevaux et al. - **Programmation efficace : Les 128 algorithmes qu'il faut avoir compris et codés dans sa vie**, Vie & Dürr ; Ellispes ; [`TryAlgo.org`](http://tryalgo.org) - :gb:/:us: Cours diffusés librement sur Internet, en anglais : + [`Algorithms.wtf`](http://algorithms.wtf/) + [`OpenDataStructures.org`](http://opendatastructures.org/ods-python.pdf) + et plein d'autres… --- # Définitions… :pencil: à définir ensemble ## - Problème de calcul… ## - Algorithmes… ## - Types de données abstrait *vs* implémentation… ## - Mesures de performance… - Temps de calcul - Mémoire - Mais aussi : batterie, bande passante, nombre lecture mémoire etc… --- # :computer: Illustrations des exemples en cours ? ## $\rightarrow$ en pseudo code (au tableau) ## $\rightarrow$ en Python :snake: (sur l'écran :cinema:)
# :pencil: Illustrations des exemples en TD/exam ? ## $\rightarrow$ en pseudo code ## $\rightarrow$ en Python :snake: *ou* en OCaml :camel: --- # Rappels sur les types de bases Domaine $D$, représentation, taille de stockage, etc - Booléen : $D = \{\text{true}, \text{false}\}$, 1 bit - Entiers : $D = \mathbb{Z}$ ou $D = \mathbb{N}$, 32 ou 64 bits :warning: généralement non exacts - Flottants : $D = \mathbb{R}$, 32 ou 64 bits :warning: généralement non exacts - Chaînes de caractères, selon l'alphabet $\Sigma$ + sur l'alphabet $\Sigma=\text{ASCII}$, 7 ou 8 bits par caractères + $\Sigma=\text{Unicode}$, 2 à 4 octets par caractères (octet = byte = 8 bit) + $D = \Sigma^*$ --- # :warning: Représentations non exactes… des entiers - En C, C++, Javascript, OCaml : les entiers bouclent ! - Les opérations de bases ne sont pas associatives ! Et pas exactes ! ```ocaml # 4611686018427387904 = (-4611686018427387904);; - : bool = true # (4611686018427387900 + 10) - 10 = 461168601842738790;; - : bool = false # 4611686018427387900 + (10 - 10) = 461168601842738790;; - : bool = false ``` - :warning: on va ignorer tout cela dans les algorithmes étudiés en cours. - On suppose pouvoir représenter les entiers $\mathbb{Z}$ en $\mathcal{O}(1)$ temps et effectuer des opérations dessus en temps constant $\mathcal{O}(1)$ --- # :warning: Représentations non exactes… des flottants - En C, C++, Javascript, OCaml, Python : les flottants utilisent la norme IEEE 754, qui donne plein d'erreurs possibles :boom: - Les opérations de bases ne sont pas associatives ! Et pas exactes ! - Les tests d'égalités sur les flottants ne sont pas "fiables" ! ```python >>> (0.1 + 0.1 + 0.1) == 0.3 False >>> (0.1 + 0.1 + 0.1) - 0.1 == 0.2 False >>> 0.1 + 0.1 + (0.1 - 0.1) == 0.2 True ``` - :warning: on va ignorer tout cela dans les algorithmes étudiés en cours. - On suppose pouvoir représenter les nombre décimaux $\mathbb{D}$ en $\mathcal{O}(1)$ temps et effectuer des opérations dessus en temps constant $\mathcal{O}(1)$ --- # Rappels : structures "linéaires" de données - Espace mémoire $\propto n$ - Taille *fixée*, `n = longueur(T)` ou $n = |T|$, calcul en $\mathcal{O}(1)$ - Contient des données généralement d'un même type + obligatoire en OCaml (typage statique) types `'a array`, `'a list`, etc (`'a arbre`) + aucune limitation en Python (typage dynamique) - En pratique : + **tableaux statiques**, **tableaux dynamiques** + **listes simplement** ou **listes doublement chaînées** + **file**, **pile**, **file de priorité** et d'autres --- # Tableau (statique) - :boom: Construction avec $n$ valeurs en $\mathcal{O}(n)$ (taille connue à l'avance) - :rocket: Accès au `i`ème élément en $\mathcal{O}(1)$ ### :pencil: En pseudo-code Initialisation : $T_{1:n}$, accès $T_i$ ou $T[i]$, écriture $T[i] \leftarrow x$ ### :camel: En OCaml : accès `t.(i)`, écriture t.(i) <- x ```ocaml # let t = [| 0; 1; 2; 3 |];; val t : int array = [|0; 1; 2; 3|] ``` ### :snake: En Python : accès `t[i]`, écriture `t[i] = x` ```python >>> tableau = [ 0, 1, 2, 3 ] ``` --- # Liste simplement chaînée - Taille *dynamique* - :rocket: Construction initiale en $\mathcal{O}(1)$ - :rocket: Ajout de $1$ élément en tête de liste en $\mathcal{O}(1)$ $\Longrightarrow$ :boom: Ajout de $n$ éléments en $\mathcal{O}(n)$ ! - :rocket: Accès au `i`ème élément en $\mathcal{O}(i)$ ### :camel: En OCaml : tête `hd l`, queue `tl l` ```ocaml # let l = [ "tete"; "suite"; "de"; "la"; "liste" ];; val l : string list = ["tete"; "suite"; "de"; "la"; "liste"] ``` ### :snake: :warning: En Python n'existe pas ! Le type `list` est un mélange entre les tableaux et les listes… (tableau dynamique) :warning: --- # Liste simplement chaînée ## :snake: En Python $\hookrightarrow$ implémentation "manuelle" avec deux petites classes - Cf. notebook Python sur [`perso.crans.org/besson/info1_algo1_2019/notebooks/`](https://perso.crans.org/besson/info1_algo1_2019/notebooks/) --- # Liste *doublement* chaînée ## :camel: En OCaml - Avec un type paramétrique - Vous pouvez essayer à la maison ## :snake: En Python $\hookrightarrow$ implémentation "manuelle" avec deux petites classes - Cf. notebook Python sur [`perso.crans.org/besson/info1_algo1_2019/notebooks/`](https://perso.crans.org/besson/info1_algo1_2019/notebooks/) --- # Étude du tri par file de priorité (tri par tas) ## 1. File de priorité ? ## 2. Implémentation par tas binaire ## 3. Tri par tas --- # Dans ce cours : des algorithmes… ### … expliqués et prouvés au tableau ### … illustrés sur des exemples $\hookrightarrow$ vous pouvez revoir les exemples à la maison sur [`www.cs.usfca.edu/~galles/visualization/Algorithms.html`](https://www.cs.usfca.edu/~galles/visualization/Algorithms.html) ### … codés en Python 3 :snake: - Montrés dans des *notebooks Jupyter* (cf. [`Jupyter.org`](https//www.jupyter.org)) - Disponibles sur [la page du cours](https://perso.crans.org/besson/teach/info1_algo1_2019/notebooks) ([`/notebooks`](https://perso.crans.org/besson/teach/info1_algo1_2019/notebooks)) - et sur [`GitHub.com/Naereen/ALGO1-Info1-2019/`](https://github.com/Naereen/ALGO1-Info1-2019/) - Des fois de façon interactive avec *Python Tutor* (cf. [`PythonTutor.com`](http://pythontutor.com/live.html#mode=edit)) - Étude empirique de complexités temps/mémoire etc. --- # Fin du cours 1/10



Merci de votre attention .