[PDF] [PDF] Plan Langage Java • Exceptions Algorithmique • Implantations - IRIF

[PDF] Plan Langage Java • Exceptions Algorithmique • Implantations - IRIF

Soit F un parcours en largeur à partir de s d'un graphe G Pour chaque sommet v ≠ s, il existe un premier élément v' de F tel que (v', v) 

[PDF] Représentation des graphes et Programmation

un graphe non orienté est dit connexe si on peut aller de tout le parcours en profondeur et le parcours en largeur Graphe : programme Java La classe 

[PDF] Parcours dun graphe

1 avr 2013 · Parcours en largeur : principe de l'algorithme Vous devez parcourir toutes les pages d'un site web Les pages sont les sommets d'un graphe 

[PDF] Plan Langage Java • Exceptions Algorithmique • Implantations dun

Soit F un parcours en largeur à partir de s d'un graphe G Pour chaque sommet v ≠ s, il existe un premier élément v' de F tel que (v', v) 

[PDF] Chapitre 3 : Exploration dun graphe - Algorithmique de - LIPN

1 Exploration d'un graphe / Parcours 2 Parcours en largeur (BFS) Partition des sommets en couches Principe de l'algorithme Implémentation Complexité

[PDF] IR2 - Algorithmique des graphes TP2 - Parcours en profondeur

en profondeur et en largeur (le parcours en largeur sur les graphes est identique à celui sur les arbres) par un ensemble d'entiers (utiliser la classe java util

[PDF] INF431 Algorithmes et Programmation: du séquentiel au - IGM

biblioth`eques déj`a programmées en Java, bénéficiant des types génériques Proposition 6 2 3 Soit L un parcours en profondeur d'abord d'un graphe orienté 

[PDF] Parcours de graphes - Projet Cristal

Graphes 4 Représentation des graphes 5 Parcours en profondeur 6 (En fait l'initialisation de m est inutile, car c'est l'option par défaut en Java) 16 

[PDF] conflit de puissance définition

[PDF] parcours lecture acces pas cher

[PDF] parcours lecture pdf

[PDF] parcours lecture le petit chaperon rouge

[PDF] parcours lecture acces avis

[PDF] parcours lecture occasion

[PDF] coexistence pacifique cours

[PDF] archives militaire en ligne

[PDF] livret militaire en ligne

[PDF] la coexistence pacifique de 1953 ? 1962 pdf

[PDF] cornière catnic

[PDF] corniere galva pour brique

[PDF] corniere pour linteau brique

[PDF] cornière support briques

[PDF] cornière pour linteau de brique

X, Petite classe 5X, Petite classe 5X, Petite classe 8X, Petite classe 8 Plan

Langage Java

• Exceptions

Algorithmique

• Implantations d'un graphe • Parcours de graphe X, Petite classe 5X, Petite classe 5X, Petite classe 8X, Petite classe 8

Exceptions

Une exception est un objet de la

classe java.lang.Exception (ou de l'une de ses sous-classes) class ExceptionPile extends Exception

ExceptionPile(String m)

System.out.println(m)

Utilisation :

int valeur() throws ExceptionPile if (estVide()) throw new ExceptionPile("Pile vide"); return contenu[hauteur-1]; X, Petite classe 5X, Petite classe 5X, Petite classe 8X, Petite classe 8

Exceptions

Effets de la levée d'exception, par

"throws" (1) création d'un objet de la classe

ExceptionPile

(2) sortie de la méthode en cours (3) recherche dans l'arbre d'appel d'un bloc qui capte l'exception

Pile p = new Pile();

try// Exécution contrôlée

System.out.println(p.valeur());

catch(ExceptionPile e)

System.out.println(m)

X, Petite classe 5X, Petite classe 5X, Petite classe 8X, Petite classe 8

Exceptions

Le bloc try lance l'exécution.

Si une erreur se produit pendant

cette exécution, l'éxécution se poursuit dans un bloc catch, avec comme argument e l'objet créé lors de la levée d'exception.

Pile p = new Pile();

try// Exécution contrôlée

System.out.println(p.valeur());

catch(ExceptionPile e)

System.out.println(m)

X, Petite classe 5X, Petite classe 5X, Petite classe 8X, Petite classe 8

Exceptions

On peut avoir 0, 1 ou plusieurs

blocs catch, qui se comportent comme un case dans un bloc switch. try// Exécution contrôlée readFromFile("monFichier"); catch(FilelNotFoundException e)

System.out.println("Pas trouvé !")

catch(IOException e)

System.out.println("Erreur d'entrée-

sortie"); catch(Exception e)// Autres erreurs

System.out.println("Erreur");

X, Petite classe 5X, Petite classe 5X, Petite classe 8X, Petite classe 8

Finally

On peut rajouter un bloc finally,

qui est exécuté que l'exception soit levée ou pas, même en cas de return, avant que le programme ne quitte le try try// Exécution contrôlée readFromFile("monFichier"); catch { ... } finally// nettoyage

Refermer les fichiers, les connections

Internet, etc.

X, Petite classe 5X, Petite classe 5X, Petite classe 8X, Petite classe 8

Matrice d'adjacence

M i,j = {

010100010010001001010001001000100 si (i, j) G

1 si (i, j) G1

2 3

4class GrapheMat

int[][] m;// Matrice d'adjacence int n; // nombre de sommets

GrapheMat(int n) {

this.n = n; m = new int[n][n]; X, Petite classe 5X, Petite classe 5X, Petite classe 8X, Petite classe 8

Exemple d'utilisation

Thm Soit M la matrice d'adjacence

d'un graphe G. Pour tout n ³ 0, Mi,jest égal au nombre de chemins de longueur n de i à j.n n true s'il existe un chemin de longueur n de i à j false sinon class GrapheMat boolean[][] m;// Matrice d'adjacence int n; // nombre de sommets }Remarque Si M est définie comme matrice booléenne, on a M i,j = { X, Petite classe 5X, Petite classe 5X, Petite classe 8X, Petite classe 8

Matrice d'incidence

1si i est l'origine de a

M i,a = {-1si i est l'extrémité de a

0sinon

Exercice : montrer que M est

unimodulaire, i. e. le déterminant de toute sous-matrice carrée de M vaut 0, -1 ou 1.(Graphe sans boucle) 1 0 1 0-1 -1 1 0 0 0

0 0 0-1 1

0-1-1 1 012

3 41
23
45

1 2 3 4 5

1 2 3 4 X, Petite classe 5X, Petite classe 5X, Petite classe 8X, Petite classe 8

Par récurrence sur la taille n de la

matrice carrée extraite. • Clair pour n = 1 • On développe le calcul du déterminant D n par rapport à une colonne. - Si une colonne est nulle, Dn = 0 - Si une colonne contient un seul coefficient non nul, 1 ou -1, D n = ± Dn-1- Si toutes les colonnes ont deux coefficients non nuls (1 et -1), la somme des colonnes est nulle et D n = 0Solution X, Petite classe 5X, Petite classe 5X, Petite classe 8X, Petite classe 8

Liste de successeurs

1 : 24

2 : 4 3 : 3

4 : 3public class GrapheListe

Liste[] succ;

int n;

GrapheListe(int n)

this.n = n; succ = new Liste[n]; }1 2 3 4 X, Petite classe 5X, Petite classe 5X, Petite classe 8X, Petite classe 8

Comparaison des tailles

Graphe à n sommets et m arcs.

Matrice d'adjacence : n2

Matrice d'incidence : nm

Liste de successeurs : n + m

X, Petite classe 5X, Petite classe 5X, Petite classe 8X, Petite classe 8

Parcours d'un graphe connexe

non orienté à partir d'un sommet s

C'est une suite S de sommets t.q.

(1) s est le premier sommet de S (2) Chaque sommet apparaît une fois et une seule dans S (3) Tout sommet sauf la racine est adjacent à un sommet placé avant lui dans la liste.Exemple : 5 3 6 2 1 4 7 est un parcours issu de 51 23
4 5 67
X, Petite classe 5X, Petite classe 5X, Petite classe 8X, Petite classe 8

On obtient une arborescence de

Trémeaux.

Ici, en partant

de s = 1 :

Complexité (n sommets, m arêtes)

O(n + m) avec des listes de

successeurs, O(n

2) avec des

matrices d'incidenceParcours en profondeur

Initialisation : S = (s)

Si S = (s

1 , ..., sn-1), on prend

pour s n un voisin de sn-1, ou, à défaut, un voisin de s n-2, ou, à défaut, un voisin de s n-3, etc.1 23
5 6 74
X, Petite classe 5X, Petite classe 5X, Petite classe 8X, Petite classe 8 public class Graphe

Liste[] succ;

boolean[] marque; int n;

Graphe(int n)

this.n = n; succ = new Liste[n]; marque = new boolean[n]; void marquer(int i) marque[i] = true; void demarquer() for (int i = 0; i < n; i++) marque[i] = false; X, Petite classe 5X, Petite classe 5X, Petite classe 8X, Petite classe 8

Trémeaux Récursif

void profondeur(int i)

System.out.print(i + " ");

marquer(i); for (Liste a = succ[i]; a != null; a = a.suivant) int v = a.contenu; if (!marque[v]) profondeur(v); void parcoursProfondeur() demarquer(); for (int i = 0; i < n; i++) if (!marque[i]) profondeur(i); X, Petite classe 5X, Petite classe 5X, Petite classe 8X, Petite classe 8quotesdbs_dbs44.pdfusesText_44