.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [Algoritmi - Goldwurm] Diario del Corso 2004/05 (http://www.dsy.it/forum/showthread.php?threadid=13819)

[Algoritmi - Goldwurm] corso 2004/05

Vedo che per l'altro turno di algoritmi i ragazzi si sono organizzati si scambiano, appunti, opinioni.... Noi invece del turno di Goldwurm siamo un po' in sordina... che ne dite di tenere un diario del corso, scambiarci appunti eventualmente? ( I miei sono scritti in maniera pessima, ma se qualcuno è interessato posso copiarli). Nessun problema invece per il diario del corso.

Intervento del moderatore:
Se vuoi puoi fare il newser di questo corso... qui c'è il link all'annuncio, facci sapere

__________________
"Voi che tingete i mari del colore dello zinco, che tramutate i boschi in gialli deserti, i venti in fumi di polveri da sparo e che bruciate i cieli. Voi che volete ripetere i malvagi atti della sconsiderata Lilith, che fu la prima moglie di Adamo e poi la sposa del Diavolo. Voi che volete ripetere la ribellione scatenata da Lucifero, del mondo celeste il più splendente. Voi! Ascoltate l'afflizione della sottospecie alata che vola alta nel cielo." [Angel Sanctuary]
::: mail: yoruno@dsy.it ::: ::: My Site ::: ::: Dsy Photo Gallery ::: ::: DeviantART Gallery :::

Ciao, c'è qualcuno che puo dirmi se per il corso ci sarà un compitino oppure ci sarà solo l'esame finale con il progetto ? Se sì, come sara strutturato? potrò seguire solo dalla prossima settimana e mi sono perso queste prime lezioni....

Ci dovrebbero essere due compitini, uno a inizio novembre l'altro a fine dicembre o a fine gennaio... Inoltre bisognerà comunque sostenere un orale. Di più al momento non si sa.

sto cercando il libro di algoritmi "INTRODUZIONE AGLI ALGORITMI" della JACKSON, sikkome è uscito fuori produzione, konoscete qalk1 disposto a vendermelo ??? grazie PLEASE

Intervento del moderatore:
Chiedi nel mercatino, è fatto apposta per questo

__________________
"Voi che tingete i mari del colore dello zinco, che tramutate i boschi in gialli deserti, i venti in fumi di polveri da sparo e che bruciate i cieli. Voi che volete ripetere i malvagi atti della sconsiderata Lilith, che fu la prima moglie di Adamo e poi la sposa del Diavolo. Voi che volete ripetere la ribellione scatenata da Lucifero, del mondo celeste il più splendente. Voi! Ascoltate l'afflizione della sottospecie alata che vola alta nel cielo." [Angel Sanctuary]
::: mail: yoruno@dsy.it ::: ::: My Site ::: ::: Dsy Photo Gallery ::: ::: DeviantART Gallery :::

DIARIO DEL CORSO 5-10-2004

Oggi il professore ha parlato delal notazione asintotica e ordini di grandezza, utili soprattutto per giudicare la complessità di un algoritmo.

Abbiamo esaminato

1) equivalenza asintotica ~
quando il quoziente tra due funzioni tende definitivamente (cioè oltre un certo n) a 1.

2) L'O grande.
una f(n) è O(g(n)) se esiste un c>0 tale che f(n) è minore o uguale di c per g(n) per ogni n maggiore di una soglia n con zero.

3) Il teta maiuscolo, uguale ordine di grandezza. Una f(n) è teta di g(n) cioè ha lo stesso ordine di grandezza se esistono c1 e c2 tali che c1f(n)< g(n) <c2f(n)

4) o piccolo, o infinitesimo di ordine superiore.
f(n) è o piccolo di g(n) se il loro rapporto tende a zero.

5) Omega grande, praticamente f(n) è omega grande di g(n) se esiste c>0 tale che f(n)è maggiore di c per g(n).

6) omega piccolo. f(n) è omega piccolo di g(n) se il loro rapporto tende a infinito.

Inoltre abbiamo fatto esercizi su queste proprieta, e alla fine abbiamo risolto l'esercizio dato l'altra volta del programma per trovare il massimo di n interi a caso scritto con linguaggio RAM, e abbiamo calcolato T e S di questo programma.

Spero di riuscire a trascrivere e postare gli appunti in grafia decente presto, così magari li posto in area files.

Grazie dei chiarimenti e Grandissimo fdecollibus per tutto ciò che riguarda gli appunti e le lezioni. CIAOZ

qual è il giorno delle lezioni di laboratorio?

Il giovedì pomeriggio....ma nn credo ci siano per un po.

Qualcuno sa dirmi cosa ha fatto venerdì scorso a lezione il profe?

Ciao,

volevo chiedervi le modalità dell' esame del prof:

- 2 compitini ....

LEZIONE DI VENERDI' 1 OTTOBRE

