Dom 18 Agosto, 06:49:58 - 2019

Autore Topic: Testo esame 7 Febbraio 2011  (Letto 7349 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline psyko

  • Ricercatore
  • ****
  • Post: 285
  • FeedBack: +13/-9
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #15 il: Mer 09 Febbraio, 12:27:58 - 2011 »
Ma che senso ha fare gli homework per poi trovarsi all'esame(io non l'ho fatto questo appello) 6 domande su 9 in cui bisogna scrivere codice... bha

Offline gengio5

  • Studente di Dottorato
  • ***
  • Post: 133
  • FeedBack: +9/-6
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #16 il: Mer 09 Febbraio, 16:02:24 - 2011 »


Ho un dubbio sulla prima domanda del test: O(n log n) è sicuramente...

Io pensavo a Omega(n)

Offline devilman

  • Studente di Dottorato
  • ***
  • Post: 171
  • FeedBack: +6/-8
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #17 il: Mer 09 Febbraio, 16:13:05 - 2011 »

Ho un dubbio sulla prima domanda del test: O(n log n) è sicuramente...

Io pensavo a Omega(n)

la risposta esatta è O(n2) se non sbaglio. se ti fai i grafici delle funzioni nlogn, n e n2 capiscio subito che è la risposta giusta è O(n2) :)
Io sono il demone nato per eliminare voi tutti dalla faccia della Terra. Io sono DEVILMAN!

Offline gengio5

  • Studente di Dottorato
  • ***
  • Post: 133
  • FeedBack: +9/-6
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #18 il: Mer 09 Febbraio, 16:36:58 - 2011 »
la risposta esatta è O(n2) se non sbaglio. se ti fai i grafici delle funzioni nlogn, n e n2 capiscio subito che è la risposta giusta è O(n2) :)

Sì ma in questo caso potrebbe anche essere O(n^3) oppure O(n^100).O sto dicendo una fesseria  :asd:

Offline Wash_88

  • Studente di Dottorato
  • ***
  • Post: 239
  • FeedBack: +27/-3
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #19 il: Mer 09 Febbraio, 17:36:58 - 2011 »
La risposta corretta è O(n2).

Sì ma in questo caso potrebbe anche essere O(n^3) oppure O(n^100).O sto dicendo una fesseria  :asd:

Si, potrebbe essere anche O(n3) o O(n100) ma ciò non toglie che O(nlogn) sia sicuramente O(n2).
« Si dice che il minimo battito d’ali di una farfalla sia in grado di provocare un uragano dall’altra parte del mondo »

Offline RinceWind

  • Neo-Laureato
  • **
  • Post: 73
  • FeedBack: +18/-19
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #20 il: Mer 09 Febbraio, 18:11:43 - 2011 »
Mi accodo. Può sembrare strano ma nlog è una funzione che, per n grande, cresce leggermente di più di quella lineare, molto meno di quella quadratica. In generale si possono ordinare le funzioni di uso comune nel verso delle velocità crescenti.
Dalla meno veloce alla più veloce:

1, logn, n, nlogn, n2, n3, 2n.

Tuttavia mi sentirei di dire che nlog è Omega(n). La definizione di Omega-grande recita: se f(n) = Omega(g(n)) allora a partire da un certo indice f(n) cresce asintoticamente come e più di g(n).
« Ultima modifica: Mer 09 Febbraio, 18:22:10 - 2011 da RinceWind »

Offline Gc24

  • Direttore di Dipartimento
  • ***
  • Post: 1637
  • FeedBack: +112/-34
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #21 il: Mer 09 Febbraio, 19:00:05 - 2011 »
Mi accodo. Può sembrare strano ma nlog è una funzione che, per n grande, cresce leggermente di più di quella lineare, molto meno di quella quadratica. In generale si possono ordinare le funzioni di uso comune nel verso delle velocità crescenti.
Dalla meno veloce alla più veloce:

1, logn, n, nlogn, n2, n3, 2n.

Tuttavia mi sentirei di dire che nlog è Omega(n). La definizione di Omega-grande recita: se f(n) = Omega(g(n)) allora a partire da un certo indice f(n) cresce asintoticamente come e più di g(n).
mi spiace contraddirti rince, ma ste domande (abbastanza meschine a mio avviso) devono essere interpretate diversamente.
1. Un algoritmo O(n logn) è sicuramente...

    * O(n)
    * Omega(n^2)
    * Omega(n)
    * O(n2)

Tu sai che l'algoritmo è O(nlogn) quindi ha upper bound nlogn e quindi SICURAMENTE ha upper bound O(n^2), cioè sei CERTO che nessun algoritmo superi n^2 (infatti non supera nemmeno nlogn)

