SoloDIAG

III Anno - BIAR => Corsi della triennale non più erogati => Fondamenti di Informatica II (fino A.A. 2013/14) => Topic aperto da: roberto93 - Mer 12 Aprile, 12:53:10 - 2017

Titolo: Nuova modalità esame
Inserito da: roberto93 - Mer 12 Aprile, 12:53:10 - 2017
Salve, ho letto sul sito del prof che da giugno 2017 cambieranno le modalità d'esame,
qualcuno sa in cosa consisterà questa nuova modalità?

grazie
Titolo: Re:Nuova modalità esame
Inserito da: LucaLindholm - Mer 12 Aprile, 16:42:02 - 2017
Bel mistero... me lo chiedevo anch'io.

Forse lo scriverà quando pubblicherà il risultato del compito di qualche giorno fa...
Titolo: Re:Nuova modalità esame
Inserito da: gargamella - Mer 12 Aprile, 17:15:33 - 2017
A ricevimento ha detto che ci sarà una parte al calcolatore, che fungerà da pretest, la parte dell'algoritmo. Se non compila si va a casa, poi ci sarà il restante scritto come al solito. Per chi dovrà fare la parte di modelli, presumibilmente sarà fatta in un'altra data. Comunque è ancora in working progress
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mer 12 Aprile, 22:32:54 - 2017
Se dovesse decidere di cambiare in questo modo l'esame, scusate ma il professore nn sta bene cor cervello. Già questo esame è tosto, in più ci mette la prova al calcolatore!!!Per me è assurdo. Non sarebbe meglio lasciare tutto com'è, o ancora meglio togliere il pretest o cose simili?
Titolo: Re:Nuova modalità esame
Inserito da: roberto93 - Mer 12 Aprile, 22:57:13 - 2017

se mette la prova al calcolatore in C poi.... voglio ridere

st'esame diventerà ancora peggio di quello che è
Titolo: Re:Nuova modalità esame
Inserito da: john - Gio 13 Aprile, 01:08:12 - 2017
Magari possiamo fare una richiesta al prof di mantenere la stessa modalità per noi del vecchio ordinamento. Alla fine noi del vecchio siamo un suo incubo.  :asd:  Penso o almeno spero che non vede l'ora che ci leviamo di torno  :asd:

Per quanto riguarda il pretest della nuova modalità, beh tocca vedere come sarà questo esercizio al calcolatore. Se la prova è come quella di ingegneria degli algoritmi del Demetrescu, allora sono cavoli nostri  :'( :'( :'(
Ingegneria degli algoritmi è stato uno dei corsi che più mi ha appassionato, ma comunque l'esame sempre tosto. 
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Gio 13 Aprile, 09:46:06 - 2017
Ma infatti sarebbe meglio che chi è vecchio ordinamento = vecchia modalità esame chi nuovo ordinamento = nuova modalità.

L'unica cosa positiva sarebbe fare algoritmi e modelli in due giorni diversi. Che calvario sto esame  :'( :'(
Titolo: Re:Nuova modalità esame
Inserito da: john - Gio 20 Aprile, 10:57:39 - 2017
Sono usciti i risultati dei laureandi, mamma mia una strage, solo 2/9 hanno superato l'esame e con 18  ??? ???
Qualcuno di voi ha il testo di algoritmi e modelli?
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Gio 20 Aprile, 11:08:43 - 2017
Il testo di modelli è questo:

PROBLEMA 1 (3+3+2+2 punti)

(a) Definire concetto di ASFD e ASFND, prestando particolare attenzione alla caratterizzazione della funzione di transizione, in termini di dominio e codominio.

(b) Spiegare perchè, dato un ASFND, ne esiste sempre (almeno) uno deterministico ad esso equivalente

(c) Assumendo AlfInput = {0,1}, disegnare i grafi degli ASFD che riconoscono i seguenti linguaggi: A ={} (linguaggio vuoto), L1=0*+1,
L2= {epsilon, 1}, L3 = AlfInput+

(d) Dato un ASFD A, quanti sono i differenti ASFD equivalenti ad A? Spiegare.

PROBLEMA 2 (5 punti)

Dimostrare che il linguaggio L = {anbn+1 | n>2} è di tipo 2

PROBLEMA 3 (6 punti)

Qual'è la categoria di linguaggi riconosciuti da una MdT dotata di nastro bidimensionale?(Immaginare il nastro come una matrice infinita, ad ogni mossa il movimento della testina appartiene all'insieme {immobile, nord, sud, est, ovest}).

PROBLEMA 4 (5 punti)

(a) Definire il problema di decisione Vertex Cover(VC) e dimostrare che esso appartiene alla classe NP

(b) Disegnare a piacere due grafi G1 e G2 entrambi connessi e di 6 nodi, tali che:
      -   VC con input (G1, 2) ha soluzione positiva (evidenziare il cover)
      -   VC con input (G2, 3) ha soluzione negativa (spiegare perché non esiste un cover di cardinalità non superiore a 3).

PROBLEMA 5 (2+4 punti)
Con riferimento al calcolo proposizionale:

(a) Definire il concetto di insieme completo di connettivi logici.
(b) Dimostrare che l'insieme {and, not} è completo.

Algoritmi invece è questo:

PROBLEMA 1 Analisi algoritmo [(a) 6/30, (b) 3/30]
Si considerino i metodi java di seguito illustrati:

Codice: [Seleziona]
// a è ordinato in modo non decrescente
static int findIt(int[] a, int k) {
    return findIt(a, k, 0, a.length-1);
}

static int findIt(int[] a, int k, int start, int end) {
    if(start > end) return -1;
    if( (k < a[start]) || (k > a[end]) ) return -1;
    if( (start == end) || (a[start] == a[end]) )
        if(a[start] == k ) return start;
        else return -1;
    //interpolazione lineare
    double slop = (double) (a[end] - a[start]) / (end -start);
    int m = (int) ((k-a[start]) / slope+.5);
    if( m < start ) m = start;
    if( m > end ) m = end;
    if( a[m] == k ) return m;
    else if( a[m] > k) return findIt(a, k, start, m-1);
    else return findIt(a, k, m+1, end);
}

Sviluppare, argomentando adeguatamente (il 50% del punteggio dell'esercizio sarà sulle argomentazioni adottate):

(a) Determinare costo asintotico di findIt(int[], int) in funzione della dimensione dell'input.
(b) Stimare informalmente in quali casi findIt si comporta meglio della ricerca binaria.

PROBLEMA 2 Progetto algoritmo C/Java [8/30]
Progettare un algoritmo (Java o C) che, dati in input un BST (chiavi int) di n > 0 elementi e un intero positivo k (1< k < n), determini e restituisca la k-esima chiave presente nel BST.

N.B. Codice non indentato penalizzazione 20%.

PROBLEMA 3 Open Addressing [5/30]
Con riferimento alla famiglia di tecniche per la risoluzione delle collisioni in una tavola hash denonminata open addressing (indirizzamento aperto), spiegare quali tecniche siano affette dal problema del clustering primario e quali dal problema del clustering secondario.(N.B. Clustering primario e secondario vanno definiti).

PROBLEMA 4 Problemi su grafi [(a) 4/30; (b) 4/30; (c) 4/30]
Con riferimento alla rappresentazione di grafi semplici basata su matrice di adiacenza, progettare algoritmi in pseudo-codice atti a risolvere i problemi seguenti con i relativi costi computazionali.
N.B. Codice non indentato penalizzazione 20%.

(a) Un grafo bipartito è un grafo semplice G= (V,E) in cui V è l'unione di due insiemi disgiunti V1 e V2 e per ciascun arco {u, v} ͼ E risulta u ͼ V1 Λ v ͼ V2 oppure u ͼ V2 Λ v ͼ V1. Scrivere un algoritmo che, data la matrice di adiacenza di un grafo semplice G, verifichi che G è bipartito.

(b) Scrivere un algoritmo che, data la matrice di adiacenza di un grafo semplice G, verifichi se G è connesso.

(c) Scrivere un algoritmo che, data la matrice di adiacenza di un grafo semplice G, verifichi che se G contiene K3 (grafo completo di tre nodi) come sottografo.

Ecco l'appello straordinari di aprile ed in tutto questo il prof ha avuto il coraggio di dire che il compito era "facile", secondo lui ovviamente.   
Titolo: Re:Nuova modalità esame
Inserito da: StudenteLavoratore - Gio 20 Aprile, 15:10:30 - 2017
Salve ragazzi,

Ho letto con attenzione il post. Io sono di sistemi informatici e lavoro. Per me sarebbe davvero difficoltoso sostenere l'esame nella nuova modalità ( figuriamoci usando c ).

Se malauguratamente dovesse andare in porto questa cosa sarei favorevole a creare una delegazione di quelli dell'ordinamento precedente e chiedere al prof di poter sostenere l'esame con le consuete modalità.

Io non seguo le lezioni quindi non so cosa dirà il prof in tempo reale. Qualcuno può tenermi aggiornato cortesemente?

Ringrazio tutti :)
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Gio 20 Aprile, 16:30:01 - 2017
A lezione il prof non ha detto nulla a riguardo. Solo la prima lezione del corso disse che avrebbe voluto cambiare la modalità d'esame ma nn sapeva ancora in che modo. Da allora tutto tace. Ma vista la proposta sarebbe meglio che cambi idea perché è una cosa assurda
Titolo: Re:Nuova modalità esame
Inserito da: StudenteLavoratore - Ven 21 Aprile, 09:34:03 - 2017
A lezione il prof non ha detto nulla a riguardo. Solo la prima lezione del corso disse che avrebbe voluto cambiare la modalità d'esame ma nn sapeva ancora in che modo. Da allora tutto tace. Ma vista la proposta sarebbe meglio che cambi idea perché è una cosa assurda

A quella lezione c'ero poi dopo un paio di lezioni non ho potuto più seguire perché la mattina devo lavorare. Se tu segui le lezioni mi fai sapere ?

Comunque hai ragione e dovremmo farci sentire se cambiasse modalità. Anche perché il nostro manifesto sta strutturato differentemente e persino il libro di testo usa Java per la parte di implementazione degli algoritmi. Ad ogni modo non si possono cambiare le carte in tavola così. Come pare si sia fatto per reti di calcolatori ( che ancora devo sostenere ) ...
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Ven 21 Aprile, 09:38:10 - 2017
Ok ti faccio sapere nel caso ci siano novità 😀
Titolo: Re:Nuova modalità esame
Inserito da: StudenteLavoratore - Ven 21 Aprile, 09:46:46 - 2017
Gentilissimo scheggia.

Titolo: Re:Nuova modalità esame
Inserito da: john - Ven 21 Aprile, 10:45:47 - 2017
A lezione il prof non ha detto nulla a riguardo. Solo la prima lezione del corso disse che avrebbe voluto cambiare la modalità d'esame ma nn sapeva ancora in che modo. Da allora tutto tace. Ma vista la proposta sarebbe meglio che cambi idea perché è una cosa assurda

A quella lezione c'ero poi dopo un paio di lezioni non ho potuto più seguire perché la mattina devo lavorare. Se tu segui le lezioni mi fai sapere ?

Comunque hai ragione e dovremmo farci sentire se cambiasse modalità. Anche perché il nostro manifesto sta strutturato differentemente e persino il libro di testo usa Java per la parte di implementazione degli algoritmi. Ad ogni modo non si possono cambiare le carte in tavola così. Come pare si sia fatto per reti di calcolatori ( che ancora devo sostenere ) ...

Tienici aggiornati Scheggia89, neanch'io frequento le lezioni per questioni lavorative. Concordo con StudenteLavoratore sul creare la delegazione. Speriamo il prof ci ripensi che sennò per noi sarà un vero incubo.
Titolo: Re:Nuova modalità esame
Inserito da: StudenteLavoratore - Ven 21 Aprile, 11:15:32 - 2017
Tienici aggiornati Scheggia89, neanch'io frequento le lezioni per questioni lavorative. Concordo con StudenteLavoratore sul creare la delegazione. Speriamo il prof ci ripensi che sennò per noi sarà un vero incubo.

Dovrebbe anche essere questione di buon senso. Noi la prova al PC la abbiamo sostenuta per il vecchio progettazione del sw studiando cose inutili su awt e swing. Il nostro f2 è diverso e prevede 6 CFU di modelli non paragonabili con la parte di modelli sostenuta nel loro f1. Direi che dovessimo svolgere l'esame nuovo solo la parte di algoritmi diventerebbe per carico di studi un esame da 10 CFU. E la cosa non mi pare per nulla giusta.
Titolo: Re:Nuova modalità esame
Inserito da: john - Mar 02 Maggio, 13:52:18 - 2017
Dovrebbe anche essere questione di buon senso. Noi la prova al PC la abbiamo sostenuta per il vecchio progettazione del sw studiando cose inutili su awt e swing. Il nostro f2 è diverso e prevede 6 CFU di modelli non paragonabili con la parte di modelli sostenuta nel loro f1. Direi che dovessimo svolgere l'esame nuovo solo la parte di algoritmi diventerebbe per carico di studi un esame da 10 CFU. E la cosa non mi pare per nulla giusta.

Sono d'accordo. Vediamo, ma ci sono novità al riguardo? Sono uscite le date dei prossimi appelli, il prossimo è tipo il primo giugno  :-\  :sisi:
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mar 02 Maggio, 14:07:39 - 2017
A lezione non ha detto ancora nulla a riguardo
Titolo: Re:Nuova modalità esame
Inserito da: zeusm - Gio 04 Maggio, 12:41:10 - 2017
Mi intrometto chiedendovi se qualcuno ha risolto i seguenti esercizi di esame di modelli:

Citazione
Quali linguaggi potrebbero essere riconosciuti da una macchina di Turing deterministica a un
nastro, “ristretta” a poter utilizzare esclusivamente la porzione di nastro contenente l’input? (Non
vi sono altre limitazioni)
Discutere informalmente ma esaurientemente la capacità computazionale della macchina, il-
lustrando anche un esempio di linguaggio che non può essere riconosciuto da una tale tipologia
macchina

e

Citazione
Mostrare l’indecidibilità del problema di stabilire se, dati una macchina di Turing T, una stringa x e un simbolo σ, la macchina T avviata sull’input x scriverà mai sul nastro il simbolo σ (suggerimento: mostrare che una siffatta macchina potrebbe essere usata per decidere halting problem).
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Ven 05 Maggio, 11:10:22 - 2017
Oggi il prof ha spiegato la nuova modalità d'esame. Per prima cosa è confermato che algoritmi e modelli verranno svolti in giorni differenti. La parte di algoritmi si svolgerà in laboratorio e la durata passa da 2 ore a 4 ore. Per l'esercizio al calcolatore, in pratica lui propone delle funzioni che risolvano un qualche cosa e noi dobbiamo implementare un  algoritmo che lo risolva. In pratica, da come ho capito io, non funge da pretest ma corrisponderebbe al problema 2 dei testi d'esame degli anni passati. Gli altri problemi saranno come al solito su analisi di costo grafi e teoria. Gli altri problemi si possono svolgere​ su carta o scrivendo su file di testo. Si può usare o Java o C come si preferisce. Spero di essere stato il più chiaro possibile su quello che ha detto il prof
Titolo: Re:Nuova modalità esame
Inserito da: LucaLindholm - Ven 05 Maggio, 12:08:10 - 2017
Beh, non è poi tanto male, se consideriamo che ora Algoritmi e Modelli si svolgeranno in due giorni differenti.

Mmh... però mi fa pensare il fatto che il tempo passi da due a quattro ore...
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Ven 05 Maggio, 12:45:46 - 2017
Inoltre ha detto anche che, se riesce, il prof proverà a mettere sul sito del corso un esempio di come sarà l'esame di algoritmi. Per le 4 ore  penso che sia meglio, ti dà più tempo su come risolvere l'esercizio al calcolatore.   
Titolo: Re:Nuova modalità esame
Inserito da: john - Ven 05 Maggio, 14:48:22 - 2017
La prova al calcolatore non farà da pretest, quindi il pretest ci sarà ancora? o saranno solo le prove di algoritmi e modelli?
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Ven 05 Maggio, 15:14:15 - 2017
Non lo ha detto esplicitamente, non posso affermarlo con certezza, ma credo che a questo punto il pretest sia abolito. Ci saranno solo prove di algoritmi e modelli in date differenti.
Titolo: Re:Nuova modalità esame
Inserito da: john - Ven 05 Maggio, 15:48:00 - 2017
Speriamo allora, perchè se sarà così allora secondo me sarà un punto a nostro favore, dato che il pretest era abbastanza rognoso.
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Ven 05 Maggio, 15:54:06 - 2017
Eh si speriamo, tanto pignolo come è presto metterà anche sul sito del corso, la nuova modalità d'esame ma da quello che ho capito sentendolo parlare a lezione, sono fiducioso sul fatto che il pretest non ci sia più :D :D
Titolo: Re:Nuova modalità esame
Inserito da: john - Ven 05 Maggio, 16:18:03 - 2017
Comunque il "problema 2 dei testi d'esame degli anni passati" era solitamente sugli alberi e i loro vari tipi di attraveramento. Vediamo, Speriamo il prof metta un esempio di come sarà l'esame, così ci possiamo più o meno regolare.
Comunque, se si conferma che il pretest è abolito penso non sarà tanto male, anche se da 2 a 4 ore di esame in laboratorio, beh mi fa pensare che l'algoritmo da risolvere al calcolatore non sarà sicuramente una passeggiata :sisi: :sisi: :sisi: :sisi: :asd: :asd: :asd: :asd:
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Sab 06 Maggio, 21:50:45 - 2017
Il prof ha aggiornato il sito spiegando la nuova modalità di esame. In sostanza è quello che vi ho detto in una risposta precedente, il pretest è abolito, l'esame durerà tra le tre e le cinque ore. Cmq per tutte le info andate sul sito  ;) :)
Titolo: Re:Nuova modalità esame
Inserito da: john - Dom 07 Maggio, 15:04:43 - 2017
Si si allora è ufficiale, il pre test è stato abolito. Secondo me è meglio così, il pretest era rognoso  :sisi:
Magari scheggia89 tu che frequenti, e anche gli altri ragazzi che frequentano le lezioni potreste spingere per far pubblicare al prof un esempio di esame. Grazie scheggia89  :P
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Dom 07 Maggio, 15:37:13 - 2017
C'è già stato qualche ragazzo che venerdì mentre spiegava le modalità aveva chiesto di fare simulazione nelle ore dedicate al laboratorio il martedì, ma per mancanza di tempo il prof ha detto che non è possibile causa primo appello troppo a ridosso della fine delle lezioni. Cmq ha detto che proverà a pubblicare sul sito un esempio d'esame con nuova modalità
Titolo: Re:Nuova modalità esame
Inserito da: Cadarn - Mar 09 Maggio, 18:47:43 - 2017
Non ho ben capito in cosa consiste questa prova al calcolatore, in pratica lui ci da delle funzioni e noi dobbiamo integrarle in un algoritmo per far girare il tutto?
E i laboratori come funzionano? Non ci ho ancora mai messo piede  :asd:
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mar 09 Maggio, 20:32:54 - 2017
In parole spicciole, è simile a come era strutturato prima con la differenza che c'è una parte da svolgere al calcolatore.Credo sia sempre di progettare un algoritmo che faccia un qualcosa richiesto dal prof. Le altre domande saranno sempre su analisi costo algoritmo grafi e domande teoriche che puoi svolgere su carta o sul PC con un file di testo.il laboratorio funziona che il martedì c'è, vai e svolgo l'esercitazione :)
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mer 17 Maggio, 08:35:33 - 2017
Il prof ha fatto alcune precisazioni per l'esame: modelli​ e algoritmi possono essere svolti in appelli differenti e, dico io purtroppo, il 50% della prova al calcolatore è la condizione necessaria per il passaggio dell'intero esame di algoritmi e non per il singolo esercizio
Titolo: Re:Nuova modalità esame
Inserito da: john - Mer 17 Maggio, 09:25:35 - 2017
Si si l'ho letto sul sito del prof proprio ieri. Ma magari il prof mettesse un modello di esame così non andiamo alla cieca. Sarebbe un'ottima cosa.
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mer 17 Maggio, 10:36:01 - 2017
Il prof ha detto che venerdì distribuirà un testo d'esame. Presumo sarà un fac-simile dell'esame nella nuova modalità. Dico presumo perché non ha specificato se lo sia o meno. Nel caso lo fosse, se non lo mette su sito, lo posterò io nel caso
Titolo: Re:Nuova modalità esame
Inserito da: LucaLindholm - Mer 17 Maggio, 15:10:06 - 2017
Il prof ha fatto alcune precisazioni per l'esame: modelli​ e algoritmi possono essere svolti in appelli differenti e, dico io purtroppo, il 50% della prova al calcolatore è la condizione necessaria per il passaggio dell'intero esame di algoritmi e non per il singolo esercizio

Perfetto il fatto di poter svolgere le due parti in due appelli differenti!

Questo fatto compensa ampiamente il fatto che la prova al calcolatore sia più tosta.

;)
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mer 17 Maggio, 16:10:59 - 2017
Secondo me non lo compensa, perché algoritmi già era di per sè tosto. Ma tanto questa è la situazione e non si può fare altrimenti  :)
Titolo: Re:Nuova modalità esame
Inserito da: john - Gio 18 Maggio, 10:04:13 - 2017
Secondo me non lo compensa, perché algoritmi già era di per sè tosto. Ma tanto questa è la situazione e non si può fare altrimenti  :)


