Guinan

.grande:maestro.

User info:

Registered: Aug 2003
Posts: 655 (0.08 al dì)
Location: Hogwarts
Corso: informatica
Anno: terzo
Time Online: 4 Days, 20:19:16 [...]
Status: Offline

Post actions:

Ho saputo gli argomenti della lezione di venerdì 12 e ve li posto:

Quicksort (cap. 8 del libro):
- descrizione del quicksort
- prestazioni del quicksort
- partizionamento peggiore
- partizionamento migliore
- partizionamento bilanciato
- concetti intuitivi sul caso medio
- versione randomizzata del quicksort
(fino a pag. 153)

__________________
- Long life and prosper!
- Elen sila lumen omentilmo!

Guinan

.grande:maestro.

User info:

Registered: Aug 2003
Posts: 655 (0.08 al dì)
Location: Hogwarts
Corso: informatica
Anno: terzo
Time Online: 4 Days, 20:19:16 [...]
Status: Offline

Post actions:

Argomenti della lezione del 16 novembre - martedì:

- ripasso di quicksort
- problema 8-2 pag 158: variazione dell'algoritmo di PARTITION
- problema 8-4: profondità della pila per quicksort
- problema 8-5: partizione sul mediano fra tre
(i problemi non sono da risolvere ma contengono informazioni interessanti)


Ordinamento in tempo lineare:
- Limiti inferiroi per l'ordinamento
- Il modello ad albero di decisione

__________________
- Long life and prosper!
- Elen sila lumen omentilmo!

Guinan

.grande:maestro.

User info:

Registered: Aug 2003
Posts: 655 (0.08 al dì)
Location: Hogwarts
Corso: informatica
Anno: terzo
Time Online: 4 Days, 20:19:16 [...]
Status: Offline

Post actions:

Argomenti della lezione del 18 novembre 2004 del prof. Torelli:


- Counting sort
- Radix sort
- Bucket sort
(tutto dal libro)

__________________
- Long life and prosper!
- Elen sila lumen omentilmo!

Guinan

.grande:maestro.

User info:

Registered: Aug 2003
Posts: 655 (0.08 al dì)
Location: Hogwarts
Corso: informatica
Anno: terzo
Time Online: 4 Days, 20:19:16 [...]
Status: Offline

Post actions:

Argomenti della lezione di venerdì 19 novembre:


* Mediano e selezione cap. 10
* Minimo e massimo
* Selezione con tempo medio lineare
* Selezione in tempo lineare nel caso peggiore
* Strutture dati cap. 11
- Introduzione
- Elementi di un insieme dinamico
- Operazioni su insiemi dinamici
- Riferimento al cap. 9.0 alla dispensa si Goldwurm.
* Pile e code
* Pile

__________________
- Long life and prosper!
- Elen sila lumen omentilmo!

nothingman3

User info:

Registered: Not Yet
Posts: N/A (0 al dì)
Location:
Corso:
Anno:
Time Online: [...]
Status:

Post actions:

scusate..qualcuno mi sa spiegare la differenza tra O(n) e TETA(n)..
le definizioni le ho capite..ma effettivamente si comportano allo stesso modo..e poi tra i due tempi di esecuzione è meglio O(n) o TETA(n)..? grazie

Guinan

.grande:maestro.

User info:

Registered: Aug 2003
Posts: 655 (0.08 al dì)
Location: Hogwarts
Corso: informatica
Anno: terzo
Time Online: 4 Days, 20:19:16 [...]
Status: Offline

Post actions:

...allora, vediamo se ho capito:

O(n) significa che l'esecuzione di qualcosa impiega"al più" tempo lineare e indica un limite superiore, ma non ha limite inferiore.

