Prova scritta del 24 gennaio 2019 di Fondamenti di Informatica I (prof. Montessoro) + Fondamenti di Informatica II (prof. Di Gaspero)
Per studenti di Ing. Gestionale immatricolati negli anni accademici 2016-17 e precedenti DURATA DELLA PROVA: 3 ORE
A pena di annullamento immediato della prova:
1) Non è possibile consultare libri o appunti (in qualunque forma) né utilizzare calcolatrici, telefoni cellulari, ecc.
2) Non è consentito comunicare (con qualunque mezzo) 3) Non è consentito uscire dall’aula
Lo studente è tenuto a scrivere, correggere, compilare ed eseguire su computer (a casa o in laboratorio) gli esercizi di programmazione prima della prova orale. Alla prova orale lo studente deve portare una memory pen USB contenente i sorgenti dei programmi corretti e le stampe dei relativi file.
Esercizio 2 (12 punti)
Un file di testo contiene un piccolo dizionario dei sinonimi. Ogni riga riporta un elenco di sinonimi (una sola parola ciascuno) preceduti da un numero intero che indica il numero di sinonimi presenti sulla riga.
Per esempio:
4 casa abitazione alloggio dimora 3 lavoro impegno occupazione
6 percorso cammino tragitto viaggio strada itinerario
Ovviamente, ogni riga contiene sempre almeno due sinonimi. Ogni gruppo di sinonimi contiene al massimo 10 parole. Il file è di lunghezza ignota, ma non superiore a 300 righe.
Si vuole sviluppare uno strumento per aiutare l’autore di un testo a scegliere tra i sinonimi dei termini da lui/lei utilizzati. Per fare questo, si vuole aggiungere al testo originale l’elenco dei sinonimi di ogni parola presente nel dizionario dei sinonimi sopra descritto, accodandoli alla parola stessa e separandoli dal carattere '/'. Nota importante: la parola stessa non va ripetuta.
Quindi, se il testo originale è
Ho trovato alloggio in una cittadina lungo il tragitto verso il posto di lavoro Il testo risultante dovrà essere
Ho trovato alloggio/casa/abitazione/dimora in una cittadina lungo il tragitto/percorso/cammino/viaggio/strada/itinerario verso il posto di lavoro/impegno/occupazione
NOTE:
- si assuma che il testo originale non contenga simboli di interpunzione - gli “a capo” non sono significativi
- si assuma che il dizionario dei sinonimi contenga declinate esplicitamente tutte le forme verbali, singolari e plurali, maschili e femminili. Quindi è sufficiente controllare la corrispondenza esatta di ciascun termine del testo con i termini nel dizionario.
Si scriva un programma in linguaggio C che riceva sulla linea di comando il nome del file contenente il dizionario dei sinonimi, il nome del file contenente il testo originale e il nome del file di uscita. Il programma deve scrivere nel file di uscita il testo originale modificato come sopra descritto.
Esercizio 2 (13 punti)
Una matrice quadrata di valori reali di dimensione n×n (detta, anche, di ordine n) è detta sparsa quando il numero di valori diversi da zero presenti nella matrice stessa sono dell’ordine di O(n) invece che O(n2). In altre parole, una matrice è sparsa quando è costituita da pochi valori diversi da zero. Ad esempio, le seguenti matrici sono sparse:
Un modo compatto per rappresentare una matrice sparsa è attraverso una sequenza di triple che indicano (i) le coordinate matriciali (ovvero gli indici i, j) dei valori diversi da zero e (ii) il valore (diverso da zero) contenuto nell’elemento con quelle coordinate.
Ad esempio, la matrice A riportata in precedenza può essere rappresentata dalla seguente sequenza di triple ,
, , , , .
Si vuole definire una struttura dati in grado di rappresentare una matrice sparsa attraverso la sequenza dei suoi elementi diversi da zero come appena descritto.
Si definisca un descrittore matrice_sparsa per la struttura dati e le eventuali strutture ausiliarie, qualora necessarie, per implementare la rappresentazione descritta.
Inoltre, la struttura dati deve supportare le seguenti operazioni, delle quali si chiede l’implementazione in linguaggio C:
• matrice_sparsa crea_matrice_sparsa(int n) che crea una matrice sparsa di ordine n “costituita” da soli zeri
• void imposta_elemento(matrice_sparsa* A, int i, int j, float v) che imposta l’elemento di coordinate (i, j) della matrice A al valore v (ovviamente v può anche assumere il valore 0.0 e in tal caso la
rappresentazione deve rimanere coerente con l’impostazione dell’elemento a tale valore);
• matrice_sparsa somma_matrici(matrice_sparsa A, matrice_sparsa B) che date due matrici A e B restituisce il contenuto di una terza matrice C che conterrà la somma di A e B; si ricorda che gli elementi c(i, j) della matrice risultato sono calcolati come somma degli elementi a(i, j) e b(i, j) di coordinate corrispondenti;
• void elimina_matrice_sparsa(matrice_sparsa* A) che elimina le eventuali strutture dati dinamiche utilizzate nella rappresentazione della matrice A.
Si discuta, informalmente, la complessità computazionale delle suddette operazioni espressa in termini di m, numero di
elementi diversi da zero presenti nella matrice (alternativamente m sarà anche la lunghezza della sequenza di rappresentazione).
Nel caso della funzione somma_matrici() si esprima la complessità in termini di mA e mB, numero di elementi diversi da zero, rispettivamente delle matrici A e B.
Suggerimento: prima di iniziare ad implementare la funzione somma_matrici() si scrivano (e si analizzino) anche le rappresentazioni delle sequenze delle matrici B e C.
Esercizio 3 (5 punti)
Scrivere una funzione in linguaggio C verifica_bilanciamento_grado(g) che, dato un grafo diretto g verifica che, per ciascun nodo del grafo, il grado entrante nel nodo e il grado uscente da siano uguali. Qualora tale condizione fosse soddisfatta la funzione dovrà restituire il valore booleano true, in caso contrario la funzione dovrà restituire il valore false.
Suggerimento: la rappresentazione del grafo (a liste di adiacenza o a matrice di adiacenza) può dare luogo a due soluzioni di difficoltà diversa, si valuti attentamente la scelta del tipo di rappresentazione utilizzata.
