ProgettoLab0405 < Labprog2pz

Tags: view all tags
<H2>Progetto di [[Labprog2pz.WebHome][Laboratorio di Programmazione]]<br>
Canale P-Z, A.A. 2004/05</H2>

*Stefano Guerrini*

----

%RED% *Sono disponibili i main di prova per il III e IV Modulo* %FINE%

----

<div style="background-color:lightcyan">

%RED% *ATTENZIONE! Sono state apportate alcune modifiche alle [[#spec_V][specifiche del V modulo]].* %FINE%

Per i dettagli vedere le [[#V_modulo][note]] o la versione aggiornata del [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/M5-2.pdf][testo delle specifiche]].

</div>

----

<div style="background-color:lightcyan">

%RED% *ATTENZIONE! Sono state apportate alcune modifiche alle [[#spec_III_IV][specifiche dei moduli III e IV]] e in particolare &egrave; stato modificato il file [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/dgp.h][dgp.h]]* %FINE%

%RED% *NB: Una delle modifiche inizialmente apportate &egrave; stata annullata.* %FINE%

Per i dettagli, vedere le note al [[#III_modulo][III]] e [[#IV_modulo][IV modulo]].

Di conseguenza, &egrave; stato anche aggiornato [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/M34-new.pdf][il testo delle specifiche del III e IV modulo]]

Inoltre, per tener conto di queste piccole modifiche, il termine per la consegna &egrave;
%RED% *prorogato a domenica 19 giugno ore 24.00* %FINE%.

</div>

----

*INVIO DELLE SOLUZIONI*

I file delle soluzioni dovranno essere inviati usando gli appositi moduli elettronici per l'invio delle soluzioni

   * [[http://twiki.dsi.uniroma1.it/~guerrini/php/upl/upl-form-lppz-0405-III.php][del terzo modulo]] (termini scaduti).

   * [[http://twiki.dsi.uniroma1.it/~guerrini/php/upl/upl-form-lppz-0405-IV.php][del quarto modulo]] (termini scaduti).

   * [[http://twiki.dsi.uniroma1.it/~guerrini/php/upl/upl-form-lppz-0405-V.php][del quinto modulo]].

La scadenza per la consegna del terzo e quarto modulo &egrave; %RED% *prorogata a domenica 19 giugno ore 24.00*  %FINE%.

<div style="background-color:yellow">
<br>
Il V modulo, che esegue la ricerca di una parola, &egrave; facoltativo.

La scadenza per la consegna del quinto modulo &egrave; %RED% *domenica 10 luglio, ore 24.00* %FINE%. <br>
&nbsp;
</div>

----
<div style="background-color:lightgrey">

%TOC%

</div>

----

---+++ Specifiche del progetto

   * [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/descrptog.pdf][descrizione generale del progetto]]

   * [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/tavole.pdf][primo modulo]]

   * [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/modulo2a.pdf][secondo modulo]] - Per implementare questo modulo si deve includere la versione aggiornata del file [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/nodes.h][nodes.h]] e utilizzare la funzione =next_word= definita nel file [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/parser.c][parser.c]], in cui &egrave; implementato il parser degli ipertesti. Per utilizzare il parser si deve includere l'header file [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/parser.h][parser.h]] e compilare il programma insieme a =parser.c=. (Per maggiori informazioni si veda la [[NextWord][pagina che descrive il parser]]).

   * <a name="spec_III_IV" />[[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/M34-new.pdf][terzo e quarto modulo]] - Per implementare questi moduli si deve usare la versione aggiornata del file [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/nodes.h][nodes.h]]. I prototipi delle funzioni da implementare, oltre che la definizione dei principali tipi di dato e delle costanti da utilizzare per implementare il modulo sono definiti nell'header file [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/dgp.h][dgp.h]].

   * <a name="spec_V" />[[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/M5-2.pdf][quinto modulo]] - I prototipi delle funzioni da implementare, oltre che la definizione dei principali tipi di dato e delle costanti da utilizzare per implementare il modulo sono definiti nell'header file [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/rank.h][rank.h]]. Tutte le funzioni da implementare in questo modulo dovranno essere contenute in un unico file =modulo5.c=.

---+++ Sorgenti forniti dai docenti

*%RED%Controllare sempre se ci sono aggiornamenti dei file%FINE%*

---++++ Header files

   * [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/table.h][table.h]] - Interfaccia della tavola composta da una tavola hash e da una lista degli elementi nella tavola hash da implementare nel primo modulo del progetto. *[aggiornato il 10/05]*
   * [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/nodes.h][nodes.h]] - Principali definizioni dei tipi per l'implementazione del grafo degli ipertesti e dei prototipi delle funzioni che creano la tavola degli ipertesti da analizzare, il dizionario delle parole di ogni pagina e il grafo dei colegamenti tra le pagine. (Aggiornato al terzo e quarto modulo del progetto.) *[aggiornato il 23/05]*
   * [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/dgp.h][dgp.h]] - Header file con i prototipi delle funzioni da implementare nel terzo e quarto modulo, e con la definizione dei principali tipi di dato e delle costanti da utilizzare nell'implementazione di questi moduli. *[aggiornato il 09/06]*
   * [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/rank.h][rank.h]] - Header file con i prototipi delle funzioni da implementare nel quinto modulo, e con la definizione dei principali tipi di dato e delle costanti da utilizzare nell'implementazione di questi moduli. *[aggiornato il 14/06]*

---++++ Il parser

   * [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/parser.h][parser.h]] - Interfaccia del parser per la lettura degli ipertesti. *[aggiornato il 10/05]*
   * [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/parser.c][parser.c]] - Implementazione del parser per la lettura degli ipertesti. *[aggiornato il 10/05]*

---++++ Pagine di input

Sono disponibili una decina di pagine html semplificate sulle quali verificare i moduli del progetto. Le pagine possono essere scaricate sotto forma di [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/pagine.tgz][archivio tar-gzipped]].

