Algorithmique et programmation orientée objet (APOO)

De Ensiwiki.

Cette page est maintenue par les enseignants et utilisée par les élèves de la matière concernée. Vos contributions sont les bienvenues, mais merci d'en discuter avant de faire des modifications non-triviales de la page, pour être sûr de ne pas perturber le déroulement du cours.

Deuxième Année Informatique

Bienvenue sur la page d'Algo 3.

Présentation

Objectifs

Le cours d'Algorithmique et programmation orientée objets (APOO) fait suite aux cours d'Algorithmique et programmation en Ada (Algo 1) et Algorithmique et structures de données (Algo 2) de première année. Les pré-requis, en terme de compétences, sont les suivants :

programmation impérative (itération, récursion, programmation procédurale, généricité ; mise en pratique) ;
structures de données élémentaires et classiques (tableaux, listes, arbres, files de priorité, dictionnaires, tables de hachage).

Fonctionnement

1 séance de 3 heures de CTD par semaine. 2 TP en temps libre, à faire en binôme, sont également au programme, comme en algo 2.

Evaluation

L'évaluation prendra la forme d'un examen écrit de 3h en fin de semestre, sur 15 points, et des 2 TP dont la note moyenne sera ramenée sur 5 points. Contrairement à l'examen écrit, les deux TP ne se rattrapent pas.

Travail personnel recommandé

18 heures par étudiant sur le cours, ce qui correspond par exemple à 1 heure pour chaque séance de 3h + 6 heures de révision. Vous pouvez par exemple faire une fiche de synthèse après chaque séance : ces fiches vous seront utiles avant l'examen pour réviser le cours.

15 heures par étudiant pour les TP temps libre, soit 7h30 par étudiant pour chacun des TP.

Au niveau méthodologique, les recommandations données en Algo 1 en première année restent valables.

Planning

Créneaux horaires

N'oubliez pas de vérifier régulièrement votre emploi du temps sur ADE.

Groupe	Horaires des séances	Enseignant
IF1 (MIF1)	Mardi 9h45-12h45	Franck Hétroy
IF2 (MIF2 + SIF)	Mardi 9h45-12h45	Matthieu Chabanas
ISI1	Mercredi 8h15-11h15	Jean-Louis Roch
ISI2	Jeudi 8h15-11h15	Augustin Lux
MMIS1 (AAD + BioInfo + MCS)	Lundi 9h45-12h45	Sébastien Viardot
MMIS2 (IRVM)	Lundi 9h45-12h45	Michel Desvignes
SLE	Vendredi 14h00-17h00	Karine Altisen
TEL	Lundi 14h00-17h00	Gwen Salaün

Contenu

Bases de l’orienté objets : concept d’objet, écriture de classes et utilisation d’objets (séances 1 à 3)
Collections et interface (séances 4 et 5)
Programmation dynamique (séances 6 et 7)
Polymorphisme, héritage (séances 8 à 10)
Résolution de problèmes d'optimisation discrète (séances 11 et 12)

Le cours s’appuie sur le langage Java. Les deux travaux pratiques (en temps libre et en binômes) demandent la programmation d’algorithmes étudiés en Java.

Documents

Supports de formation

Résumé de la syntaxe java
Cours 1 : Programmation objet, Exception et Java
Cours 2 : Conteneurs, Interface, Nommage et Package
Cours 3 : Programmation dynamique
Cours 4 : Héritage (voir cours de Ph. Genoud ici et là)
Cours 5 : De java à C++ Introduction quelques slides sur C++

Exercices

TD 1
TD 2
TD 3 voici quelques exercices supplémentaires pour entrainement exercices en complément du TD3
TD 4 et 5
- Point de départ pour Tabex
TD7 et 8
- Exercices de programmation dynamique
TD9 et 10
- Héritage
TD 11 et 12

Annales d'examens

APOO étant un cours nouveau, il n'y a pas d'annales parfaitement ciblés. Certains énoncés de TD sont issus de sujets d'examen. En voici 3 autres.

Voici 2 sujets utiles pour l'aspect "algorithmique", provenant des cours "Algorithmique" en 2a Télécom.

Voici 1 sujet pour l'aspect orienté objets, provenant du cours d'algo2 en 1A Ensimag.

