Sab 24 Agosto, 15:10:30 - 2019

Autore Topic: Nuova modalità esame  (Letto 9998 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline scheggia89

  • Studente di Dottorato
  • ***
  • Post: 156
  • FeedBack: +3/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #105 il: 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.

Offline john

  • Neo-Laureato
  • **
  • Post: 68
  • FeedBack: +0/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #106 il: 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)
« Ultima modifica: Mer 14 Giugno, 10:07:09 - 2017 da john »

Offline scheggia89

  • Studente di Dottorato
  • ***
  • Post: 156
  • FeedBack: +3/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #107 il: 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? 

Offline zeusm

  • Studente
  • *
  • Post: 32
  • FeedBack: +0/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #108 il: 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.

Offline john

  • Neo-Laureato
  • **
  • Post: 68
  • FeedBack: +0/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #109 il: 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.

Offline nox91

  • Global Moderator
  • Studente
  • *****
  • Post: 24
  • FeedBack: +1/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #110 il: 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?

Offline john

  • Neo-Laureato
  • **
  • Post: 68
  • FeedBack: +0/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #111 il: 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  :-\
« Ultima modifica: Mer 14 Giugno, 15:47:08 - 2017 da john »

Offline Cingols

  • Studente
  • *
  • Post: 26
  • FeedBack: +4/-1
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #112 il: Mer 14 Giugno, 16:51:36 - 2017 »
Chiedeva i cammini minimi, si faceva con bellman-ford!
<.<

Offline scheggia89

  • Studente di Dottorato
  • ***
  • Post: 156
  • FeedBack: +3/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #113 il: 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?

Offline roberto93

  • Studente
  • *
  • Post: 25
  • FeedBack: +2/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #114 il: Mar 04 Luglio, 16:33:08 - 2017 »
raga siamo al 4 aprile, il 13 c'è il secondo appello, ma sti risultati??

Offline LucaLindholm

  • Studente
  • *
  • Post: 45
  • FeedBack: +1/-0
  • Luca Lindholm
    • Mostra profilo
    • Luca Lindholm
Re:Nuova modalità esame
« Risposta #115 il: 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...

:(
Studente di Ingegneria Informatica, sviluppatore per Windows (UWP).

Offline LucaLindholm

  • Studente
  • *
  • Post: 45
  • FeedBack: +1/-0
  • Luca Lindholm
    • Mostra profilo
    • Luca Lindholm
Re:Nuova modalità esame
« Risposta #116 il: 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?
« Ultima modifica: Ven 14 Luglio, 17:49:52 - 2017 da LucaLindholm »
Studente di Ingegneria Informatica, sviluppatore per Windows (UWP).

Offline scheggia89

  • Studente di Dottorato
  • ***
  • Post: 156
  • FeedBack: +3/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #117 il: 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).

Offline Cingols

  • Studente
  • *
  • Post: 26
  • FeedBack: +4/-1
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #118 il: 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.
<.<

Offline john

  • Neo-Laureato
  • **
  • Post: 68
  • FeedBack: +0/-0
    • Mostra profilo
Re:Nuova modalità esame
« Risposta #119 il: 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 ?