Discussion :

[baobab95]

bonjour,
voila dans mon exam de java il y avait cette question, mais je n'ai pas compris la réponse !!

Code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
Class D {
public int x;
public D() { x = 3;}
public D (int a) {this(); x=x+a;}
public D (int a, int b){ this(b); x=x-a;}

Qu'afficheras le code suivant ?

Code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
D a = nex D(5,6);
System.out.println(a.x);

la réponse est 4..Pourquoi ?

[michel.di]

D(5,6) fait appel a D(6) qui initialise x à 3 et D(6) fait x+=6 soit 9 et D(5,6) fait 9-5 soit 4
j'espère avoir été clair!

[baobab95]

[QUOTE=michel.di
j'espère avoir été clair! [/QUOTE]

Oui ! Merci beaucoup !!

[michel.di]

ravi de t'avoir aidé!

[baobab95]

je vais en profiter car j'ai encore des doutes au sujet d'une chose !
la compléxité !! (c'est ce qui me fais me planter à chaque fois !)
voila l'énoncé :
on considère la boucle suivante (n > 0) :
for (int i = 0 ; i < n; i+=1) for (int j = 1; j < n; j=2*j) f(i);

1) Le nombre d'apels de f est un O(n)
2) Le nombre d'apels de f est un O(n²)
3) Le nombre d'apels de f est un O(log(n))
4) Le nombre d'apels de f est un O(nlog(n))

au passage si quelqu'un à un bon cours sur la compléxité je prends car je suis vraiment nul !
pour moi la bonne réponse été la 2 (car il y a deux boucle imbriquée) mais apparament c'est la 4...

[michel.di]

il s'agit bien de la 4 car pour ta première boucle tu fais bien n parcours mais pour la seconde tu divises par deux à chaque tour et il s'agit alors de log n !
J'ai eu des cours cette année en Master mais les exemples du pdf ne sont pas corrigés, ça ne t'aidera pas!

[baobab95]

j'ai vraiment pas tout saisi sur la complexité !
alors d'aprés ce que j'ai lu dans ta réponse, cela dépend aussi de ce qu'il y a comme condition dans la boucle, et pas uniquement la boucle...
pour moi jusqu'ici c'était une boucle for est de compléxité n si on imbrique une boucle dans une autre on passe a n² et ainsi de suite, en revanche si les boucle ne sont pas imbriquée cela fait 2n...

alors comment reconnaitre réellement lorsque c'est n ou log(n) ?
si tu as eu des cours tu peux peut-etre m'aider ! moi je suis en 1iere année de licence...Désolé si tu n'as pas le temps ce n'est pas grave !

Merci pour tout

[michel.di]

oui ça dépend aussi de la façon dont est incrémenté ton indice! la a chaque tour de boucle tu divises ton nombres de tours par 2!
j'ai des cours de complexité que j'ai eu en licence, regarde un peu!
http://www.fil.univ-lille1.fr/portai...em=S3&ue=API2#
tu as pas mal de pdf avec les cours

[Astartee]

on considère la boucle suivante (n > 0) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for (int i = 0 ; i < n; i+=1)
   for (int j = 1; j < n; j=2*j)
      f(i);