Mai 2006

Elements de correction

Ces codes java correspondent à ce qui a été traité en TD. Il est conseillé de consulter les codes associés au groupe de TD auquel vous appartenez. Les éléments de solutions proposés dans ces codes dépendent du discours donné en TD, et ne sont en aucun cas une correction "absolue".

MMIS - AAD/Bio/MCS

TD1
- Complexe.java
- Mandelbrot.java
TD2
TD3
- FilePriorite.java
TD4
- Graphe.java
TD11
- Article.cpp
- Article.h
- SacADos.cpp version sans la résolution
- SacADos.h

MMIS - IRVM

Telecom

MIF1

TD6
- Arbre binaire de recherche

TD11
- Article.h (note : tout le code a été écrit dans le .h, ce qui est une facilité qu'on emploit parfois mais qui n'est pas recommandée)
- SacADos.h
- main.cpp pour vous aider à tester
- Makefile pour vous aider à compiler

SIF+MIF2

TD3 (Tas)
TD4 (Itérateurs sur Tabex et ABR)

ISI1

ISI2

TD9-10
- Exo2: circuit

SLE

TP 1

Comment commenter votre code, pour générer la documentation correspondante.

Rotation dans un espace 3D d'après wikipedia

Sujet du TP
Annexe : TestFacette.java

Correctifs à l'énoncé du TP et éléments complémentaires

Renommer la classe Vecteur3D en Point3D. Cette classe représente un point en 3 dimensions, et non un vecteur. Par ailleurs, on précise que les rotations se font par rapport à un axe qui passe par l'origine du repère.

La représentation graphique de la facette doit-elle être en 3D ou en 2D?
- L'écran est en 2 dimensions donc la représentation est en 2D. Pour obtenir cette représentation graphique, l'affichage se fait avec la projection des points et facettes sur le plan oXY (en d'autres termes les points sont dessinés dans l'espace 2D sans tenir compte de la composante en Z).

La méthode ajouterSphere permet d'ajouter une sphère à l'objet sur lequel on applique la méthode (paramètres de cette méthode à définir).
- Une sphère sera constituée de facettes.
- Il faudra faire des facettes de 3 points, ces points seront distants du centre C de la sphère d'un rayon R. Pour obtenir toutes les facettes de la sphère, il faut construire tous les points constituant les facettes de la sphère sur un nombre fini d'angles (par exemple autour de l'axe Z, et autour de l'axe Y).
- Autre possibilité, partir d'une approximation grossière d'une sphère (par exemple trois points sur l'équateur + un point pour chaque pole), et diviser récursivement, autant de fois qu'on le souhaite, chaque facette. Une facette peut être divisée en trois en introduisant un nouveau point en son milieu, ou en quatre en introduisant un nouveau point au milieu de chaque arête. Ensuite, déplacer les points nouvellement créés pour qu'ils soient effectivement sur la sphère, i.e. à distance constante du centre de celle-ci.

La méthode ajouterSurface permet d'ajouter toutes les facettes d'une surface passée en argument, à la surface sur laquelle on applique cette méthode.
- Remarque : Si d'autres méthodes ne sont pas ajoutées pour construire d'autres type de surface qu'une sphère, alors toutes les surfaces créées seront forcément des ensembles de sphères. Il est conseillé de définir d'autres méthodes telles que : ajouterCylindre, ajouterTore, ...

TP2

Sujet Attention ! Le sujet a été mis à jour le 4/11 à 17h 15 !

Annexe

Code fourni : package branchandbound

Complément sur la méthode.

Pour la partie cours, l'annexe contient ce que vous devez comprendre et utiliser pour réaliser votre tp. C'est ce document que vous devez étudier dans les premiers temps avant de regarder le code java. Le deuxième document contient un complément sur l'étude du 2e problème: on ne vous demande pas d'implémenter les améliorations qu'il propose.

Galerie de programmes

A compléter : n'hésitez pas à participer !

Bibliographie indicative

B. Eckel : "Thinking in Java", Prentice-Hall, 4th edition, 2006.
T. Cormen, C.E. Leiserson, R. Rivest, C. Stein : "Introduction to algorithms", MIT Press, 2nd edition, 2001.

Liens divers