Theta(n) significa che l'esecuzione di qualcosa impiega "intorno" a un tempo lineare e indica un limite sia inferiore che superiore al tempo di esecuzione, quindi è decisamente meglio.
(cioè l'intervallo in cui sta il tempo di esecuzione è più ristretto)

... o no?
.. a me sembra giusto, altrimenti significa che non ho capito un beato algoritmo.....

...qualcuno mi conferma?

__________________
- Long life and prosper!
- Elen sila lumen omentilmo!

Guinan

.grande:maestro.

User info:

Registered: Aug 2003
Posts: 655 (0.08 al dì)
Location: Hogwarts
Corso: informatica
Anno: terzo
Time Online: 4 Days, 20:19:16 [...]
Status: Offline

Post actions:

..ed ora beccatevi gli argomenti di ieri sera,
martedì 23 novembre:

CAP 11 - libro:

- Le code
- Le liste concatenate
- Ricerca in una lista concatenata
- Inserimento in una lista concatenata
- Cancellazione da una lista concatenata
- Sentinelle
- Realizzazione di puntatori e oggetti
(fino a pag. 200)

__________________
- Long life and prosper!
- Elen sila lumen omentilmo!

Guinan

.grande:maestro.

User info:

Registered: Aug 2003
Posts: 655 (0.08 al dì)
Location: Hogwarts
Corso: informatica
Anno: terzo
Time Online: 4 Days, 20:19:16 [...]
Status: Offline

Post actions:

O(n) e Theta (n): nessuo si butta?
... mi è venuto il dubbio che sia esattamente il contrario!!!

dove sono i secchioni della prima fila a dx?
quelli che fanno sempre le domande al prof?

__________________
- Long life and prosper!
- Elen sila lumen omentilmo!

mattcobain

I am my own parasite

User info:

Registered: Oct 2003
Posts: 1033 (0.13 al dì)
Location: Periferia sud-ovest
Corso: Informatica Magistrale
Anno: Fuori corso
Time Online: 13 Days, 19:47:00: [...]
Status: Offline

Post actions:

per quanto riguarda la storia O(n) Theta(n) anchio penso come guinan....a meno che anchio non abbia capito un beato algoritmo!
per i vispi colleghi della prima fila a destra....mah!?!? secondo me sono troppo avanti per usare dsy
fila sinistra forever!!!!

eragon_81

User info:

Registered: Oct 2004
Posts: 16 (0.00 al dì)
Location: Milano
Corso: Informatica
Anno: 3
Time Online: 6:21:36 [...]
Status: Offline

Post actions:

Ciao a tutti,

forse sono un po' OT ma non sapevo dove postare questa cosa.
Volevo far sapere che oggi ho comprato il libro del corso in copisteria (pieffecopy) ed era l'ultima copia. Quindi non andate in copisteria a comprarlo, ma procuratevi un originale da qualche compagno e fotocopiatelo.
So che probabilmente a quest'ora il libro ce l'avranno tutti, ma la ragazza della pieffecopy ha insistito perchè postassi questa news.

Regards,
eragon

elpampero

Aniversario

User info:

Registered: Sep 2003
Posts: 911 (0.12 al dì)
Location: Milano
Corso: Informatica Magistrale
Anno: I
Time Online: 8 Days, 3:06:36 [...]
Status: Offline

Post actions:

Per Guinan:
la spiegazione dell' O grande e del theta che hai dato va più che bene.
Infatti O(n) significa che una funzione può crescere al max come n mentre il theta indica che una funzione è praticamente come n.

Avrei una domanda:
Il prof ha detto se chiederà all'esame tutta la pappardella su fibonacci e la dimostrazione per arrivare alla formula di Eulero?

Guinan

.grande:maestro.

User info:

Registered: Aug 2003
Posts: 655 (0.08 al dì)
Location: Hogwarts
Corso: informatica
Anno: terzo
Time Online: 4 Days, 20:19:16 [...]
Status: Offline

Post actions:

Il prof. ha detto che non chiede le dimostrazioni matematiche (almeno lo spero, sennò sono nei guai)

Ti conviene comunque guardare nei filez dove sono postate una serie di domande-tipo che fa all'esame (in effetti non ci sono domande di tipo matematico)

__________________
- Long life and prosper!
- Elen sila lumen omentilmo!

elpampero

Aniversario

User info:

Registered: Sep 2003
Posts: 911 (0.12 al dì)
Location: Milano
Corso: Informatica Magistrale
Anno: I
Time Online: 8 Days, 3:06:36 [...]
Status: Offline

Post actions:

Infatti..mi serviva per conferma. Anche nelle lezioni dell'anno scorso diceva la stessa cosa...
Grazie mille

Guinan

.grande:maestro.

User info:

Registered: Aug 2003
Posts: 655 (0.08 al dì)
Location: Hogwarts
Corso: informatica
Anno: terzo
Time Online: 4 Days, 20:19:16 [...]
Status: Offline

Post actions:

Martedì 30 novembre, causa sciopero generale, la lezione di Algoritmi del prof. Torelli (turno 2) non avrà luogo.


Vi metto anche gli argomenti della lezione di ieri, giovedì 25:

Dagli appunti del prof: "Grafi e alberi":
- 2.5: Quanta memoria occorre per descrivere un albero?

Dal libro (da pag 201 a pag 205)
- 11.4: Rappresentazione di alberi radicati

__________________
- Long life and prosper!
- Elen sila lumen omentilmo!

Guinan

.grande:maestro.

User info:

Registered: Aug 2003
Posts: 655 (0.08 al dì)
Location: Hogwarts
Corso: informatica
Anno: terzo
Time Online: 4 Days, 20:19:16 [...]
Status: Offline

Post actions:

Argomenti della lezione di venerdì 26 novembre 2004:

Cap. 12 (libro): le tabelle hash
- tabelle ad indirizzamento diretto
- tabelle hash
- Il metodo di divisione
- il metodo di moltiplicazione
(fino a pag. 216)

NON faremo il cap. 12.3.3 sulle funzioni hash universali.

Vi ricordo che martedì 30 la lezione è sospesa causa sciopero generale.

__________________
- Long life and prosper!
- Elen sila lumen omentilmo!