Ven 19 Luglio, 04:27:59 - 2019

Autore Topic: Soluzioni esami recenti (parte di Algoritmi)  (Letto 9559 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline yoshy87

  • Studente
  • *
  • Post: 48
  • FeedBack: +6/-0
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #15 il: Lun 15 Luglio, 15:51:03 - 2013 »
In questo esame viene richiesto il costo in termini di spazio del metodo

http://www.dis.uniroma1.it/~fiii/esame/AA%202011-12/4.appello--24-07-2012/fiii20120724_FI2.pdf

come si calcola?  :oooo: :help:
"L'università americana di Berkeley ha prodotto due importanti invenzioni: l'LSD e Unix; credo non sia una coincidenza."

Offline unòzer

  • Studente di Dottorato
  • ***
  • Post: 194
  • FeedBack: +10/-4
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #16 il: Lun 15 Luglio, 16:20:24 - 2013 »
Secondo me è O(n) con n numero di elementi dell'array. Perché ad ogni passo ricorsivo salva in temp un elemento dell'array per poi invertirlo.

Offline heavenriver

  • Global Moderator
  • Direttore di Dipartimento
  • *****
  • Post: 1060
  • FeedBack: +103/-67
  • z = z² + c
    • Mostra profilo
    • Sito web (Curriculum Vitae)
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #17 il: Mar 16 Luglio, 08:40:41 - 2013 »
Secondo me è O(n) con n numero di elementi dell'array. Perché ad ogni passo ricorsivo salva in temp un elemento dell'array per poi invertirlo.

Ragionevole, concordo. Più in generale, per "spazio" si intende quanto occupa in memoria rispetto alla dimensione dell'input :sisi:

Offline Vagabond

  • Neo-Laureato
  • **
  • Post: 88
  • FeedBack: +4/-2
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #18 il: Dom 08 Settembre, 18:56:10 - 2013 »
Ciao ragazzi. Come fareste il punto b (rendere iterativo il metodo) del primo esercizio del 11 Novembre 2011?

public class mistero {
   
   private static double mistero(double[] a, int i, double x){
      if(i == a.length-1) return a;
      return a + x*mistero(a,i+1,x);
   }
   
   public static double mistero(double[] a, double x){
      return mistero(a,0,x);
   }
}

Offline heavenriver

  • Global Moderator
  • Direttore di Dipartimento
  • *****
  • Post: 1060
  • FeedBack: +103/-67
  • z = z² + c
    • Mostra profilo
    • Sito web (Curriculum Vitae)
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #19 il: Lun 09 Settembre, 09:25:08 - 2013 »
E' un semplice metodo che calcola la somma dei valori contenuti in un array. Basta fare un banale ciclo for per convertirlo in iterativo :sisi:

Offline lucanox

  • Professore Associato
  • *
  • Post: 587
  • FeedBack: +61/-35
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #20 il: Lun 09 Settembre, 10:12:26 - 2013 »
non calcola la somma dei valori..  moltiplica i valori a* x e li somma .. per esempio dato un array di double { 1.0 , 2.0, 3.0  } e un double x (per esempio 2.0  )l'output sarà 1.0 +2.0*(2.0+2.0*(3.0+ 2.0*(1.0))) = 25.0

Offline Giurina

  • Studente di Dottorato
  • ***
  • Post: 182
  • FeedBack: +5/-2
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #21 il: Lun 09 Settembre, 14:39:24 - 2013 »
non calcola la somma dei valori..  moltiplica i valori a* x e li somma .. per esempio dato un array di double { 1.0 , 2.0, 3.0  } e un double x (per esempio 2.0  )l'output sarà 1.0 +2.0*(2.0+2.0*(3.0+ 2.0*(1.0))) = 25.0

Io farei:

INT m = a[a.length-1];
For(INT i = a.length-2; i>= 0; i--){
     m = m per x;
     m += a;
}
Return m;

Controlla se è giusto che l'ho fatto al volo e scritto con il cell

Offline Giurina

  • Studente di Dottorato
  • ***
  • Post: 182
  • FeedBack: +5/-2
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #22 il: Mar 10 Settembre, 12:18:42 - 2013 »
Ragazzi, qualcuno ha fatto il problema 3 del compito del 14/09/2011?
« Ultima modifica: Mar 10 Settembre, 12:42:09 - 2013 da Giurina »

Offline ciaociao

  • Studente
  • *
  • Post: 37
  • FeedBack: +6/-1
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #23 il: Mar 10 Settembre, 13:21:11 - 2013 »
Ragazzi, qualcuno ha fatto il problema 3 del compito del 14/09/2011?

Ho provato a farlo sfruttando il DFS ed aggiungendo ai vertici un campo int per memorizzare l'altezza dell'albero DFS  a cui si trova; ho scritto lo pseudocodice supponendo di aver gia settato tutti i vertici e gli spigoli unexplored:

Algorithm DFS(G, v)
Setlabel(v, visited)
For all e ∈ G.incidentEdge(v)
     If getlabel(e) = unexplored
     W <- opposite(v,e)
     If getlabel(w) = unexplored
         Setlabel(w, discovery)
         DFS(G,w)
     Else if w.getaltezza() = v.getaltezza() setlabel(e, cross)
     Else if w.getaltezza() > v.getaltezza() setlabel(e, forward)
     Else setlabel(e, back)



Back (v,w) = w è un antenato di v nell'albero degli archi discovery
Forward (v,w) = w è nel livello successivo di v nell'albero degli archi discovery
Cross (v,w) = w nello stesso livello di v nell'albero degli archi discovery

Che ne dite? Ha senso?

Offline Giurina

  • Studente di Dottorato
  • ***
  • Post: 182
  • FeedBack: +5/-2
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #24 il: Mer 11 Settembre, 09:38:18 - 2013 »
Domanda sull'esame dell' 11/11/2011
Il problema 2b dice:
Citazione
istanziare(in java) il PQ-sort nel caso di coda di priorita implementata con lista ordinata e confrontarlo con l'insertion-sort(descritto in java)

Sulle slide c'è scritto:
Citazione
Insertion-sort è una variante di PQ-sort dove la coda di priorità  è implementata con una sequenza ordinata

Quando mi chiede di confrontarli cosa devo fare visto che in teoria sono la stessa cosa?

Offline Giurina

  • Studente di Dottorato
  • ***
  • Post: 182
  • FeedBack: +5/-2
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #25 il: Mer 11 Settembre, 11:03:46 - 2013 »
Del problemama 3 ho svolto il punto c che nelle soluzioni gia postate non c'era;
Secondo voi va bene??????
Codice: [Seleziona]
public boolean compute(String x){
      Return compute( x, this.root(), 0); // ho supposto che il grafo abbia una radice che rappresenta lo stato iniziale
}

Public boolean compute(string x, vertex r, int i){
     If (i<x.length) return r.isFinal();   //isFinal() ritorna un booleano a seconda se lo stato n è finale(true) o no(false)
     Char c = x.charAt(i);
     Iterator<edge> it = incidentEdge(r).iterator();
     While(it.hasNext()) {
          Edge e = it.next;
          If (e.getSimbolo() = c) {
              Vertex v = opposite(r, e);
              return compute(x, v, i+1);
          }
      }
      Return false;
}

Offline yellow

  • Neo-Laureato
  • **
  • Post: 59
  • FeedBack: +1/-0
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #26 il: Sab 14 Settembre, 21:17:44 - 2013 »
Vorrei chiedere secondo voi se è esatta questa implementazione per il problema 2 di questo testo d'esame http://www.dis.uniroma1.it/~fiii/esame/AA%202011-12/5.appello--12-09-2012/fiii20120912_ASD.pdf
Grazie!
qui il codice: http://pastebin.com/wBnzyxzz
o qui sotto:
Codice: [Seleziona]
public class RecursionTree{
 
        private RecursionNode nodo;
        private RecursionTree root;
        private RecursionTree figlioS;
        private RecursionTree figlioD;
        private countNode;
       
        public RecursionTree(RecursionNode n){}
        public RecursionTree(){}
       
        public int size(){}
        public RecursionTree getRoot(){}
        public RecursionNode getNode(){}
        //se il RecursionTree è vuoto questo metodo aggiunge la radice
        public RecursionTree addFiglio(){}
        private RecursionTree aggFiglioS(RecursionNode fs){}
        private RecursionTree aggFiglioD(RecursionNode fd){}
        private RecursionTree getFiglioS(){}
        private RecursionTree getFiglioD(){}
        private RecursionTree removeFiglioS(){}
        private RecursionTree removeFiglioD(){}
        public RecursionTree remove(){}
        private boolean isLeaf(){}
        private RecursionTree removeInternal(RecursionNode n){}
        public RecursionTree removeExternal(RecursionNode n){}
       
       
       
       
       
        public static RecursionTree mergeSort(int[] a){
                RecursionTree result=new RecursionTree();
                return mergesortRic(a,0,a.length-1,result);
        }
       
       
       
        public static RecursionTree mergeSortRic(int[] a,int i, int j, RecursionTree tree){
                if(i>=j) return tree;
               
               
                else{
                        int medio=(i+j)/2;
                        mergeSortRic(a,i,medio,tree.getFiglioS());
                        mergeSortRic(a,medio+1,j,tree.getFiglioD());
                        return tree.addFiglio(merge(a,i,medio,j,tree));
                }
                // i while hanno un costo di O(2((j-1)+1))
                //il mergeSort ha funzione T(n)=T(n/2)+T(n/2)+nc2,T(0)=c1; dunque 2T(n/2)+nc2 per il master Theorem 2==2 e quindi O(n^1*log(n)) come già sapevamo
                //poichè le operazioni sugli alberi sono fatte sequenzialmente il loro costo è O(1) per ogni inserimento di un nodo e quindi il costo totale è O(n)
                // il costo totale di mergeSort(int[] a) è dunque O(nlogn)
        public static RecursionTreee merge(int[] a,int i, int medio, int j, RecursionTree tree){
               
                int it1=i;
                int it2=medio+1;
                int[] aux=new int[(j-i)+1];
                int countAux=0;
/*              while(it1<=j){
                        aux[countAux++]=a[i++];
                }
                iti=i;
                countAux=0;
        */
                while(it1<=medio && it2<=j){
                        if(a[it1]<=a[it2]){
                                aux[countAux++]=a[it1++];
                        }else{
                                aux[countAux++]=a[it2++]
                        }
                       
                }
                while(it1<=medio){
                        aux[countAux++]=a[it1++];
                }
                while(it2<=j){
                        aux[countAux++]=a[it2++];
                }
                countAux=0;
                it1=i;
                while(i<=j){
                        a[it1++]=aux[countAux++];
                }
                return new RecursionTree(aux);
       
        }
        //costo O(n) dove n è il numero di nodi quindi size(), poichè visita tutti i nodi una sola volta
        public static void preOrder(RecursionTree t){
                if(t==null) return;
                else{
                        System.out.println(t.getNode().geElement());
                        preOrder(t.getFiglioS());
                        preOrder(t.getFiglioD());
                }
       
        }
« Ultima modifica: Sab 14 Settembre, 21:38:15 - 2013 da yellow »