Concordo con scheggia89.
Poi ho visto sul google calendar del Prof che l'esame l'ha spostato al 12 giugno e il primo ci sta tipo una simulazione di esame. Potresti confermare questa cosa scheggia89? Grazie in anticipo  :asd: :asd:

Ah dimenticavo, scheggia89 ma venerdì a che ora ce sta lezione, e soprattutto dove? >:D  Perchè ci sto facendo un pensiero di venire per questo testo d'esame. Ma vorrei sapere l'orario appunto per organizzarmi  :P
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Gio 18 Maggio, 10:41:15 - 2017
Si è confermato che l'esame è stato spostato il 12 giugno, lo ha detto il professore. Ho letto anche io su google calendar della simulazione del 1 giugno, ma su questo il professore non ha detto nulla se si fà o meno. Lezione inizia alle 8 in aula 1 del dipartimento di chimica alla città universitaria. In pratica entri in città universitaria a via de lollis e subito a sinistra. Ti ricordo che non sono per niente sicuro se il testo d'esame che distribuirà venerdì sia un fac-simile dell'esame nella nuova modalità, é solo una mia supposizione, niente di più. :) :)
Titolo: Re:Nuova modalità esame
Inserito da: john - Gio 18 Maggio, 12:58:11 - 2017
VAbbè in ogni caso potrebbe essereci utile, vediamo se riesco a venire  :asd:  >:( In ogni caso Scheggia ci faresti un grandissimo favore se lo pubblichi, ti saremo eternamente grati  :P
Titolo: Re:Nuova modalità esame
Inserito da: girl8x - Gio 18 Maggio, 15:48:39 - 2017
Il prof ha fatto alcune precisazioni per l'esame: modelli​ e algoritmi possono essere svolti in appelli differenti e, dico io purtroppo, il 50% della prova al calcolatore è la condizione necessaria per il passaggio dell'intero esame di algoritmi e non per il singolo esercizio

Quindi significa che per esempio a giugno si può fare solo una parte e poi a luglio o altro appello (per massimo sei appelli) si può fare l'altra parte? O ci si deve presentare obbligatoriamente ad entrambe nello stesso appello?
Titolo: Re:Nuova modalità esame
Inserito da: StudenteLavoratore - Gio 18 Maggio, 17:26:07 - 2017
Secondo me non lo compensa, perché algoritmi già era di per sè tosto. Ma tanto questa è la situazione e non si può fare altrimenti  :)

Posso chiedere in che senso si sta assumendo che L esame diventerà ancora più "tosto" di quello che era ?

Ma il prof ha intenzione di aggiornare il sito fornendo esempi di prove di esame ?
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Gio 18 Maggio, 19:40:46 - 2017
Quindi significa che per esempio a giugno si può fare solo una parte e poi a luglio o altro appello (per massimo sei appelli) si può fare l'altra parte? O ci si deve presentare obbligatoriamente ad entrambe nello stesso appello?
Si significa proprio questo. Puoi decidere di fare algoritmi a giugno e modelli a luglio o viceversa. Il prof terrá i risultati per almeno un anno
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Gio 18 Maggio, 20:32:48 - 2017
Posso chiedere in che senso si sta assumendo che L esame diventerà ancora più "tosto" di quello che era ?

Ma il prof ha intenzione di aggiornare il sito fornendo esempi di prove di esame ?
Già solo il fatto che il passaggio dell'esame è vincolato alla prova al calcolatore,nel senso che bisogna fare almeno il 50% per superarlo. Cioè se ad esempio faccio perfetto analisi costo e grafi e magari sbaglio a fare la parte al pc, perdo l'intero esame. Secondo me è sbagliata come cosa
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Ven 19 Maggio, 08:44:44 - 2017
Il prof intende fare la simulazione il 1 giugno ma è da confermare perché devono verificare disponibilità laboratorio e che la simulazione funzioni. Bisogna tenere d'occhio il calendario. Il testo d'esame che voleva distribuire oggi lo metterà sul sito stasera o domani mattina
Titolo: Re:Nuova modalità esame
Inserito da: john - Ven 19 Maggio, 11:02:56 - 2017
Grazie Scheggia di ternerci aggiornati. Ti devo il caffè  :asd:
 Io purtroppo non sono riuscito a venire oggi  :'( :'(  speriamo si confermi la simulazione perchè andare a fare l'esame alla cieca non è il massimo. Già algoritmi è tosto pensa ora con la nuova modalità come sarà.
Quindi oggi non ce l'ha fatta a distrbuirlo il testo? Comunque si si, terrò d'occhio anche il sito del prof.
Grazie Scheggia.
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Ven 19 Maggio, 11:45:37 - 2017
Grazie Scheggia di ternerci aggiornati. Ti devo il caffè  :asd:
 Io purtroppo non sono riuscito a venire oggi  :'( :'(  speriamo si confermi la simulazione perchè andare a fare l'esame alla cieca non è il massimo. Già algoritmi è tosto pensa ora con la nuova modalità come sarà.
Quindi oggi non ce l'ha fatta a distrbuirlo il testo? Comunque si si, terrò d'occhio anche il sito del prof.
Grazie Scheggia.
Non è riuscito a completarlo in tempo e quindi non è riuscito a distribuirlo oggi, la completerà e pubblicherà sul sito stasera o domani  mattina. Inoltre vorrebbe che la svolgessimo e discuterne la soluzione a lezione il mercoledì. Sulla simulazione ha detto che non riesce al momento a farla funzionare come dovrebbe ma conta di riuscirci.
Titolo: Re:Nuova modalità esame
Inserito da: girl8x - Ven 19 Maggio, 19:17:51 - 2017
Ragazzi invece la prova di modelli è strutturata allo stesso modo ? Perché ho letto sul sito del prof che dura 120 minuti quindi un po' di più rispetto a prima...vuol dire che c'è qualcosa in più?
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Ven 19 Maggio, 19:35:28 - 2017
Ho notato solo ora che la prova di modelli dura 120 minuti e non più 90. Sinceramente non sò se ci sia qualcosa in più. Il professore non ha detto niente riguardo a questo.
Titolo: Re:Nuova modalità esame
Inserito da: john - Sab 20 Maggio, 09:34:39 - 2017
Eh pure io, speriamo di no comunque.  :-\ :-\
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Lun 22 Maggio, 09:41:52 - 2017
Il prof ha pubblicato sul sito il testo di esame che non è riuscito a consegnare venerdì scorso
Titolo: Re:Nuova modalità esame
Inserito da: CIP - Lun 22 Maggio, 10:00:43 - 2017
Il prof ha pubblicato sul sito il testo di esame che non è riuscito a consegnare venerdì scorso
Grazie della segnalazione!
Sul sito leggo che il prof. discuterà del testo d'esame in classe. Magari qualcuno riuscirebbe eventualmente a riportare gli argomenti discussi qui sul forum? sarebbe di grande aiuto anche e soprattutto se propone delle possibili soluzioni.
Purtroppo a causa del lavoro non mi è possibile seguire tale lezione :)
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Lun 22 Maggio, 11:36:04 - 2017
Grazie della segnalazione!
Sul sito leggo che il prof. discuterà del testo d'esame in classe. Magari qualcuno riuscirebbe eventualmente a riportare gli argomenti discussi qui sul forum? sarebbe di grande aiuto anche e soprattutto se propone delle possibili soluzioni.
Purtroppo a causa del lavoro non mi è possibile seguire tale lezione :)
Sì, verrà discusso a lezione il mercoledì, a cura degli studenti. Nel senso che vorrebbe che fossero gli studenti ad andare alla lavagna e proporre la soluzione che secondo loro è corretta e il prof, nel caso, intervenire.
Titolo: Re:Nuova modalità esame
Inserito da: john - Mar 23 Maggio, 07:07:40 - 2017
Allora, se questo è il fac simile dell'esame nella nuova modalità, allora non è cambiato molto.  :P :P :P
Comunque il secondo esercizio, che riguarda il progetto da sviluppare al calcolatore è un esercizio dell'appello di gennaio del 2016  :P Infatti l'ho fatto in cartaceo, ma non so se sia giusto, sicuramente no. A questo punto misa tanto che vengo mercoledì a lezione.
Titolo: Re:Nuova modalità esame
Inserito da: Ndre - Mar 23 Maggio, 09:50:21 - 2017
ma dove si trova questo testo d'esame? grazie
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mar 23 Maggio, 10:13:17 - 2017
Allora, se questo è il fac simile dell'esame nella nuova modalità, allora non è cambiato molto.  :P :P :P
Comunque il secondo esercizio, che riguarda il progetto da sviluppare al calcolatore è un esercizio dell'appello di gennaio del 2016  :P Infatti l'ho fatto in cartaceo, ma non so se sia giusto, sicuramente no. A questo punto misa tanto che vengo mercoledì a lezione.
Se fosse davvero così la prova di algoritmi al calcolatore all'esame sarebbe fantastico, ma sinceramente ci credo poco.  :) :)
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mar 23 Maggio, 10:14:40 - 2017
ma dove si trova questo testo d'esame? grazie
https://sites.google.com/a/dis.uniroma1.it/asd-sapienza/esame
Titolo: Re:Nuova modalità esame
Inserito da: Ndre - Mar 23 Maggio, 18:03:56 - 2017
grazie
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mer 24 Maggio, 09:49:17 - 2017
Il testo d'esame pubblicato dal prof è quello stile esame nella nuova modalità. Il problema 2 è tipicamente la parte da svolgere al calcolatore il cui bisogna "produrre" codice. Inoltre verrà fornito una serie di input per testare la soluzione e se necessario materiale aggiuntivo. Nell'esempio del testo d'esame pubblicato sul sito la parte di rappresentazione dell'albero te la dà già lui. Ha confermato inoltre che il 50% si riferisce al passaggio dell' intero esame perché ha detto che quest'anno vuole dare più importanza alla parte di scrivere codice. Altra precisazione, cio che viene scritto deve essere compilabile altrimenti la valutazione è 0%. La simulazione del primo giugno ancora da confermare.
Titolo: Re:Nuova modalità esame
Inserito da: zeusm - Mer 24 Maggio, 15:28:01 - 2017
Sono state date soluzioni di questo testo?
Nel problema 1 il costo mi viene O(n2) e operante in place
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mer 24 Maggio, 15:40:30 - 2017
Sono stati svolti i primi 2 problemi e nel terzo problema solo la parte dei costi e sono stati svolti dagli studenti. I rimanenti verranno svolti venerdì. Il primo è in pratica un insertion-sort ricorsivo che quindi ha costo THETA(n2). Sul secondo problema, parlo per me, non è che lo abbia capito molto putroppo. Da quel poco che ho capito bisogna fare una visita in postOrdine ma non ho ben capito in che modo. Sul terzo se riesco provo a postarla.
Titolo: Re:Nuova modalità esame
Inserito da: john - Mer 31 Maggio, 10:49:27 - 2017
Ragazzi ho visto sul sito che la simulazione di esame in laboratorio è stata confirmata per domani, io purtroppo non ce la faccio ad andarci. Qualcuno che ci va gentilmente può dopo la simulazione scrivere più o meno come si è svolto? Magari potrebbe scrivere come funziona e il testo che distribuirà per la simulazione.

