Pages: [1]   Go Down
Print
Author Topic: notizie sulle due ultime lezioni  (Read 1753 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
EL TIBURON
Matricola
*
Offline Offline

Gender: Male
Posts: 90



« on: 09-01-2009, 13:18:17 »

qualcuno saprebbe dirmi cosa si é fatto nella lezione di giorno 7 e in quella di giorno 9? P.S. é il mio primo post da PSP  pc
Logged

Eres lo que quieres ser.
KingDavid
Forumista
***
Offline Offline

Posts: 788


Alla fine [...] tutta la realtà è binaria.


« Reply #1 on: 09-01-2009, 15:19:57 »

qualcuno saprebbe dirmi cosa si é fatto nella lezione di giorno 7 e in quella di giorno 9? P.S. é il mio primo post da PSP  pc

 
Logged

Basti pensare che un ipotetico quadrato di specchi, lungo 200 chilometri per ogni lato, potrebbe produrre tutta l'energia necessaria all'intero pianeta.
(Carlo Rubbia)
David
Matricola
*
Offline Offline

Posts: 19


« Reply #2 on: 09-01-2009, 20:10:47 »

Allora giorno 7 ha spiegato la prima parte sui "cammini minimi" ,mentre oggi non so cosa abbia fatto perchè non ero presente.
Logged
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.474


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #3 on: 10-01-2009, 00:53:26 »

Mercoledì 7 il prof. ha spiegato i seguenti argomenti:
  • grafi rappresentati tramite matrice di adiacenza (e complessità spaziale relativa a tale rappresentazione))
  • grafi rappresentati tramite liste di adiacenza (e complessità spaziale relativa a tale rappresentazione)
  • definizione di cammino a partire da un grafo G=(V,E) e il suo peso a partire da G e da una funzione peso w:E→R
  • tre notazioni per denotare insiemi di cammini che sono sottoinsiemi dei cammini di un grafo G
  • definizione di distanza δG(a, b) tra due nodi a,b ∈ V
  • definizione di cammino minimo
  • presentazione di 4 problemi sui cammini minimi su grafi che ci si propone di risolvere
  • Lemma sull'ammissione di cammini minimi per un grafo pesato (G, w)
  • Grafo dei cammini minimi (ottenuto da un grafo qualsiasi)
.

Venerdì 9, poi, il prof. Cantone ha dato la dimostrazione della proprietà di cui gode il grafo dei cammini minimi secondo cui
se MIN_PATHS (G; s) ≠ ∅ ⇒ PATHS (G's; s) = MIN_PATHS (G; s)
ove G's è il grafo dei cammini minimi dall'unica sorgente s considerata.

Questo per quanto riguarda la teoria propriamente detta.

Poi (sempre venerdì) ha fatto una esercitazione risolvendo con noi per prima cosa il problema dello zaino (sia in forma con materiali frazionati sia in forma con materiali interi, risolto quest'ultimo con la programmazione dinamica che ha complessità esponenziale per adesso, fino a quando un nuovo plurimilionario fortunatissimo non scoprirà un algoritmo migliore dell'attuale noto  ) e poi ha risolto in aula un esercizio che si trova sui documenti degli esercizi passati il cui testo è:

Sia S una sequenza finita di nodi e sia label:S→N una data funzione definita sugli elementi delle sequenze S. Si descriva un algoritmo che costruisca un albero binario ordinato pieno T tale che:
  • la sequenza delle foglie di T, lette da sinistra a destra, coincida con S
  • il valore della funzione sulla radice di T sia minimo dove:
            ╭
            │ label (x)                se x è una foglia
    φ (x) = ┤
            │ [φ(l)]² + [φ(r)]²        altrimenti, con l e r figli risp. sinistro e destro di x
            ╰

che si risolve sfruttando argomentazioni simili a quelle usate per la codifica di Huffman e per risolvere il problema della parentesizzazione del prodotto di matrici.
 
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
KingDavid
Forumista
***
Offline Offline

Posts: 788


Alla fine [...] tutta la realtà è binaria.


« Reply #4 on: 10-01-2009, 02:04:21 »

Grazie reversengineer questa si che è una risposta precisa e soprattutto utile.  ok
Logged

Basti pensare che un ipotetico quadrato di specchi, lungo 200 chilometri per ogni lato, potrebbe produrre tutta l'energia necessaria all'intero pianeta.
(Carlo Rubbia)
EL TIBURON
Matricola
*
Offline Offline

Gender: Male
Posts: 90



« Reply #5 on: 11-01-2009, 20:15:17 »

grazie ragazzi per le risposte e in particolare a reversengineer.

Potete postare la soluzione o almeno un abozzo dell'esercizio di cui sopra? (Quello di creare l'albero binario ordinato e pieno T col costo minimo sfruttando la funzione fi definita su un insieme di nodi S)

Perché nonostante si è accennato alla soluzione non sono riuscito a capire come procedere....

Grazie.
Logged

Eres lo que quieres ser.
Pages: [1]   Go Up
Print
Jump to: