Objectifs
Introduire, au travers d'exemple de problèmes simples, diverses
approches algorithmiques. Certaines seront programmées et testées sur
machines. Les approches abordées sont:
- Formule close;
- Exhaustive (Brute-Force);
- Récursive;
- Programmation dynamique;
- Heuristique;
- Approximation;
- Gloutonne (Greedy);
- Diviser pour régner (Divide-and-Conquer);
et si on a le temps:
- Probabiliste;
- Programmation linéaire;
- Relaxation avec branchement et élagage (Branch-and-Bound);
- Solveur SAT.
Nous programmerons en
C avec un tout petit peu d'OpenGL/SDL
pour plus de graphismes. Les concepts techniques et les objets que
l'on croisera seront: les algorithmes, la complexité, les graphes, les
distances, les points du plan, ...
Organisation
- Volume (créneaux d'1h20): 12 CM + 6 TD + 18 TP
- Organisation (en semaine): 4x CM + 6x (CM+TD+TP) + 2x
(TD+TP). Il y aura un test la semaine du 3 avril (cette année, il
aura lieu le jeudi 6 avril 2023 se présentera sous la forme d'un
devoir maison à réaliser en temps limité). La dernière semaine de TP
est normalement un TP noté de 2h40 (cette année, il aura lieu le
jeudi 13 avril 2023 à 14h).
- Modalités:
1 examen (50%) + 1 contrôle continu (50% = test écrit (1/3) + TP
noté (2/3))
Enseignants et contacts
Groupes et séries
Notes de cours
![ouvrir le pdf [pdf]](../img/pdf_icon1.png)
Ne les imprimez pas ! car elles sont mises
à jour régulièrement.
Vidéos 2020 du Chapitre 4: Navigation
En raison de l'épidémie de Covid-19 seuls les 4 premiers chapitres
sont au programme.
Références
Feuilles de TD/TP
Il y a une fiche de TD chaque semaine de TD, publiée au fur et à
mesure. Les semaines de TP sans TD n'ont pas de fiche pdf, les
instructions étant dans le .c de la séance.
- TD1/TP1.1 - Voyageur de commerce (brute-force): sujet, tsp.tgz, tsp_brute_force.c, tsp_brute_force.h
- TP1.2 - Voyageur de commerce (prog. dynamique): tsp_prog_dyn.c, tsp_prog_dyn.h
- TD2/TP2.1 - Voyageur de commerce (heuristiques): sujet, tsp_heuristic.c, tsp_heuristic.h
- TP2.2 - Voyageur de commerce (approximation): tsp_mst.c, tsp_mst.h
- Fichiers individuels (ceux de tsp.tgz): Makefile, tools.h, tools.c, tsp_main.c
- TD3/TP3.1 - Tas binaire: sujet, heap.tgz, test_heap.c (inclus dans heap.tgz)
- A star is born... tp-a_star.mp4 [23'36'' - 36 Mo]
- TP3.2 - Algorithme A*: a_star.c,
mygrid.txt
- TD4/TP4.1 - Complément sur A*: sujet
- TP4.2 - Complément sur A* (suite)
- TD5/TP5.1 - Paire de points les plus proches: sujet, pppp.tgz
(comprenant pppp.h, pppp.c, htable.h, htable.c)
- TP5.2 - Paire de points les plus proches (suite)
Pour travailler sur votre ordinateur personnel, ce qui est possible
(surtout en mode de travail à distance) sans être recommandé, il vous
faudra installer les librairies OpenGL, GLU, GLUT, SDL2, et peut-être
modifier le
Makefile qui a été testé sous les systèmes Linux,
Mac OsX, WSL et bien sûr sur les machines du Crémi.
Installation SDL2
Pour l'installation de (Open)GL et SDL2 sous votre système, merci à
ceux qui ont la solution sur un système particulier de communiquer.
Pour Linux, généralement la solution est
$ sudo apt-get install libsdl2-dev libsdl2-image-dev libsdl2-ttf-dev freeglut3-dev
Pour tester si SDL2 marche bien sous votre système, vous pouvez
essayer
$ glxgears
qui doit afficher une fenêtre avec une petite animation (des roues de
couleurs qui tournent). Il y a aussi
$ sdl2-config --libs
$ sdl2-config --cflags
qui devraient vous donnez les chemins pour les includes et librairies.
Pour les utilisateurs de Windows 10 (SDL2 via WSL), je vous suggère
ce lien. Il est bien sûr toujours possible de compiler (make),
d'éditer vos fichiers (
VS
Code) et de lancer l'exécution depuis le crémi via une connexion
ssh. Cela marche assez bien même si c'est moins confortable qu'en
local.
Tests, DM et examens