Grazie in anticipo ragazzi.
Titolo: Re:Nuova modalità esame
Inserito da: LucaLindholm - Mer 31 Maggio, 18:55:34 - 2017
Neanch'io domani posso venire, per cui se poteste chiedere al professore di confermare la possibilità di poter dare le due parti d'esame in due appelli separati, sarebbe ottimo.

;)
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Gio 01 Giugno, 13:41:28 - 2017
Ragazzi ho visto sul sito che la simulazione di esame in laboratorio è stata confirmata per domani, io purtroppo non ce la faccio ad andarci. Qualcuno che ci va gentilmente può dopo la simulazione scrivere più o meno come si è svolto? Magari potrebbe scrivere come funziona e il testo che distribuirà per la simulazione.

Grazie in anticipo ragazzi.
Sono andato alla simulazione. In pratica viene fornito user e password per accedere al PC per la prova al calcolatore. Dopodiché si deve avviare la macchina virtuale e lì ci sarà una cartella esame dove verrà caricato il testo d'esame. Comunque appena torno a casa posto il testo della simulazione così vi rendete conto di come è.
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Gio 01 Giugno, 13:43:49 - 2017
Neanch'io domani posso venire, per cui se poteste chiedere al professore di confermare la possibilità di poter dare le due parti d'esame in due appelli separati, sarebbe ottimo.

;)
Io oggi volevo domandargli quello che hai chiesto. Purtroppo me ne sono ricordato tardi ed era già andato via. Prova a mandargli una mail e se risponde facci sapere che dice
Titolo: Re:Nuova modalità esame
Inserito da: Quadrifoglio - Gio 01 Giugno, 15:01:19 - 2017
Scusate ragazzi lo so che non è il topic giusto ma mi sono perso la password delle slide del professore non è che potete darmela. Grazie.
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Gio 01 Giugno, 17:30:49 - 2017
ecco il testo della simulazione con le classi di supporto in c e java fornite oggi dal prof e che sono in allegato.
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Sab 03 Giugno, 18:46:53 - 2017
Posto la soluzione del primo esercizio della simulazione di esame.
Codice: [Seleziona]
/* restituisce TRUE se completo, FALSE altrimenti */
public boolean isComplete(){
            int res = isComplete(this);
            if(res == -1) return false;
            return true;
}
       
        private int isComplete(BinTree t) {
            // se albero nullo, non completo
            if(t == null)
                return -1;
           
            // albero con solo radice, è completo
            if( (t.left == null) && (t.right == null) )
                return 0;
           
            // Chiamo ricorsivamente i sottoalberi sx e dx
            int h1 = isComplete(t.left);
            int h2 = isComplete(t.right);
             
            // se entrambi i sottoalberi non sono completi
            if((h1 == -1) || (h2 == -1))
                return -1;
           
            if(h1 != h2) return -1;
           
            return 1+h1;
        }

Sul secondo invece sto tentando di usare una visita in ampiezza con utilizzo di una coda. Nel senso che ogni volta che estraggo il nodo dalla coda, creo figlio sx e figlio dx e poi li rimetto in coda.Quando estraggo dalla coda un altro nodo, ricreo figlio sx e figlio dx e cosi via, fino a che non arrivo a livello level. Una bozza di soluzione, per ora solo in pseudocodice, di ciò che stavo pensando (non sono per niente sicuro che sia corretto). Che ne pensate voi? Può essere una strada percorribile o qualcuno è riuscito a risolvere il secondo esercizio in maniera diversa? Sto parecchio in difficoltà su questo
 :(
Codice: [Seleziona]

  Algoritmo generateCompleteTree(int level)
  Input:    numero di livelli dell'albero
  Output:  albero binario completo

   Creo una coda
   Creo nodo BinTree t
   int i
   coda.enqueue(t)
   i++
   while( i < level) {
       BinTree v = coda.dequeue();
       creo figlio sinistro
       creo figlio destro
       t.setLeftChild(sx)
       t.setRightChild(dx)
       coda.enqueue(sx)
       coda.enqueue(dx)
       i++;
  }

   return t
}
Titolo: Re:Nuova modalità esame
Inserito da: Riettez23 - Dom 04 Giugno, 01:16:28 - 2017
Io l'ho risolto così. I test girano, ne ho creati degli altri e girano pure quelli. Fammi sapere  ;D Non ho mai la certezza assoluta quando scrivo codice  ;D ;D ;D

Codice: [Seleziona]
int countLev;

void *genCompleteBinTreeAux(int nLev, binTree* root/*, int countLev*/)
{
    if(countLev >= nLev)
return;
   
    setLeftChild(root, root->key + 1);   
    setRightChild(root, root->key + 2);

    countLev++;

    genCompleteBinTreeAux(nLev, root->left/*, countLev*/);
    genCompleteBinTreeAux(nLev, root->right/*, countLev*/;

    countLev--;

    return;
}

binTree *genCompleteBinTree(int nLev)
{
    unsigned int numberOfNodes = pow(2, nLev) - 1;
    //printf("numberOfNodes %d\n", numberOfNodes);

    binTree *t = newBinTree(1);
    countLev = 1;

    if(nLev > 1)
        genCompleteBinTreeAux(nLev, t/*, countLev*/);

    //printf("countNodes %d\n", countNodes(t));
    return t;
}
Titolo: Re:Nuova modalità esame
Inserito da: john - Dom 04 Giugno, 10:34:20 - 2017
Ragazzi scusate ma qualcuno è riuscito a prenotarsi? Su Infostud non mi appare niente. Ce sta solo l appello di algoritmi e sistemi dati, ma fondamenti di informatica 2 del vecchio ordinamento no.
Titolo: Re:Nuova modalità esame
Inserito da: Riettez23 - Dom 04 Giugno, 10:56:05 - 2017
Devi prenotarti dal sito  ;)

https://sites.google.com/a/dis.uniroma1.it/asd-sapienza/esame
Titolo: Re:Nuova modalità esame
Inserito da: john - Dom 04 Giugno, 11:03:23 - 2017
Sì grazie, ma qu esto modulo è solo per quelli del nuovo ordinamento. Io sono del vecchio ordinamento che devono prenotarsi su infostud.
"Gli studenti 2013-14, o aa.aa. precedenti, debbono prenotarsi solo attraverso Infostud."
Titolo: Re:Nuova modalità esame
Inserito da: Riettez23 - Dom 04 Giugno, 11:46:46 - 2017
Hai ragione sorry   :-\
Titolo: Re:Nuova modalità esame
Inserito da: zeusm - Dom 04 Giugno, 12:29:18 - 2017
Nel vecchio sito c'è scritto che anche il vecchio ordinamento deve prenotarsi tramite google form : http://www.dis.uniroma1.it/%7Efiii/esame.html
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Dom 04 Giugno, 13:51:27 - 2017
Io l'ho risolto così. I test girano, ne ho creati degli altri e girano pure quelli. Fammi sapere  ;D Non ho mai la certezza assoluta quando scrivo codice  ;D ;D ;D

Codice: [Seleziona]
int countLev;

void *genCompleteBinTreeAux(int nLev, binTree* root/*, int countLev*/)
{
    if(countLev >= nLev)
return;
   
    setLeftChild(root, root->key + 1);   
    setRightChild(root, root->key + 2);

    countLev++;

    genCompleteBinTreeAux(nLev, root->left/*, countLev*/);
    genCompleteBinTreeAux(nLev, root->right/*, countLev*/;

    countLev--;

    return;
}

binTree *genCompleteBinTree(int nLev)
{
    unsigned int numberOfNodes = pow(2, nLev) - 1;
    //printf("numberOfNodes %d\n", numberOfNodes);

    binTree *t = newBinTree(1);
    countLev = 1;

    if(nLev > 1)
        genCompleteBinTreeAux(nLev, t/*, countLev*/);

    //printf("countNodes %d\n", countNodes(t));
    return t;
}
Praticamente fai una visita in pre-ordine per creare albero completo. Non capisco una cosa, perché metti anche countlevel--?
Titolo: Re:Nuova modalità esame
Inserito da: Riettez23 - Dom 04 Giugno, 14:12:12 - 2017
Perché facendo appunto preorder arrivi fino a sinistra in basso all'inizio, e quindi risalendo (per poter costruire anche la parte destra) devi decrementare il livello altrimenti ti fermi subito nell if
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Dom 04 Giugno, 14:16:55 - 2017
Perché facendo appunto preorder arrivi fino a sinistra in basso all'inizio, e quindi risalendo (per poter costruire anche la parte destra) devi decrementare il livello altrimenti ti fermi subito nell if
Ah okay ora capisco. Grazie mille del tuo aiuto
Titolo: Re:Nuova modalità esame
Inserito da: Riettez23 - Dom 04 Giugno, 14:22:25 - 2017
Ah okay ora capisco. Grazie mille del tuo aiuto

Di nulla, fammi sapere se ti funziona  :) Per caso sai se il prof abbia dato altro materiale simile? Perché altrimenti mi tocca scrivere il codice di test a manina per esercitarmi sugli altri testi  :-\
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Dom 04 Giugno, 14:34:47 - 2017
Di nulla, fammi sapere se ti funziona  :) Per caso sai se il prof abbia dato altro materiale simile? Perché altrimenti mi tocca scrivere il codice di test a manina per esercitarmi sugli altri testi  :-\
Non ha dato altro materiale per esercitarsi.
Titolo: Re:Nuova modalità esame
Inserito da: john - Dom 04 Giugno, 14:37:47 - 2017
Nel vecchio sito c'è scritto che anche il vecchio ordinamento deve prenotarsi tramite google form : http://www.dis.uniroma1.it/%7Efiii/esame.html

Grazie mille, non l'avevo visto.
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Dom 04 Giugno, 17:04:19 - 2017
Di nulla, fammi sapere se ti funziona  :) Per caso sai se il prof abbia dato altro materiale simile? Perché altrimenti mi tocca scrivere il codice di test a manina per esercitarmi sugli altri testi  :-\
ho provato a far funzionare il codice che hai scritto, ma fino a level = 2 funziona. Quando faccio su level=3 da errore e crea problemi.Sicuramente sono io che non riesco ad adattare la tua soluzione alla struttura del codice della simulazione di esame.
Titolo: Re:Nuova modalità esame
Inserito da: Riettez23 - Dom 04 Giugno, 19:53:21 - 2017
ho provato a far funzionare il codice che hai scritto, ma fino a level = 2 funziona. Quando faccio su level=3 da errore e crea problemi.Sicuramente sono io che non riesco ad adattare la tua soluzione alla struttura del codice della simulazione di esame.

Codice: [Seleziona]
unsigned int countNodes(binTree* t)
{
    if (t == NULL)
return (0);

    return (1 + countNodes(t->left) + countNodes(t->right));
}

boolean isCompleteAux(binTree *t, unsigned int count, unsigned int numberOfNodes)
{
    if(t == NULL)
    {
        if(numberOfNodes != 2)
    return TRUE;

return FALSE;
    }

    if(count >= numberOfNodes)
return FALSE;

    return(isCompleteAux(t->left, 2*count + 1, numberOfNodes) && isCompleteAux(t->right, 2*count + 2, numberOfNodes));
   
}

boolean isComplete(binTree *t)
{
    unsigned int numberOfNodes = countNodes(t);
    return isCompleteAux(t, 0, numberOfNodes);
}

Guarda questo è il mio codice per quanto riguarda l'esercizio 1. A me richiamando questa "isComplete" funge  ??? Comunque ci può stare che ho sbagliato.

Con questi test:
Codice: [Seleziona]
    nc_t1 = buildNonCompleteTree1();
    nc_t2 = buildNonCompleteTree2();
    nc_t3 = buildNonCompleteTree3();
    nc_t4 = buildNonCompleteTree4();
    nc_t5 = buildNonCompleteTree5();
    nc_t6 = buildNonCompleteTree6();
    nc_t7 = buildNonCompleteTree7();

    c_t1 = buildCompleteTree1();
    c_t2 = buildCompleteTree2();

    c1 = genCompleteBinTree(1);
    c2 = genCompleteBinTree(2);
    c3 = genCompleteBinTree(3);
    c4 = genCompleteBinTree(4);
    c5 = genCompleteBinTree(6);
    c6 = genCompleteBinTree(24);

