 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
Informazione
Clicca QUI per vedere il messaggio nel forum |
| mark |
Di sicuro sarà stato anche già chiesto varie volte ma forse, ora esistono informazioni più fresche quindi vi chiedo se si riesce a preparare algoritmi, la parte teorica almeno, attraverso le videolezioni e mediamente, se due mesi sono sufficienti.
grazie |
| ideafix |
Ciao mark,
Io ti consiglierei oltre alle videolezioni, che userei solo per alcuni argomenti, di usare parecchio il libro (Cormen, Leiserson, Rivest, C. Stein, Introduzione agli algoritmi e strutture dati ).
Il libro è veramente fatto bene e ti aiuta a fissare le idee.
Il programma è vasto, ma secondo me in due mesi se ti metti sotto lo prepari ;) .
ti consiglio anche queste videolezioni
http://ocw.mit.edu/OcwWeb/Electrica...Notes/index.htm
sono del MIT tenute dal Prof. Charles Leiserson (Uno degli autori del libro)
ciao |
| DarkSchneider |
cavolo, le lezioni del MIT
ma sono mp3 in inglese? |
| ideafix |
| no sono anche video , in inglese cmq |
| mark |
Originally posted by ideafix
Ciao mark,
Io ti consiglierei oltre alle videolezioni, che userei solo per alcuni argomenti, di usare parecchio il libro (Cormen, Leiserson, Rivest, C. Stein, Introduzione agli algoritmi e strutture dati ).
Il libro è veramente fatto bene e ti aiuta a fissare le idee.
Il programma è vasto, ma secondo me in due mesi se ti metti sotto lo prepari ;) .
ti consiglio anche queste videolezioni
http://ocw.mit.edu/OcwWeb/Electrica...Notes/index.htm
sono del MIT tenute dal Prof. Charles Leiserson (Uno degli autori del libro)
ciao
ciao ideafix,
grazie per le informazioni. Le videolezioni quindi, sono ancora valide secondo te ? |
| ideafix |
Si,
Il programma che ha fatto quest'anno è praticamente identico a quello che ha fatto nelle videolezioni (ha solo cambiato l'ordine "cronologico" di alcuni argomenti).
Propio per questa sua tendenza a saltare un pò da un argomento ad un altro ti consiglio di usare tanto il libro come "traccia", giusto per non perderti :D |
| mark |
scusa ideafix,
ma l'eventuale progetto quando dovrebbe uscire ? |
| ideafix |
il progetto esce sempre la data dell'appello (quella indicata sul SIFA)
quindi:
ti iscrivi ad un appello sul sifa, il giorno indicato esce il progetto nel quale compaiono anche le scadenze relative al progetto (in genere hai 2 settimane).
A questo punto se hai passato il progetto sostieni l'orale che si compone di 2 parti.
1) discuti il progetto (niente di che solo per capire che sia farina del tuo sacco e discutete le scelte di implementazione es. perchè hai scelto di usare un albero RB...)
2) l'orale vero e proprio su la teoria |
| mark |
Originally posted by ideafix
il progetto esce sempre la data dell'appello (quella indicata sul SIFA)
quindi:
ti iscrivi ad un appello sul sifa, il giorno indicato esce il progetto nel quale compaiono anche le scadenze relative al progetto (in genere hai 2 settimane).
A questo punto se hai passato il progetto sostieni l'orale che si compone di 2 parti.
1) discuti il progetto (niente di che solo per capire che sia farina del tuo sacco e discutete le scelte di implementazione es. perchè hai scelto di usare un albero RB...)
2) l'orale vero e proprio su la teoria
sei stato chiarissimo, grazie 1000 per ora :) |
| mark |
non mi ricordo se l'ho chiesto, ma come traccia per le cose da studiare va bene il diario del corso 2006/2007 ?
e poi....
ne file di excel che si può trovare sul sito unimi, quello con le date degli appelli, c'è fissato un appello di algoritmi per il 5 settembre, significa che dopo quello si deve attendere sino a gennaio ?
ciao |
| CaboM.BNA |
PURTOPPO si, stop fino a gennaio... anke io lo sto preparando... mi sono IMPOSTO DI PASSARLO a settembre... (per ora sono alla 3 videolezione)
per la traccia credo vada bene il programma di quest'anno... (io non l'ho nemmeno guardata: vedo le videolezioni e poi mi studio/ripasso sul libro gli argomenti trattati a [video]lezione) |
| mark |
Originally posted by CaboM.BNA
PURTOPPO si, stop fino a gennaio... anke io lo sto preparando... mi sono IMPOSTO DI PASSARLO a settembre... (per ora sono alla 3 videolezione)
per la traccia credo vada bene il programma di quest'anno... (io non l'ho nemmeno guardata: vedo le videolezioni e poi mi studio/ripasso sul libro gli argomenti trattati a [video]lezione)
ciao CaboM.BNA , ottima mossa!
E..... diamoci da fare entrambi per passare anche questo esame :D
Come ti sembrano le videolezioni ?
redo che con un paio d'ore al giorno, ovviamente sino a settembre, dovremmo farcela, salvo intoppi, ovviamente.
In caso di incomprensioni di qualche argomento "ostico", c'è pur sempre questo forum :)
Buon studio |
| CaboM.BNA |
le videolezioni le ho trovate interessanti... 2 anni fa quando CERCAI di frequantare le lezioni erano in tardo pomeriggio e il sempre-stesso-tono-di-voce di Torelli mi faceva regolarmente cadere in trance ed abbioccarmi... :zzz:
ora che posso seguire con ritmi miei, invece devo dire che mi trovo piuttosto bene.. Torelli mi pare un buon docente e delle prime 5 ore che ho ascoltato ho capito TUTTO... :-o intolre ho notato che Torelli non calca eccessivamente la mano sul'aspetto matematico, ma cerca di spiegare dimostrazioni e pseudocodice tramite i disegni...
il forum è utilissimo, ma tra videolezioni e libro credo che non ci dovrebbero essere grosse difficoltà...
un saluto e buono studio anche te! |
| mark |
| a me continua a sfuggire come, osservando un albero, si riesce a stabilire che un codice è prefisso :? |
| CaboM.BNA |
cito Torelli: (from videolezioni)
"è guradando l'albero che possiamo dimostrarlo: una parola è di codice è associata alle foglie (e non ai nodi interni!) e le stringhe che corrispondono ai prefissi sono quelle che si fermano ai nodi interni... Noi arriviamo SEMPRE ad una foglia e non ci fermiamo mai prima di arrivare ad una foglia; dunque di prefissi non ce ne sono. Il fatto di associare le parole alle foglie ci garantisce che è un codice prefisso." |
| mark |
ho ascoltato quel pezzo 10 volte ma non ne ho ricavato nulla, sarà la stanchezza, nemmeno ora da quello che mi scrivi :shock:
quello che sono riuscito a trascrivere detto dal prof:
guardando l'albero si vede subito se un codice è prefisso perchè associamo sempre un codice ad una foglia e ciò garantisce che è prefisso |
| CaboM.BNA |
Cerco di spegarlo con altre parole...
Le foglie differiscono tutte PER ALMENO 1 BIT... Sicché non possiamo mai avere 2 parole uguale... Quando "crei" una parola (p1), parti dalla radice e poi segui un percorso univoco nodo per nodo fino a quando non arrivi alla foglia. Se vi fosse un prefisso (p2), dovrebbero esservi parole termanano ad un nodo interno, in modo che il percorso che segui per arrivare a p2 concida, cioè SIA PARTE, del percorso che seguiresti per arrivare a p1. |
| mark |
| vuoi dire che se un codice non fosse prefisso avremmo lettere posizionate all'interno dei nodi dell'albero in quanto alcune lettere, anzichè fermarsi solo come foglie diverrebbero anchesse nodi e verrebbero "sfondati"(passami il termine) da parole prefisse ? |
| CaboM.BNA |
la prima parte ok, ma non capisco questa frase...
Originally posted by mark
... alcune lettere, anzichè fermarsi solo come foglie diverrebbero anchesse nodi e verrebbero "sfondati"(passami il termine) da parole prefisse ?
cioè se fosse non prefisso (e qundi nel linguaggio esisterebbero dei prefissi), le parole corrispondenti ai prefissi SAREBBERO PROPRIO QUELLE ASSOCIATE AI NODI INTERNI...
adex mi riaggancio a quello scritto nel post precedente..
ecco il link ad un'immagine, cosi mi spiego con un esempio...
Del linguaggio fanno parte i simboli: a,b,c,d,e,f,p (il pallino in basso a dx nel disegno sarebbue una "e").
Questi simboli vengono codificati in bit con le seguenti sequenze di bit (e percio parole): a=0, p=1, c=100, b=101, d:111, f=1100, e=1101.
SE NON vi fossero simboli associati ai nodi interni, ma solo alle foglie, in percorso per arrivare ad ogni foglia è univoco e diverso da altri percorsi. Per arrivare a "f" seguo lo stesso percorso che userei per arrivare al nodo "e" (ossia '110'), ma arrivato al nodo interno "14" i due percorsi differiscono per l'ultimo bit.
Poiche vi è un simbolo ASSOCIATO AD UN NODO INTERNO, tutti i percorsi che passano da quel nodo (e quindi tutte le parole che in binario iniziano per '1') hanno "p" come prefisso. Se vogliamo arrivare "a","b","c","d","e","f" PASSIAMO PER FORZA da "p"; perciò "p" è un prefisso. |
| mark |
lo avevo capito proprio così, coem lo hai spiegato ora, anche se dalle mie parole forse non si era molto capito molto
mi sono fatto anche un banale esempio con tali dati:
a=0; b=01; c=10
frequenze
a=30; b=10; c=5
e poi costruendo l'albero si vede proprio che sullo stesso cammino(nodo interno) della lettera 'a' ci passa la lettera 'b', quindi il codice da me proposto non è prefisso in quanto il codice di 'a' è prefisso per il codice di 'b' e non è univoco
grazie 1000 :) |
| mark |
a me della videolezione 1 è rimasto un dubbio. Si parla di problemi di dimensione n e il prof dice che, se per ridurlo di una dimensione uso sempre il medesimo numero di passi, es: 10, allora i passi totali saranno n*n e cioè n^2.
Poi, enuncia un certo k e dice che se un problema è di dimensioni 1 e poi 2 e poi 3 e poi k, n^2 non è più valido per determinare il numero di passi necessari per risolvere il problema; e tira in ballo la "somma" di Gauss.... ??????
Help |
| CaboM.BNA |
confesso che non mi ricordo bene di tutto quello su cui ha parlato/divagato...
cmq non te preocupe... quella parte li "non serve"... io mi son segnato veramente poca roba...
l'unica cosa che ho trovato interessante (oltra all'idea su come si fa a calcolare la somma di Gauss) è stata: "SE HO UN PROBLEMA DI DIMENSIONE n E AD OGNI PASSO DIMEZZO IL MIO PROBLEMA, DOPO QUANTI PASSI RIDUCO IL MIO PROBLEMA ALLA DIMENSIONE 1? DOPO lg(n) PASSI."
il resto, a mio avviso lo puoi tranquillamente lasciare perdere... (la max dai un'occhiata sul libro a come calcolare i fattoriali, come dice Torelli) |
| mark |
Originally posted by CaboM.BNA
confesso che non mi ricordo bene di tutto quello su cui ha parlato/divagato...
cmq non te preocupe... quella parte li "non serve"... io mi son segnato veramente poca roba...
l'unica cosa che ho trovato interessante (oltra all'idea su come si fa a calcolare la somma di Gauss) è stata: "SE HO UN PROBLEMA DI DIMENSIONE n E AD OGNI PASSO DIMEZZO IL MIO PROBLEMA, DOPO QUANTI PASSI RIDUCO IL MIO PROBLEMA ALLA DIMENSIONE 1? DOPO lg(n) PASSI."
il resto, a mio avviso lo puoi tranquillamente lasciare perdere... (la max dai un'occhiata sul libro a come calcolare i fattoriali, come dice Torelli)
da come esponeva le cose sembra che gli desse molta importanza. Se hai notato, serviva per introdurre quel famoso theta(n^2). Non conoscendo il docente non è facile comprendere cosa serve, ah...
Hai visto il riassunto delle videolezioni qui sul dsy ? |
| CaboM.BNA |
io comincio a postare il mio dubbio... tu ci metterai un po ad arrivarci, vito che è la (video)lezione del 14-10-2003, ma magari oltre a noi altri PAZZI studiamo algoritmi ad agosto...
heap:shock:
trattasi dell'ultimo pezzetto del paragrafo 3.2, delgli appunti di Torelli sugli HEAP. Il mio problema è la frase sottolineata. Piu che italiano mi pare sumero antico. Non ho capito ASSOLUTAMENTE NULLA (mentre tutto quello che è stato detto precendetemente mi è sembrato chiaro) |
| CaboM.BNA |
trovati i riassunti... dopo che me l'hai detto li ho visto nell'area filez... ben fatti, saranno sicuramente utili...
ho visto il pezzo a cui ti riferivi...
la questione è piuttosto semplice.
HO UN PROBLEMA DI DIMENSIONE n. SUPPONIAMO CHE PER RIDURRE DI 1 LA DIMENSIONE DEL MIO PROBLEMA (E PERCIO FARLO DIVENTARE DI DIMENSIONE n-1) IO CI IMPIEGO n TEMPO. ADESSO DOBBIAMO RISOLVERE UN PROBLEMA DI DIMENSIONE n-1. POI AVRO UN PROBLEMA DI DIMENSIONE n-2... ETC.
DOPO n OPERAZIONI ARRIVERO AD AVERE UN PROBLEMA DI DIMENSIONE 1. SICCOME OGNI OPERAZIONE MI E' COSTATA n TEMPO, IN TUTTO CI AVRO IMPIEGATO n*n TEMPO.
k viene citato solo per spiegarti PERCHE si vogliono n passi. fare n-1, poi (n-1)-1, poi ((n-1)-1)-1 richiede lo stesso numero di passi anche se andassimo "alla rovescia" (e percio da 1 ad n): 1, poi 1+1, poi (1+1)+1... devo in ogni caso fare n operazioni. [sia che decrementi di 1 alla volta partendo da n, sia che sommi +1 ogni volta partendo da 1]
......
continuo domani... adex devo uscire perche sono in ritadro... byez |
| mark |
cito il prof, o quasi
ho un problema di dimensione n e impiego tempo n per ridurre di 1 la dimensione del problema e facendo n operazioni ora ho ridotto il problema a dimensione n-1
quante operazioni per arrivare a problema di didmensione 1 ?
se il numero di passi fosse sempre n e lo faccio per n volte il numero di passi sarebbe n^2.
Ma se ho dimensione del problema variabile ? dimens 1, poi dimens 2, poi dimens 3, poi dimens 4, poi dimens 5, poi dimens 6, come faccio ?
numero di passi sarà ancora n^2 ?
sarà dell'ordine di n^2 ma quanto precisamente ?
entra in ballo Gauss!
somma di
0+100
1+99
2+98
etc...sempre 100
e
1+2+3+4+5+6+7.....100
li metto insieme nel modo indicato negli appunti del prof e divido per due, ottenendo 5050, e quindi ?
quanto sopra è dell'ordine di n^2
chiari i vari passaggi rispetto agli appunti del prof, ma no capisco l'aggancio col problema di dimensione variabile, boh! |
| CaboM.BNA |
| in sostanza: io ho un problema che ha complessità 1, poi 2, poi 3... e cosi fino a n. Per calcolare il tempo che ci metto a risolverlo uso la somma di Gauss. Il risultato ottenuto è dell'ordine di grandezza di n^2. |
| mark |
Originally posted by CaboM.BNA
in sostanza: io ho un problema che ha complessità 1, poi 2, poi 3... e cosi fino a n. Per calcolare il tempo che ci metto a risolverlo uso la somma di Gauss. Il risultato ottenuto è dell'ordine di grandezza di n^2.
grazie
p.s.
in ultima analisi, a me sembra che abbia mostrato un certo numero di metodi per determinalre il numero di passi per risolvere un problema o sbaglio ?
nell'ordine:
- log2(n)
- n^2
- Gauss
|
| CaboM.BNA |
| si... il numero di passi o tempo necessario... |
| Bravo Yankee |
| Qualcuno di voi è riuscito ad iscriversi in qualche modo all'appello del 5 settembre del prof. Torelli? Sul SIFA non è ancora disponibile e, considerando la chiusura estiva, non so quando lo sarà. |
| CaboM.BNA |
azz.. :shock:
mi ero completamente dimenticato che ci si dovesse iscrivere!
thx yankee...
ho appena controllato e come giustamente facevi notare, non ci si può ancora iscrivere...
facciamo che il pirmo che vede la data disponibile (o meglio si ricorda di controllare) scrive qui un bel post... :D
se entro il 25 agosto non esce nulla, mandiamo una mail a Torelli... (tanto saremo solo noi tre... o al max altri 1 o 2 masochisti) |
| KIMMY |
| Ecco un'altra masochista ^^ sono al mare con dietro le videolezioni di torelli e me ne guardo una al giorno all'ora di pranzo....... concilia il sonno ahaahhaha cmq se vedo che sul sifa ci si può iscrivere posterò qui :) |
| Renaulto |
Originally posted by CaboM.BNA
(tanto saremo solo noi tre... o al max altri 1 o 2 masochisti)
Eccomi! Vista la data e l'ora, direi che la definizione ci sta tutta.
Sul SIFA ancora nulla. |
| CaboM.BNA |
beh... come giustamente fai notare, vista data&ora la definizione di "masochista" per te mi pare addirittura riduttiva... ;)
io sono arrivato alla videolezione del 27-11-2003... negli ultimi 40 minuti di quella del 25-11 ho VERAMENTE rischiato di perdere la (poca) sanità mentale che mi era rimasta... :pazzo:
credo che nemmeno Torelli sia in grado di chiarire ciò che ha (vanamente&caoticamente) ha cercato di spiegare...
e pensare che dopo le prime lezioni in cui ho fatto un po di fatica mi SEMBRAVA di cominciare a capire l'argomento, e a volte persino i (pseudo)casuali excursus che ad un primo ascolto sembrano completamente off-topic...
col C come siete messi? io ricordo ben poco... domani devo iniziare a leggere un po' il manuale... |
| CaboM.BNA |
libro pagina 219. Esercizio 12.2-3
qualcuno saprebbe buttare giu in una decina di righe la procedura (ovviamente in pseudocodice) per Tree-Predecessor?
Chiedo perche secondo me non è proprio "simmetrica a Tree-Successor" come dice il libro.
Vi sono 3 casi:
I - il nodo è la radice: il predecessore è il nodo più a destra del sottoalbero sinistro.
II- il nodo NON ha figlio sinistro: il predecessore è il padre.
III - il nodo ha figlio sinistro: il predecessore è il figlio sinistro.
Mi confermate? |
| CaboM.BNA |
yuuuhuuuuuuu.... c'è nessuno? :look:
mi sento come la particella di sodio.... |
| tata1283 |
ma sul sifa sbaglio o ancora l'iscrizione non c'è?
Ormai dovrebbe esserci no? |
| CaboM.BNA |
| la segreteria didattica era chiusa fino al 24/08... Lunedi, quando riapre dovrebbero mettere online le iscrizioni... spero... |
| CaboM.BNA |
| aperte le iscrizioni via SIFA... |
| khelidan |
| ci sono anchio per l'appello!io mi son viste le lezioni circa una anno fa e sinceramente me le potevo risparmiare,il libro spiega davvero bene e tanto all'orale anche se fai pseudo scena muta ti conferma il voto del progetto,il piu sarà fare un pttimo progetto!Peneultimo esame,speriamo bene..... |
| number15 |
| Io di informatica turno diurno, posso dare tranquillamente l'esame con Torelli studiando sul libro? |
| Toras |
Originally posted by number15
Io di informatica turno diurno, posso dare tranquillamente l'esame con Torelli studiando sul libro?
si :D |
| number15 |
| Mi sembra di capire che tu abbia avuto una buona esperienza!?!? |
|
|
|
|