argomento della lezione è il modello RAM (random access machine)
si tratta di una macchina composta da 2 nastri input tape (read only) e output tape (write only), un local counter, un programma e una memoria formata da n registri. il primo registro R0 è di calcolo.

i nastri sono divisi in celle, la testina è posizionata sulla prima cella e shifta a dx ad ogni lettura/scrittura. gli input del programma stanno nelle prime n celle, le altre sono BLANK

SINTASSI
esistono 5 tipi di istruzioni per il linguaggio ram:
-I/O
-aritmetiche
-trasferimento dati
-controllo (aggiornamento LC)
-arresto HALT

ogni istruzione (tranne halt) è composta da un codice e un operando (op o Label)

op può assimere valore
-immediato: =i
-di indirizzamento diretto: i (valore contenuto nel registro Ri)
-di indirizzamento indiretto: *i (valore contenuto nel registro Rk dove k è il valore contenuto in Ri)

ELENCO DELLE ISTRUZIONI

I/O
   -READ op   trasferisce il valore dell'input tape in op (che può essere i o *i)
   -WRITE op   stampa op (=i, i o *i) sull'output tape

ARITMETICHE
   -ADD op   (R0 = R0 + op)
   -SUB op   (R0 = R0 - op)
   -MULT op   (R0 = R0 * op)
   -DIV op   (R0 = R0 / op)
(in tutti questi casi op può essere =i, i o *i)
    esempio pratico:
ADD =5    R0 = R0 + 5
ADD 5    R0 = R0 + R5
ADD *5    R0 = R0 + R<valore contenuto in R5>

TRASFERIMENTO
   -LOAD op R0=op (op può essere =i, i o *i)
   -STORE op op=R0 (op può essere i o *i)

CONTROLLO
   -JUMP Label   salto incondizionato
   -JZERO Label   jump if R0==0
   -JGTZ Label   jump if R0>0
   -JBLANK Label   jump if input tape==blank

esempio di algoritmo: leggi una sequenza di numeri
        LOAD =2 //R0=2
        STORE 1 //R1=R0 (=2)
leggi READ *1 //R<contenuto di R1>=input corrente
        LOAD 1 //R0=R1
        ADD =1 //R0++
        STORE 1 //R1=R0
        JBLANK end
        JUMP leggi
end   HALT



SEMANTICA
si definisce stato la configurazionedi una macchina RAM durante il calcolo

S:{r,w,lc,0,1,...,k}
dove
r=indice read
w=indice write
lc=indice contatore
0,1,...k=indici registri

stato iniziale: S0(r)=S0(w)=S0(lc)=1 S0(k)=0 per tutti i k
stato prossimo:ogni stato definisce al + uno stato successivo, funzione dello stato corrente e dell'istruzione corrente

si definisce computazione una serie di stati in cui S'=f(S,input) che si conclude con uno stato d'arresto

Originally posted by superfabius
qual è il giorno delle lezioni di laboratorio?

Originally posted by Polsy
scicchissimo il tuo avatar!

Originally posted by superfabius
gvazie gvazie cavo

Originally posted by Polsy
LEZIONE DI VENERDI' 1 OTTOBRE

Ciao,

volevo chiedervi le modalità dell' esame del prof:

- 2 compitini ....+ orale + progetto?????

2 compitini si (per chi segue)
orale si
progetto nn si sa....con sta storia che le lezioni di laboratorio nn ci sono....

DIARIO DEL CORSO 7-10-2004

Ancora su sintassi e sematnica della macchina RAM. Calcolo come sequenza di stati di una macchina, dove stato. Calcolabilità, la funzione PSI , definita su programma P e sequenza di interi x, come vettore dei valori stampanti durante l'esecuzione, o indefinito nel caso in cui il programma non si fermi. Misurazione della complessità di un programma RAM: il criterio uniforme.

P.S. domani non ci sarò e non potrò aggiornare questo thread... se qualcuno altro può farlo.....

http://homes.dsi.unimi.it/~aguzzoli/algo.htm

leggete l'avviso in rosso

__________________
Il DSY su Facebook!!!

Originally posted by superfabius
qual è il giorno delle lezioni di laboratorio?

Originally posted by Lunik
http://homes.dsi.unimi.it/~aguzzoli/algo.htm

leggete l'avviso in rosso

ragazzi io non c'ero venerdì, qualcuno può aggiornare il diario del corso!

DIARIO DEL CORSO 8-10-2004

tesi di Church
complessità di un programma RAM: il criterio logaritmico
analisi logaritmica di un algoritmo
formula di Stirling

purtroppo non ho potuto fare un riassunto dettagliato come quello dell'altra volta, è che ci sono un bel po' di formule matematiche che non riesco a scrivere qua....magari se recupero uno scanner prima o poi posto gli appunti direttamente...

Originally posted by Lunik
http://homes.dsi.unimi.it/~aguzzoli/algo.htm

leggete l'avviso in rosso

che il prof ha deciso di sospendere le lezioni per protesta contro la riforma moratti
giusto lunik?