Il terminale mi stampa questo:
Codice: [Seleziona]
Completo nc_t1? 0
Completo nc_t2? 0
Completo nc_t3? 0
Completo nc_t4? 0
Completo nc_t5? 0
Completo nc_t6? 0
Completo nc_t7? 0
Completo c_t1? 1
Completo c_t2? 1
Completo c1? 1
Completo c2? 1
Completo c3? 1
Completo c4? 1
Completo c5? 1
Completo c6? 1
Titolo: Re:Nuova modalità esame
Inserito da: john - Lun 05 Giugno, 10:44:37 - 2017
Ragazzi ma all'esame quale ambiente di sviluppo useremo? Eclipse? notepad++?
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Lun 05 Giugno, 15:10:33 - 2017
Ragazzi ma all'esame quale ambiente di sviluppo useremo? Eclipse? notepad++?
Non ha specificato quale ambiente di sviluppo usare alla simulazione. Presumo quello che si usava nelle esercitazioni precedenti ma io non ci sono mai andato quindi nn lo so. Cmq credo sia una scelta libera dello studente
Titolo: Re:Nuova modalità esame
Inserito da: LucaLindholm - Lun 05 Giugno, 16:49:18 - 2017
Ragazzi ma all'esame quale ambiente di sviluppo useremo? Eclipse? notepad++?

Nei computer del Laboratorio c'è un vasto assortimento di editor e IDE, tra cui Notepad++, Eclipse, NetBeans, VS, etc.

Titolo: Re:Nuova modalità esame
Inserito da: john - Mar 06 Giugno, 10:28:48 - 2017
Grazie ragazzi. Spero allora a scelta dello studente.  :asd:
Titolo: Re:Nuova modalità esame
Inserito da: john - Mer 07 Giugno, 11:14:37 - 2017
Allora, sul primo esercizio l'ho fatto identico a scheggia89, per quello non ho problemi, per quanto riguarda il secondo, era un casino. Sono riuscito a far compilare l'algoritmo ma non sono sicuro della soluzione.

Codice: [Seleziona]

.....
public static void appoGenerateCompleteTree (BinTree res, int k, int level){

if (level == 0) return;
BinTree sx = new BinTree(k++);
if (res.setLeftChild(sx))
appoGenerateCompleteTree(sx, k, level-1);

BinTree dx = new BinTree(k++);
if (res.setRightChild(dx))
appoGenerateCompleteTree(dx, k, level-1);
}

public BinTree generateCompleteTree(int level){

//implementare un albero binario completo con level livelli
int k = 0;
BinTree res = new BinTree(k++);
appoGenerateCompleteTree (res, k, level-1);
return res;
}
......

E i vari test:

Codice: [Seleziona]
1
-#
-#
Albero Completo
1
-2
--#
--#
-#
Albero non Completo
1
-2
--#
--#
-3
--#
--#
Albero Completo
4
-#
-5
--#
--#
Albero non Completo
4
-1
--2
---#
---#
--3
---#
---#
-5
--#
--#
Albero non Completo
11
-12
--14
---#
---#
--#
-13
--#
--15
---#
---#
Albero non Completo
1
-#
-#
Albero Completo
1
-#
-1
--#
--#
Albero non Completo
Albero Completo

Ditemi cosa ne pensate, non sono sicuro della soluzione  ??? ??? ??? ??? :asd:
Titolo: Re:Nuova modalità esame
Inserito da: roberto93 - Mer 07 Giugno, 11:29:00 - 2017
salve ragazzi, qualcuno ha svolto il problema 4?

io l'ho formulato come problema MST,  ma in generale è un problema di cammini minimi, ogni elemento della matrice è ricavato dal peso dell'arco che viene aggiunto all'albero dei cammini minimi.

per quanto riguarda i costi, la matrice occupa spazio quadratico in memoria, mentre la lista è lineare in termini di numero di nodi + archi

sul tempo: l'algoritmo in entrambi i casi dovrebbe avere costo nel caso peggio (n+m) * logn, in quanto non si fanno operazioni di inserimento di vertici (che hanno costo quadratico se si usa una matrice) ma solo operazioni insertEdges che in entrambi i casi costano O(1)

fatemi sapere voi come l'avete fatto cosi ci confrontiamo :)
grazie
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mer 07 Giugno, 15:36:15 - 2017
Allora, sul primo esercizio l'ho fatto identico a scheggia89, per quello non ho problemi, per quanto riguarda il secondo, era un casino. Sono riuscito a far compilare l'algoritmo ma non sono sicuro della soluzione.

Codice: [Seleziona]

.....
public static void appoGenerateCompleteTree (BinTree res, int k, int level){

if (level == 0) return;
BinTree sx = new BinTree(k++);
if (res.setLeftChild(sx))
appoGenerateCompleteTree(sx, k, level-1);

BinTree dx = new BinTree(k++);
if (res.setRightChild(dx))
appoGenerateCompleteTree(dx, k, level-1);
}

public BinTree generateCompleteTree(int level){

//implementare un albero binario completo con level livelli
int k = 0;
BinTree res = new BinTree(k++);
appoGenerateCompleteTree (res, k, level-1);
return res;
}
......

E i vari test:

Codice: [Seleziona]
1
-#
-#
Albero Completo
1
-2
--#
--#
-#
Albero non Completo
1
-2
--#
--#
-3
--#
--#
Albero Completo
4
-#
-5
--#
--#
Albero non Completo
4
-1
--2
---#
---#
--3
---#
---#
-5
--#
--#
Albero non Completo
11
-12
--14
---#
---#
--#
-13
--#
--15
---#
---#
Albero non Completo
1
-#
-#
Albero Completo
1
-#
-1
--#
--#
Albero non Completo
Albero Completo

Ditemi cosa ne pensate, non sono sicuro della soluzione  ??? ??? ??? ??? :asd:
Nel secondo esercizio generi l'albero ma non hai la certezza che esso sia completo. L'esercizio 2 chiede che quando fai generateCompleteTree ti deve creare sempre un albero completo. E nel codice non sembra che lo faccia questo. Ma sinceramente è un mio pensiero, non sono tanto sicuro che sia corretto ciò che ho detto
Titolo: Re:Nuova modalità esame
Inserito da: zeusm - Mer 07 Giugno, 15:45:17 - 2017
salve ragazzi, qualcuno ha svolto il problema 4?

io l'ho formulato come problema MST,  ma in generale è un problema di cammini minimi, ogni elemento della matrice è ricavato dal peso dell'arco che viene aggiunto all'albero dei cammini minimi.

per quanto riguarda i costi, la matrice occupa spazio quadratico in memoria, mentre la lista è lineare in termini di numero di nodi + archi

sul tempo: l'algoritmo in entrambi i casi dovrebbe avere costo nel caso peggio (n+m) * logn, in quanto non si fanno operazioni di inserimento di vertici (che hanno costo quadratico se si usa una matrice) ma solo operazioni insertEdges che in entrambi i casi costano O(1)

fatemi sapere voi come l'avete fatto cosi ci confrontiamo :)
grazie

Io ho usato ho usato un grafo pesato in cui i vertici rappresentano le n stazioni e gli archi le m tratte. I pesi degli archi indicano la distanza tra due stazioni.
Per il punto b ho usato Dijkstra facendolo partire da ogni vertice e restituendo un vettore di distanze minime dagli altri vertici.
Poi ho messo i vettori di tutti i vertici in una matrice nxn e lasciato ad infinito le stazioni non collegate. Non so se sia giusta questa soluzione.
Titolo: Re:Nuova modalità esame
Inserito da: Gianzo - Gio 08 Giugno, 12:07:01 - 2017
Buon giorno a tutti! Anche io sto preparando quest'esame e ho pensato a questa soluzione per l'esercizio proposto dal Prof, sia la prima che la seconda parte. ecco a voi:

Codice: [Seleziona]
int i = 0;
int n = 0;
public boolean isComplete(){
i = 0;
n = 0;
BinTree b = this;
isComplete(b);
int h = (int) (n-1)/2;
if(h>i&& h!=0||n!= (2*i)+1) return false;
return true;
}

public void isComplete(BinTree root){
n++;
if(root.left!= null && root.right!= null)
i++;
if(root.left!=null){
  isComplete(root.left);
}
if(root.right!= null)
isComplete(root.right);

}
questo è il metodo isComplete(), praticamente ho ragionato sulle proprietà dei nodi in un albero binario completo, con n conto i nodi totali e con i solo quelli interni. ecco cosa mi restituisce:
Codice: [Seleziona]
1
-#
-#
Albero Completo
1
-2
--#
--#
-#
Albero non Completo
1
-2
--#
--#
-3
--#
--#
Albero Completo
4
-#
-5
--#
--#
Albero non Completo
4
-1
--2
---#
---#
--3
---#
---#
-5
--#
--#
Albero Completo
11
-12
--14
---#
---#
--#
-13
--#
--15
---#
---#
Albero non Completo

Per la seconda parte invece mi sono servito del TDA coda implementato in queue.java, servendomene per fare una visita in preOrder senza usare la ricorsione. Non ho capito cosa significhi l'intero che rappresenta il "livello" dell'albero, io l'ho interpretato come il log2 del numero dei nodi che sono alla stessa "altezza". il test di completezza viene sempre corretto ma non riesco a far eseguire l'ultima chiamata nel programma di test:
Codice: [Seleziona]
Random rnd = new Random();

public BinTree generateCompleteTree(int level){
BinTree bt = this;
BinTree ris = bt;
Queue q = new Queue();

int i = 0;
int nodes = 0;

while(i<level){
if(i>0)
bt = (BinTree) q.dequeue();
BinTree sx = new BinTree(rnd.nextInt(50));
BinTree dx = new BinTree(rnd.nextInt(50));
if(bt.right == null){
bt.setRightChild(dx);
q.enqueue(dx);}
if(bt.left==null){
bt.setLeftChild(sx);
q.enqueue(sx);}
nodes = nodes+1;
double l2 =  Math.floor(Math.log(nodes)/Math.log(2));
if((int) l2==i){
nodes = 0;
i++;}
}
return ris;
}
Ed ecco cosa mi restituiscono i test sul secondo metodo...
Codice: [Seleziona]
1
-29
--38
---#
---#
--49
---#
---#
-17
--38
---#
---#
--36
---#
---#
Albero Completo
Figlio destro già presente
1
-40
--#
--#
-1
--#
--#
Albero Completo
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
        at java.util.Random.<init>(Random.java:137)
        at java.util.Random.<init>(Random.java:105)
        at binTree.BinTree.<init>(BinTree.java:64)
        at binTree.BinTree.generateCompleteTree(BinTr
        at test.BinTreeTest.main(BinTreeTest.java:78)
Come vedete non riesce a lanciare l'ultimo metodo... aiuti?  ;D
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Gio 08 Giugno, 12:58:41 - 2017
Buon giorno a tutti! Anche io sto preparando quest'esame e ho pensato a questa soluzione per l'esercizio proposto dal Prof, sia la prima che la seconda parte. ecco a voi:

Codice: [Seleziona]
int i = 0;
int n = 0;
public boolean isComplete(){
i = 0;
n = 0;
BinTree b = this;
isComplete(b);
int h = (int) (n-1)/2;
if(h>i&& h!=0||n!= (2*i)+1) return false;
return true;
}

public void isComplete(BinTree root){
n++;
if(root.left!= null && root.right!= null)
i++;
if(root.left!=null){
  isComplete(root.left);
}
if(root.right!= null)
isComplete(root.right);

}
questo è il metodo isComplete(), praticamente ho ragionato sulle proprietà dei nodi in un albero binario completo, con n conto i nodi totali e con i solo quelli interni. ecco cosa mi restituisce:
Codice: [Seleziona]
1
-#
-#
Albero Completo
1
-2
--#
--#
-#
Albero non Completo
1
-2
--#
--#
-3
--#
--#
Albero Completo
4
-#
-5
--#
--#
Albero non Completo
4
-1
--2
---#
---#
--3
---#
---#
-5
--#
--#
Albero Completo
11
-12
--14
---#
---#
--#
-13
--#
--15
---#
---#
Albero non Completo

Per la seconda parte invece mi sono servito del TDA coda implementato in queue.java, servendomene per fare una visita in preOrder senza usare la ricorsione. Non ho capito cosa significhi l'intero che rappresenta il "livello" dell'albero, io l'ho interpretato come il log2 del numero dei nodi che sono alla stessa "altezza". il test di completezza viene sempre corretto ma non riesco a far eseguire l'ultima chiamata nel programma di test:
Codice: [Seleziona]
Random rnd = new Random();

public BinTree generateCompleteTree(int level){
BinTree bt = this;
BinTree ris = bt;
Queue q = new Queue();

int i = 0;
int nodes = 0;

while(i<level){
if(i>0)
bt = (BinTree) q.dequeue();
BinTree sx = new BinTree(rnd.nextInt(50));
BinTree dx = new BinTree(rnd.nextInt(50));
if(bt.right == null){
bt.setRightChild(dx);
q.enqueue(dx);}
if(bt.left==null){
bt.setLeftChild(sx);
q.enqueue(sx);}
nodes = nodes+1;
double l2 =  Math.floor(Math.log(nodes)/Math.log(2));
if((int) l2==i){
nodes = 0;
i++;}
}
return ris;
}
Ed ecco cosa mi restituiscono i test sul secondo metodo...
Codice: [Seleziona]
1
-29
--38
---#
---#
--49
---#
---#
-17
--38
---#
---#
--36
---#
---#
Albero Completo
Figlio destro già presente
1
-40
--#
--#
-1
--#
--#
Albero Completo
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
        at java.util.Random.<init>(Random.java:137)
        at java.util.Random.<init>(Random.java:105)
        at binTree.BinTree.<init>(BinTree.java:64)
        at binTree.BinTree.generateCompleteTree(BinTr
        at test.BinTreeTest.main(BinTreeTest.java:78)
Come vedete non riesce a lanciare l'ultimo metodo... aiuti?  ;D
Io il parametro level per generare l' albero completo l'ho interpretato in questo modo:
level=0 c'è il nodo radice
level=1 ci devono essere due nodi
level=2 ci devono essere 4  nodi
level=3 ci devono essere 8 nodi
......
level=i ci devono essere 2i nodi

Non so se è la tua stessa interpretazione
Titolo: Re:Nuova modalità esame
Inserito da: Gianzo - Gio 08 Giugno, 15:09:39 - 2017
E' la stessa che ho dato io! Mi sono dimenticato di aggiungere che ho provato pure a farla in maniera ricorsiva (senza l'ausilio della coda) ma mi da sempre il solito errore
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Gio 08 Giugno, 15:38:36 - 2017
E' la stessa che ho dato io! Mi sono dimenticato di aggiungere che ho provato pure a farla in maniera ricorsiva (senza l'ausilio della coda) ma mi da sempre il solito errore
ah ok :D :D non mi ero reso conto che stavamo dicendo la stessa cosa scusami  :asd:
Titolo: Re:Nuova modalità esame
Inserito da: john - Gio 08 Giugno, 16:07:02 - 2017
Nel secondo esercizio generi l'albero ma non hai la certezza che esso sia completo. L'esercizio 2 chiede che quando fai generateCompleteTree ti deve creare sempre un albero completo. E nel codice non sembra che lo faccia questo. Ma sinceramente è un mio pensiero, non sono tanto sicuro che sia corretto ciò che ho detto

