PROBLEMA Algoritmi e Strutture Dati

[IlGattoNero1921]

Buongiorno, sto preparando in questo periodo l'esame di algoritmi. Non avendo potuto seguire a causa di alcuni problemi di salute mi trovo in una situazione particolare. Ho una buona preparazione a livello teorico fra appunti di alcuni colleghi e compagni ma non ho alcuna dispensa a livello di esame scritto. Allego una traccia d'esame nello spoiler.

Spoiler

Un’agenzia governativa sanitaria vuole realizzare un sistema che permetta di studiare la possibile diffusione di una malattia contagiosa in un insieme di persone sotto osservazione. Il contagio può avvenire solo in presenza di contatti diretti tra le persone e, per via dell’incubazione, anche persone apparentemente sane possono contagiare altre persone. Le persone sono individuate univocamente dal loro codice fiscale, e sono caratterizzate da nome, cognome, età, genere, anamnesi. L’anamnesi di una persona è una lista di patologie che si sono presentate nel passato nella storia di questa. Il sistema deve rappresentare i contatti diretti che sono avvenuti tra le persone distinguendo se vi è stato un unico contatto, molteplici contatti o nessuno.

Si rappresenti la situazione sopra descritta, supposta a regime (il candidato non si deve occupare quindi dell’inizializzazione). Il candidato deve, inoltre, implementare i seguenti metodi e valutarne la complessità computazionale:

1) metodo m1 (inserisci contatto), che riceve due persone e incrementa di uno il numero di contatti diretti avvenuti tra queste persone.

2) metodo m2 (possibile contagio), che riceve due persone A e B e restituisce vero se è possibile che, anche per via indiretta e cioè attraverso altre persone, è possibile che B sia stata contagiata da A (supposta affetta dalla malattia).

3) metodo m3 (contatti diretti) che riceve una persona A e il nome di una patologia P e restituisce la lista delle persone che hanno avuto contatti diretti con A e che hanno P nella loro anamnesi.

4) metodo m4 (max_contatti_multipli) che riceve due persone A e B e restituisce una sequenza di persone che costituiscono un percorso di contatti diretti tra A e B che massimizzi i contatti molteplici. Per esempio, se tra A e B esistono solo due percorsi, il primo costituito da <A,C,B> il secondo da <A,D,B>, e si suppone che tra A e C, tra C e B e tra D e B ci sia stato un unico contatto, mentre tra A e D ci sono stati molteplici contatti, allora il metodo dovrebbe restituire il percorso <A,D,B> che include 1 contatto multiplo mentre il percorso <A,C,B> non ne include alcuno.

La parte scritta deve essere fatta interamente in Java, vi vorrei chiedere se potreste indirizzarmi sulle parti da studiare e se avete qualche dispensa ve ne sarei grato. Ho allegato l'esame solo per potervi far capire una traccia d'esame.

 

[BAT]