Originally posted by superfabius
che il prof ha deciso di sospendere le lezioni per protesta contro la riforma moratti
giusto lunik?

__________________
Il DSY su Facebook!!!

a lezione il prof ha detto qualcosa riguardo alle esercitazioni?!

AVVISO
venerdì 15 ottobre non ci sarà lezione

Originally posted by Polsy
AVVISO
venerdì 15 ottobre non ci sarà lezione

DIARIO DEL CORSO 12-10-2004

Linguaggio di alto livello AG. Ripasso di strutture già viste in Programmazione (sic dicit magister) come assegnazione di variabile, if then else, while, begin, repeat. Procedure, passaggio parametri.

Strutture dati elementari, presentazione. Definizione, derivazione di strutture dati. Il vettore

Originally posted by superfabius
e giovedi' 14?!

ho trovato lo scanner!!

scansione degli appunti

Originally posted by Polsy
ho trovato lo scanner!!

scansione degli appunti

Originally posted by fdecollibus
Che gran donna amici, che gran donna! Dobbiamo ringraziarla tutti quanti, e quando dico tutti quanti intendo tutti quanti!

GRAZIE POLSY!!!

DIARIO DEL CORSO 14-10-2004

Ancora sulle strutture dati. Vettori, Liste, operazioni elementari su Vettori e Liste.

AVVISO
gio 21/10 -> lezione normale + lezione di laboratorio con Goldwurm (13.30-16-30)
ven 22/10 ->anche se c'è sciopero la lezione si fa lo stesso dalle 14.30 alle 17
mar 26/10 ->lezione sospesa
gio 28/10 ->lezione normale + laboratorio al pomeriggio (sempre con Goldwurm)

DIARIO DEL CORSO 19/10/2004
Argomento della lezione: Liste
riassunto della puntata precedente
alcune operazioni in più sulle liste
implementazioni delle liste:
-tabelle
-liste concatenate
-coppie di vettori
definizione di puntatore

a breve gli appunti nell'area filez

Ma da quello che ho capito io le prossime lezioni del giovedì pomeriggio nn saranno di laboratorio ma solo il recupero delle lezioni perse venerdì scorso e martedì prossimo, giusto?

Originally posted by tata1283
Ma da quello che ho capito io le prossime lezioni del giovedì pomeriggio nn saranno di laboratorio ma solo il recupero delle lezioni perse venerdì scorso e martedì prossimo, giusto?

Originally posted by Polsy
in effetti non lo so...sono arrivata in ritardo stamattina e ho copiato quegli avvisi dalla lavagna....avevo dato per scontato ke fosse laboratorio dagli orari, x cui mi sa ke hai ragione tu

infatti questo pomeriggio ha fatto teoria...

DIARIO DEL CORSO 21/10/2004

STRUTTURE DATI
---pile---
implementazioni:
-tabella
-liste concatenate
---code---
implementazioni:
-vettore

esercizi sulle strutture dati: simulazione di una pila mediante 2 code, gestione di strutture complesse (pile di code, ...) con calcolo (uniforme e logaritmico) dell'algoritmo
elenco delle sommatorie che troveremo spesso nel calcolo logaritmico di un algoritmo (le spiegherà per bene nei prossimi giorni), approssimazione di una sommatoria con un integrale (cap 2 della sua dispensa)

AVVISO
martedì 26 dalle 10.30 alle 12.30 c'è laboratorio con aguzzoli
da giovedì prossimo (28) riprende regolarmente il corso di laboratorio dalle 13.30 alle 16.30 con aguzzoli


DIARIO DEL CORSO 22-10-2004
Strutture dati: GRAFI

--Grafi Orientati--
definizioni di: lato, cappio, cammino, cammino semplice, lunghezza, componente fortemente connessa
relazioni di: raggiungibilità, connessione
IMPLEMENTAZIONI:
-matrice di adiacenza
-liste di adiacenza
-coppie di vettori

--Grafi Non Orientati--
definizioni di:cammino, componente connessa, grafo connesso, cricca (o clicca), insieme indipendente, albero, foresta, sottografo, albero di copertura
IMPLEMENTAZIONI:
-matrice di adiacenza
-liste di adiacenza
-coppie di vettori

ho chiesto al prof notizie del primo compitino, ha detto che non ha ancora deciso la data ma sarà entro il 10 novembre

Originally posted by Polsy



ho chiesto al prof notizie del primo compitino, ha detto che non ha ancora deciso la data ma sarà entro il 10 novembre

Originally posted by superfabius
ma l'orale se passi i compitini è obbligatorio?

DIARIO DEL CORSO 20-10-2004
Laboratorio con Aguzzoli

precisazioni sul corso: l'esame di laboratorio consisterà in un progetto (da consegnare dopo 2-3 settimane dalla pubblicazione) e in un colloquio orale il cui il prof NON FARA' DOMANDE DI TEORIA ma solo una discussione sul progetto e sulla scelta delle strutture utilizzate per impelmentarlo.
il compilatore gcc per windows lo si trova sul sito di aguzzoli o all'indirizzo www.cs.colorado.edu/~main/cs1300