No non genero un albero qualsiasi, genero sempre un albero "pieno" in tutti i suoi livelli. Allora lo crea sempre un albero completo. infatti in "generateCompleteTree" io creo la radice dell'albero (ogni nodo di un livello avranno la stassa chiave che corrisponde appunto al loro livello nell'albero). La radice infatti la creo con chiave 1, poi passo la radice appena creata alla funzione "appoGenerateCompleteTree" con la sua chiave e con il livello diminuito di 1, questo perchè ogni nodo deve avere al massimo un sottoalbero di altezza level-1, level-2, level-3 ecc ecc, questo a seconda di dove si trovi il nodo.
La funzione ricorsivamente crea i vari figli sinistri e destri, ogni nodo e ogni livello sarà pieno, la ricorsione si fermerà quando level sarà 0.
Ed essendo pieno in ogni livello, e quando ha questa caratteristica l'albero è sempre un albero completo.
Titolo: Re:Nuova modalità esame
Inserito da: john - Gio 08 Giugno, 16:51:47 - 2017
Ragazzi, ma qualcuno ha fatto l'esercizio 3 "Livello con somma con chiavi più alta" dell'esercitazione del 21 marzo?

https://drive.google.com/drive/folders/0B4_lsbtik3xJMjhVY29SWW9HU2c

Vi lascio il link, e in allegato il testo, sto scapocciando perchè non so come impostare l'algoritmo, ho visto anche la soluzione ma proprio non riesco a capire la logica che ha seguito il prof  :asd: :sisi:

Titolo: Re:Nuova modalità esame
Inserito da: Gianzo - Ven 09 Giugno, 10:30:59 - 2017
Ragazzi, ma qualcuno ha fatto l'esercizio 3 "Livello con somma con chiavi più alta" dell'esercitazione del 21 marzo?

https://drive.google.com/drive/folders/0B4_lsbtik3xJMjhVY29SWW9HU2c

Vi lascio il link, e in allegato il testo, sto scapocciando perchè non so come impostare l'algoritmo, ho visto anche la soluzione ma proprio non riesco a capire la logica che ha seguito il prof  :asd: :sisi:

In realtà dovresti usare una visita in ampiezza dell'albero, la soluzione è basata su coda, infatti nella visita lui salva sempre il primo figlio del nodo n in q e poi scorre i fratelli di n (se ne ha) per ottenere la somma delle chiavi
Titolo: Re:Nuova modalità esame
Inserito da: john - Ven 09 Giugno, 11:34:26 - 2017
In realtà dovresti usare una visita in ampiezza dell'albero, la soluzione è basata su coda, infatti nella visita lui salva sempre il primo figlio del nodo n in q e poi scorre i fratelli di n (se ne ha) per ottenere la somma delle chiavi

Ah ok ok, ora ho capito. Grazie tante.
Tu come hai svolto il punto due della terza domanda? Qualcuno per caso ha lo svolgimento fatto a lezione?
Titolo: Re:Nuova modalità esame
Inserito da: nox91 - Ven 09 Giugno, 12:30:19 - 2017
Scusate, ma il primo esercizio della simulazione non viene come costo la sommatoria da 1 a array.length?
Nel caso peggiore, ovvero un array in ordine decrescente [4,3,2,1] esegue 6 chiamate, con 5 elementi 10.
Titolo: Re:Nuova modalità esame
Inserito da: zeusm - Ven 09 Giugno, 15:57:46 - 2017
Scusate, ma il primo esercizio della simulazione non viene come costo la sommatoria da 1 a array.length?
Nel caso peggiore, ovvero un array in ordine decrescente [4,3,2,1] esegue 6 chiamate, con 5 elementi 10.

Io l'ho svolto così, non so se sia corretto :
La dimensione dell'input è la dimensione dell'array che chiamo n. f3(int[]) ha costo costante se n <=1 altrimenti ha costo pari al costo di f2(int[],int).
f2 ha costo costante se n<=1 ovvero se i > n altrimenti ha costo n*(costo di f1) dato che la chiamata ricorsiva di f2 viene eseguita nel caso peggiore n volte.  f1(int[],int ,int) dovrebbe avere nel caso peggiore costo O(n) quindi in totale il costo di f3 dovrebbe essere O(n2
Titolo: Re:Nuova modalità esame
Inserito da: roberto93 - Sab 10 Giugno, 10:24:09 - 2017
qualcuno ha svolto l'esercizio 2 dell'esempio del "nuovo" ? quello sui terminali isolati del BST
Titolo: Re:Nuova modalità esame
Inserito da: Gianzo - Sab 10 Giugno, 12:07:39 - 2017
qualcuno ha svolto l'esercizio 2 dell'esempio del "nuovo" ? quello sui terminali isolati del BST

Ecco una mia soluzione... ho provato vari test ed effettivamente finora mi ha sempre dato il risultato giusto. Il tempo è sicuramente lineare perchè fa due visite dell'albero in postorder ma in metodi separati, ma non so se effettivamente sarebbe possibile ridurre tutto ad una visita sola. l'unica accortezza è che non ritorna null perchè il metodo è void, ma non dovrebbe essere difficile modificare la signature dei metodi.

Codice: [Seleziona]
public void trovaIsolati(BinTree T){

BinTree[] Ts = new BinTree[2];
trovaIsolati(T,T,Ts,0);

if(Ts[0] == null|| Ts[1] == null){
                 System.out.print("nessuna coppia di isolati trovata!");
return ;
                }
BinTree pred = null;
creaPercorso(T,Ts[0],Ts[1],pred);
System.out.println(s.toString()+" "+s2.toString());
int ciaone = s.pop();
while(s2.size()>0){
n++;
s.push(s2.pop());
}
System.out.println(n);
System.out.println(s.toString());
}

        Stack <Integer> s= new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();

public void creaPercorso(BinTree T,BinTree fst, BinTree snd, BinTree pred){
if(T.left!=null)
creaPercorso(T.left,fst,snd,T);
if(T.right!=null)
creaPercorso(T.right,fst,snd,T);
if(T.key == fst.key){
s.push(T.key);
}
if(T.key == snd.key){
s2.push(T.key);
s2.push(pred.key);
}
if(!s.isEmpty()&&!s2.isEmpty()&&s2.peek() == s.peek())return ;
if(s.size()>0 && T.key == s.peek()&& pred!=null)
s.push(pred.key);
else if(s2.size()>0){
    if(T.key == s2.peek()&& pred!=null)
s2.push(pred.key);
}
}

int l1 = 0;
int l2 = 0;


public void trovaIsolati(BinTree T,BinTree pred,BinTree[] ts,int lvl){
if(T.left!= null)
trovaIsolati(T.left,T,ts,lvl+1);
if(T.right!=null)
trovaIsolati(T.right,T,ts,lvl+1);
if((ts[0]== null||l1<lvl)&&(pred.left == T || pred.right == T)
&&(pred.right == null || pred.left == null)&&(T.left== null&& T.right== null)){
if(l1 <= lvl){ts[1] = ts[0];
ts[0] = T;}
if(ts[0]==null||l1<lvl)
  ts[0] = T;
l1 = lvl;
}
               else if((ts[1]== null||l2<=lvl)&&(pred.left == T|| pred.right == T)
&&(pred.left == null || pred.right == null)&&(T.left== null&& T.right== null)){

      ts[1] = T;
      l2 = lvl;
}
}
Titolo: Re:Nuova modalità esame
Inserito da: john - Mar 13 Giugno, 10:01:19 - 2017
Ragazzi ma a voi come è andata ieri?
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mar 13 Giugno, 10:17:27 - 2017
per quanto mi riguarda ho avuto un pò di difficoltà al problema 1  e al problema 4 nei punti (b) e (c). Il problema 2 riguardante la programmazione per fortuna non è stato difficile e l'ho fatto tutto.
Titolo: Re:Nuova modalità esame
Inserito da: john - Mer 14 Giugno, 05:55:26 - 2017
Io invece ho avuto difficoltà con la domanda 2, penso me lo valuta pochissimo. Vabbè  :-X :-X Poi della seconda domanda il punto "c" non sono riuscito a finirlo che ho avuto dei problemi con il punto a che sono riuscito a farlo ma ci ho messo troppo tempo. Poi la domanda 4 il punto "c" l'ho lasciato praticamente in bianco.  :-X :-X :-X
Sicuramente per quanqto riguarda la prova al calcolatore era abbastanza fattibile, ma le domande di teoria erano abbastanza impegnative specie la 2.
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mer 14 Giugno, 09:39:29 - 2017
Io invece ho avuto difficoltà con la domanda 2, penso me lo valuta pochissimo. Vabbè  :-X :-X Poi della seconda domanda il punto "c" non sono riuscito a finirlo che ho avuto dei problemi con il punto a che sono riuscito a farlo ma ci ho messo troppo tempo. Poi la domanda 4 il punto "c" l'ho lasciato praticamente in bianco.  :-X :-X :-X
Sicuramente per quanqto riguarda la prova al calcolatore era abbastanza fattibile, ma le domande di teoria erano abbastanza impegnative specie la 2.

Come hai risolto il punto (b) del problema 4 dove c'era l' arco con peso negativo? All'inizio avevo pensato a Djistrkra ma con peso negativo non funziona e non mi è venuto in mente altro.
Titolo: Re:Nuova modalità esame
Inserito da: john - Mer 14 Giugno, 10:01:27 - 2017
Come hai risolto il punto (b) del problema 4 dove c'era l' arco con peso negativo? All'inizio avevo pensato a Djistrkra ma con peso negativo non funziona e non mi è venuto in mente altro.

Allora con Djkstra ci avevo pensato anch'io, ma poi mi sono ricordato che Djkstra con grafi ad archi negativi non fornirebbe una soluzione ottimale. E l'algoritmo adatto a questo problema era quello di Floyd-Warshall, che appunto accetta anche gli archi negativi. Solo che ho sbagliato a scrivere il loro costo. Se non erro Djkstra è O(m+n) mentre Floyd-Warshall è O(m^3)
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mer 14 Giugno, 10:09:01 - 2017
Allora con Djkstra ci avevo pensato anch'io, ma poi mi sono ricordato che Djkstra con grafi ad archi negativi non fornirebbe una soluzione ottimale. E l'algoritmo adatto a questo problema era quello di Floyd-Warshall, che appunto accetta anche gli archi negativi. Solo che ho sbagliato a scrivere il loro costo. Se non erro Djkstra è O(m+n) mentre Floyd-Warshall è O(m^3)

Quindi sarebbe bastato scrivere lo pseudocodice di  Floyd-Warshall  come quello delle slide e andava bene? 
Titolo: Re:Nuova modalità esame
Inserito da: zeusm - Mer 14 Giugno, 10:22:27 - 2017
Quindi sarebbe bastato scrivere lo pseudocodice di  Floyd-Warshall  come quello delle slide e andava bene?
Se non mi sbaglio, si chiedeva il minimum spanning tree. Io ho usato Prim Jarnik che teoricamente dovrebbe funzionare anche con pesi negativi.
Titolo: Re:Nuova modalità esame
Inserito da: john - Mer 14 Giugno, 10:32:41 - 2017
Se non mi sbaglio, si chiedeva il minimum spanning tree. Io ho usato Prim Jarnik che teoricamente dovrebbe funzionare anche con pesi negativi.

Aia  ??? ??? se è cosi allora ho toppato alla grande  :-X. Io sinceramente non ricordo cosa chiedeva, mi hai fatto venire il dubbio.  Comunque si Prim Jarnik funziona con grafi non orientati e con pesi non negativi.
Titolo: Re:Nuova modalità esame
Inserito da: nox91 - Mer 14 Giugno, 14:42:03 - 2017
Ragazzi sono abbastanza convinto che l'algoritmo da usare per i grafi fosse Bellman-Ford, perchè a differenza di Floyd-Warshall, si applica ai grafi non orientati.

Punto "4-a" e "4-c" che avete messo invece?
Titolo: Re:Nuova modalità esame
Inserito da: john - Mer 14 Giugno, 15:32:03 - 2017
Mazza li abbiamo detti tutti  :asd: :asd: Djkstra, Floyd-Warshall, Prim Jarnik, Bellman-Ford. Ma la domanda del giorno è: Cosa chiedeva? Il minimum spanning tree oppure cammini minimi? Io ricordo cammini minimi ma zeusm mi ha fatto venire il dubbio dato che lui sostiene lo spanning tree. Io sinceramente non mi ricordo.

Comunque il la 4 a l ho praticamente lasciato in bianco  :-\
Titolo: Re:Nuova modalità esame
Inserito da: Cingols - Mer 14 Giugno, 16:51:36 - 2017
Chiedeva i cammini minimi, si faceva con bellman-ford!
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mer 14 Giugno, 17:01:40 - 2017
Ragazzi sono abbastanza convinto che l'algoritmo da usare per i grafi fosse Bellman-Ford, perchè a differenza di Floyd-Warshall, si applica ai grafi non orientati.

Punto "4-a" e "4-c" che avete messo invece?
Io al punto 4-a ho messo:
1. cammini minimi a sorgente singola
2. cammini minimi per ogni coppia di vertici in G
3. cammini minimi per una singola coppia

Il 4c ho lasciato in bianco. Sul punto 4-b possono essere d'accordo su belman ford. L'unico dubbio che ho é che belman-ford funziona con pesi negativi ma non ci devono essere cicli negativi. Nell' esame di lunedì come si faceva a capire se c'era o non c'era un ciclo negativo? In generale come si capisce se in un grafo è presente un ciclo negativo?
Titolo: Re:Nuova modalità esame
Inserito da: roberto93 - Mar 04 Luglio, 16:33:08 - 2017
raga siamo al 4 aprile, il 13 c'è il secondo appello, ma sti risultati??
Titolo: Re:Nuova modalità esame
Inserito da: LucaLindholm - Sab 08 Luglio, 19:49:35 - 2017
Scusate se chiedo, ma voi su quale materiale basate il vostro studio?

Perché il materiale fornito e indicato dal professore non è che mi abbia convinto più di tanto... mi lascia tanti dubbi.

Partendo, ad esempio, dall'analisi dei costi degli algoritmi, sia le slide che il Zanichelli non è che siano proprio tanto chiare: nella teoria scritta, si fa a malapena un'analisi descrittiva di certi algoritmi, ma il professore chiede di analizzare, "argomentando adeguatamente" (e lì i dubbi si moltiplicano), una concatenazione ricorsiva di piccoli algoritmi, chiedendo di specificare se un algoritmo operi "in-place" o meno.
In generale, sembra che la teoria scritta vada in una certa direzione, mentre gli esercizi d'esame (specialmente della nuova modalità introdotta quest'anno) vadano in un'altra.