mentre per il discorso dell'omega, l'omega è un lower bound, quindi se sai che ha un upper bound O(nlogn) non sai nulla sul lower bound, può essere tanto omega(n) che omega(logn)

la tua interpretazione non è errata, ma per il testo della domanda non è esatta la tua risposta in quanto sul lower bound non possiamo dire nulla con certezza


invece nella domanda 3, "un algoritmo che ha lower bound n^2...." le parti sono invertite, non possiamo dire nulla con certezza su algoritmi che superano n^2 (visto che la domanda non ci da l'upper bound) quindi l'unica cosa deducibile con certezza è che, avendo un lower bound n^2, nessun algoritmo lo risolve in O(n) altrimenti sarebbe stato omega(n) e non omega(n^2)
((to.be())||(!to.be()))

Offline RinceWind

  • Neo-Laureato
  • **
  • Post: 73
  • FeedBack: +18/-19
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #22 il: Mer 09 Febbraio, 19:05:23 - 2011 »
Azz... ai tempi miei mica era così difficile!  :asd:

Offline Gc24

  • Direttore di Dipartimento
  • ***
  • Post: 1637
  • FeedBack: +112/-34
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #23 il: Mer 09 Febbraio, 19:17:01 - 2011 »
la cosa forte è che credo tutti noi conoscano bene i concetti di upper e lower bound, ma complicarsi con questi ragionamenti contorti...:S anche perchè CONCETTUALMENTE non sono tutte errate (vedi caso di prima...)
((to.be())||(!to.be()))

Offline gengio5

  • Studente di Dottorato
  • ***
  • Post: 133
  • FeedBack: +9/-6
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #24 il: Mer 09 Febbraio, 19:36:11 - 2011 »

E meno male che questo test doveva essere facile  :asd: Avevo preso una toppa colossale!

Invece la risposta alla 7 qual è?

Offline RinceWind

  • Neo-Laureato
  • **
  • Post: 73
  • FeedBack: +18/-19
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #25 il: Mer 09 Febbraio, 19:37:48 - 2011 »
Ho capito il discorso gc: in pratica non abbiamo alcuna informazione in merito al lower bound dell'algoritmo, è così? Difatti la notazione O-grande indica un upper bound, un tetto che non si può superare... mentre, matematicamente parlando, potremmo scendere a piacere. Eh, mi sembrano tanto i quiz che affrontai per ricerca operativa - cambiano una virgola e ti fregano.

Offline RinceWind

  • Neo-Laureato
  • **
  • Post: 73
  • FeedBack: +18/-19
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #26 il: Mer 09 Febbraio, 19:50:56 - 2011 »
E meno male che questo test doveva essere facile  :asd: Avevo preso una toppa colossale!

Invece la risposta alla 7 qual è?

Uhm... ci ho pensato un po' su. Propendo per la quarta risposta, ma non ne sono sicuro. In pratica a(x) si trova in input la funzione b(x)... se ci metto o(fB(|X|)) a risolvere b(x) ci metterò poi o(fA (|Y|)) a risolvere l'input prodotto da b(x) (di lunghezza Y). Quindi somma dei tempi. Attendo conferma.
« Ultima modifica: Mer 09 Febbraio, 19:52:44 - 2011 da RinceWind »

Offline Gc24

  • Direttore di Dipartimento
  • ***
  • Post: 1637
  • FeedBack: +112/-34
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #27 il: Mer 09 Febbraio, 19:53:17 - 2011 »
boh, non lo so qual è quella corretta della 7...
stavolta penso si agiusto il tuo ragionamento, dopotutto se sostituiamo a queste barbare notazioni matematiche dei costi tipo logn o n^2 il costo è logn+n^2
((to.be())||(!to.be()))

Offline RinceWind

  • Neo-Laureato
  • **
  • Post: 73
  • FeedBack: +18/-19
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #28 il: Mer 09 Febbraio, 19:56:25 - 2011 »
Aspetta gc, mi correggo da solo. X indica il numero di bit necessari a rappresentare l'input della funzione no? Se a(x) si trova b(x) come input, quanti bit servono a rappresentare b(x)? Credo proprio |b(x)|. Allora la risposta corretta è la prima.

Offline Lorixx89

  • Professore Associato
  • *
  • Post: 641
  • FeedBack: +60/-14
    • Mostra profilo
Re: Testo esame 7 Febbraio 2011
« Risposta #29 il: Gio 10 Febbraio, 21:47:02 - 2011 »
Aspetta gc, mi correggo da solo. X indica il numero di bit necessari a rappresentare l'input della funzione no? Se a(x) si trova b(x) come input, quanti bit servono a rappresentare b(x)? Credo proprio |b(x)|. Allora la risposta corretta è la prima.

Ora non ricordo bene, ma sono sicuro al 99% che la risposta a quella domanda era la somma di due termini.