[PDF] [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é 



Previous PDF Next PDF





[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

INF431

AlgorithmesetProgrammation:

dusequentielaudistribue

Ecolepolytechnique

PartieI

FrancoisMorain&Jean-MarcSteyaert

2 2

Tabledesmatieres

IProgrammation13

1ProgrammeravecJava15

2Introductionaugenielogiciel35

3Complexiteetstructuresdedonnees45

3

4TABLEDESMATIERES

IIGraphes49

4Proprieteselementairesdesgraphes51

5Accessibilite59

6Parcours69

TABLEDESMATIERES5

7Topologie91

7.2.1

8EuleretHamilton121

9.2.3

6TABLEDESMATIERES

IIILangages147

10Langagesrationnels149

11Parenthesages,Langagesalgebriques177

TABLEDESMATIERES7

12Analysesyntaxiqueetautreslangages203

IVAnnexes227

14QuelquesclassespredeniesdeJava229

15LaclasseGraphe233

8TABLEDESMATIERES

Presentation

Lesbutsducours

ainsiquedesprotocoles.

Remerciements

leremercionschaleureusement. 9 10

Notations

Lecardinald'unensembleEseranotejEj.

Algorithme,pseudocodeetprogramme

objets).

2.Lesinstructionsseronttermineesparun;.

nuerontd'existeralasortiedesiterations. globale,saufindicationexplicite. commeenJava. 11 y.

L#z=(x1,...,xn,z)

ou z#L=(z,x1,...,xn) t ete(L)=x1;ecrire y<-tˆ ete(L); designespard´

Onauradoncformellement:

L=tˆ

ete(L)#reste(L)=d´ ebut(L)#queue(L) ront^etredonneesquandnecessaire. ecrire. surleselementsdutableau. rechercheMinimum(A) imin<-0; pouri<-1` alongueur(A)-1faire siA[i]Premierepartie

Programmation

13

Chapitre1

ProgrammeravecJava

1.1Modularite

1.1.1Motivation

revelentrapidementinsusants. 15

16CHAPITRE1.PROGRAMMERAVECJAVA

1.1.2Modules

(cf.section2.2.2). publicclassFIFO{ privateintdebut,fin; privatebooleanpleine,vide; privateint[]contenu; publicFIFO(intn){ debut=0;fin=0; pleine=n==0;vide=true; contenu=newint[n]; publicstaticvoidajouter(intx,FIFOf){ f.contenu[f.fin]=x; f.fin=(f.fin+1)%f.contenu.length; f.vide=false;f.pleine=f.fin==f.debut; publicstaticintsupprimer(FIFOf){ if(f.vide) thrownewError("FileVide.");

1.1.MODULARITE17

intres=f.contenu[f.debut]; f.debut=(f.debut+1)%f.contenu.length; f.vide=f.fin==f.debut;f.pleine=false; returnres; lesfonctionsd'acces. publicclassFIFO{ privateListedebut,fin; publicFIFO(intn){debut=null;fin=null;} publicstaticvoidajouter(intx,FIFOf){ if(f.fin==null) f.debut=f.fin=newListe(x); else{ f.fin.suivant=newListe(x); f.fin=f.fin.suivant; publicstaticintsupprimer(FIFOf){ else{ intres=f.debut.val; if(f.debut==f.fin) f.debut=f.fin=null; elsef.debut=f.debut.suivant; returnres; utiliserdesinterfaces,voirlasection1.3.

18CHAPITRE1.PROGRAMMERAVECJAVA

1.2Programmationparobjets

1.2.1Motivations

traitement. partageespartouslesobjetsdelaclasse. desdessinsenJava.

1.2.2L'heritageparl'exemple

y: classPoint{ doublex,y; unecouleur:

1.2.PROGRAMMATIONPAROBJETS19

classPointCextendsPoint{ finalstaticintJAUNE=0,ROUGE=1; intc;

PointC(doublex0,doubley0,intcol){

x=x0;y=y0;c=col;//[1] publicstaticvoidmain(String[]args){

PointCpc=newPointC(3,4,JAUNE);

classePoint.

Completonsl'exemple:

classPoint{ doublex,y; staticintNP=1; staticvoidafficherAbscisse(Pointp){

System.out.println("P:"+p.x);

classPointCextendsPoint{ finalstaticintJAUNE=0,ROUGE=1; intc;

PointC(doublex0,doubley0,intcol){

x=x0;y=y0;c=col; publicstaticvoidmain(String[]args){

PointCpc=newPointC(3,4,JAUNE);

afficherAbscisse(pc);

System.out.println("NP="+NP);

elleaussiaccessibledepuisPointC. lecode: classPoint{

20CHAPITRE1.PROGRAMMERAVECJAVA

staticvoidafficherAbscisse(Pointp){

System.out.println("Point:"+p.x);

classPointCextendsPoint{ staticvoidafficherAbscisse(Pointp){

System.out.println("PointC:"+p.x);

publicstaticvoidmain(String[]args){

PointCpc=newPointC(3,4,JAUNE);

afficherAbscisse(pc);

Point.afficherAbscisse(pc);

specialiserdesmethodesd'objet: classPoint{ voidafficher(){

System.out.println("p:"+x);

classPointCextendsPoint{ voidafficher(){

System.out.println("pc:"+x);

publicstaticvoidmain(String[]args){

PointCpc=newPointC(3,4,JAUNE);

Pointp=newPoint();

p.x=1; pc.afficher(); p.afficher();

1.2.PROGRAMMATIONPAROBJETS21

1.2.3Proprietesdel'heritage

contenantl'objet. classPointCextendsPoint{ finalstaticintJAUNE=0,ROUGE=1; intc;

PointC(doublex0,doubley0,intcol){

super();//facultatif x=x0;y=y0;c=col; publicstaticvoidmain(String[]args){

PointCpc=newPointC(3,4,JAUNE);

super: classPoint{ doublex,y;

Point(doublex0,doubley0){

x=x0;y=y0; classPointCextendsPoint{ finalstaticintJAUNE=0,ROUGE=1; intc;

PointC(doublex0,doubley0,intcol){

super(x0,y0);//n´ ecessaire c=col; publicstaticvoidmain(String[]args){

PointCpc=newPointC(3,4,JAUNE);

22CHAPITRE1.PROGRAMMERAVECJAVA

(malheureusement?)licite: classPointCextendsPoint{ finalstaticintJAUNE=0,ROUGE=1; intx; intc;

1.2.4Contr^oled'accesetsous-classes

courante; classesdelaclassecourante. exemple. final). methodesoriginellementdenies.

1.2.5Unpeudetypage

Theorie

1.2.PROGRAMMATIONPAROBJETS23

BenjaminPierceoudeAbadi-Cardelli.

EtenJava

if(pinstanceofPointC)

System.out.println("couleur="+p.c);

Doncl'expression(PointC)pequivauta:

if(pinstanceofPointC) p else thrownewClassCastException(); t explicitesinecessaire: byte<:short<:int<:long float<:double char<:int<:long

C<:C0siCestunesous-classedeC0.

Ex.PointC<:Point.

8CC<:Object

equals,toString. intx=3;

Objetxobj=newInteger(x);

inty=xobj.intValue();

24CHAPITRE1.PROGRAMMERAVECJAVA

Quelquesexemplesextr^emes

classA{ intx;

A(){x=1;}

classBextendsA{

B(){x=2;}

publicstaticvoidmain(String[]args){

Bb=newB();

Aa=newB();

System.out.println(b.x);

System.out.println(a.x);

Leprogrammeache:

2 2 marchepuisqueBestsous-classedeA.

Cetteproprietepermetd'ecrire:

classPoint{ doublex,y; staticvoidtranslation(Pointp, doubledx,doubledy){ p.x+=dx;p.y+=dy; classPointCextendsPoint{ finalstaticintJAUNE=0,ROUGE=1; intc;

PointC(doublex0,doubley0,intcol){

x=x0;y=y0;c=col; publicstaticvoidmain(String[]args){

PointCpc=newPointC(3,4,JAUNE);

translation(pc,1,2);

1.2.PROGRAMMATIONPAROBJETS25

Parcontre,lecodesuivantnepeutmarcher:

classPoint{ staticPointtranslation(Pointp, doubledx,doubledy){

Pointpt=newPoint();

pt.x=p.x+dx;pt.y=p.y+dy; returnpt; classPointCextendsPoint{ publicstaticvoidmain(String[]args){

PointCpc=newPointC(3,4,JAUNE);

pc=(PointC)translation(pc,1,2); pasl'execution(ClassCastException).

Heritageetsurcharge

classeval'instancier. suivant? classC{ voidf(){ g(); voidg(){

System.out.println(1);

classDextendsC{ voidg(){

System.out.println(2);

publicstaticvoidmain(String[]args){

Dx=newD();

26CHAPITRE1.PROGRAMMERAVECJAVA

x.f(); fA;BgetU;U02fA;BgavecT0<:TetU0<:U? classA{ publicstaticvoidmain(String[]args){

Tx=newT0();Uy=newU0();

System.out.println(x.f(y));

intf(Ay){return1;} classBextendsA{ intf(By){return2;}

1.3LesinterfacesdeJava

dessontabstraitesetpubliques. interface. dansuneclasse. prietesattenduesd'uneFIFO:quotesdbs_dbs44.pdfusesText_44