Purtroppo non ho potuto seguire le lezioni e inizio a capire che solo seguendole si possa affrontare per bene questo esame, a quanto pare.

E vedendo il numero di insufficienze prese dagli studenti del nostro V.O., sembra che di dubbi ce ne siano tanti...

:(
Titolo: Re:Nuova modalità esame
Inserito da: LucaLindholm - Ven 14 Luglio, 17:24:28 - 2017
Come è andata l'esame ieri, ragazzi?

Io, nell'esercizio dei Grafi, ho messo minimum spanning tree a sorgente singola, usando l'algoritmo di Prim-Jarnik.

Voi?
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Ven 14 Luglio, 20:56:00 - 2017
Parlo per me, una mezza schifezza. Sul problema sui grafi anche io ho messo come problema da risolvere un minimum spannig tree, anche se non ne sono molto sicuro. Sul primo ho messo costo Theta (log3 n).
Titolo: Re:Nuova modalità esame
Inserito da: Cingols - Sab 15 Luglio, 17:59:51 - 2017
A me il primo veniva O(n) mentre quello dei grafi era sicuramente minium spanning tree ma io ho usato kruskal.
Titolo: Re:Nuova modalità esame
Inserito da: john - Lun 17 Luglio, 09:14:39 - 2017
Io al primo ho messo log (n), ho ragionato come con merge sort. E l ultimo era minimum spanning tree, ma io ho usato prim-Jarnik.

Ragazzi ma sui risultati di modelli di giugno qualcuno ne sa qualcosa ?
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mer 19 Luglio, 20:38:43 - 2017
Io al primo ho messo log (n), ho ragionato come con merge sort. E l ultimo era minimum spanning tree, ma io ho usato prim-Jarnik.

Ragazzi ma sui risultati di modelli di giugno qualcuno ne sa qualcosa ?
So usciti i risultati di modelli. Come sempre c'è stata una strage
Titolo: Re:Nuova modalità esame
Inserito da: john - Mer 19 Luglio, 22:36:31 - 2017
Io sinceramente un pò male ci sono rimasto, mica me ll'aspettavo. cChe poi la cosa che mi da un pò fastidio è che ti pubblica i risultati a pochi giorni del prossimo appello. Quindi in teoria avrei solo 3 giorni per ripassare tutto. Vabbè, ci becchiamo lunedì mattina.
Titolo: Re:Nuova modalità esame
Inserito da: LucaLindholm - Gio 20 Luglio, 01:21:31 - 2017
So usciti i risultati di modelli. Come sempre c'è stata una strage

Per ora sto preparando Algoritmi per settembre, che è un esame fattibile... penso che per Modelli avrò bisogno di fare un bel viaggio a Lourdes, invece.

:(
Titolo: Re:Nuova modalità esame
Inserito da: john - Gio 20 Luglio, 04:47:31 - 2017
Ci andiamo insieme 😅
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Gio 20 Luglio, 07:47:16 - 2017
Ma avete letto l'aggiornamento che ha messo sulla modalità d'esame? Chi fa meno di 12 punti nn viene ammesso all'appello successivo?il prof sta fuori cor cervello cmq.
Titolo: Re:Nuova modalità esame
Inserito da: john - Gio 20 Luglio, 09:56:34 - 2017
Beh se la mette così speriamo insomma che nei prossimi appelli non metta domande impossibili. 
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Gio 20 Luglio, 10:11:52 - 2017
Beh se la mette così speriamo insomma che nei prossimi appelli non metta domande impossibili.
Io non ci spererei, sinceramente. Ha messo questa cosa solo per avere meno compiti da correggere negi appelli di esame. Sto prof non ha voglia de fa na cippa de nulla e mette solo domande impossibili. Ha decisamente rotto le palle.
Titolo: Re:Nuova modalità esame
Inserito da: john - Gio 20 Luglio, 11:14:06 - 2017
Io non ci spererei, sinceramente. Ha messo questa cosa solo per avere meno compiti da correggere negi appelli di esame. Sto prof non ha voglia de fa na cippa de nulla e mette solo domande impossibili. Ha decisamente rotto le palle.

Eh nemmeno io ci spero, vabbè la cosa che mi da più fastidio è il fatto che ok sono stato bocciato, ma potrebbe pubblicare i risultati un pò prima e non a POCHI giorni del prossimo appello. Se veramente la bocciatura era grave almeno dammi qualche giorno in più per ripassare oppure approfondire argomenti che non sono stato in grado spiegare all'esame. Non abbiamo solo questo esame da dare, parlo per me avrei altri 4 esami da preparare per la laurea oltre al lavoro. Spero il prof capisca la situazione, capisco che lui è esigente ma ecco ci venga anche un pò incontro ... Vabbè.
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Gio 20 Luglio, 11:24:30 - 2017
Eh nemmeno io ci spero, vabbè la cosa che mi da più fastidio è il fatto che ok sono stato bocciato, ma potrebbe pubblicare i risultati un pò prima e non a POCHI giorni del prossimo appello. Se veramente la bocciatura era grave almeno dammi qualche giorno in più per ripassare oppure approfondire argomenti che non sono stato in grado spiegare all'esame. Non abbiamo solo questo esame da dare, parlo per me avrei altri 4 esami da preparare per la laurea oltre al lavoro.
Hai perfettamente ragione. Ci ha messo quasi un mese per correggere una trentina di compiti di modelli. Questa è pigrizia del prof. E non è neanche uno che interessa approfondire gli argomenti visto che quando vado a ricevimento molto spesso non lo fa, ovvio parlo per me.
Titolo: Re:Nuova modalità esame
Inserito da: LucaLindholm - Gio 20 Luglio, 12:09:13 - 2017
Hai perfettamente ragione. Ci ha messo quasi un mese per correggere una trentina di compiti di modelli. Questa è pigrizia del prof. E non è neanche uno che interessa approfondire gli argomenti visto che quando vado a ricevimento molto spesso non lo fa, ovvio parlo per me.

Chiedo scusa se lo chiedo, ma mi sapreste dire gentilmente quali erano più o meno le 5 domande del compito di modelli di giugno?

Giusto per capire cosa dovrò affrontare nella sessione di ottobre-novermbre (in realtà Modelli l'ho già un po' studiato, anche se non approfonditamente ancora).

XD
Titolo: Re:Nuova modalità esame
Inserito da: CIP - Sab 22 Luglio, 11:22:38 - 2017
Ragazzi, mi accodo anche io alla richiesta di LucaLindholm, FI2 ed elettronica sono i miei ultimi 2 esami da un bel pezzo ormai.  Sono del vecchio ordinamento ed avendo anche un lavoro full time risulta molto difficile studiare questi esami in poco tempo. Se avete risorse da condividere o consigli per la parte di modelli, sono entrambi ben accetti :)
Titolo: Re:Nuova modalità esame
Inserito da: john - Sab 22 Luglio, 18:08:35 - 2017
Ecco il testo dell ultimo appello
Titolo: Re:Nuova modalità esame
Inserito da: john - Mar 25 Luglio, 12:44:42 - 2017
Questo è il testo dell appello di ieri, sicuramente l esame era molto più tosto rispetto a quello di giugno   :-\ :-\ boh vabbe a voi come è andata ?
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mar 25 Luglio, 17:37:01 - 2017
io concordo con te sul fatto che il compito sia stato più difficile di luglio. Parlando per me non è andata un granché. L'unica cosa che sono sicuro di aver fatto bene è il problema 6. Per gli altri, ho avuto difficoltà con automa a pila e sul problema 5 in cui non sapevo dove mettere le mani. Io l'argomento su np-completezza vertex cover ecc non ci capisco nulla  :( :( :-\
Titolo: Re:Nuova modalità esame
Inserito da: john - Mar 25 Luglio, 18:10:17 - 2017
La stessa identica situazione, poi ho avuto difficoltà pure con l esercizio sulla macchina di turing.
Per quanto riguarda l esercizio 5 beh all appello di giugno nom sapendo come fare l esercizio, scrissi tutto sulla riduzione polinomiale e sugli np-completi, vertex cover, ecc . Me l ha valutato solo il 15% quindi neanche un punto. Questa volta quindi l'ho lasciato in bianco, anche perché non ho avuto neanche il tempo. Mi sono concentrato sugli altro esercizi. Poi questa domanda vale tipo 6 punti, ti taglia le gambe.  :-\
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mar 25 Luglio, 18:47:31 - 2017
La stessa identica situazione, poi ho avuto difficoltà pure con l esercizio sulla macchina di turing.
Per quanto riguarda l esercizio 5 beh all appello di giugno nom sapendo come fare l esercizio, scrissi tutto sulla riduzione polinomiale e sugli np-completi, vertex cover, ecc . Me l ha valutato solo il 15% quindi neanche un punto. Questa volta quindi l'ho lasciato in bianco, anche perché non ho avuto neanche il tempo. Mi sono concentrato sugli altro esercizi. Poi questa domanda vale tipo 6 punti, ti taglia le gambe.  :-\
ah si anche io ho avuto difficoltà sul punto b)  nel problema sulla macchina di turing. Infatti sono quasi sicuro che non mi darà manco un punto
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Gio 03 Agosto, 22:20:11 - 2017
Ma si sa qualcosa su quando escono i risultati di luglio? Non è possibile che ogni volta ci vuole tutto sto tempo per correggerli a mio avviso!!! Bah
Titolo: Re:Nuova modalità esame
Inserito da: Zepone - Ven 04 Agosto, 09:05:21 - 2017
Il problema, fondamentalmente, è che ad ogni appello d'Amore ha 4 esami da correggere: Algoritmi e Strutture Dati, Modelli e Complessità di Calcolo, Computer Network and Security, Web Application Security and privacy. Anche noi alla magistrale siamo in attesa, abbiamo fatto CNS la stessa mattina di modelli e il prof ci disse che ci sarebbe voluto comunque Agosto (inteso come quanto meno la prima settimana).
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mer 16 Agosto, 10:04:15 - 2017
Sono usciti i risultati di algoritmi dell'appello di luglio
Titolo: Re:Nuova modalità esame
Inserito da: Zepone - Mer 16 Agosto, 10:28:47 - 2017
Vero; il che lascia supporre che non dovrebbe mancare molto per gli altri risultati.
Titolo: Re:Nuova modalità esame
Inserito da: john - Mer 16 Agosto, 15:17:37 - 2017
Penso che gli studenti del vecchio ordinamento siano più o meno le prime 15 matricole della lista. Solo 3 l'hanno superato :-\ :-\ Beh un'altra strage  :sisi: :sisi: Rido per non piangere  ::) ::) ::)
Aspettiamo l'altra strage a modelli e siamo apposto  :P
Titolo: Re:Nuova modalità esame
Inserito da: Zepone - Gio 17 Agosto, 14:15:58 - 2017
Sospetto che dei 3 esami residui i primi risultati noti saranno quelli di Modelli; ipotizzo ciò perché tipicamente le materie di Morpheus sono tra le ultime che uno riesce a superare nella triennale, non tanto nella magistrale. Quindi credo che darà la priorità a Modelli. Ripeto, è un mio sospetto eh.
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Sab 26 Agosto, 18:33:35 - 2017
Per l'esame di modelli la correzione sarà in presenza nel suo studio lunedì dalle 9:30. Ma quindi chi non può esserci come fa a sapere i risultati?
Titolo: Re:Nuova modalità esame
Inserito da: john - Sab 26 Agosto, 19:57:25 - 2017
Ma cosa vuoldire correzione in presenza? Scusate ma mica ho capito -.-  Io comunque non so se riesco ad andare nel suo studio, come cacchio faccio ora -.- -.-
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Sab 26 Agosto, 20:52:07 - 2017
Sul sito c'è scritto questo: Correzione in presenza lun 28 agosto, dalle h 9:30, studio docente. Infatti mi chiedevo se per chi non riesce ad andare come può sapere i risultati? Ho mandato anche una mail al prof ma non ho ricevuto ancora risposta
Titolo: Re:Nuova modalità esame
Inserito da: john - Sab 26 Agosto, 21:03:38 - 2017
Io non so che dirti, mi trovo nella stessa situazione, che per favore scheggia89 potresti dirmi poi cosa ti ha detto, sempre se ti risponde ? Io non so se ci riesco, ma che p.....e ma perchè ogni volta deve fare così, perchèèèèè
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Sab 26 Agosto, 21:14:28 - 2017
Se risponde ti faccio sapere. Io penso,anzi spero, che alla fine li metterà anche online . Cmq conviene che mandi l'email anche tu magari a te risponde    :D
Titolo: Re:Nuova modalità esame
Inserito da: john - Sab 26 Agosto, 21:50:58 - 2017
Si si provo anchio ad inviarli una mail. Ma non capisco qual'è lo scopo di questa correzione in presenza, chi deve lavorare deve chiedere un giorno di permesso per farsi dire dal vivo che l'esame l'ha superato oppure bocciato (facendo le corna)?  :o :o :o :o  Vabbè, allora scheggia89 ci aggiorniamo allora dai.
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Dom 27 Agosto, 11:33:39 - 2017
Come ho sperato, la correzione in presenza era un opzione. Infatti sul sito ha corretto la cosa in questo modo:
Correzione in presenza lun 28 agosto, dalle h 9:30, studio docente. Naturalmente si tratta solo di un'opzione: tutti i risultati appariranno, come sempre, sul web, e la valutazione non risentirà della presenza/assenza dalla correzione del 28. Potrebbe accadere che i risultati escano sul web il 29 o il 30.
Titolo: Re:Nuova modalità esame
Inserito da: john - Dom 27 Agosto, 12:34:12 - 2017
Si si ho letto anch'io. Vabbe ora vedo se andarci comunque sul tardo pomeriggio, che comunque può servire, vediamo.
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mar 29 Agosto, 17:14:32 - 2017
So usciti i risultati di modelli. Per la cronaca ne è passato uno solo ahahahaha. Rido per non piangere
Titolo: Re:Nuova modalità esame
Inserito da: john - Mar 29 Agosto, 17:36:13 - 2017
Ecco si ho appena visto, scheggia ma ti ricordi questa cosa di chi prendeva meno di 12 non poteva fare il prossimo appello?  L ha specificato sul sito accanto al link dei risultati, che vuoldire che quelli del vecchio ordinamento il prossimo appello non lo fa nessuno tranne uno che ha preso 12.53?
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mar 29 Agosto, 17:53:04 - 2017
Ecco si ho appena visto, scheggia ma ti ricordi questa cosa di chi prendeva meno di 12 non poteva fare il prossimo appello?  L ha specificato sul sito accanto al link dei risultati, che vuoldire che quelli del vecchio ordinamento il prossimo appello non lo fa nessuno tranne uno che ha preso 12.53?
si ma questo vale nell'appello di settembre. Nel senso che chi è stato bocciato a luglio, può fare l'appello di settembre e nel caso prende meno di 12 punti non può fare l'appello straordinario di ottobre e verbalizza la bocciatura
Titolo: Re:Nuova modalità esame
Inserito da: john - Mar 29 Agosto, 17:56:30 - 2017
Ma sei sicuro scheggia? Guarda che se l ha specificato accanto al link dei risultati di luglio una ragione ci sarà, sennò l avrebbe specificato al momento in cui pubblica i risultati di settembre non credi ?

