Bloc 5 : Algorithmique avancée
La formation et l'évaluation auront lieu entièrement en distanciel.
La connaissance des limites théoriques à ce que peut calculer une machine automatique -théorie des fonctions calculables et machines de Turing- donne à l'enseignant le surplomb nécessaire pour comprendre que tous les problèmes ne sont pas décidables. Une étude d'algorithmes avancés dont un ou des algorithmes d'apprentissage permet à l'enseignant de mettre en perspective les enjeux actuels de l'intelligence artificielle.
Pré-requis
Les connaissances et savoir-faire des blocs 1, 2, 3 et 4 sont pré-requis pour suivre ce bloc.
Programme
Le programme officiel du bloc 5 se trouve à l'adresse suivante.
Planning : (les supports se trouvent plus bas)
- Lundi 21 8h45 : démarrage (J. Velcin) visio.
- Lundi 21 Arbres et Programmation dynamique (N. Pronost) : toutes les visios sur ce lien:
- 9h-11h : cours à distance (arbres) [vidéo+visio]
- 11h-12h : séance de questions-réponses [visio]
- 14h-17h : pratique à distance (prog. dynamique) [visio]
- Mardi 22 juin Graphes et algorithmes randomisés (L. Gonnord): toutes les visios sur ce lien.
- 9h Accueil rapide / café sur la visio
- 9h10-10h Vidéo graphes + questions sur le rocket-chat
- 10h10-12h Séance d'exercices en live sur la visio
- 14h-17h : TP en live sur la visio: graphes, algorithmes randomisés
- Jeudi 24 juin 9h-12h : cours et pratique à distance (complexité), visio.
- Jeudi 24 juin aprem sur (849228814) cette visio
- Jeudi 24 juin 14h-15h : cours à distance (introduction à l'intelligence artificielle et à l'apprentissage automatique)
- Jeudi 24 juin 15h-16h : cours à distance (recherche textuelle)
- Jeudi 24 juin 16h-17h : pratique à distance + séance de questions-réponses (recherche textuelle)
- Vendredi 25 juin 9h-12h : cours et pratique à distance (calculabilité) (N. Portier) - visio (lien, ID réunion 886 8370 6266, code d'accès 157932)
- Vendredi 25 juin 14h-15h : assistance (calculabilité)
- Vendredi 25 juin 15h-16h : assistance (autres thèmes)
- Jeudi 1er juillet : examen à distance (2h)
Modalités pédagogiques :
Nous utiliserons les outils suivants :
- Rocket-chat, pour les discussions asynchrones
- BigBlueButton, WebEx, Zoom pour la classe virtuelle synchrone
- Pour la partie programmation : un environnement Python 3 et un IDE (au choix)
Modalités de contrôle des connaissances
L'évaluation se base sur trois notes :
- Une note de devoir maison qui correspondra à des exercices pratiques portant sur une partie du programme (coefficient 3).
Deux devoirs seront demandés (un portant sur la programmation dynamique, un second sur la calculabilité) durant la semaine pour un rendu le jeudi 1er juillet.
- Devoir sur la programmation dynamique
- Devoir sur la calculabilité
- un examen écrit le jeudi 1er juillet réalisé en temps limité - 2h - (à distance) qui portera sur l'ensemble des notions vues dans le bloc, à l'exception des thèmes demandés pour les devoirs maison (coefficient 4).
- Une note correspondant au FOAD réalisé en binôme (coefficient 3), à rendre au plus tard le 6 juillet: instructions ici
Pour rappel, la validation du DIU se fait par UE sans compensation, le DIU étant validé si et seulement si l'ensemble des UE est validé.
Trois sujets pour l'examen :
Formation Ouverte A Distance (FOAD)
Les modalités de la FOAD sont les mêmes que celles du bloc 4.
L'objectif de la FOAD est, en groupe de deux personnes, de pratiquer et approfondir les contenus du bloc en produisant du matériel pédagogique utile en classe pour la spécialité NSI de Terminale, que ce soit des activités en classe ou de type projet. Il s'agit de prévoir un contenu d'environ 3h de face à face avec les élèves.
Le rendu devra être accompagné d'une courte vidéo de présentation. La date limite pour le rendu est fixée au 6 juillet.
Ressources
- Arbres :
- CM : (transparents, pdf) et (vidéo YouTube) - à consulter si possible avant le lundi 21 juin 9h et au pire entre 9h et 10h
- TD/TP : (pdf) et script Python utile - séance de questions/réponses encadrée le lundi 21 juin entre 10h et 12h en visio (lien visio)
- TP : Fichier complet Python Arbre.py
- Programmation dynamique :
- TD : (énoncé, pdf) - séance interactive le lundi 21 juin de 14h à 17h en visio (lien visio), merci de relire la partie 'Algorithme glouton' de l'UE 2 avant la séance
- TD : (corrigé, pdf) et (script, py)
- Graphes :
- CM : généralités (transparents, pdf), Vidéo (mp4), Vidéo2 (mp4) Vidéo (mp4) à consulter si possible avant la séance de mardi ou au pire entre 9h et 10h.
- Quelques exercices (pdf) si vous voulez regarder. On fera en live/visio quelques rédactions d'exercices le mardi 22 juin de 10 à 12h sur la visio
- Une librairie de Graphes que l'on décortiquera en début de séance de l'après-midi. Il est demandé d'installer Graphviz en amont, la commande
python3 TestLib.py
doit pouvoir être lancée sans erreur - Séance de l'après-midi~: début : implémentation d'algos élémentaires sur les graphes non orientés. code solution
- Travail personnel : algorithmes de calcul de distances CM distances (transparents, pdf).
- Partie optionnelle: CM coloriages (transparents, pdf) , Vidéo (mp4)
- Des Annales variées (pdf) et leurs éléments de correction (non garantis sans erreur)
- Algorithmes randomisés
- Pas de CM, uniquement quelques exemples.
- Un TP de marches aléatoires: énoncé, et code fourni. Objectif : au moins la partie 1D mardi 22 juin en deuxième partie d'après-midi.code solution
- Recherche textuelle
- Transparents de cours : recherche textuelle
- Export du notebook Python : export html
- Le cours est accessible en vidéo sur YouTube (liens fournis par email).
- Introduction à l'intelligence artificielle et à l'apprentissage automatique :
- Transparents de cours :
intelligence artificielle
apprentissage automatique - Le cours est accessible en vidéo sur YouTube (liens fournis par email).
- Transparents de cours :
intelligence artificielle
- Complexité :
- Transparents de cours : (transparents, pdf)
- Exercices : (pdf)
- Calculabilité :
Videos et transcript du cours : lien fourni par email
Références : C’est très facile de trouver des cours de calculabilité en ligne en français. Je recommande le premier chapitre du livre de complexité de Sylvain Perifel, disponible gratuitement en pdf sur sa page : https://www.irif.fr/~sperifel/complexite.pdf
"Lectures d'été" sur le sujet :
- Logicomix : (en français ou en anglais). "Logicomix (2008) est un roman graphique sur la quête des fondements des mathématiques. Il est scénarisé par l'écrivain Apóstolos K. Doxiàdis (auteur notamment d’Oncle Petros et la conjecture de Goldbach) et le professeur et chercheur en informatique théorique Christos H. Papadimitriou (de l'université de Californie, Berkeley)." (wikipedia)
- Gödel Escher Bach les brins d'une guirlande éternelle : Un classique, un gros pavé. Et en plus il vaut mieux la version papier qu'électronique car il y a beaucoup de dessins. Si vous êtes mélomane, ça vous intéressera encore plus. wikipedia : Au premier niveau de lecture, cet ouvrage démontre les interactions entre les mathématiques, l'art et la musique. Et ce en s'appuyant sur les réalisations du logicien Kurt Gödel, de l'artiste Maurits Cornelis Escher et du compositeur Jean-Sébastien Bach qui semblent s'entrelacer. L'ouvrage exploite les concepts d'analogie, de réductionnisme/holisme, mais aussi les paradoxes (et notamment les paradoxes de Zénon), la récursivité, l'infini, et les systèmes formels. Ses nombreux exemples de phrases auto-référentes sont liés aux ambigrammes, ces mots miroir qu'il a inventés, et discuté dans un article "Création et créativité".
- La Machine de Turing, Jean-Yves Girard, Alan Turing, points seuil (qui le classe dans les sciences humaines !!) Tout petit livre, le texte de Turing est étonnamment lisible.qqch sur la vie d'Alan Turing Si vous ne connaissez pas la vie de Turing, allez lire ça quelque part, c'est très intéressant...et triste. Et si vous passez près de Londres, prévoyez une journée à Bletchley Park, l'endroit secret où Turing a déchiffré Enigma pendant la guerre.
Contacts
Merci de nous contacter en mettant[diu-lyon] bloc 5
en objet du mail.
- Nicolas Pronost: responsable DIU (at univ-lyon1 point fr)
- Julien Velcin: responsable du bloc 5 (at univ-lyon2 point fr)