Java Semestre 2 Starter 2004-2005
TP n°1 - TD n°1 - TP
n°2 - TD n°2 - TD n°3 - TP
n°3 - TD n°4 - TP n°4
TD n°5 et n°6 - TP n°5 et n°6 - TD n°7 - TP n°7 - TD n°8 - TD n°9
Sujet de projet
TP n°8 - TD n°10 - TD n°11 -
TP n°9 et n°10 - TD n°12 - TP
n°11
TD n°13 et n°14 - TP n°12 - TD n°15 et n°16 - TD n°17
Fichier archive complet du site : Java-Starter.zip
Planning du semestre
| n° | Semaine | Cours | TD | TP |
| 1 | 31/01/05 | - | 1 | 1 |
| 2 | 07/02/05 | 1 | 2 | 1 |
| 3 | 14/02/05 | - | ||
| 4 | 21/02/05 | 1 | 1 | 1 |
| 5 | 28/02/05 | 1 | 2 | 1 |
| 6 | 07/03/05 | 1 | 1 | 2 |
| 7 | 14/03/05 | 1 | 2 | 1 |
| 8 | 21/03/05 | 1 | 1 | 1 |
| 9 | 28/03/05 | 1 | 1 | - |
| 10 | 04/04/05 | 1 | 1 | 2 |
| 11 | 11/04/05 | - | ||
| 12 | 18/04/05 | - | ||
| 13 | 25/04/05 | 1 | 2 | 1 |
| 14 | 02/05/05 | 1 | 1 | - |
| 16 | 09/05/05 | - | 1 | 2 |
| 17 | 16/05/05 | - | 1 | 1 |
| 18 | 23/05/05 | - | - | 1 |
| 19 | 30/05/05 | Examens | ||
API Java 1.3.1 de Sun - API Java 1.4.2 de Sun - API Java 1.5 de Sun
Squelette d'une application Java avec entrées/sorties au clavier et à l'écran
TP n°1 : Rappels sur les structures répétitives (Semaine 1)
Premier exercice : Exercice 1 du sujet de
TP (pdf) 
La méthode double Math.random() retourne une valeur numérique flottante tirée au
hasard dans l'intervalle [0.0, 1.0[. En multipliant cette valeur par 101 et en castant en
un entier, on obtient une valeur entière comprise dans l'intervalle [0,100].
Une structure "tant que" permet l'implantation de l'algorithme (tant que la
valeur lue est différente de la valeur recherchée).
On pourra inclure un compteur pour donner le nombre de tentatives en fin de jeu.
Deuxième exercice : Exercice 2 du sujet de
TP (pdf)
L'"idée" de l'algorithme consiste à accumuler les valeurs données
successivement dans une variable "total" et à compter le nombre "cpt"
de valeurs données pour ensuite pouvoir donner la moyenne (total/cpt).
Une structure "tant que" permet l'implantation de l'algorithme (tant que la
valeur lue est différente de la valeur -1). On prendra garde à bien gérer la
terminaison de l'algorithme de manière à éviter d'inclure -1 dans les notes dont on
calcule la moyenne.
Troisième exercice : Exercice 3 du sujet
de TP (pdf)
La classe String contient un certain nombre de méthodes de manipulation de chaîne de caractères. Les méthodes pouvant être utilisées dans cet exercice sont : char charAt(int index) et String substring(int deb, int fin).
TD n°1 : Correction de l'examen de session 1 (Semaine 1)
Premier exercice : Exercice 1 du sujet
d'examen de première session (pdf) (Attention, lire k:=-4 et non k:=4)
On pourra "tracer" l'algorithme en dressant trois colonnes pour suivre
l'évolution du contenu des variables k,i et j à mesure que les instructions de
l'algorithme sont exécutées.
ATTENTION, les deux boucles sont imbriquées.
Deuxième exercice : Exercice 2 du sujet
d'examen de première session (pdf)
Après lecture de la position initiale du robot, le premier traitement réalisé par
l'algorithme consistera à vérifier que le parcours du robot sur le damier ne peut pas le
conduire à sortir du damier. Si c'est le cas, le parcours ne sera pas lancé. De plus, il
faut vérifier que la position initiale du robot n'est pas en dehors du damier.
Il existe plusieurs techniques permettant de réaliser le parcours. La plus élémentaire
consiste (1) à définir deux variables x et y permettant de stocker la position
"instantanée" du robot et (2) à implanter 4 boucles successives
d'incrémentation de x et de y pour obtenir et afficher chacune des positions
instantanées.
Pour l'implantation, on utilisera naturellement la structure itérative "pour"
car on sait combien de fois chacune de ces boucles a à être exécutée avant même
qu'elle ne soit amorcée.
TP n°2 : Rappels sur les méthodes - Implantation des exercices du TD n°1 (Semaine 2)
Premier exercice : Exercice 2 du sujet
d'examen de première session (pdf)
Implanter l'exercice 2 du TD n°1 (parcours d'un robot sur un damier).
Deuxième exercice : Exercice 3 du sujet
(pdf)
Pour déterminer la valeur maximale de 3 valeur, on pourra dans un premier temps vérifier s'il s'agit de la première valeur, puis si ce n'est pas elle, faire le choix entre la deuxième et la troisième.
Exercices supplémentaires
Exercice 1 du sujet (pdf)
Pas d'indication particulière.
Exercice 2 du sujet (pdf)
Pas d'indication particulière.
Exercice 4 du sujet (pdf)
L'algorithme est conçu sur une boucle "tant que" qui permet de faire décroitre la valeur cible v par décrément de 1. Cette boucle s'exécute tant que la valeur v n'est pas diviseur des deux nombres (on a trouvé la plus grande valeur diviseur des deux nombre) et v n'est pas égal à 1 (diviseur ultime).
Exercice 1 du sujet d'examen de première session (pdf)
(Attention, lire k:=-4 et non k:=4)
Implanter l'exercice 1 du TD n°1 (traçage manuel d'un algorithme).
Sujet (html)
Pas d'indication particulière.
TD n°2 : Sous-programmes, méthodes (Semaine 2)
Premier exercice : Exercice 4 du sujet
(pdf) : Calcul du pgcd de deux nombres
L'algorithme est conçu sur une boucle "tant que" qui permet de faire décroitre la valeur cible v par décrément de 1. Cette boucle s'exécute tant que la valeur v n'est pas diviseur des deux nombres (on a trouvé la plus grande valeur diviseur des deux nombre) et v n'est pas égal à 1 (diviseur ultime).
Deuxième exercice : Exercice 3 du sujet
d'examen de première session (pdf) : Remplissage
TD n°3 : Manipulation de tableaux de variables (Semaine 2)
On prendra bien garde au fait que, tant en langage algorithmique, qu'en Java, un tableau de n cellules est manipulé sur des indices entiers dans l'intervalle [0,n-1].
Premier exercice : Exercice 2 du sujet
(pdf)
Pas d'indication particulière.
Deuxième exercice : Exercice 3 du sujet
(pdf)
Une boucle "tant que" permettra de parcourir les deux tableaux jusqu'à établir qu'ils ont été entièrement parcourus ou bien que les deux valeurs placées aux mêmes indices sont différentes. Dans le premier cas, le résultat est vrai. Dans le second cas, le résultat est faux.
Troisième exercice : Exercice 4 du sujet
(pdf)
Une boucle "pour" est construite de manière à accumuler dans une variable entière tous les produits 2 à 2 entre les entiers de même indice des deux tableaux. Le résultat est la valeur finale de cette variable.
Quatrième exercice : Exercice 5 du sujet
(pdf)
Quatre variables entières sont utilisées pour ce traitement:
- deux variables pour stocker les valeurs maximales et minimales (initialisées toutes
deux à la valeur de l'entier d'indice 0 du tableau),
- deux variables pour stocker les indices dans le tableau des valeurs maximales et
minimales (initialisées toutes deux à 0 pour indiquer que les valeurs mnimale et
maximale sont celles lues à l'indice 0 du tableau).
Une boucle "pour" est construite de manière à parcourir le reste du tableau
où la recherche est effectuée. Donc on itère de l'indice 1 à l'indice n-1. A chaque
itération, on compare l'élément d'indice courant. S'il est plus grand (resp. plus
petit) que l'entier de valeur maximale (resp. minimale) trouvé jusqu'à présent, la
variable maximum (resp. minimum) est affectée avec la valeur de l'élément d'indice
courant et l'indice du maximum (resp. minimum) est affecté avec l'indice courant.
Cinquième exercice : Exercice 6 du sujet
(pdf)
Une variable compteur est utilisée.
On parcourt entièrement le tableau au moyen d'une structure "pour". A chaque
itération, si la valeur de l'élément courant est égale à la valeur dont le nombre
d'occurrences est recherché, le compteur est incrémenté de un.
Le résultat est la valeur finale du compteur.
Sixième exercice : Sujet
(html)
Pas d'indication particulière.
TP n°3 : Implantation des tableaux en Java (Semaine 4)
La "traduction" en Java de la définition algorithmique d'un tableau est la
suivante:
t : Tableau [N] d'entier
->
int [] t = new int[N];
N est le nombre de cellules allouées pour le tableau. Ce peut être une constante où une
variable, mais une fois le tableau déclaré (alloué), cette taille est immuable.
L'opérateur new est utilisé pour réaliser une allocation de mémoire pour les N éléments du tableau. Cette mémoire est allouée dynamiquement sur la mémoire disponible pour l'application Java en cours de fonctionnement. C'est Java lui-même qui gère le processus de désallocation de la mémoire allouée lorsque les variables correspondantes ne sont plus utilisées.
Runtime.getRuntime().freeMemory() permet de savoir quelle est la quantité de mémoire disponible.
Premier exercice : Exercice 1 du sujet
(pdf)
Le tableau est parcouru par implantation d'une boucle for sur une variable i pour
affecter la valeur i à l'élément d'incide i.
t.length permet de connaître la taille du tableau t.
Exercice supplémentaire
Sujet (html)
Pas d'indication particulière.
Deuxième exercice : Exercice 2 du sujet
(pdf)
Pas d'indication particulière.
Troisième exercice : Exercice 1 du sujet
(pdf)
Pas d'indication particulière.
Quatrième exercice : Exercice 2 du sujet
(pdf)
Une variable entière est utilisée pour accumuler successivement tous les produits élémentaires du produit scalaire.
Cinquième exercice : Exercice 3 du sujet
(pdf)
Pas d'indication particulière.
Sixième exercice : Exercice 4 du sujet
(pdf)
Une variable entière est utilisée pour comptabiliser toutes les occurences de l'entier rechercher.
Exercice supplémentaire
Sujet (html)
Pas d'indication particulière.
TD n°4 : Manipulation de tableaux de variables (Semaine 4)
Premier exercice : Exercice 1 du sujet
(pdf)
Le tableau de caractères est en donnée et en résultat de l'action.
Une boucle "pour" permet d'échanger les caractères deux à deux. Elle est
implantée pour s'écuter n/2 fois (division entière) où n est le nombre de caractères
du tableau.
L'échange du contenu de deux variables nécessite l'emploi d'une variable auxiliaire du
même type.
Deuxième exercice : Exercice 2 du sujet
(pdf)
Le principe général de programmation est le même que celui de l'exercice précédent si ce n'est que l'on compare au lieu de permuter et que sitôt qu'une différence est constatée, il est possible de terminer la fonction avec faux pour résultat.
Troisième exercice : Exercice 3 du sujet
(pdf)
Un tableau de n+1 booléens est utilisé pour indiquer si les entiers de l'intervalle
[0,n] sont premier ou non. Le but de l'action est de remplir ce tableau avec les bonnes
valeurs.
L'algorithme commence par l'initialisation de l'intégralité de ce tableau à faux, faux
puis vrai jusqu'au bout pour indiquer que, au départ, 0 et 1 ne sont pas premier et que
toutes les valeurs de 2 à n le sont.
Ensuite une boucle permet d'itérer sur i entre 2 et sqrt(n) pour mettre à faux tous les
multiples de i entre i*i et n. On programme donc deux boucles imbriquées l'une dans
l'autre.
TP n°4 : Implantation des tableaux en Java (Semaine 5)
Premier exercice : Exercice 1 du sujet
(pdf)
Pas d'indication particulière.
Deuxième exercice : Exercice 2 du sujet
(pdf)
Pas d'indication particulière.
Troisième exercice : Exercice 3 du sujet
(pdf)
Pas d'indication particulière.
TD n°5 et n°6 : Les tris (Semaine 5)
Premier exercice : Exercice 1 du sujet (pdf)
On pourra écrire une fonction permettant de déterminer l'indice de la valeur minimale
d'un tableau de valeurs pour les indices compris entre deux valeurs limites inclues
(boucle pour).
On pourra ensuite utiliser cette fonction pour écrire la fonction de tri par sélection
d'un tableau de valeurs (boucle pour).
Deuxième exercice : Exercice 2 du sujet (pdf)
Le tri à bulle s'implante naturellement au moyen d'une boucle principale de type tant
que (tant que une permtutation a eu lieu). Dans cette boucle tant que, une boucle pour
permet de réaliser le parcours à la recherche des permutations. L'utilisation d'une
variable booléenne initialisée à faux à chaque exécution de la boucle tant que et
affectée à vrai en cas de permutation permet de détecter le fait qu'au moins une
permutation a eu lieu.
A chaque exécution du tant que, une nouvelle valeur du tableau rejoint sa position
définitive en fin de tableau. Il n'est donc pas nécessaire de reparcourir le tableau
jusqu'à cette valeur. A chaque parcours, on a besoin d'aller moins loin dans le tableau.
Troisième exercice : Exercice 3 du sujet
(pdf)
On pourra écrire une fonction permettant de déterminer la position d'insertion d'une
valeur dans un tableau de valeurs pour qu'après insertion, le tableau reste trié (boucle
tant que car la recherche s'arrête quand on a trouvé la bonne position).
On pourra écrire une fonction permettant d'insérer à une position particulière une
valeur dans un tableau de valeurs. Il est nécessaire de décaler de une cellule toutes
les valeurs du tableau à partir de la position d'insertion pour pouvoir ensuite affecter
la cellule libérée avec la valeur (boucle pour car on sait combien de décalages doivent
être réalisés). Le décalage doit être effectué à rebours depuis la fin du tableau.
Ces deux fonctions étant écrites, on pourra écrire une fonction de tri par insertion
d'un tableau de valeurs.
TP n°5 et n°6 : Les tris (Semaine 6)
Premier exercice : Exercice 1 du sujet (pdf)
Pas d'indication particulière.
Deuxième exercice : Exercice 2 du sujet (pdf)
Pas d'indication particulière.
Troisième exercice : Exercice 3 du sujet
(pdf)
Pas d'indication particulière.
Exercice supplémentaire : Sujet
(pdf)
On s'efforcera de conserver la linéarité de l'algorithme tant pour la crétion des tableaux triés initiaux que pour l'opération de fusion entre deux tableaux. Ceci exclut l'emploi de tout algorithme de tri.
TD n°7 : Les matrices (Semaine 6)
Premier exercice : Exercice 1 du sujet
(pdf)
La matrice à remplir est passée en donnée et résultat.
Deux boucles pour imbriquées permettent de lire au clavier successivement toutes les
valeurs de la matrice. La première boucle donne le premier indice, la seconde donne le
second.
Exercice supplémentaire : Sujet
(pdf)
Pas d'indication particulière.
Deuxième exercice : Exercice 2 du sujet
(pdf)
Deux boucles pour imbriquées permettent d'afficher successivement toutes les valeurs de la matrice.
Troisième exercice : Exercice 3 du sujet
(pdf)
La recherche de minimum est implantée sous deux versions:
- la valeur minimale est recherchée,
- les indices de la valeur minimale sont recherchés.
Dans les deux cas, deux boucles imbriquées permettent d'implanter une recherche classique
de minimum.
Quatrième exercice : Exercice 4 du sujet
(pdf)
Une simple boucle pour permet de calculer la somme de la diagonale par accumulation. Les indices des éléments de la diagonale sont ceux où les deux valeurs sont identiques.
Cinquième exercice : Exercice 5 du sujet
(pdf)
Le produit de deux matrices pourra être implanté par imbrication de 3 boucles pour. Les 2 boucles pour principales programment le calcul de chacune des composantes de la matrice résultat. La boucle pour la plus interne est celle qui implante le produit ligne par colonne.
Exercice supplémentaire : Sujet
(pdf)
L'adaptation à réaliser par rapport à l'exercice précédent consiste à ajuster les tailles des matrices et les limites de variabilité des "pour".
Sixième exercice : Exercice 6 du sujet
(pdf)
Pas d'indication particulière.
Exercice supplémentaire : Sujet
(pdf)
On parcourt la diagonale de la matrice.
Sitôt qu'une valeur non égale à true est trouvée, on peut conclure à la non
réflexivité.
TP n°7 : Les matrices (Semaine 7)
La "traduction" en Java de la définition algorithmique d'un tableau à deux
indices (matrice) est la suivante:
t : Tableau [N][M] d'entier
->
int [][] t = new int[N][M];
N*M est le nombre de cellules allouées pour le tableau à deux indices. N et M peuvent
être des constantes où des variables, mais une fois le tableau déclaré (alloué), ces
tailles sont immuables.
On peut généraliser l'utilisation des tableaux à un nombre quelconque d'indices au
lieu de 1 ou 2. On devra placer autant de [ ] que d'indices à utiliser. Les tailles selon
chacun des indices devront être notifiées dans le new d'allocation.
Il est à noter que le new peu échouer si la quantité de mémoire disponible est
insuffisante. Exemple: l'allocation d'un tableau de 1000*1000*1000 double demande
8*1000*1000*1000 soit 8000000000 d'octets ce qui peut excéder la quantité disponible.
Premier exercice : Exercice 1 du sujet
(pdf)
Pas d'indication particulière.
Deuxième exercice : Exercice 2 du sujet
(pdf)
Pas d'indication particulière.
Troisième exercice : Exercice 3 du sujet
(pdf)
Pas d'indication particulière.
Quatrième exercice : Exercice 4 du sujet
(pdf)
Pas d'indication particulière.
Cinquième exercice : Exercice 5 du sujet
(pdf)
Pas d'indication particulière.
Exercice supplémentaire : Sujet
(pdf)
Pas d'indication particulière.
TD n°8 : Les matrices (Semaine 7)
Premier exercice : Exercice 1 du sujet
(pdf)
La fonction de test pourra utiliser quatre autres fonctions à développer:
- une fonction de somme des valeurs d'une colonne,
- une fonction de somme des valeurs d'une ligne,
- une fonction de somme des valeurs d'une diagonale directe,
- une fonction de somme des valeurs d'une diagonale indirecte.
Le test pourra être interrompu avec pour résultat faux sitôt qu'une valeur trouvée est
différente de celle trouvée jusqu'à présent.
Deuxième exercice : Exercice 2 du sujet
(pdf)
Pas d'indication particulière.
Troisième exercice : Exercice 3 du sujet
(pdf)
Une copie de la matrice est créée si p = 1.
Si p n'est pas égal à 1, on pourra accumuler les produits matriciels sur la même
variable tableau.
Exercice supplémentaire : Sujet
(pdf)
On parcourt la diagonale de la matrice.
Sitôt qu'une valeur non égale à true est trouvée, on peut conclure à la non
réflexivité.
TD n°9 : Représentation des problèmes (Semaine 7)
Les structures de données choisies lors de la phase de représention des problèmes doivent assurer le stockage des informations traitées pour la résolution du problème. Le choix du type de struture pouvant avoir une influence sur la facilité de programmation et la qualité (en particulier, la rapidité) de la solution, une attention particulière sera portée à ce choix.
Premier exercice : Exercice 1 du sujet
(pdf)
Pas d'indication particulière.
Deuxième exercice : Exercice 2 du sujet
(pdf)
Pas d'indication particulière.
TP n°8 : Les matrices (Semaine 8)
Premier exercice : Exercice 1 du sujet
(pdf)
Pas d'indication particulière.
Deuxième exercice : Exercice 2 du sujet
(pdf)
Pas d'indication particulière.
Troisième exercice : Exercice 3 du sujet
(pdf)
Pas d'indication particulière.
TD n°10 : Complexité et recherche dichotomique (Semaine 8)
On considère un tableau d'entiers contenant une liste de nombres triés
par ordre croissant. On souhaite déterminer la position d'insertion d'une valeur au sein
de ce tableau. La méthode de recherche classique par parcours séquentiel du tableau à
la recherche de la dernière valeur inférieure ou égale à la valeur à insérer est
simple mais inefficace car elle s'exécute en un temps en o(n).
La méthode de recherche dichotomique exploite mieux le fait que le tableau est trié. Son
principe consiste :
- à considérer que la place à trouver se trouve dans un intervalle de recherche
initialement égal au tableau lui-même,
- à itérer en réduisant, à chaque itération, d'un facteur 2 la taille de cet
intervalle jusqu'à ce qu'il devienne de taille 1.
A chaque itération, l'intervalle global est réduit à son 1er demi intervalle ou son
2ème demi-intervalle suivant la comparaison de la valeur à placer par rapport à la
valeur médiane de l'intervalle global.
TD n°11 : Correction de l'examen de TD (Semaine 9)
TP n°9 et n°10 : Complexité et début du projet (Semaine 10)
Premier exercice
Deuxième exercice
TD n°12 : Exercices divers (Semaine 10)
Premier exercice
Implanter un algorithme de calcul de toutes les factoriels de i pour i compris entre 1 et n.
Deuxième exercice
Implanter un algorithme de calcul de toutes les valeurs fib(i) pour i compris entre 0
et n.
On rappelle que fib(0) = 0, fib(1) = 1 et fib(n) = fib(n-1)+fib(n-2) pour tous les n >=
2.
Troisième exercice
Quelle est la complexité des deux algorithmes précédents.
Quatrième exercice
On souhaite représenter au sein d'un programme informatique des polygones du plan.
Le nombre de sommets de ces polygones est quelconque.
Les coordonnées des sommets sont réelles.
Définir une struture de données permettant de représenter de tels polygones.
Cinquième exercice
Ecrire un algorithme de calcul de la position du centre d'un polygone.
Sixième exercice
Ecrire un algorithme de calcul du périmètre d'un polygone.
TP n°11 : Travail sur le projet (Semaine 13)
TD n°13 et n°14 : Premiers concepts de programmation orientée objet (Semaine 13)
Premier exercice : Exercice 1 du sujet (pdf)
Développement d'une classe Compteur.
Deuxième exercice : Exercice 2 du sujet
(pdf)
Développement d'une classe Personne.
Troisième exercice : Exercice 1 du sujet (pdf)
Développement d'une classe Cercle qui s'appuie sur une classe Position.
Quatrième exercice : Exercice 2 du sujet (pdf)
Développement d'une classe Pile d'objets instanciant la classe Object.
TP n°12 : Premiers concepts de programmation orientée objet (Semaine 14)
Implanter les trois premiers exercices des TD n°13 et n°14. On devra programmer un fichier java pour chacune des classes ainsi qu'un fichier java pour chacune des trois applications.
Premier exercice : Exercice 1 du sujet (pdf)
Deuxième exercice : Exercice 2 du sujet
(pdf)
Troisième exercice : Exercice 1 du sujet (pdf)
TD n°15 et n°16 : La récursivité (Semaine 14)
Premier exercice : Exercice 1 du sujet (pdf)
Pas d'indication particulière.
Deuxième exercice : Exercice 3 du sujet (pdf)
Pas d'indication particulière.
Troisième exercice : Exercice 4 du sujet (pdf)
Pas d'indication particulière.
Quatrième exercice : Exercice 5 du sujet (pdf)
Pas d'indication particulière.
Cinquième exercice : Sujet
(html)
Pas d'indication particulière.
Sixième exercice : Sujet
(html)
Pas d'indication particulière.
TD n°17 : Révisions (Semaine 15)
Premier exercice : Sujet
(html)
Pas d'indication particulière.
Deuxième exercice : Sujet
(html)
Pas d'indication particulière.
Auteur: Nicolas JANEY
UFR Sciences et Techniques
Université de Besançon
16 Route de Gray, 25030 Besançon
nicolas.janey@univ-fcomte.fr