Edit

Scusa ho Letto male. Misa hai ragione a quanto pare questo parte da settembre
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mar 29 Agosto, 18:07:19 - 2017
Ma sei sicuro scheggia? Guarda che se l ha specificato accanto al link dei risultati di luglio una ragione ci sarà, sennò l avrebbe specificato al momento in cui pubblica i risultati di settembre non credi ?

eh si ne sono sicuro. Anche perchè dalle modalità d'esame c'è scritto:
[NEW] A partire dall'appello di settembre 2017 (incluso), chi consegue un risultato particolarmente negativo (< 12.00) durante l'esame dovrà saltare l'appello successivo (no distinzioni fra appelli regolari e straordinari); gli esiti delle prove a cui verrà successivamente ammesso saranno verbalizzati in ogni caso (promosso/bocciato).

Se fosse come dici tu avrebbe verbalizzato la bocciatura, ma a me non è arrivato nulla. E poi lo ha specificato sopra al link del form di prenotazione di settembre, non in quello di luglio. Comunque se non sei sicuro puoi sempre chiedere al prof :D
 
Titolo: Re:Nuova modalità esame
Inserito da: john - Mar 29 Agosto, 18:32:00 - 2017
Si si hai ragione  :asd: avevo letto male
Titolo: Re:Nuova modalità esame
Inserito da: john - Gio 31 Agosto, 13:59:23 - 2017
Ragazzi ma la quarta domanda dell ultimo esame di luglio di modelli, come l avete svolto? Io pensavo di averlo fatto bene invece  :-X :-X in allegato l esercizio
Titolo: Re:Nuova modalità esame
Inserito da: Chloe06 - Gio 14 Settembre, 22:20:59 - 2017
Scusate qualcuno ha i testi degli esami di algoritmi di giugno e luglio?? Grazie :)
Titolo: Re:Nuova modalità esame
Inserito da: LucaLindholm - Ven 15 Settembre, 17:53:25 - 2017
Soprattutto sarebbe utile capire come "impostare" le risposte alle varie domande e ho tanti dubbi.


In particolare, voi tutta la teoria sull'analisi degli algoritmi e le equazioni di ricorrenza, dove le avete studiate?

Per quanto riguarda la progettazione degli algoritmi e l'esercizio di miscellanea, ci sono degli argomenti che il professore predilige o su cui abbia particolarmente insistito?

Come si deve rispondere alla prima domanda dell'esercizio dei grafi?
 Io nell'esame di ASD di luglio avevo definito i nodi, gli archi e il tipo di problema, ma il professore me lo valutò solo il 10%, pur avendo sostanzialmente azzeccato l'algoritmo da usare nel secondo punto (sebbene valutato solo al 60%)...


Questo esame e quello di Modelli mi stanno mettendo un'angoscia che non avevo mai provato prima per altri compiti.