pour moi la bonne réponse été [Le nombre d'apels de f est un O(n²)] (car il y a deux boucle imbriquée) mais apparament c'est [Le nombre d'apels de f est un O(nlog(n))]

Il y a certes 2 boucles, mais ce ne sont pas les mêmes !

Première boucle : for (int i = 0 ; i < n; i+=1)
A chaque passage dans la boucle, on incrémente i de 1. Donc au k-ième passage dans la boucle i=k.
On sort de la boucle dès que i>=n, c'est à dire dès que k>=n.
On va donc passer environ n fois dans la boucle.

Deuxième boucle : for (int j = 1; j < n; j=2*j)
A chaque passage dans la boucle, on multiplie j par 2. Donc au k-ième passage dans la boucle j=2^k.
On sort de la boucle dès que j>=n, c'est à dire dès que 2^k>=n.
On va donc passer environ log2(n) fois dans la boucle.

pour moi jusqu'ici c'était une boucle for est de compléxité n si on imbrique une boucle dans une autre on passe a n² et ainsi de suite, en revanche si les boucle ne sont pas imbriquée cela fait 2n...

Ce n'est pas parce qu'il y a une condition de sortie de la forme "indice < n" qu'on va passer n fois dans la boucle. Il faut aussi regarder ce qu'on fait de l'indice : sa valeur initiale, son évolution... L'indice est-il également modifié à l'intérieur de la boucle ? Peut-on sortir de la boucle sans respecter la condition de sortie (avec un break) ? etc

[baobab95]

ok je comprend deja un peu mieux...

Mais lorsqu'une boucle fais
for (int i =0; i < n; i+=3)

elle est de complexité O(n)...
C'est parcequ'on considére qu'on fais environ n fois la chose ?
Enfaite on est dans le cas log(n) que lorsqu'on s'éloigne assez des "environs n fois"
comme par exemple dans le cas d'une multiplication ou d'une division.

Cela est correct ??

[michel.di]

dis que j'explique mal! :p
oui la dans ce cas tu seras en O(n)
Pour ce qui est du log tu seras dans ce cas la quand tu as quelque chose tu genre i*= n n étant un entier quelconque >1 et que i est croissant ou que tu as i/= n , i étant décroissant

[michel.di]

Mais lorsqu'une boucle fais
for (int i =0; i < n; i+=3)

elle est de complexité n car tu as n/3 itérations soit 1/3 n et dans ce cas tu es en O(n) car tu as une constante multiplicative


Définition
On dit que g(n) est un majorant asymptotique pour f (n) et
l'on écrit f (n) € O(g(n)) s'il existe une constante strictement
positive c telle que pour n assez grand on ait
0 <= f (n) <= c.g(n)
Ceci revient à dire que f (n) est inférieure à g(n) à une
constante multiplicative près et pour n assez grand.

J'espère que ça t'aide

[baobab95]

non justement je dis que je comprends mieux ^_^ !!
ok donc complexité je commence vraiment à y voir clair !
je suis en train de refaire le qcm (avec son corrigé) le seul probleme c'est que ya pa d'explication avec les réponses ... :/

du coup j'ai d'autre question..je suis désolé mais j'ai pas beaucoup de temps pour reviser, les rattrapages arrivent vite, alors vu que j'ai des gens doués j'en profite (tu voi je t'envoi même des compliments !!)

question 34)
Soit la classe : class A {public int i;} Le code suivant A a = new a(); Object o=a; o.i=10;

a) c'est correct et peut etre compilé et exécuté
b) c'est incorrect

(je précise que je recopie les question telles qu'elles le sont posées, c'est pour vous dire la joie que c'est de lire un bout de code écrit comme ca en exam...)

[michel.di]

la je dois partir mais je te répond dans la soirée ou demain!
bon courage pour tes révisions, va falloir que je m'y mette aussi!
bonne soirée

[baobab95]

ok merci beaucoup !
jveux pas faire le chieur mais mon exam est lundi, donc si ta 5 minutes ce soir :p

Merci pour tout en tout cas, la ca va j'arrive a faire les question sur la complexité sans me tromper !!

[Astartee]

Pour la compléter les indications de michel.di concernant les calculs de complexité : il faut comprendre le O(...) comme signifiant "de l'ordre de ... lorsque n tend vers l'infini".
Par exemple : 3n²+50n+10000000 = O(n²). En effet, lorsque n est très grand, c'est le terme en n² qui prédomine.
Et on ne prend pas en compte les constantes multiplicatives. Faire passer la complexité d'un algorithme de 2*n à n, c'est certes appréciable car on divise les temps de calculs par 2, mais ce n'est rien par rapport à le faire passer à une complexité en log(n).
Ensuite il existe bien sûr une définition mathématique à la notation O(...), mais si tu as compris ce qui est au-dessus ça te suffira largement.

Soit la classe : class A {public int i;} Le code suivant A a = new a(); Object o=a; o.i=10;
a) c'est correct et peut etre compilé et exécuté
b) c'est incorrect

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
class A {
   public int i;
}

Définition d'une classe A contenant un champ de type int, pas de problème.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

A a = new a();

On n'a pas défini de constructeur dans A, mais on peut quand même utiliser le constructeur par défaut sans argument...
(enfin, je crois... je n'ai rien sous la main pour vérifier, là)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Object o=a;

Toute classe hérite de la classe Object donc pas de problème pour cette instruction.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

o.i=10;

Et c'est là que ça bloque !
La variable o contient un Object. Alors certes, il se trouve qu'en l'occurence il s'agit d'une instance de A, mais le compilateur ne peut pas le deviner, il connaît la variable o comme un Object, un point c'est tout. Et un Object ne possède pas de champ nommé i. Ça ne compilera pas.

[michel.di]

Astartee je te confirme qu'il n'y a pas besoin de constructeur!

[baobab95]

D'accord, alors déjà pour la complexité merci je pense avoir compris, j'arrive à répondre à la plupart des question, merci beaucoup !!

ensuite, pour la classe object je vais devoir me documenter....
lorsqu'on fais ((A)o).i = 10. Cela devient correct compilable et exécutable !!

Ya des choses pas très claires dans ma tête encore ! :p
mais je vais trouver des ressources sur le net c'est sur !

l'exam c'est demain ^_^

Merci pour tout !

[michel.di]

oui car tu cast l'objet dans le bon type et dans ce cas tu peux appliquer toutes les méthodes de A!

[baobab95]

haaa d'accord ca revient au même que de faire (int)1,5 par exemple !! j'avais pas pensé à ça !!