Nei prossimi giorni verranno aggiunte altre pagine a quelle gi&agrave; disponibili.

----

---+++ Soluzioni fornite dai docenti

---++++ Soluzioni I modulo

La soluzione fornita implementa una tavola hash con gestione interna (lineare) delle collisioni.

   * [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/hashtab.h][hashtab.h]]
   * [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/hashtab.c][hashtab.c]]
   * [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/table.c][table.c]]
   * [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/modulo1.c][modulo1.c]]

Chi non ha sviluppato il primo modulo, o lo ha sviluppato in modo incompleto o errato, pu&ograve; utilizzare la soluzione fornita dal docente per verificare e completare il secondo modulo. 

----

---+++ NOTE

---++++ I modulo

   * [[FunzioneHash][Un esempio di funzione hash]]

   * *(21/04/05)*  *Per quanto riguarda la dimensione della tavola hash.* Questa pu&ograve; essere fissata con una costante (ad esempio, 10000). Se si vuole poter avere tavole hash di dimensione diverse, si pu&ograve; assumere che la dimensione di una nuova tavola sia memorizzata in una variabile globale, cambiando il valore di questa variabile le successive tavole cambiano di dimensione. Si osservi che ci&ograve; richiede che per ogni istanza di tavola sia memorizzata in qualche forma la sua dimensione, ci&ograve; si pu&ograve; ottenere con una opportuna definizione di HASHTABLE.

   * *(22/04/05)*  *A proposito del main di prova.* Un semplice modo per provare il modulo &egrave; quello di scrivere un main che, dopo aver creato la tavola  prendendo i file da una directory (ad esempio, prefissata o il cui nome &egrave; letto da input o ottenuto sulla linea di comando), scandisce gli elementi nella tavola (usando la lista) e per ogni elemento prova a cercarlo nella tavola (cos&igrave; si prova la ricerca nella tavola hash) e poi ne stampa la chiave. Se tutto va bene, si dovrebbe ottenere la lista dei file contenuti nella directory data. Un file main che esegue il precedente test e che sar&agrave; usato per verificare i seguenti programmi &egrave; scaricabile: [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/main1.c][scarica il file main1.c]].