:(

P.S.: Come è andato l'esame di Modelli ieri?
Qualcuno ha il testo del compito?
Titolo: Re:Nuova modalità esame
Inserito da: Chloe06 - Ven 15 Settembre, 19:31:07 - 2017
Ecco il testo di modelli. Sinceramente non sapevo proprio come approcciare il problema 4 su CLIQUE.   :(
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Sab 16 Settembre, 09:37:42 - 2017
Per quanto mi riguarda l'esame è andato na mezza schifezza. Se riesco a prende 18 ho fatto un miracolo :). Per chi ha fatto modelli giovedì, come vi è andato. In particolare come bisognava rispondere alle domande del problema 1?Io ho avuto parecchi dubbi. Mentre gli altri come li avete svolti?
Titolo: Re:Nuova modalità esame
Inserito da: LucaLindholm - Sab 16 Settembre, 20:22:10 - 2017
Ecco il testo di modelli. Sinceramente non sapevo proprio come approcciare il problema 4 su CLIQUE.   :(

Grazie.   ;)

Per quanto mi riguarda l'esame è andato na mezza schifezza. Se riesco a prende 18 ho fatto un miracolo :). Per chi ha fatto modelli giovedì, come vi è andato. In particolare come bisognava rispondere alle domande del problema 1?Io ho avuto parecchi dubbi. Mentre gli altri come li avete svolti?

Purtroppo non posso aiutare, perché per ora sono concentrato su Algoritmi (relegando Modelli a ottobre o all'anno nuovo, sebbene abbia già iniziato un po' a interessarmene)... e proprio per questo ho posto quelle domande riguardo ad ASD subito sopra questi vostri post... perché ho come l'impressione che, non avendo potuto frequentare il suo corso, le slide e il libro non dicano tutto...

Chiedo scusa se sono un po' insistente in questa materia, ma stranamente la sto trovando più difficile di quanto non sembrasse all'inizio.    :|
Titolo: Re:Nuova modalità esame
Inserito da: girl8x - Dom 15 Ottobre, 12:08:15 - 2017
Salve ragazzi,
riguardo la nuova modalità di esame, le due prove possono essere sostenute in appelli differenti si, ma non importa se la sessione è ordinaria o straordinaria giusto? Indipendentemente dalla sessione quindi?
Cioè ad esempio se si sostiene una parte a novembre, l'altra parte la si può sostenere a gennaio o altro appello? (max entro 6 appelli).
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Sab 21 Ottobre, 20:25:10 - 2017
Scusate qualcuno ha i testi degli esami di algoritmi di giugno e luglio?? Grazie :)
Sono riuscito a reperire la parte di algoritmi dell'appello di luglio. Allego il testo dell' esame ed anche la mia personale soluzione (di cui non sono molto convinto delle soluzioni) ai primi due punti del problema 2 sulla programmazione. Sul punto tre del problema 2 non so proprio come procedere anche perché non so cosa si intende per rettangolo isotetico.

Classe BinNode.java
Codice: [Seleziona]
  public class BinNode{
        /* NON MODIFICARE NIENTE IN QUESTO FILE */
        protected int[] coordinates;
        protected BinNode left;
        protected BinNode right;

        public BinNode(int x, int y) {
            coordinates = new int[2];
            coordinates[0] = x;
            coordinates[1] = y;
            this.left = null;
            this.right = null;
        }
       
        public BinNode getLeft(){
        return left;
        }

        public BinNode getRight(){
        return right;
        }
       
        public BinNode setLeft(BinNode n){
        left = n;
        return left;
        }

        public BinNode setRight(BinNode n){
        right = n;
        return right;
        }
       
        public int[] getCoordinates(){
            return coordinates;
        }
    }

classe BST.java
Codice: [Seleziona]
public class BST{

    private BinNode root;

    public BST() {
        /* NON MODIFICARE */
        this.root = null;
    }

    public BinNode BST_insert(int x, int y) {
        /*DA IMPLEMENTARE*/
root = BST_insert(root, x, y);
return root;
    }

private BinNode BST_insert(BinNode root, int x, int y) {

    // Se albero vuoto, inserisco nodo
    if(root == null)
            return new BinNode(x, y);
       
// Prendo le coordinate (x1, y1) di root
int[] c = root.getCoordinates();

// Se il punto (x,y) < di root, mi sposto nel sottoalbero sinistro
if( (x < c[0]) || ( ( x == c[0]) && ( y < c[1]) ) )
    root.left = BST_insert(root.left, x, y);
// mi sposto nel sottoalbero destro
else if( (x > c[0]) || ((x == c[0]) && ( y > c[1])) )
    root.right = BST_insert(root.right, x, y);
else {
}

return root;
}


     public void print(BinNode t, int level) {
        /* MODOFICABILE*/
        for (int i = 0; i < level - 1; i++) {
            System.out.print("   ");
        }

        if (level > 0) {
            System.out.print(" |--");
        }
        if (t == null){
            System.out.println("#");
            return;
        }


        System.out.println( "(" + t.getCoordinates()[0] + "," + t.getCoordinates()[1] + ")" );

        print(t.getLeft(), level + 1);
        print(t.getRight(), level + 1);
    }
    public void BST_print(){
        /* MODOFICABILE*/
        print(root, 0);
    }

    public int aligned(int x){
        /*DA IMPLEMENTARE*/
if(root == null)
    return 0;

        return aligned(root, x, 0); //istruzione aggiunta per permettere la compilazione
    }

private int aligned(BinNode root, int x, int cont) {

// Prendo le ooordinate della radice
int[] c = root.getCoordinates();
if(x == c[0]) {
    cont = cont+1;
if(x < c[0] && root.getLeft() != null)
    cont = aligned(root.getLeft(), x, cont);
if(x > c[0] && root.getRight() != null)
    cont = aligned(root.getRight(), x, cont);
}

if(root.getLeft() != null)
cont = aligned(root.getLeft(), x, cont);
if(root.getRight() != null)
cont = aligned(root.getRight(), x, cont);

return cont;

}

    public int rangeQ(int x1, int y1, int x2, int y2){
        /*DA IMPLEMENTARE*/
        return 0; //istruzione aggiunta per permettere la compilazione
    }

}
Driver.java
Codice: [Seleziona]
public class Driver {


    public static void main(String[] argv) {

    BST b = new BST();
   
        b.BST_insert(1,4);
        b.BST_insert(6,6);
        b.BST_insert(3,4);
        b.BST_insert(5,1);
        b.BST_insert(6,4);
        b.BST_insert(2,7);
        b.BST_insert(2,2);
        b.BST_insert(8,1);
        b.BST_insert(6,2);
        b.BST_insert(8,7);
        b.BST_insert(1,1);
        b.BST_insert(8,1);

        System.out.println("Albero: \n");
        b.BST_print();

        System.out.println("\nRicerca valore x: \n");
        for (int k=0; k<10; k++){
            System.out.println("Numero nodi con coordinata x="+k+": " + b.aligned(k));
        }

        System.out.println("\nRicerca range: \n");
        int [][] coordinatesTest = {
            {0, 0, 10, 10},
            {2, 2, 2, 2},
            {2, 6, 2, 6},
            {3, 0, 2, 10},
            {0, 3, 10, 2},
            {0, 4, 10, 4},
            {2, 4, 10, 4},
            {3, 5, 2, 1},
            {2, 2, 3, 4},
            {2, 7, 3, 4},
            {4, 3, 7, 5}
        };

        for (int i=0; i<coordinatesTest.length; i++){
            System.out.println("x1="+ coordinatesTest[i][0] +", y1="+coordinatesTest[i][1]+", x2="+coordinatesTest[i][2]+", y2="+coordinatesTest[i][3]+": " + b.rangeQ(coordinatesTest[i][0], coordinatesTest[i][1], coordinatesTest[i][2], coordinatesTest[i][3]));
        }
       



    }
}

Ho provato anche a fare il problema 1 sempre dello stesso appello. Anche in questo caso si accettano suggerimeni sulla correttezza o meno della mia soluzione. In particolare nel punto a non sono molto sicuro della impostazione e svolgimento della equazione di ricorrenza

PROBLEMA 1

(a)  La dimensione dell'input è il numero di elementi dell'array, cioè n.  Sia T(n) = tempo esecuzione problema(int[]) e sia T1(n) = tempo esecuzione problema(int[] ,int, int)

Allora T(n) = T1(n) per n > 0 cioè l'array deve avere almeno un elemento nel caso peggiore, altrimenti costo costante algoritmo.

    T1(n) = c1               per n=1
    T1(n) = c2 + 3T1(n/3)    altrimenti

    Sviluppando l'equazione di ricorrenza avremo che:

    T1(n) = c2 + 3T1(n/3) = c2 + 3[ c2 + 3T1(n/9) = c2 + 3c2 + 9T1(n/9) = c2 + 3c2 + 9c2 + 27T1(n/27) = ... =
          = c2E 0k-1 3i   + 3kT1(n/3k)  (E sta ad indica la sommatoria e 0 , k-1 sono indici di partenza e fine)

l'eq di ricorrenza termina per n/3k = 1 ==> k = log3 n.

Quindi Tk = c2E 0log3 n -1 + 3log3 nT1(n/3log3n) = c2log3 n + nc1 ==> THETA(n)

Concludendo quindi il costo dell'algoritmo problema(int[]) è THETA(n).

(b) Si è possibile riformularlo senza introduzione scandendo l'array e andando a sommare gli elementi. Perché il metodo problema somma tutti gli elementi dell'array. La riformulazione è la seguente:

Codice: [Seleziona]
static double problemaIterativo(int[] a) {
    double somma = 0.0;
for(int i=0; i<=a.length-1; i++)
    somma += a[i];

return somma;

Ho provato anche a fare il problema 3 e ora posto come l'ho svolto io.(anche qui non sono sicuro delle mie risposte). Si accettano qualsiasi tipo di aiuto, suggerimento o correzione di ciò che ho scritto.

Problema 3

(a) è un albero AVL che fissata un altezza h, ha il minor numero di nodi possibile mantenendo il bilanciamento

(b) La relazione tra alberi di Fibonacci e sequenza di fibonacci è che come qualsiasi albero di fibonacci di altezza può essere ottenuto da una radice e da un sottoalbero di altezza h-2 a sinistra ed h-1 come sottoalbero destro, così la sequenza di fibonacci  di ciascun numero può essere ottenuto dalla somma dei due precedenti. In sintesi quindi un albero di fibonacci è la sequenza di fibonacci più 1.

(c) Ci permette di dire che l'altezza dell'albero è almeno THETA(log2 n). La dimostrazione basta guardare le slide su AVL 
Titolo: Re:Nuova modalità esame
Inserito da: CIP - Mar 24 Ottobre, 10:01:12 - 2017
Ragazzi, avrei un paio di domande veloce, magari qualcuno si è già trovato nella stessa situazione.
Dovrei provare l'esame all'appello straordinario, il problema è che sono attualmente poco preparato sulla parte di Modelli e non credo di farcela con i tempi. Ad ogni modo, in caso mi presentassi all'appello di algoritmi e non a quello di modelli, il compito di algoritmi verrebbe semplicemente scartato?
Per conservare una delle due parti si deve ottenere un voto non gravemente insufficiente nell'altra?
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Mar 24 Ottobre, 10:15:33 - 2017
Ragazzi, avrei un paio di domande veloce, magari qualcuno si è già trovato nella stessa situazione.
Dovrei provare l'esame all'appello straordinario, il problema è che sono attualmente poco preparato sulla parte di Modelli e non credo di farcela con i tempi. Ad ogni modo, in caso mi presentassi all'appello di algoritmi e non a quello di modelli, il compito di algoritmi verrebbe semplicemente scartato?
Per conservare una delle due parti si deve ottenere un voto non gravemente insufficiente nell'altra?
Da quello che ho capito io, se fai solo algoritmi e non modelli, il compito non viene scartato. Comunque er esserne certo, ti consiglio di chiedere conferma al professore.
Titolo: Re:Nuova modalità esame
Inserito da: CIP - Mar 24 Ottobre, 10:32:26 - 2017
Da quello che ho capito io, se fai solo algoritmi e non modelli, il compito non viene scartato. Comunque er esserne certo, ti consiglio di chiedere conferma al professore.

Grazie mille!
Titolo: Re:Nuova modalità esame
Inserito da: roberto93 - Gio 26 Ottobre, 12:02:28 - 2017
ciao ragazzi, ma la regola dei 12 punti minimi all'appello precedente per poter accedere al successivo è ancora valida? grazie
Titolo: Re:Nuova modalità esame
Inserito da: CIP - Gio 26 Ottobre, 13:13:44 - 2017
ciao ragazzi, ma la regola dei 12 punti minimi all'appello precedente per poter accedere al successivo è ancora valida? grazie
Stando al seguente link (http://"http://www.dis.uniroma1.it/~fiii/esame.html") la regola sarà valida da Gennaio 2018, riguarda solo la parte di Modelli e comporterà anche la verbalizzazione dell'esito negativo (che non ho idea di cosa implichi in termini di percorso accademico).
Titolo: Re:Nuova modalità esame
Inserito da: CIP - Gio 26 Ottobre, 20:48:26 - 2017
Stavo dando un'occhiata al post di Scheggia89 sull'appello di Luglio, sto provando a risolvere il problema al calcolatore, fornirò una mia soluzione appena disponibile. Comunque per il terzo punto, credo che non sia molto difficile. Se ho capito bene, si hanno 2 vertici opposti di un rettangolo. Prendendo questi vertici singolarmente e centrandoli nell'origine di 2 sistemi cartesiani, si ottiene un rettangolo per intersezione degli assi, non so se mi sono spiegato..  :asd:

EDIT: ho provato questa soluzione per il terzo esercizio del problema 2, e ho considerato punti interni anche i punti sulla frontiera del rettangolo. Qualcuno potrebbe confermare se il ragionamento è corretto?
Codice: [Seleziona]
   public int rangeQ(int x1, int y1, int x2, int y2){
        /*DA IMPLEMENTARE*/

        if(x1 > x2){
        int tmp = x2;
        x2 = x1;
        x1 = tmp;
        }
        if(y1 > y2){
        int tmp = y2;
        y2 = y1;
        y1 = tmp;
        }
        return rangeQRec(this.root,x1,y1,x2,y2);
    }

    public int rangeQRec(BinNode t, int x1, int y1, int x2, int y2){
    if(t==null) return 0;
    int[] c = t.getCoordinates();
    int count = 0;
    if(c[0] >= x1 && c[0] <= x2 && c[1] >= y1 && c[1] <= y2)count++;
return count + rangeQRec(t.getLeft(), x1,y1,x2,y2) + rangeQRec(t.getRight(), x1,y1,x2,y2);
    }

EDIT2: Qalcuno ha idea su dove è possibile prendere compiti d'esame di algoritmi, compresi dei pacchetti java
necessari per lo svolgimento? grazie!
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Ven 27 Ottobre, 17:51:50 - 2017
Stavo dando un'occhiata al post di Scheggia89 sull'appello di Luglio, sto provando a risolvere il problema al calcolatore, fornirò una mia soluzione appena disponibile. Comunque per il terzo punto, credo che non sia molto difficile. Se ho capito bene, si hanno 2 vertici opposti di un rettangolo. Prendendo questi vertici singolarmente e centrandoli nell'origine di 2 sistemi cartesiani, si ottiene un rettangolo per intersezione degli assi, non so se mi sono spiegato..  :asd:

EDIT: ho provato questa soluzione per il terzo esercizio del problema 2, e ho considerato punti interni anche i punti sulla frontiera del rettangolo. Qualcuno potrebbe confermare se il ragionamento è corretto?
Codice: [Seleziona]
   public int rangeQ(int x1, int y1, int x2, int y2){
        /*DA IMPLEMENTARE*/

        if(x1 > x2){
        int tmp = x2;
        x2 = x1;
        x1 = tmp;
        }
        if(y1 > y2){
        int tmp = y2;
        y2 = y1;
        y1 = tmp;
        }
        return rangeQRec(this.root,x1,y1,x2,y2);
    }

    public int rangeQRec(BinNode t, int x1, int y1, int x2, int y2){
    if(t==null) return 0;
    int[] c = t.getCoordinates();
    int count = 0;
    if(c[0] >= x1 && c[0] <= x2 && c[1] >= y1 && c[1] <= y2)count++;
return count + rangeQRec(t.getLeft(), x1,y1,x2,y2) + rangeQRec(t.getRight(), x1,y1,x2,y2);
    }

EDIT2: Qalcuno ha idea su dove è possibile prendere compiti d'esame di algoritmi, compresi dei pacchetti java
necessari per lo svolgimento? grazie!
Sinceramente io non ho capito bene il tuo ragionamento per il punto 3 dell'esercizio di programmazione, scusami :( . Potresti spiegarti meglio, magari con un esempio ?
Titolo: Re:Nuova modalità esame
Inserito da: CIP - Ven 27 Ottobre, 18:13:44 - 2017
Allora, provo con un esempio pratico al volo. Hai un punto p1=(1,1) e un punto p2=(2,2). Stando alla definizione data del rettangolo isotetico, cioè con lati paralleli agli assi coordinati (o meglio, assi cartesiani), otteniamo un rettangolo con vertici (1,1), (1,2), (2,1), (2,2). Questo rettangolo si ottiene in pratica disegnando i punti iniziali su un foglio (che da definizione sono vertici opposti!) e poi tracciando i vari lati, sapendo che sono paralleli agli assi cartesiani. Dall'intersezione dei lati tracciati a partire dai 2 vertici iniziali, otteniamo gli altri 2 vertici del rettangolo.
La soluzione java è molto semplice una volta capita questo ragionamento. In realtà per risolverlo ti basta sapere che la coordinata x1 delimita da sinistra, la x2 delimita da destra, y1 delimita dal basso e infine y2 dall'alto (queste premesse sono vere solo se x1 < x2 e y1 < y2, per questo io li riordino prima di passarli al metodo ricorsivo  :D ). Tutti i punti che rispettano queste condizioni di inclusione sono contenuti nel rettangolo.
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Ven 27 Ottobre, 19:50:50 - 2017
Allora, provo con un esempio pratico al volo. Hai un punto p1=(1,1) e un punto p2=(2,2). Stando alla definizione data del rettangolo isotetico, cioè con lati paralleli agli assi coordinati (o meglio, assi cartesiani), otteniamo un rettangolo con vertici (1,1), (1,2), (2,1), (2,2). Questo rettangolo si ottiene in pratica disegnando i punti iniziali su un foglio (che da definizione sono vertici opposti!) e poi tracciando i vari lati, sapendo che sono paralleli agli assi cartesiani. Dall'intersezione dei lati tracciati a partire dai 2 vertici iniziali, otteniamo gli altri 2 vertici del rettangolo.
La soluzione java è molto semplice una volta capita questo ragionamento. In realtà per risolverlo ti basta sapere che la coordinata x1 delimita da sinistra, la x2 delimita da destra, y1 delimita dal basso e infine y2 dall'alto (queste premesse sono vere solo se x1 < x2 e y1 < y2, per questo io li riordino prima di passarli al metodo ricorsivo  :D ). Tutti i punti che rispettano queste condizioni di inclusione sono contenuti nel rettangolo.
Ora credo di aver capito, grazie mille davvero :D
Titolo: Re:Nuova modalità esame
Inserito da: CIP - Sab 28 Ottobre, 10:24:27 - 2017
Ora credo di aver capito, grazie mille davvero :D
Figurati! Grazie a te per il testo dell'esame.
Comunque, stavo cercando di risolvere il problema 1. Mi trovo d'accordo con l'impostazione della tua equazione di ricorrenza.. però ho solo un dubbio. Nel caso dell'algoritmo, il passo base si ha se n==1 oppure se n==2, quindi non dovrebbe essere così? :

T(n) = 3T(n/3) + c1 per n > 2
T(n) = c2 per n <= 2

se fosse questo il caso, nello "srotolamento" dell'equazione di ricorrenza, andrei a considerare sempre n/(3^i) = 1 come passo base? Oppure in questo caso considererei n/(3^i) = 2?
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Sab 28 Ottobre, 11:39:54 - 2017
Figurati! Grazie a te per il testo dell'esame.
Comunque, stavo cercando di risolvere il problema 1. Mi trovo d'accordo con l'impostazione della tua equazione di ricorrenza.. però ho solo un dubbio. Nel caso dell'algoritmo, il passo base si ha se n==1 oppure se n==2, quindi non dovrebbe essere così? :

T(n) = 3T(n/3) + c1 per n > 2
T(n) = c2 per n <= 2

se fosse questo il caso, nello "srotolamento" dell'equazione di ricorrenza, andrei a considerare sempre n/(3^i) = 1 come passo base? Oppure in questo caso considererei n/(3^i) = 2?
Non capisco quando dici che il passo base si ha anche per n==2. Forse ti riferisci al passo if(i + 1 == j) return a + a[j]; vero? In quel caso, ma non ne sono molto sicuro, puoì scegliere o uno o l'altro, poichè sono valori costanti che non infuenzano analisi asintotica. Tra i due scelgo n== 1 perchè è più facile
Titolo: Re:Nuova modalità esame
Inserito da: CIP - Sab 28 Ottobre, 13:59:19 - 2017
Ok, ha senso il tuo ragionamento :)
Solo una cosa che volevo precisare riguardo l'ultimo passaggio dell'equazione di ricorrenza.
La sommatoria ha per somma il termine  [1 - 3(log3(n)-1)+1] / (1 - 3), che semplificata diventa (1 - n)/(1-3), giusto? non cambia il costo asintotico dell'algoritmo, era solo per essere precisi a livello di calcolo numerico  ;D
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Sab 28 Ottobre, 15:09:14 - 2017
Ok, ha senso il tuo ragionamento :)
Solo una cosa che volevo precisare riguardo l'ultimo passaggio dell'equazione di ricorrenza.
La sommatoria ha per somma il termine  [1 - 3(log3(n)-1)+1] / (1 - 3), che semplificata diventa (1 - n)/(1-3), giusto? non cambia il costo asintotico dell'algoritmo, era solo per essere precisi a livello di calcolo numerico  ;D
si credo di si. :D il problema 1 quindi alla fine può essere corretto? :D :D
Titolo: Re:Nuova modalità esame
Inserito da: CIP - Sab 28 Ottobre, 15:29:21 - 2017
Beh, secondo me l'equazione di ricorrenza è impostata e sviluppata bene, quindi sarei portato a dire di si.
Poi non so se c'è qualcosa che ci sta sfuggendo, ma non credo.
Anche il problema 2 è giusto.
Sto ripassando la parte sui grafi per poter fare il quarto.
Devo dire che se i primi due esercizi sono più o meno sempre così, allora sono abbastanza abbordabili.
Il quarto a differenza degli altri mi crea sempre qualche problemino e il terzo è totalmente casuale, quindi serve anche un po' di fortuna  :asd:
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Sab 28 Ottobre, 16:26:17 - 2017
Beh, secondo me l'equazione di ricorrenza è impostata e sviluppata bene, quindi sarei portato a dire di si.
Poi non so se c'è qualcosa che ci sta sfuggendo, ma non credo.
Anche il problema 2 è giusto.
Sto ripassando la parte sui grafi per poter fare il quarto.
Devo dire che se i primi due esercizi sono più o meno sempre così, allora sono abbastanza abbordabili.
Il quarto a differenza degli altri mi crea sempre qualche problemino e il terzo è totalmente casuale, quindi serve anche un po' di fortuna  :asd:
Ho le stesse tue difficoltà sul problema 4 sui grafi, infatti ancora non sono riuscito a dare una possibile soluzione. Il terzo di solito riguarda la parte teorica di algoritmi ma non sempre è così però, mette di solito cose strane
Titolo: Re:Nuova modalità esame
Inserito da: scheggia89 - Lun 30 Ottobre, 17:59:17 - 2017
Posto una mia personale soluzione (si accettano obiezioni dato che non sono molto convinto di ciò) punto (a) del problema 4 sui grafi dell'appello di luglio.

Il grafo in questione è un grafo non orientato pesato. I vertici sono gli n edifici ed il centro di distribuzione C con coordinate (x1,y1), .... , (xn,yn). Gli archi sono i cavi necessari al collegamento dove il peso è rappresentato dalla lunghezza del cavo stesso. Il problema da risolvere è quelllo dei cammini minimi ed in particolare è il SSSP(G, s) (Single Source Shortest Path), cioè determinare un albero dei cammini radicato in s, dove s è la sorgente che rappresenta il centro di distribuzione C.

Sui punti (b), (c) ancora ci sto ragionando
Titolo: Re:Nuova modalità esame
Inserito da: LucaLindholm - Mer 01 Novembre, 18:33:12 - 2017
Posto una mia personale soluzione (si accettano obiezioni dato che non sono molto convinto di ciò) punto (a) del problema 4 sui grafi dell'appello di luglio.

Il grafo in questione è un grafo non orientato pesato. I vertici sono gli n edifici ed il centro di distribuzione C con coordinate (x1,y1), .... , (xn,yn). Gli archi sono i cavi necessari al collegamento dove il peso è rappresentato dalla lunghezza del cavo stesso. Il problema da risolvere è quelllo dei cammini minimi ed in particolare è il SSSP(G, s) (Single Source Shortest Path), cioè determinare un albero dei cammini radicato in s, dove s è la sorgente che rappresenta il centro di distribuzione C.

Sui punti (b), (c) ancora ci sto ragionando

Io, per il punto (b) del 4° esercizio di luglio, scrissi semplicemente l'algoritmo di Prim-Jarnik come trovato sul libro e basta... me lo valutò al 60%, il che significa che andava "personalizzato", ma non so come.
Titolo: Re:Nuova modalità esame
Inserito da: Chloe06 - Lun 11 Dicembre, 19:50:45 - 2017
Qualcuno ha il testo dell'esame di modelli di novembre? Grazie :)
Titolo: Re:Nuova modalità esame
Inserito da: LucaLindholm - Lun 08 Gennaio, 00:32:25 - 2018
Qualcuno ha il testo dell'esame di modelli di novembre? Grazie :)

Tra l'altro, riguardando i risultati del compito di novembre, mi acocrgo solo ora che gli esercizi fossero ben 5!

Come erano strutturati gli esercizi, cosa chiedevano?

Credevo fossero solo 4 e organizzati come a luglio... ora sono un po' impensierito.

:|