argomenti della lezione:
presentazione del linguaggio C, cenni storici,caratteristiche (pregi e difetti), nascita dello standard ANSI
esempio di programma
definizioni di funzione, istruzione e direttiva al preprocessore
analisi della compilazione:
-preprocessione
-creazione di file .o (formato intermedio)
-creazione dell'eseguibile

io ho seguito fin qui perchè sono dovuta andare a lavorare ed ero in ritardo...se qualcuno ha seguito fino in fondo può completare il diario di oggi please?

ho notato che aguzzoli non dice praticamente niente in più dei suoi lucidi, quindi non penso sia il caso di postare appunti di laboratorio nell'area filez...che dite?

Originally posted by Polsy

io ho seguito fin qui perchè sono dovuta andare a lavorare ed ero in ritardo...se qualcuno ha seguito fino in fondo può completare il diario di oggi please?

ho notato che aguzzoli non dice praticamente niente in più dei suoi lucidi, quindi non penso sia il caso di postare appunti di laboratorio nell'area filez...che dite?

AVVISO IMPORTANTE
venerdì 12 novembre alle ore 14.30 in aula G21 si terrà il primo compitino di algoritmi

argomenti del compito:
modello ram
criteri di costo uniforme e logaritmico
espressioni asintotiche
valutazione di somme
strutture dati elementari
grafi/alberi e algoritmi di visita

il prof ha detto che conta di finire di spiegare tutti gli argomenti del primo compito entro il 5 novembre, x lasciarci una settimana in cui esercitarci

DIARIO DEL CORSO 29-10-2004
argomento della lezione: alberi
definizioni di: radice, padre, figlio, fratello, foglia, nodo interno, predecessore (antenato), successore (discendente), profondità, altezza, alberi bilanciati e sbilanciati
rappresentazione semplice (implementazione) di un generico albero
--ALBERI ORDINATI--
definizione
implementazione
visita pre-ordine e post-ordine
--ALBERI BINARI--
definizioni di: albero binario, figlio destro e figlio sinistro
differenza con gli alberi ordinati
implementazione
visita in ordine simmetrico
--ALBERO BINARIO COMPLETO--
definizione
calcolo della profondità e del numero dei nodi


AVVISO
oggi goldwurm ha preso le firme per l'iscrizione al primo compitino

Ero assento, non ho potuto firmare per l'iscrizione al primo
compitino.
Ci saranno altre occasioni per firmare?
Quante firme sono necessarie?

Originally posted by gboavm
Ero assento, non ho potuto firmare per l'iscrizione al primo
compitino.
Ci saranno altre occasioni per firmare?
Quante firme sono necessarie?

DIARIO DEL CORSO 2-11-2004
argomento del giorno: procedure ricorsive
-esempio1-> torre di hanoi: algoritmo per risolvere il gioco, calcolo logaritmico del tempo richiesto (=equazione di ricorsione)
-esempio2-> ricerca binaria: algoritmo di ricerca in un vettore ordinato, calcolo logaritmico del tempo

traduzione iterativa della ricorsione:
schema generale delle procedure ricorsive, implementazione di procedure ricorsive mediante pila (stack), record di attivazione di una procedura

poi ha fatto un esempio di algoritmo ma io me ne sono dovuta andare quindi non so che dipo di esempio abbia fatto...se qualcun'altro può completare il diario mi fa un favore...

da tanto ero di fretta mi sono dimenticata di chiedere per le firme del compitino e se metterà anche la ricorsione negli argomenti del compito (nell'elenco non l'ha specificata, ma credo proprio che la metta)
raga scusate ma oggi non ci sto con la testa...

le firme per il compitino le ha prese anche oggi e credo lo farà anche giovedì.

Per ultima cosa oggi ha fatto lo schema dell'algoritmo usato per evitare la ricorsione.

Originally posted by tata1283
le firme per il compitino le ha prese anche oggi e credo lo farà anche giovedì.

Per ultima cosa oggi ha fatto lo schema dell'algoritmo usato per evitare la ricorsione.

Grazie cara sei sempre la migliore

Polsy trovo molto utili i tuoi appunti che hai caricato nell'area filez. ti prego a nome di chi non riesce a seguire tutte le lezioni (in particolare le pomeridiane) di continuare nel tuo impegno

grazie

Originally posted by Polsy
DIARIO DEL CORSO 2-11-2004
argomento del giorno: procedure ricorsive
-esempio1-> torre di hanoi: algoritmo per risolvere il gioco, calcolo logaritmico del tempo richiesto (=equazione di ricorsione)
-esempio2-> ricerca binaria: algoritmo di ricerca in un vettore ordinato, calcolo logaritmico del tempo

DIARIO DEL CORSO 5-11-2004
VISITA IN PROFONDITA' DEI GRAFI
-procedura ricorsiva
    tempo di calcolo secondo il criterio uniforme
