[C] - Algoritmi e strutture dati

[LOVE85]

Salve vorrei vedere se ho capito che cosa devo fare dato questo testo:

Ogni consegna deve essere composta da un unico archivio compresso contente:

* Un file contenente i nomi dei componenti del gruppo.
* Codice sorgente (in c standard) con relativo makefile. Il codice dovrà fornire il tempo di esecuzione dell'algoritmo (utilizzare la funzione di libreria clock).
* Documentazione contenente la descrizione dell'implementazione, il costo computazionale, risultati sperimentali, e tutto ciò che ritenete opportuno (lunghezza massima 5 pagine). Nella relazione dovete indicare l'algoritmo con cui volete partecipare alla competizione.


Primo Progetto.

* Selection randomizzata
* Selection lineare (deterministica) nel caso pessimo (versione ricorsiva)
* Selection lineare (deterministica) nel caso pessimo (versione iterativa)

Per selection randomizatta si intende creare un algoritmo come il selection sort di una sequenza in questo caso generata casualmente vero?

E che si intende per selection lineare deterministiche nei due casi pessimi?
C'è qualcuno che è bravo e potrebbe darmi una mano o meglio una spiegazione?

Grazie

Cris & Stefy

Ciao Ciao

[Ziosilvio]

* Selection randomizzata
* Selection lineare (deterministica) nel caso pessimo (versione ricorsiva)
* Selection lineare (deterministica) nel caso pessimo (versione iterativa)

Per selection randomizatta si intende creare un algoritmo come il selection sort di una sequenza in questo caso generata casualmente vero?

E che si intende per selection lineare deterministiche nei due casi pessimi?
Si intendono alcuni algoritmi classici di selezione di un elemento all'interno di un vettore, che sono stati quasi certamente spiegati a lezione e si trovano senza dubbio sul vostro libro di testo.

[LOVE85]

.....non credo che si trovi perchè volevo capire se bisognava fare un algoritmo selection sort in c e poi implementare la funzione che genera la random. E' su qusto che mi sono impuntanto. Grazie..:muro: :muro:

[Qwertid]

Prova a consultare il libro

"Cormen, Rivest, Stein" - Introduzione agli algoritmi e alle strutture dati.

Lì dovresti trovare molte risposte :) Ciao!

Comunque la randomizzata è un caso a parte dai miei ricordi e non implica numeri generati casualmente

[Sick Boy]

Il codice dovrà fornire il tempo di esecuzione dell'algoritmo (utilizzare la funzione di libreria clock).

scusate l'intromissione, ma la funzione di libreria clock calcola il tempo di esecuzione di un algoritmo in modo preciso?

perchè a me servirebbe di sapere se c'è qualche modo di calcolare il tempo di esecuzione anche di una sola porzione di codice.

[Ziosilvio]

(Sul mio libro di testo) non credo che si trovi
Ti sei reso conto di aver appena detto di non sapere cosa c'è nel tuo libro di testo?
volevo capire se bisognava fare un algoritmo selection sort in c e poi implementare la funzione che genera la random. E' su qusto che mi sono impuntanto.
La selezione randomizzata è un algoritmo di selezione, e non di ordinamento.
Devi scegliere il j-esimo elemento più piccolo di un vettore; ma non sai se il vettore è ordinato o no.
Allora, o ordini il vettore (in tempo O(n log n) se usi Quicksort) e poi prendi il j-esimo elemento; oppure fai una serie di chiamate "furbe" alla sola funzione di partizionamento del Quicksort (scegli il pivot, metti tutti gli elementi minori o uguali al pivot a sinistra e quelli maggiori del pivot a destra) scegliendo il pivot ogni volta a caso, il tutto in tempo medio O(n).

Su questi argomenti trovi qualche dispensa QUI (http://www.cs.utexas.edu/~vlr/s06.357/notes/), sono gli appunti di un corso simile all'Università del Texas (http://www.cs.utexas.edu/~vlr/s06.357/notes/).
Sulla generazione di sequenze pseudorandom c'è un mio tutorial nella sottosezione "Corsi, tutorial e FAQ": dovrei aggiornarlo, ma può darsi che basti per quello che devi fare tu.

[LOVE85]

Salve abbiamo implementato questo. Potreste controllare? Grazie. Ciao Ciao
Se devo aggiungere o cambiare qualcosa fatemi sapere.
Perchè noi abbimao provato a far quest'algoritmo. Prò c'è un problema come mai il tempo in secondi viene troppo grosso? Guardate il file!!!! Grazie!!!

[LOVE85]

-DA CANCELLARE-

[Ziosilvio]

Sono disponibile online adesso per cui basta che copiate ciò nel vostro msn et voilà mi vedrete grazie.
Mettere in chiaro il proprio contatto MSN, la propria email ecc. su un forum pubblico non mi sembra la cosa più prudente del mondo...

... però, se ricordo bene, puoi inserirlo nel profilo utente su Hardware Upgrade, e dovrebbe comparire l'iconcina di MSN sotto il tuo nome, in modo che chi vuole contattarti lì possa farlo.

[LOVE85]

Ecco sistemato il messaggio precedente. Ma adesso però sarà possibile che ci mette così poco il tempo di esec su questo nuovo file?? Grazie.
Inserito un nuovo file.

[LOVE85]

???????????????????????????????????????????? allora?