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.

Correction

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.

Correction

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).

Correction

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.

Correction

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.

Correction

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).

Correction

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.

Correction

Exercices supplémentaires

Exercice 1 du sujet (pdf)

Pas d'indication particulière.

Correction

Exercice 2 du sujet (pdf)

Pas d'indication particulière.

Correction

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).

Correction

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).

Correction

Sujet (html)

Pas d'indication particulière.

Correction

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).

Correction

Deuxième exercice : Exercice 3 du sujet d'examen de première session (pdf) : Remplissage

Correction

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.

Correction

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.

Correction

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.

Correction

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.

Correction

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.

Correction

Sixième exercice : Sujet (html)

Pas d'indication particulière.

Correction

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.

Correction

Exercice supplémentaire

Sujet (html)

Pas d'indication particulière.

Correction

Deuxième exercice : Exercice 2 du sujet (pdf)

Pas d'indication particulière.

Correction

Troisième exercice : Exercice 1 du sujet (pdf)

Pas d'indication particulière.

Correction

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.

Correction

Cinquième exercice : Exercice 3 du sujet (pdf)

Pas d'indication particulière.

Correction

Sixième exercice : Exercice 4 du sujet (pdf)

Une variable entière est utilisée pour comptabiliser toutes les occurences de l'entier rechercher.

Correction

Exercice supplémentaire

Sujet (html)

Pas d'indication particulière.

Correction

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.

Correction

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.

Correction

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.

Correction

TP n°4 : Implantation des tableaux en Java (Semaine 5)

Premier exercice : Exercice 1 du sujet (pdf)

Pas d'indication particulière.

Correction

Deuxième exercice : Exercice 2 du sujet (pdf)

Pas d'indication particulière.

Correction

Troisième exercice : Exercice 3 du sujet (pdf)

Pas d'indication particulière.

Correction

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).

Correction

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.

Correction

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.

Correction

TP n°5 et n°6 : Les tris (Semaine 6)

Premier exercice : Exercice 1 du sujet (pdf)

Pas d'indication particulière.

Correction

Deuxième exercice : Exercice 2 du sujet (pdf)

Pas d'indication particulière.

Correction

Troisième exercice : Exercice 3 du sujet (pdf)

Pas d'indication particulière.

Correction

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.

Correction

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.

Correction

Exercice supplémentaire : Sujet (pdf)

Pas d'indication particulière.

Correction

Deuxième exercice : Exercice 2 du sujet (pdf)

Deux boucles pour imbriquées permettent d'afficher successivement toutes les valeurs de la matrice.

Correction

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.

Correction

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.

Correction

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.

Correction

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".

Correction

Sixième exercice : Exercice 6 du sujet (pdf)

Pas d'indication particulière.

Correction

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é.

Correction

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.

Correction

Deuxième exercice : Exercice 2 du sujet (pdf)

Pas d'indication particulière.

Correction

Troisième exercice : Exercice 3 du sujet (pdf)

Pas d'indication particulière.

Correction

Quatrième exercice : Exercice 4 du sujet (pdf)

Pas d'indication particulière.

Correction

Cinquième exercice : Exercice 5 du sujet (pdf)

Pas d'indication particulière.

Correction

Exercice supplémentaire : Sujet (pdf)

Pas d'indication particulière.

Correction

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.

Correction

Deuxième exercice : Exercice 2 du sujet (pdf)

Pas d'indication particulière.

Correction

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.

Correction

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é.

Correction

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.

Correction

Deuxième exercice : Exercice 2 du sujet (pdf)

Pas d'indication particulière.

Correction

TP n°8 : Les matrices (Semaine 8)

Premier exercice : Exercice 1 du sujet (pdf)

Pas d'indication particulière.

Correction

Deuxième exercice : Exercice 2 du sujet (pdf)

Pas d'indication particulière.

Correction

Troisième exercice : Exercice 3 du sujet (pdf)

Pas d'indication particulière.

Correction

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)

Correction exercice n°1

Correction exercice n°2

Correction exercice n°3

TP n°9 et n°10 : Complexité et début du projet (Semaine 10)

Premier exercice

- Implanter l'exercice n°2 de l'examen de TD
- Modifier l'implantation réalisée de manière à compter et afficher combien d'opérations d'affectation et combien de tests sont réalisés au cours de l'exécution.

Deuxième exercice

- Présenter les structures de données et les principaux algorithmes à développer pour la réalisation du projet Néomix.
- Commencer l'implantation du projet.

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.

Correction

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.

Correction

Troisième exercice

Quelle est la complexité des deux algorithmes précédents.

Correction

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.

Correction

Cinquième exercice

Ecrire un algorithme de calcul de la position du centre d'un polygone.

Correction

Sixième exercice

Ecrire un algorithme de calcul du périmètre d'un polygone.

Correction

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.

Correction

Deuxième exercice : Exercice 2 du sujet (pdf)

Développement d'une classe Personne.

Correction

Troisième exercice : Exercice 1 du sujet (pdf)

Développement d'une classe Cercle qui s'appuie sur une classe Position.

Correction

Quatrième exercice : Exercice 2 du sujet (pdf)

Développement d'une classe Pile d'objets instanciant la classe Object.

Correction

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)

Correction

Deuxième exercice : Exercice 2 du sujet (pdf)

Correction

Troisième exercice : Exercice 1 du sujet (pdf)

Correction

TD n°15 et n°16 : La récursivité (Semaine 14)

Premier exercice : Exercice 1 du sujet (pdf)

Pas d'indication particulière.

Correction

Deuxième exercice : Exercice 3 du sujet (pdf)

Pas d'indication particulière.

Correction

Troisième exercice : Exercice 4 du sujet (pdf)

Pas d'indication particulière.

Correction

Quatrième exercice : Exercice 5 du sujet (pdf)

Pas d'indication particulière.

Correction

Cinquième exercice : Sujet (html)

Pas d'indication particulière.

Correction

Sixième exercice : Sujet (html)

Pas d'indication particulière.

Correction

TD n°17 : Révisions (Semaine 15)

Premier exercice : Sujet (html)

Pas d'indication particulière.

Correction

Deuxième exercice : Sujet (html)

Pas d'indication particulière.

Correction

Auteur: Nicolas JANEY
UFR Sciences et Techniques
Université de Besançon
16 Route de Gray, 25030 Besançon
nicolas.janey@univ-fcomte.fr