-proceduta iterativa
    simulazione del comportamento della pila durante l'esecuzione dell'algoritmo (iterativo) su un albero

il prof ha anche consigliato alcuni esercizi per prepararsi al compito:

--dai temi d'esame-- cioè qua
data       esercizi
1-4-03       1 e 2 (ps: c'è un errore nel primo, al posto di 3n*parte intera inferiore di n, c'è solo 3n)
4-2-03       3
19-12-02    1 (del tema 1)
8-2-02       2
9-1-02       2
5-12-01      2 (tema 1)
6-2-01       1 (tema 1)
12-2-00      2 (tema 2)

--dalla dispensa di teoria-- cioè qua
sezione   esercizi
2.3          1,2,3
2.4.3         tutti
5.3          1,2,3,6

--dall'eserciziario-- cioè qua
esercizi
4.1
4.2
4.3
6.2
6.3
6.4
6.6
6.7
6.8
6.9

la prossima lezione ha detto che è disponibile a correggere in classe esercizi che non ci vengono, quindi MI RACCOMANDO proponete esercizi!!!

speriamo bene!!

__________________
IL MIGLIOR TELEFILM TRA I MIGLIORI.... VOTA!!

aggiornata l'area filez (finalmente!)
chiedo venia per il vergognoso ritardo....non succederà più....promesso....

DIARIO DEL CORSO 9-10-04 (prima ora)
purtroppo ho potuto seguire solo la prima ora, in cui il prof ha corretto gli esercizi 4.1 e 4.3 dell'eserciziario

alcune precisazioni sul compito: non ci sono restrizioni sulla partecipazione al secondo compitino (cioè non serve aver totalizzato tot punti come minimo nel primo compitino....a meno ke uno non consegni proprio in bianco)
nel compito ci sarà la ricorsione, ma solo legata all'esplorazione di alberi, e cmq non chiederà il tempo di calcolo di una procedura ricorsiva.

se qualcuno ha seguito la seconda parte e vuole aggiornare il diario mi fa un favore

Nella seconda parte ha svolto un altro esercizio.
ISTANZA: -T = <V,E> albero ordinato
-per ogni v appartenente a V, L(v) è la lista ordinata dei
figli di v
SOLUZIONE: per ogni v appartenente a V, A[v] = altezza di v in T.

Praticamente dato un albero, la procedura deve creare un vettore di interi, ciascun elemento del quale rappresenta l'altezza del nodo corrispondente. Per il nodo m, A[m] è la sua altezza.
Ha scritto l'algoritmo in maniera ricorsiva e in maniera iterativa e ne ha fatto una brevissima analisi secondo il criterio uniforme...

ATTENZIONE!

Giovedi 11/9/2004 le lezioni di Goldwurm e Aguzzoli non si terrano per una riunione sul decreto Moratti.

fdecollibus

(il vice-Polsy)

