 | |
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 |
esame del 29/1
Clicca QUI per vedere il messaggio nel forum |
| pirlo21 |
ciao raga...come siete messi per questo esame? perchè non ci diamo una mano?
Innanzitutto volevo chiedervi se sapete dov'è l'aula dell'esame perchè io di via comelico conosco solo il silab...thanks |
| Kira82 |
| L'aula beta è sulla sinistra, appena dentro al cortile guarda a sinistra, vedrai una porta a vetri, l'aula è subito lì dentro a destra. |
| pirlo21 |
| ok grazie.. e per i risultati? vengono dati prima dell'orale o si sapranno quando alla discussione dell'orale? |
| Kira82 |
Io credo che li faccia sapere prima anche perchè sul sito c'è scritto che l'orale lo puoi fare solo dopo aver fatto scritto e progetto, e il progetto lo può fare solo chi ha superato lo scritto..quindi sinceramente spero che li faccia sapere anche abbastanza in fretta perchè non mi metto a sudare sul progetto per 2/3 settimane per poi scoprire di non aver passato lo scritto e quindi non poterlo consegnare.
Per lo meno questo è ciò che ho capito io dalla sezione esame del sito..ho capito male forse? |
| pirlo21 |
| spero anche io, ma leggendo nei risultati dell'ultimo scritto c'è scritto semplicemente che chi ha consegnato si deve presentare all'orale...mah... |
| Kira82 |
| Da quello che ha detto il prof a lezione nell'ultimo appello non è passato nessuno..infatti c'è scritto che chi ha consegnato può visionare lo scritto..non che può fare l'orale |
| darkshadow |
Originally posted by Kira82
Da quello che ha detto il prof a lezione nell'ultimo appello non è passato nessuno..infatti c'è scritto che chi ha consegnato può visionare lo scritto..non che può fare l'orale
Dai sul serio???
ho dato un'occhiata al testo e non mi sembra difficile (a parte l'esercizio 2.c che non ho ancora capito come funziona l'algoritmo con le foreste bilanciate)!! |
| Kira82 |
| Se è solo quello che non hai capito potrei chiederti come risolveresti l'es 3? |
| darkshadow |
basta che scegli come radice dell'albero l'intero presente nella posizione centrale in questo modo avrai lo stesso numero di nodi a sx e a dx mantenendo l'altezza minima.
Prendi l'intero in posizione centrale
lo inserisci nell'albero
richiami la procedura per costruire il sottoalbero sx
richiami la procedura per costruire il sottoalbero dx |
| Kira82 |
Grazie della risp..immaginavo di dover prendere l'intero presente nella posizione centrale ma non ne ero certa, e poi i successivi li prendo in ordine o con lo stesso criterio?perchè se li prendo in ordine quelli minori della radice saranno tutti figli destri del primo figlio sinistro della radice, mentre quelli maggiori della radice saranno tutti figli destri del primo figlio destro della radice..non riesco a ritrovarmi...non è che scriveresti anche l'algoritmo che implementa l'albero di tale esercizio?
Grazie mille |
| darkshadow |
Originally posted by Kira82
Grazie della risp..immaginavo di dover prendere l'intero presente nella posizione centrale ma non ne ero certa, e poi i successivi li prendo in ordine o con lo stesso criterio?perchè se li prendo in ordine quelli minori della radice saranno tutti figli destri del primo figlio sinistro della radice, mentre quelli maggiori della radice saranno tutti figli destri del primo figlio destro della radice..non riesco a ritrovarmi...non è che scriveresti anche l'algoritmo che implementa l'albero di tale esercizio?
Grazie mille
Procedura Crea_Albero (i, j)
begin
k:= parte inferiore (i+j)/2
INSERISCI (T, k)
Crea_Albero (i, k-1) ------> Crea il sottoalbero sx
Crea_Albero (k+1, j) ------> Crea il sottoalbero dx
end
MAIN (n)
begin
T:= albero di ricerca binaria vuoto
Crea_Albero (1, n)
return T
end |
| darkshadow |
qualcuno invece mi puo spiegare come cavolo funziona l'heapsort???
per esempio l'esercizio 1 del tema d'esame del 08/02/07 |
| Kira82 |
Io l'ho capito così l'heapsort:
deve ordinare tutti i nodi in modo che la radice sia maggiore di tutti e ogni padre sia maggiore dei suoi figli.
Data il nodo i il figlio sinistro è 2i e quello destro 2i+1
Ora la procedura CreaHeap(A) ragiona cosi:
n := dimensione di A
for i =n/2,n/2 -1, ... , 1(tutte parti intere inferiori)
do aggiornaheap(i,n)
Mentre la procedura aggiornaheap(i,j) lavora così:
se 2i(ovvero figlio sin)=j allora se 2i > i (=figlio>padre) --> scambiali
altrimenti se 2i<j allora considera il figlio maggiore di i(lo chiamerò k) e se k>del padre scambiali ed esegui aggiornaheap (k,j)
Ora nell'es. del 8/02/07 viene così:
A = 2,1,6,5,4,7,9,8,3
quindi n = 9
l'albero è fatto così
2
1 6
5 4 7 9
8 3
allora esegui
- aggiornaheap(4,9) quindi confronti tra il 4° e il 9° elemento di A --> k = 8 ed essendo 8>5 scambi 5-8 e richiami
aggiornaheap(8,9)-->va bane così(n.b. 8 perchè in questo caso K é l'8° elemento)
- aggiornaheap(3,9) --> k = 9 e 9>6 quindi scambi 6-9 e poi aggiornaheap(7,9) --> va bene così
-aggiornaheap(2,9) --> ecc.
fino ad arrivare ad aver sistemato tutto con i seguenti scambi successivi:1-8,1-5,2-9,2-7 e il nuovo ordinamento è questo:
9,8,7,5,4,2,6,1,3
Spero di essere stata chiara e soprattutto che sia giusto..io l'ho capito e fatto così..se qualcuno l'ha fatto diverso me lo dica..grazie |
| darkshadow |
prima non riuscivo ad arrivare alla soluzione perche' avevo fatto un errore nell'algoritmo invece di metter 2i avevo messo i. adesso anch'io l'ho capito.
Allora raga come siete messi per domani??
Avete fatto gli esercizi sui grafi??
esercizio 4 tema d'esame del 12/06/07
esercizio 3 tema d'esame 05/09/07 |
| Kira82 |
L'es. 3 del 05/09/2007 si risolve così(sicura perchè l'ha svolto il prof in aula)
begin
for v € V do D[v] := ┴
Q:= Enqueue(Λ, s)
D[s] := 0
while Q != Λ do {
v:= Front(Q)
Q:= Dequeue(Q)
for w € L(v) do
if D[w] = ┴ then {D[w] := D[v] +1
Q:= Enqueue(Q,w) }
}
return D[u]
end
L'es. 4 del 12/06/07 è così invece
begin
U:= Λ // conterrà nodi raggiungibili
for v € V do D[v] := ┴
Q:= Enqueue(Λ, s)
D[s] := 0
while Q != Λ do {
v:= Front(Q)
Q:= Dequeue(Q)
for w € L(v) do
if D[w] = ┴ then { D[w] := D[v] +1
U:= inserisci_in_testa({v,w}, U)
Q:= Enqueue(Q,w) }
}
return U
end
Spero di esserti stata d'aiuto..in bocca al lupo per domani!! |
| pirlo21 |
| qualcuno che l'ha fatto bene può postarci la soluzione??? io a parte l'heapsort sono andato un po' a casaccio...in particolare l'esercizio 3...thanks |
| pirlo21 |
| nessun aiuto?? è già la terza volta di fila che esce l'esercizio sulle operazioni UNION-FIND...qualcuno lo sa risolvere? |
| pirlo21 |
| nessun aiuto?? è già la terza volta di fila che esce l'esercizio sulle operazioni UNION-FIND...qualcuno lo sa risolvere? |
| Kira82 |
L'es del compito del 29/01 sulle operazioni union-find si faceva così:
per foresta semplice veniva
- per n pari era un albero con per radice an e figlio destro an-2 e figlio sinistro an+1
-per n dispari veniva albero con radice an-1, figlio sinistro an e figlio destro an-3
(quindi l'ultimo nodo non foglia dell'albero era a2 con figlio destro a1 e figlio sinistro a3; a2 era figlio destro di a4 e il figlio sinistro di a4 era a5..)
Per quanto riguarda la foresta con bilanciamento invece veniva a2 radice e padre di tutti gli altri nodi.
tempo di calcolo era ordine di grandezza di n^2
Spero di essere stata abbastanza chiara. |
| pirlo21 |
| mentre nel caso bilanciato è giusto che il tempo sia O (n log n)? |
| darkshadow |
Originally posted by pirlo21
mentre nel caso bilanciato è giusto che il tempo sia O (n log n)?
No!!
nelle foreste bialnciate ti ritrovi con un solo nodo come radice e tutti gli altri come fligli.
Se hai capito le operazioni UNION-FIND dovresti sapere che le operazioni richiedono un tempo pari all'altezza dell'albero. Nel caso di foreste semplici l'altezza dell'albero e' n/2 mentre nelle foreste bilanciate l'altezza dell'albero e' 1 (perche' c'e' un nodo radice e tutti gli altri sono figli). Quindi T(n) = n * O(h) nelle foreste con bilanciamento.
Dove h = altezza dell'albero = 1 ed n per il ciclo for. ------> T(n) = O(n). |
| pirlo21 |
| ok grazie..in effetti non ho molto chiare le operazione union-find...purtroppo gli eserciziari del prof sono pieni di esercizi ma quelli svolti o con le soluzioni sono proprio pochi... ho provato a farne un po' e grazie a kira ho capito almeno come costruire la foresta...grazie |
|
|
|
|