---++++ II modulo

   * *(04/05/05)*  *Il parser.* Il parsing dei file ipertesto &egrave; implementato dalla funzione =next_word=. La descrizione del modo in cui utilizzare questa funzione e dei valori ritornati da tale funzione &egrave; riporato alla   [[NextWord][pagina che descrive il parser]] fornito dai docenti per leggere le parole contenute negli ipertesti.

   * *(12/05/05)*  *Directory con i file da ricercare.* Nella tavola progettata nel primo modulo non &egrave; stata prevista la memorizzazione del path della directory contenente i file, nonostante sia stata prevista la possibilit&agrave; di leggere i file da una qualsiasi directory passata come argomento sulla linea di comando. Inoltre, dato che la funzione =crea_diz_ipertesti= da implementare nel secondo modulo non riceve come parametro la directory dei file, nel secondo modulo non &egrave; possibile accedere agli ipertesti (a meno che non si trovino nella directory in cui &egrave; eseguito il programma). Per ovviare a questo inconveniente, &egrave; stata aggiunta al file =nodes.h= la dichiarazione esterna di una variabile =char&nbsp;*main_path=. Questa variabile serve per memorizzare il path della directory degli ipertesti; quindi, tutte le funzioni progettate nel secondo modulo potranno usare tale variabile globale per determinare il path completo dei file da leggere. La variabile =main_path= sar&agrave; definita nel file del main e il main, prima dell'esecuzione di =crea_diz_ipertesti=, dovr&agrave; associargli il valore opportuno.

   * *(12/05/05)*  *Verifica del II modulo.* &Egrave; disponibile una versione preliminare del main che sar&agrave; usato per verificare le soluzioni del secondo modulo ([[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/main2.c][scarica il file main2.c]]). Questo main,
      * per prima cosa richiama la funzione =create_node_table= fornita nel primo modulo (la directory in cui vengono ricercati gli ipertesti &egrave; quella in cui &egrave; eseguito il programma oppure una dircetory passata come argomento sulla linea di programma);
      * quindi richiama la =create_diz_locale= sviluppata nel secondo modulo (a proposito del problema della conoscenza del path della directory degli ipertesti all'interno di questa funzione, si veda una nota precedente);
      * infine, stampa le informazioni memorizzate negli elementi della tavola dei nodi.

---++++ III modulo

   * *(03/06/05)*  *<nop>PageRank.* Nella specifica del modulo ignorare la frase del paragrafo&nbsp;1.1 che dice: "Non &egrave; difficile provare che la somma dei <nop>PageRank di tutti gli ipertesti &egrave; uguale al numero degli ipertesti.". Questa propriet&agrave; si riferisce ad una formula per il calcolo del <nop>PageRank diversa da quella proposta nelle specifiche del modulo.

   * *(09/06/05)*  Il prototipo della funzione =page_rank= &egrave; stato corretto, aggiungendo il parametro che indica il numero massimo di iterazioni da eseguire per il calcolo del <nop>PageRank (come dalle specifiche del modulo). Vedere la versione aggiornata di [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/dgp.h][dgp.h]].

   * *(14/06/05)*  *%RED% [NEW!] %FINE%*  *Verifica del III modulo.* &Egrave; disponibile una versione preliminare del main che sar&agrave; usato per verificare le soluzioni del terzo modulo ([[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/main3.c][scarica il file main3.c]]). Questo main, dopo aver creato il grafo degli ipertesti usando le funzioni del primo e secondo modulo, calcola e stampa il <nopo>PageRank di tutte le pagine.