Parte di Java di tipo "imperativo" (in senso lato), ossia una specie di traduzione in Java dei fondamenti di programmazione che dovresti già conoscere da corsi precedenti, ossia:
tipi primitivi (interi, virgola mobile, booleani, caratteri), stringhe, commenti, istruzioni condizionali (if/if-else, switch), cicli (for,while,do), variabili (dichiarazione, inizializzazione scope o campo d'azione), costanti, operatori aritmetici/logici/relazionali lettura dell'input, stampa dell'output,
funzioni/metodi statici + passaggio di parametri, array monodimensionali e bidimensionali, ricorsione.
Fondamenti di programmazione a oggetti: concetto di classe, attributi e metodi, ereditarietà, polimorfismo, overriding ed overloading di metodi, concetto di interfaccia, la classe ArrayList. Fondamenti di gestione delle eccezioni.
Non è necessario studiare argomenti avanzati a meno che il tuo corso non lo preveda (per es. i generics). Poi immagino che dovrai imparare a definire da te strutture dati fondamentali come liste, pile, code, grafi (senza usare quelle già integrate nel linguaggio, a meno che non sia consentito).
A occhio e croce per la traccia che hai postato ti servono come minimo matrici (con cui rappresentare grafi) e liste (per cui potrebbe essere sufficiente arraylist). Comunque in genere online sul sito del tuo corso dovresti reperire tracce (ed eventuale soluzione) dei compiti passati (ti suggerisco caldamentie di recuperarli, ci sarà sicuramente qualche tuo collega che ce l'ha).

 

[IlGattoNero1921]

Parte di Java di tipo "imperativo" (in senso lato), ossia una specie di traduzione in Java dei fondamenti di programmazione che dovresti già conoscere da corsi precedenti, ossia:
tipi primitivi (interi, virgola mobile, booleani, caratteri), stringhe, commenti, istruzioni condizionali (if/if-else, switch), cicli (for,while,do), variabili (dichiarazione, inizializzazione scope o campo d'azione), costanti, operatori aritmetici/logici/relazionali lettura dell'input, stampa dell'output,
funzioni/metodi statici + passaggio di parametri, array monodimensionali e bidimensionali, ricorsione.
Fondamenti di programmazione a oggetti: concetto di classe, attributi e metodi, ereditarietà, polimorfismo, overriding ed overloading di metodi, concetto di interfaccia, la classe ArrayList. Fondamenti di gestione delle eccezioni.
Non è necessario studiare argomenti avanzati a meno che il tuo corso non lo preveda (per es. i generics). Poi immagino che dovrai imparare a definire da te strutture dati fondamentali come liste, pile, code, grafi (senza usare quelle già integrate nel linguaggio, a meno che non sia consentito).
A occhio e croce per la traccia che hai postato ti servono come minimo matrici (con cui rappresentare grafi) e liste (per cui potrebbe essere sufficiente arraylist). Comunque in genere online sul sito del tuo corso dovresti reperire tracce (ed eventuale soluzione) dei compiti passati (ti suggerisco caldamentie di recuperarli, ci sarà sicuramente qualche tuo collega che ce l'ha).

Ciao, scusa per il ritardo. In ogni caso il mio problema principale è la parte degli esercizi a livello di teoria posso compensare attraverso i libri ed alcuni appunti. Mentre per quanto riguarda esercizi non ne abbiamo nessuno di risolto(abbiamo solo alcune tracce). Se riuscissi a mandarmi delle dispense te ne sarei grato. Ho provato a fare il metodo 1 ma non ho ben capito come utilizzare DirectedSparseGraph,DirectedWeightedSparseGraph,UndirectedSparseGraph. E pensavo di risolvere il primo tramite questo metodo che ho trovato nelle librerie:

public boolean addEdge(V v1, V v2) {
Collection<V> coll = new ArrayList<>(2);
coll.add(v1);
coll.add(v2);
return graph.addEdge(new Object(), coll);    }

 

[BAT]

Non ho dispense da darti: Java l'ho studiato da solo. La classe per grafi sparsi a cui ti riferisci non mi risulta far parte del linguaggio (almeno fino a Java 8); suppongo che sia una libreria esterna. D'altra parte durante il corso di algoritmi e strutture dati ti avranno sicuramente insegnato a rappresentare i grafi (normalmente con le matrici) e avranno sicuramente fatto alcuni algoritmi base (per esempio cammini minimi con l'algoritmo di Dijkstra, abbastanza semplice quando il grafo è rappresentato da sole matrici numeriche).
Ma se non conosci le basi del linguaggio non ti puoi avventurare a fare esercizi su algoritmi e strutture dati, finisce che non riesci neanche a compilare.
Rifatti velocemente in Java un po' di esercizi di programmazione di base, di quelli che avrai fatto nel corso base di programmazione, ti serve a prendere confidenza col linguaggio. Penso che ti basterebbe una settimana, perché immagino che tu sappia già come programmare.
Solo dopo prova ad implementare da te qualche struttura dati semplice come lista, pila, coda e alberi binari: se le hai già fatte in uno tra C/C++/Pascal/Python sei in grado di implementarle in Java. Questo ti servirà a prendere confidenza con gli oggetti.
Gli esercizi d'esame li devi fare per ultimi.