| Prossima revisione | Revisione precedente |
| matematica:asd:asd_21:progetto_21 [05/05/2022 alle 10:21 (3 anni fa)] – creata Roberto Grossi | matematica:asd:asd_21:progetto_21 [13/06/2022 alle 13:50 (3 anni fa)] (versione attuale) – Roberto Grossi |
|---|
| ====== Progetto di ASD 2021/2022 ====== | ====== Progetto di ASD 2021/2022 ====== |
| |
| Il gioco delle K parole consiste nell'indovinare una parola W che si combina bene con le K parole fornite. Per esempio, con K=2, se le parole fornite sono Buffalo e Clinton, la parola che si combina bene con loro è W = Bill. Affinché le K parole siano valide in questo gioco, non devono dar luogo ad ambiguità nella scelta di W: quest'ultima deve risultare come l'**unica** scelta ragionevole. Un noto quiz televisivo utilizza questo gioco con K=5. | Il gioco delle K parole consiste nell'indovinare una parola W che si combina bene con le K parole fornite. Per esempio, con K=2, se le parole fornite sono Buffalo e Clinton, la parola che si combina bene con loro è W = Bill (ossia Buffalo Bill e Bill Clinton). Affinché le K parole siano valide in questo gioco, non devono dar luogo ad ambiguità nella scelta di W: quest'ultima deve risultare come l'**unica** scelta ragionevole. Un noto quiz televisivo utilizza questo gioco con K=5. |
| |
| |
| Il progetto richiede di individuare insiemi di K parole valide per questo gioco, utilizzando i testi di alcune pagine prese da Wikipedia e "ripulite" dalla formattazione. È richiesto di modellare tale problema utilizzando un grafo non orientato G = (V,E), dove V rappresenta le parole distinte che si trovano nelle varie pagine di Wikipedia e ciascun arco (u,v) in E indica che le due parole corrispondenti a u e v appaiono consecutivamente (in alternativa, sufficientemente vicine) in almeno una di tali pagine. | Il progetto richiede di individuare insiemi di K parole valide per questo gioco, utilizzando i testi di alcune pagine prese da Wikipedia e "ripulite" dalla formattazione. È richiesto di modellare tale problema utilizzando un grafo non orientato G = (V,E), dove V rappresenta le parole distinte che si trovano nelle varie pagine di Wikipedia e ciascun arco (u,v) in E indica che le due parole corrispondenti a u e v appaiono consecutivamente (in alternativa, sufficientemente vicine) in almeno una di tali pagine. |
| | |
| | |
| | Riassumendo: l'input sono le pagine wikipedia e un intero K; l'output sono un certo numero di linee (per esempio una decina), dove ciascuna linea contiene K + 1 parole separate da uno spazio (le prime K parole sono scelte come indicato sopra, e la (K+1)-esima è la parola W univocamente associata a quest'ultime). |
| |
| Sono lasciate allo studente delle scelte: | Sono lasciate allo studente delle scelte: |
| * se ignorare le "stop word" come articoli, preposizioni, verbi ausiliari, ecc.; | * se ignorare le "stop word" come articoli, preposizioni, verbi ausiliari, ecc.; |
| * se vedere G come grafo pesato o meno (per esempio in quante pagine occorrono le coppie di parole); | * se vedere G come grafo pesato o meno (per esempio in quante pagine occorrono le coppie di parole); |
| * se annotare i nodi e gli archi di G con ulteriori informazioni se necessarie. | * se annotare i nodi e gli archi di G con ulteriori informazioni (qualora fossero necessarie); |
| | * il criterio di rilevanza con cui scegliere le linee di output (infatti potrebbero esserci molte potenziali soluzioni da cui pescare). |
| |
| Il progetto si basa su file presi dal mondo reale e prevede di effettuare un'analisi sperimentale dei dati per validare se le scelte di K parole fornite abbiano senso o meno: | Il progetto si basa su file presi dal mondo reale e prevede di effettuare un'analisi sperimentale dei dati per validare se le scelte di K parole fornite abbiano senso o meno: |
| * qui c'è un piccolo campione per fare le prove ; | * qui c'è un piccolo campione per fare le prove {{ :matematica:asd:asd_21:wiki-small.zip |}}; |
| * qui c'è un campione di circa 21mila pagine per un totale di circa 100 milioni di caratteri : più pagine si riescono a trattare, meglio è. | * qui c'è un campione di circa 21mila pagine per un totale di circa 100 milioni di caratteri {{ :matematica:asd:asd_21:wikipedia_20k.zip |}}: più pagine si riescono a trattare, meglio è. |
| |
| | |
| * ''od -c'' è utile per vedere il contenuto di un file testuale, carattere per carattere, inclusi i caratteri non stampabili; vedi [[https://www.geeksforgeeks.org/od-command-linux-example/]] | * ''od -c'' è utile per vedere il contenuto di un file testuale, carattere per carattere, inclusi i caratteri non stampabili; vedi [[https://www.geeksforgeeks.org/od-command-linux-example/]] |
| * ''mmap'' è utile per accedere a un file testuale come se fosse un gigantesco array di caratteri; vedi [[matematica:asd:asd_21:mmap]] e [[http://man7.org/linux/man-pages/man2/mmap.2.html]] | * ''mmap'' è utile per accedere a un file testuale come se fosse un gigantesco array di caratteri; vedi [[matematica:asd:asd_21:mmap]] e [[http://man7.org/linux/man-pages/man2/mmap.2.html]] |
| | * ''getline'' in C++ è un'altra funzione molto utile per fare il parsing del testo; vedi [[https://www.geeksforgeeks.org/getline-string-c/]] |
| | * Per leggere i nomi dei file presenti in una directory, il cui path è nella variabile ''home'', ci sono vari modi. Per esempio, il seguente dovrebbe funzionare sui vari sistemi operativi (codice da compilare con ''g++ -std=c++17'' o comando equivalente): |
| | <code> |
| | #include <iostream> |
| | #include <string> |
| | #include <filesystem> |
| | |
| | using namespace std; |
| | namespace fs = std::filesystem; |
| | |
| | int main() { |
| | string home = "."; // directory corrente, oppure mettere il path esteso della directory con i file |
| | for (const auto& entry : fs::directory_iterator(home)) |
| | std::cout << entry.path() << std::endl; |
| | return 0; |
| | } |
| | </code> |
| | |
| | |