DIARIO DEL CORSO 16-11-2004
ALGORITMI DI ORDINAMENTO
definizione di relazione d'ordine e di insieme ordinato
relazione d'ordine lessicografica (definizione e esempi)
relazione d'ordine di rango (o militare)
RISOLUZIONE DI PROBLEMI DI ORDINAMENTO
-algoritmo di inserimento (procedura, esempio di esecuzione e calcolo del numero di confronti al variare dell'input)
-mergesort (procedura e esempio di esecuzione)

DIARIO DEL CORSO 18-11-2004
ancora mergesort:
piccola modifica alla procedura merge dell'altra volta
simulazione di esecuzione di mergesort sul vettore (7 5 10 6 9)
ANALISI DI MERGESORT
spazio richiesto (criterio uniforme)
tempo richiesto (inteso come n° di confronti effettuati) secondo il criterio uniforme

AVVISO
il prossimo compitino sarà probabilmente il 14 gennaio
argomenti del compito: algoritmi di ordinamento, divide et impera, greedy
probabile esercizio: simulare l'esecuzione di un algoritmo su un determinato input tipo la simulazione dello stack durante l'esecuzione del mergesort (in maniera molto generale, giusto evidenziare quali sono i confronti effettuati)

Diario del corso (Aguzzoli)

• operatori aritmetici
  
• operatori di incremento e decremento
  
• operatori di assegnamento
  
• operatori di assegnamento combinati
  
• variabili e lvalue
  

• dichiarazioni di variabili
  
• inizializzazione e assegnamento
  
• il tipo char
  
• il tipo int
  
• i tipi short, long e unsigned
  
• i tipi reali float, double, long double
  
• l'operatore sizeof
  
• conversione e cast
  
• conversioni aritmetiche
  
• cast
  

Voti primo compitino

AVVISO

Il prof. ha messo fuori i voti del primo compitino:

Eccoli qui

Qualcuno mi sa spiegare il criterio dei voti?
Grazie

Credo che dovresti chiederlo direttamente al professore....

in ritardissimo...
DIARIO DEL CORSO 19-11-2004
correzione di alcuni esercizi del compitino
analisi del n° di confronti e del tempo di calcolo (uniforme) richiesto da mergesort

DIARIO DEL CORSO 23-11-2004
metodo "DIVIDE ET IMPERA"
-idea intuitiva
-algoritmo generico

casi particolari di algoritmi divide et impera
-mergesort
-ricerca binaria

altri algoritmi divide et impera famosi (solo nominati, senza spiegazione)
-algoritmo di Strassen per il calcolo del prodotto di matrici
-algoritmo per il prodotto di interi
-algoritmo per il calcolo della trasformata di Fourier

analisi dei tempi di calcolo dell'algoritmo generico divide et impera

DIARIO DEL CORSO 25/11/2004
algoritmo x trovare il massimo e il minimo tra gli elementi di un vettore:

Algoritmo semplice

• procedura
  
• spazio di memoria richiesto
  
• tempo di calcolo
  
• numero dei confronti effettuati
  

• procedura
  
• spazio di memoria richiesto
  
• tempo di calcolo
  
• numero dei confronti effettuati
  

DIARIO DEL CORSO 26-11-2004
Algoritmo generale x il prodotto di matrici
- procedura
- tempo di calcolo
Algoritmo di Strassen
- procedura
- tempo di calcolo
Algoritmo x il prodotto di interi
- procedura
- calcolo del n° di operazioni binarie richieste dall'algoritmo al variare dell'input

esercizi x casa
sezione 6.4.1 esercizi 1, 2, 4

AVVISO
martedì 30/11 non ci sarà lezione di algoritmi
venerdì 3/12 al posto della lezione di teoria ci sarà laboratorio con aguzzoli (sempre in G21)

Ciao a tutti.
ma allora lamodalità dell'esame sarà:
progetto e compito scritto e orale?? se non ho passato il primo compitino!!

Originally posted by Motomax
Ciao a tutti.
ma allora lamodalità dell'esame sarà:
progetto e compito scritto e orale?? se non ho passato il primo compitino!!

DIARIO DEL CORSO 2-12-2004
algoritmo per calcolare il valore 7^n (mod k)
- procedura tradizionale
- calcolo tempo/spazio secondo il criterio uniforme/logaritmico
- procedura divide et impera
- calcolo tempo/spazio secondo il criterio uniforme/logaritmico

esercizi x casa
es. 3 tema 1-4-03
es. 2 tema 4-2-03
es. 3 tema 11-12-03 (temi 1 e 2)
es. 2 tema 5-12-01

altro esercizio:
ISTANZA: n , a1 , a2 , ... , an (naturali >0)
|ai|=m     per ogni i=1,...,n
SOLUZIONE: p=a1*a2*...*an

a) descrivere un algoritmo iterativo x risolvere il problema
fare l'analisi dei tempi di calcolo e dello spazio di memoria richiesti secondo i 2 criteri (in funzione di n e m)

b) descrivere un algoritmo divide et impera x lo stesso problema

c) valutare tempo e spazio secondo i 2 criteri
(NOTA: nel calcolo del tempo logaritmico basta dare una valutazione O "o grande")

DIARIO DEL CORSO 9-12-04
HEAPSORT
definizione di HEAP
algoritmo di costruzione di uno heap + simulazione di esecuzione dell'algoritmo, calcolo del numero di confronti eseguiti e del tempo di calcolo
algoritmo di Heapsort + tempo di calcolo
esercizio x casa: stimare il n° di confronti eseguiti da Heapsort nel caso peggiore su input di n elementi (dovrebbe venire 2nlog(base 2)n + una quantità lineare)

DIARIO DEL CORSO 10-12-2004
QUICKSORT
-caratteristiche principali dell'algoritmo
-procedura intuitiva
-risoluzione dell'equazione di ricorrenza che determina il n° dei confronti eseguiti da quicksort nel caso peggiore
-procedura quicksort
-procedura partition (chiamata all'interno di quicksort)
-simulazione di esecuzione della procedura partition (casi limite e caso medio)

esercizio x casa: simulare l'esecuzione dell'algoritmo Heapsort sul vettore (1,3,2,5,6,7,9,4,2) mettendo in evidenza i confronti e gli scambi eseguiti

DIARIO DEL CORSO 14-12-2004
ripasso generale su quicksort
analisi del tempo di calcolo (n° di confronti) di quicksort nel caso medio


AVVISO
la lezione di venerdì 17 si terrà in aula G12

DIARIO DEL CORSO 16-12-2004
RICORSIONE TERMINALE
cenni generali
esempi:
-ricerca binaria
-versione ottimizzata di quicksort

ps: oggi sono arrivata a lezione in ritardo e non ci stavo molto con la testa, quindi se ho scritto ca**ate correggetemi

DIARIO DEL CORSO 17-12-2004
versione iterativa di quicksort
tipico esercizio divide et impera: problema del prodotto iterato (algoritmo, analisi uniforme e logaritmica del tempo e dello spazio richiesti

DIARIO DEL CORSO 21-12-2004
ALBERI DI RICERCA BINARIA
-definizione della struttura dati
-operazioni MIN, MAX, MEMBER, CERCA, INSERISCI, DELETE
-algoritmo di costruzione dell'albero, esempi di caso peggiore e caso medio (con relativi ordini di grandezza)

esercizi x casa:
1) definire l'algoritmo di ordinamento su un albero di ricerca binaria
2)definire una versione iterativa delle operazioni CERCA e INSERISCI

