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 DS la semaine du 19/02 en remplacement d'une
séance de TD/TP classique. L'épreuve sera regroupé lundi 19/02 à
17h, dans un amphi du A22. Pour ce DS, vous n'aurez pas le droit aux
documents, sauf à une feuille (recto/verso) A4 manuscrite. La
dernière semaine de TP, donnera lieu à des TPs notés. Pour 2024, la
durée sera 2h10 et ils auront lieu le mercredi 10/04 et jeudi
11/04.
- 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
![[pdf]](../img/pdf_icon1.png "ouvrir le pdf")
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.c,
pppp.h
- 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, Examens, TP noté