---++++ IV modulo

   * *(03/06/05)* =struct info<nop>_parola=. Nella definizioe di questa struttura occorre aggiungere un campo in cui memorizzare il nome dell'ipertesto contenente la parola (il campo =struct info_ipertesto *it= contiene solo le informazioni relative ai link entranti e uscenti dall'ipertesto, al dizionario locale e al <nop>PageRank. Alla struttura si deve pertanto aggiungere il campo =char&nbsp;*it_name;= che punta alla stringa del nome dell'ipertesto  (vedi la versione aggiornata del file [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/dgp.h][dgp.h]]).

   * %RED% *MODIFICA ANULLATA* %FINE% <s>*(09/06/05) * Nella dichiarazione della funzione =dgp_ins= si &egrave; aggiunto un terzo parametro di tipo =struct tabelem *= per accedere sia al nome dell'ipertesto che contiene la parola da inserire nel dgp, sia al puntatore alla =struct info_ipertesto= da salvare nel dgp;</s>

   * *(09/06/05) Nel file =dgp.h= &egrave; stata rimossa la linea =#include "hashtab.h"=. Vedere la versione aggiornata di [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/dgp.h][dgp.h]].

   * *(09/06/05) La modifica al prototipo della =dgp_ins= &egrave; annullata. Quindi, il prototipo rimane<br> =struct tabelem <nop>*dgp_ins(struct dgp <nop>*DGP, char <nop>*key);= <br>Il modo di operare per inserire gli elementi nel =dgp= &egrave; il seguente:
      * si scandisce il dizionario locale di tutte le pagine e per ogni parola si crea una =struct info_parola= contenente i dati dell'ipertesto di cui si sta scandendo il dizionario locale; quindi,
         1. si verifica se la parola &egrave; gi&agrave; presente nel =dgp= e, se la parola non &egrave; presente, la si aggiunge al =dgp= richiamando la =dgp_ins=, la quale assocer&egrave; al nuovo elemento inserito nella tavola una lista di ipertesti in cui occorre la parola vuota;
         2. si aggiunge la =struct info_parola= alla lista degli ipertesti in cui occorre la parola.

   * *(14/06/05)*  *%RED% [NEW!] %FINE%*  *Verifica del IV modulo.* &Egrave; disponibile una versione preliminare del main che sar&agrave; usato per verificare le soluzioni del quarto modulo ([[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/main4.c][scarica il file main4.c]]).<br> *NB.* Questo main &egrave; ancora preliminare e potrebbe contenere errori. Si prega di segnalare al docente eventuali problemi incontrati nel suo utilizzo.<br> Il main di prova, dopo aver creato il grafo degli ipertesti usando le funzioni del primo e secondo modulo
      * crea il dizionario globale usando la funzione =crea_dgp= implemenatata nel IV modulo
      * scandisce tutti i dizionari locali degli ipertesti, e per ogni parola trovata in un dizionario locale
         1. ricerca la parola nel dgp
         2. stampa la parola e l'ipertesto del dizionario locale che si sta scandendo
         3. preleva dal dgp e stampa la lista degli ipertesti in cui la parola occorre

---++++ V modulo

   * *(11/06/05) =struct <nop>LiIp=. Come nel caso della =struct info<nop>_parola=, nella definizione di questa struttura occorre aggiungere un campo in cui memorizzare il nome dell'ipertesto. Alla struttura si deve pertanto aggiungere il campo =char&nbsp;*it_name;= che punta alla stringa del nome dell'ipertesto (vedi la versione aggiornata del file [[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/rank.h][rank.h]]).

   * *(11/06/05) Nella dichiarazione della funzione =buid_LiIp= si &egrave; aggiunto un parametro di =struct dgp *= che fa riferimento al dizionario globale delle parole.

   * *(14/06/05) %RED% [NEW!] %FINE%* Come gi&agrave; fatto nel modulo 3 per il calcolo del PageRank, in =struct LiIp= conviene aggiungere un campo =double rank_aux= di ausilio per il calcolo del valore non normalizzato del rank di una pagina (un campo &egrave; sufficiente perch&egrave; il rank della pagina relativo a una ricerca ricerca non richiede l'applicazione di un procedimento iterativo). Il file =[[http://www.dsi.uniroma1.it/~guerrini/LabProg/Progetto-0405/src/rank.h][rank.h]]= &egrave; stato aggiornato con la nuova definizione di =struct <nop>LiIp=.

----
-- Users.StefanoGuerrini - 27 Apr 2005