INFO:
2° compitino: 14-1-2005 alle 14.30 in aula G21
ultima lezione: 28-1-2005
appello (scritto) di febbraio: 8-2-2005

Ultima lezione 28/1/05 vuol dire che farà lezione solo venerdì 28 o anche il martedì e il giovedì?

le lezioni proseguono regolarmente fino al 28, quindi compresi tutti i martedì, i giovedì e i venerdì fino a quella data

Ke pakko!!
Grazie!

Allora, che si dice del esame ? beh, ne` e` ancora di tempo per studiare... ma, prima si fa una bella dormita durante il natale, xche` per il capodanno si deve festeggggiare, o no ?
Grazie per il vostro aiuto (a postare tutto quello che e` successo alle lezioni) Buon Feste raga!

__________________
I`m Not Trying To Predict The Future, I Only Want To Prevent It!

a proposito... qualcuno ha idea di quando Aguzzoli farà uscire il primo progetto?

ragazzi scusate le ragnatele nell'area filez, è ke ho avuto un po' da fare ultimamente, cmq ora è aggiornata

DIARIO DEL CORSO 11-1-2005
alberi 2-3
-definizione
-implementazione tramite tabella
-procedura MIN
-procedura MEMBER
-procedura CERCA
-procedura INSERT
-procedura SPLIT
-procedura DELETE
-procedura AGGIORNA

questi argmenti (come quelli della prox lezione) non saranno chiesti al compitino

domani non posso andare a lezione, qualcuno può aggiornare il diario x me?

DIARIO DEL CORSO 13-01-05

B-tree (B-alberi)
- idea intuitiva
- definizione
- procedura CERCA
- procedura SPLIT
- procedura di inserimento

Qualcuno mi conferma che le prossime lezioni di Algoritmi si faranno in aula G12 e quelle di laboratorio in G13?
Grazie!

Originally posted by tata1283
Qualcuno mi conferma che le prossime lezioni di Algoritmi si faranno in aula G12 e quelle di laboratorio in G13?
Grazie!

Per quello che so io le variazioni sono queste:

- martedì 18 lezione in G12
- giovedì 20 lab in G13
- venerdì 21 lab in G12
- martedì 25 lezione in G12
- giovedì 27 lab in G13
- venerdì 28 ultima lezione in G12

Spero di nn aver sbagliato niente!!

Originally posted by Polsy

commenti sul compito? io l'ho trovato non particolarmente difficile (nel senso ke avrebbe potuto essere + cattivo) a parte x lo spazio logaritmico del 3° esercizio
cmq ha detto ke i risultati usciranno alla fine della prox settimana, probabilmente giovedì [/B]

Originally posted by vlaste
L'esercizio 3 credo sia molto simile all'esercizio 3 del tema dell'1/4/03............
E credo anche di averlo cannato!!

bene allora ho cannato tutta la parte di analisi

LEZIONE DEL 18/01/05

in assenza di polsy vi riassumo gli argomenti della lezione di oggi...

- Riepilogo su Alberi di ricerca binaria, Alberi 2-3, B-Alberi con relativi tempi di calcolo delle operazioni MIN, MAX, MEMBERSHIP

- Definizione di PARTIZIONE su un insieme finito (con relativi esempi)

- Riepilogo delle definizioni di RELAZIONE DI EQUIVALENZA e CLASSI DI EQUIVALENZA di un insieme

- Spiegazione di 2 proposizioni che legano partizioni di un insieme con relazioni di equivalenza (con relative dimostrazioni)

- OPERAZIONI SULLE PARTIZIONI: UNION e FIND (entrambe con definizioni ed esempi)

- STRUTTURE DATI PER ESEGUIRE OPERAZIONI UNION e FIND (foreste semplici, foreste con bilanciamento, foreste con bilanciamento e connessioni)

- SPIEGAZIONE PROCEDURE UNION e FIND in pseudocodice (quello che usa lui x intenderci ), con osservazioni sui tempi di calcolo

spero di essere stato esauriente, per chiarimenti o inesattezze sono a disposizione

ciao a tutti

__________________
Mai tornare indietro, neanche per prendere la rincorsa.

DIARIO DEL CORSO 20-1-05
FORESTE CON BILANCIAMENTO
-definizione
-implementazione tipica
-procedure union e find
-esempio di esecuzione della procedura union
-teorema (e dimostrazione) x il calcolo di n-1 operazioni union partendo dalla partizione identità

ALGORITMO DI KRUSKAL
-idea intuitiva
-algoritmo in linguaggio AG


AVVISO
risultati del secondo parziale e media totale

DIARIO DEL CORSO 25-1-05

-ripasso algoritmo di kruskal
-tempo di calcolo dell'algoritmo
-semplificazione dell'algoritmo di kruskal come prototipo di algoritmo greedy
-definizione di sistema indipendente
-esempi di sistemi indipendenti (foresta, cricca, matching) e non indipendenti (cicli in un grafo non orientato, alberi)
-problemi di massimo e di minimo in un sistema indipendente
-algoritmo greedy per risolverli (con tempo di calcolo)
(ps: se ha dato una definizione formale di algoritmi greedy io me la sono persa)

AVVISO MOLTO IMPORTANTE
per sostenere l'orale bisogna iscriversi all'esame scritto anke se si è ammessi coi compitini (mi sembra di aver capito ke questa storia ha a ke fare coi nuovi registri elettronici...)

Ma in che giorno si sostiene l'orale?
Il giorno dell'appello, 7 febbraio? Lo stesso giorno che si presenta il progetto? O il progetto si presenta dopo??
Bah..................

Originally posted by vlaste
Ma in che giorno si sostiene l'orale?
Il giorno dell'appello, 7 febbraio? Lo stesso giorno che si presenta il progetto? O il progetto si presenta dopo??
Bah..................

Goldwurm oggi diceva che probabilmente l'orale ci sarà i primi di marzo....

Bene, domani scatterà la domanda al prof!

DIARIO DEL CORSO 27-1-05

ancora algoritmi greedy:
-caso in cui l'algoritmo sbaglia (cioè x quali sistemi di indipendenza l'algoritmo non è corretto con alcune funzioni peso)
-definizione di matroide
-teorema di rado

L'altro giorno sono andato via prima e nn ho chiesto niente al prof... si sa quand'è l'orale per chi ha passato i due compitini?

l'orale x i compitini è lo stesso dello scritto, cioè a fine febbraio/inizio marzo (la data precisa non si sa ancora)
per tutti quelli che hanno fatto il progetto di gennaio (controllo remoto) e i compitini di goldwurm, al momento dell'invio del progetto dovete specificare che il vostro orale sarà con goldwurm, non con trubian
in ogni caso ricordate di iscrivervi all'appello scritto di febbraio anche se avete passato i compitini, ALTRIMENTI IL VOSTRO VOTO NON POTRA' ESSERE VERBALIZZATO

DIARIO DEL CORSO 28-1-05
ultima lezione!!!!!!
PROGRAMMAZIONE DINAMICA
-caratteristiche principali
-problema della chiusura transitiva di un grafo (idea + algoritmo)
-problema del cammino di peso minimo tra 2 nodi (idea + algoritmo + tempo e spazio)

esercizi:

dalla dispensa di teoria
sez. 12.3 es 1, 2
sez 12.7.3 es 2

dall'eserciziario
8.1
8.2
8.3
9.1
9.6

goldwurm ha precisato che sarà disponibile durante il suo orario di ricevimento tranne che nella prima settimana di marzo

Ma quando uscirà il nostro progetto? qualcuno lo sa?

E si discute il progetto nello stesso momento dell'orale?

Cmq un grazie a Polsy per i 1000 sbattimenti e le 1000 informazioni!!

il nostro progetto dovrebbe uscire tra l'otto e il dieci febbraio, in concomitanza con il primo scritto

Originally posted by vlaste

Cmq un grazie a Polsy per i 1000 sbattimenti e le 1000 informazioni!!

prego!

A brevissimo nuovi appunti sull'area files....

Mi permetto di postare il link a una pagina che secondo me spiega e fa capire MOLTO bene i b-alberi... è molto chiara e discorsiva, anche se purtroppo è in inglese

http://www.semaphorecorp.com/btp/algo.html

Domandone: ma si può fare l'orale dell'8 marzo senza aver presentato il progetto?

Originally posted by vlaste
Domandone: ma si può fare l'orale dell'8 marzo senza aver presentato il progetto?

Orale con Goldwurm

Qualcuno ha già fatto o sa come possa essere la prova orale dell' 8 Marzo con Goldwurm??
Volevo sapere che genere di domande fa, se entra nel particolare degli argomenti, quanto dura mediamente un orale... ecc.
Se qualcuno mi può aiutare lo ringrazio!
CIAO!

Originally posted by Polsy
che io sappia no...cmq credo proprio ti tengano buona la parte scritta (nel caso manda una mail a goldwurm)

Originally posted by vlaste
Domandone: ma si può fare l'orale dell'8 marzo senza aver presentato il progetto?

__________________

Originally posted by SexOnTheBeach
se vuoi puoi andare a farlo al posto mio... io ho il problema inverso:
si può dare l'orale in un'altro appelo, avendo già passato compitini e progetto??