Divideix I Venc
  • ** Siga v un Array d'int que representen una corba contínua i monòtona creixent, v[0]<0 i v[v.length-1>0]. Hi ha una posició k de v, tal que entre v[k] i v[k+1] la funció val 0. Dissenya el mètode recursiu (encreuament) que més eficientment calcule eixa posició k. Eva Santonja Civantos **
public static int encreuament(T[]v, int i, int j){
 i = 0;
  j= v.length-1;
int p = (i + j) / 2;
if(v[p]<=0){
    if(v[p+1] > 0{
        return p;  }
    else { return encreuament(v, p+1, v.length-1);  }
}
else{ return encreuament(v, 0, p); }
}
  • Quan es considera que un algorisme d'ordenació és estable? Guillermo Montilla Tomás
    • Un algorisme d'ordenació es denomina estable si preserva l'ordre relatiu original entre valors iguals.

Quin és el millor cas de l'algoritme de selecció?## María Alabau Bosque
* Quan l'element a cercar és el menor (k = 1) o el major (k = n) i aquest actua com a pivot.

  • Quina és l’estrategia a seguir per a l’implementacio de la cerca binaria o dicottomica en un array ordenat? Cardona Lorenzo, Víctor
    • Dividir i vencer. Comprovar l’element de la meitat, si es igual es retorna i, si no, tornar a cridar a la funció però buscant només a la meitat de l’array on podría trobar-se.
  • Quins son el passos de l'aproximació divideix i venceràs? García Agost, David
    • 1 Dividir el problema en subproblemes. 2 Vèncer, resoldre els subproblemes de forma recursiva.3 Combinar, les solucions dels subproblemes per a obtenir la solució al problema original.
  • En que es diferencien els algorismes de Mergesort i Quicksort? Talens Ferrer, Raúl
    • En que la part més costosa de l'algorisme és el pas de dividir en Quicksort, mentre que en Mergesort és el pas de combinar.
  • Quin és l'objectiu del algorisme partició utilitzat en Quicksort? Vicente Gavilà Buigues
    • L'objectiu d'aquest algorisme es reorganitzar un vector A[x…z], deixant en A[x…y] els elements menors o igual que en A[y+1…z], fent que queden el més equilibrat posible.
  • Per què a l'algorisme de partició no es situa el pivot automàticament a la mitjana del vector? Serrano Estellés, Héctor
    • Perquè el cost de calcular la mitjana d'un vector és molt elevat.
  • Quin es el problema de la selecció del k-èssim i com es pot solucionar? Sánchez López, Daniel
    • El problema consisteix en cercar el k-èssim menor element. La solució mes eficient seria utilitzar l'algorisme de Dividir i Venç amb la idea de l'algorisme de partició: El vector es divideix en dos, on en un els elements del primer seran menors o iguals al pivot, i en el segon, majors o iguals. Despres busquem en el subvector corresponent fent cridades recursives i si el nombre es menor que el pivot, aleshores estarà en el primer subvector, i si no, en el segon.
  • Quan és possible que un algorisme amb cost quadràtic guanye a un amb cost lineal? Maria Ribes de la Concepción
    • Quan el número de dades a processar és molt baix, la funció quadràtica dóna millor temps de resposta que una lineal.
  • Quin es el pitjor cas posible per a l'algorisme Quicksort? Per què? Genís Martínez Sanchis
    • El pitjor cas ocorre quan, agafant com pivot el primer element, el vector està totalment ordenat en l'ordre correcte o en l'incorrecte, o equivalentment quan el pivot és major o menor a tots els altres degradant-lo a un cost de O(n²).
  • Què és el teorema mestre i per a què s'utilitza? Esteve Chulià, Joan Ramón
    • El teorema mestre es una ferramenta de resolució d'equacions de recurrència que ens permet trobar una solució per a aquestes de forma ràpida i senzilla. Hi ha que tindre en compte que algunes d'aquestes equacions no es poden resoldre d'aquesta manera.
  • A l'hora d'implementar l'algorisme Quicksort, fem ús d'un algorisme de partició. Perquè a aquest no es recomanable gastar la mitjana del vector (encara el que partiria de manera equilibrada) i quins recursos utilitzem en el seu lloc? Miguel García Bohigues
    • Per el seu elevat cost de càlcul degut que tindriem que tindre el vector ordenat per a trobar la mitjana. Com a recursos alternatius podem utilitzar la mitjana entre 3 elements qualsevol, el primer element del vector, o un pivot aleatori.
  • Realitza un pas de particio amb l'algorisme Quicksort prenent com a pivot el nº 55 del següent array [55 33 22 66 44 11 33 77] Jose Daniel Ferrando Ferrer
    • [33 33 22 11 44 66 55 77]
  • Quina és la diferència de costos entre una cerca seqüencial i una cerca binària (o dicotòmica)? Brines i García, Joaquim
    • La cerca seqüencial té un cost linial i la cerca binària té un cost logarítmic
  • Com es podrien millorar els costos en l'algoritme Mergesort? Cristian Medina Azorín
    • Una possible millora seria no realitzar cridades recursives quan la talla del vector a tractar es xicoteta, fent una ordenació per inserció o selecció directa.
  • Quin es el millor cas i el pitjor cas de l'algorisme de selecció? Aitana Villaplana
    • En el millor cas, l’element a cercar és el menor (k = 1) o major (k = n) i aquest actua com a pivot, i aixó tendría un cost O(n). I en el cas pitjor, el vector es troba ordenat de forma no decreixent i cerquem l’element major (k = n), en eixe cas tendría cost O(n^2).
  • En MergeSort, per què no s'utilitza l'algorisme de fusió que no utilitza un vector adicional per a evitar l'inconvenient de l'espai? Àngel Chirlaque Zapata
    • Perquè el que fa que tinga una constant alta el MergeSort és la quantitat de dades que ha de moure. Així que una forma de reduir-les és no usar un vector auxiliar.
  • En l'algorisme quicksort, quina millora es podría fer respecte al pivot? Joan Vicent Pedro Martí
    • Triar-lo de forma aleatoria, abans de realitzar cada partició s’intercanviaria el valor de l’element utilitzat com a pivot amb el valor de l’element seleccionat a l’atzar.
  • Dins de l'estratègia de MergeSort, en que consisteix el pas de combinar? Jordi Belda Felipe
    • És la combinació de les dues subseqüències ordenades anteriorment(de forma recursiva utilitzant mergesort) per a generar la solució general mitjançant merge(fusió, mescla natural).
  • Suposem que vivim en el 2060, les persones ja no s'identifiquen amb un nom propi, sinó que s'identifiquen pel número de DNI (sense lletra). La tecnologia ha avançat i quan volem accedir al metre de València, aquest s'encarregarà d'ordenar a les persones, segons el seu número de DNI (de menor a major), per a indicar-los en què vagó del metre s'han de seure. Tin en conter que cada metre té 6 vagons (talla de l'array) i en aquest moment entren al metre 6 persones (elements del array). Si fores l'encarregat de gestionar el sistema d'ordenament del metre, Quins dels següents algoritmes (mergesort, inserció directa, quicksort, selecció directa) són els més recomanables? Per què? Algun no es podria usar? Stella Esparza Torregrosa
    • Com s'ha mencionat en l'enunciat, tenim un array de 6 elements, és a dir, un array amb una talla xicoteta. De primeres podríem usar qualsevol dels algoritmes d'ordenament mencionats però si ens centrem en el detall de què l'array és d'una talla molt xicoteta seria convenient utilitzar inserció directa o selecció directa, perquè encara que aquests tinguen un cost quadràtic, quan treballem amb talles d'array xicotetes són molt eficients.
  • Indica quin és el cost en el cas millor i pitjor de l'algorisme quicksort. Raona la resposta. Albert Grau Anguera
    • El cas millor tindrà un cost de linial, ja que dividirà en dues parts equilibrades. En canvi, el cas pitjor tindrà un cost quadràtic, ja que dividirà una meitat amb un element i l'altre amb els restants.
  • Quin és el teorema mestre per a recurrència divisoria? T(n) = aT(n / b) + Θ(nk) amb a ≥ 1 i b > 1. Javier Contrí González
    • T(n) = O (nlogba) si a > bk
    • O (nk log n) si a = bk
    • O (nk) si a < bk
  • Quins son el principal avantatge i el principal inconvenient de l'algoritme MergeSort? Enrique Antonio Cores Rodríguez
    • Que amb MergeSort queda garantit un cost temporal de O(n log n) fins i tot en el pitjor cas, però el cost de memoria es molt elevat.
  • Si l'algoritme QuickSort te un cost menor que molts altres, com es que no es l'únic que es gasta? Pablo S. Díaz Castelló
    • Cada algoritme te unes ventajes i uns inconvenients, es per tant que també s'han de tindre en compte factors com el cost de càrrega de memòria, tipus de dades a ordenar, etc.
  • Una fábrica de bollería produce donnuts. Para controlar la calidad del producto, tienen en cuenta su peso; pero, por un defecto en la máquina, existe un donnut inferior a los demás. Suponiendo que un array v contiene las referencias de todos los donnuts (string) y que se dispone de un método peso(v, i, j, k, l) tal que, en constante, dado dos sub-Arrays de v de igual talla v[i,j] y v[k, l] … Devuelve 0 si los donnuts de v[i, j] pesan lo mismo que las de v[k, l]. Devuelve -1 si los donnuts de v[i, j] pesan menos que los de v[k, l]. Devuelve 1 si los donnuts de v[i, j] pensan mas que los de v[k, l]. Resuelve con el método Divide y Venceras que, con coste logarítmico en el peor caso, devuelva el índice del array v donde se encuentra el donnut defectuoso. Nota: La caja puede ser tanto PAR como IMPAR. Miguel Ángel Mateo Casalí
Public static int DonnutDefectuoso (String[] v) { return DonnutDefectuoso(v, 0, v.length -1);} 
Private static int DonnutDefectuoso(String[] v, int i, int j){
if (i == j) return i;
int m = (i +j)/2;
if ((i-j+1)%2 == 0){
    if (DonnutDefectuoso(v, i, m, m+1, j< 0) return DonnutDefectuoso(v, i, m);
     else return DonnutDefectuoso(v, m+1,j);}
else {
    int res = peso (v, i, m-1, m+1, j);
    if (res == 0) return m;
    if ( res < 0) return DonnutDefectuoso(v, i, m-1);
    return DonnutDefectuoso(v, m+1, j);}
}
  • A l'algorisme de selecció, en el millor del casos, l'element a cercar es o el menor o el major, i aquest fa també de pivot; però, qué passa en la cas del que l'element a cercar siga la mitjana? Francesc Ferrer Pérez.
    • Amb cada execució del métode, la talla del problema es redueix a la meitat, fins trobar l'element cercat fent seleccions continues "de mig vector en mig vector";el cost, es igualment lineal.
  • Sabent que l'estructura del MergeSort es dividir, vencer i combinar, cap la posibilitat de millorar aquest algorisme? Martinez Chulvi, Vicent.
    • Per exemple, podriem no realitzar cridades recursives quan la talla del vector és xicoteta, fent una ordenació per inserció o selecció directa, o tanmateix podriem evitar moviments redundants de dades fent cridades alternativament sobre el vector original i el vector auxiliar.
  • Cual sería el cas millor del anàlisi del cost de Quicksort? Jesús Peiró López
    • El cas millor sería aquell en el qual cada trucada a partition deixa les dues parts equilibrades.
  • Com podríem millorar l'algorisme QuickSort quan la talla del vector es xicoteta? Álvaro Salvador González
    • Llevant les cridades recursives, i canviar a un algorisme d'inserció o de selecció directa.
  • Quin sería el valor ideal per al pivot el l'algorisme de partició? Iris López Martínez
    • És clar que el valor ideal per al pivot és la mitjana del vector, però açò resulta massa car de calcular.
  • Dada la siguiente implementación del problema de la falsa moneda: Andrea Murcia Serrano
private static int falsaMoneda(double [] vec, int ini, int fi){
    if (ini == fi) return ini;
    int m=(ini+fi)/2;
    if ((fi-ini+1)%2 != 0){ // no es parell
        if (pesar(vec, ini, m-1) == pesar(vec, m+1, fi)){
        return m;
        }else{
        if (pesar(vec, ini, m-1) < pesar(vec, m+1, fi)){
            return falsaMoneda(vec, m+1,fi);
        } else {
            return falsaMoneda(vec, ini, m-1);
        }
        }
    } else { // par
        if (pesar(vec, ini, m) < pesar(vec, m+1, fi)){
        return falsaMoneda(vec, m+1,fi);
        } else{
        return falsaMoneda(vec, ini, m);
        }
    }
    }

* ¿Qué pasaría si la variable m fuera calculada como m=(fi-ini)/2?
* El algoritmo creado fallaría porque la llamada recursiva no se haría correctamente. Estaríamos accediendo a una posición del array con la que no queremos trabajar. Ejemplo: si tenemos un array de 5 elementos (pos de 0 a 4) encontrar la mitad con (fi-ini)/2 nos daría el mismo resultado que con (fin+ini)/2. En cambio, si partimos el array cogiendo las posiciones de 2 a 4, (fin-ini)/2 nos devolverá la posición 1 y no la 3 como se esperaba.

  • Un cost serà sempre igual per a cada algorisme? Laura Medina Chaveli
    • No, pot ser diferent ja que segons quines siguen les instàncies significatives el cost pot ser millor o pitjor. Per exemple: un algorisme pot tindre un cost més alt si té un array ordenat i un més baix si no ho està.
  • Suposem que tenim un algorisme amb una n que tendeix a infinit i podem implementar tots aquest tipus de costos (log n , n, 2ⁿ, n², 1, n log n) per a realitzar l'algorisme. Quins serán de millor a pitjor els costos que podria utilitzar el nostre algorisme? Sergi Vendrell García
    • -O(1) ⊂ O(log n) ⊂ O(n) ⊂ O(n log n) ⊂ O(n²) ⊂ O(2ⁿ)
  • Observa la següent implementació de l'algoritme merge i troba en ella 4 errors: Jesús Yáñez Signes
private static <T extends Comparable<T>> void merge(T v[], int esqA, int esqB, int dretB){
int i = esqA, dretA = esqB - 1, j = esqB, k = 0, r;
T[] aux = (T[]) new Comparable[dretB-esqA];
while ( i <= dretA && j <= dretB ) {
  if ( v[i] < v[j] )
     aux[k] = v[i];
     i++;
  else
     aux[k] = v[j];
     j++;
  k++;
}
for(r = j; r <= dretA; r++) aux[k++] = v[r];
for(r = i; r <= dretB; r++) aux[k++] = v[r];

for(k=0, r=esqA; r<=dretB; r++, k++) v[r]=aux[k];
}
  • Resposta:
private static <T extends Comparable<T>>
void merge(T v[], int esqA, int esqB, int dretB){
int i = esqA, dretA = esqB - 1, j = esqB, k = 0, r;
T[] aux = (T[]) new Comparable[dretB-esqA+1];
while ( i <= dretA && j <= dretB ) {
  if ( v[i].compareTo(v[j]) < 0 )
     aux[k] = v[i];
     i++;
  else
     aux[k] = v[j];
     j++;
  k++;
}
for(r = i; r <= dretA; r++) aux[k++] = v[r];
for(r = j; r <= dretB; r++) aux[k++] = v[r];

for(k=0, r=esqA; r<=dretB; r++, k++) v[r]=aux[k];
}
  • Què és una instància significativa? Elena Garrigós Candela
    • Les instàncies significatives són aquells casos que fan que els algorismes es comporten d'una manera distinta per a la mateixa talla del problema.
  • En què consisteix l'algorisme de divideix i venceràs?Mireia Vico Burruezo
    • Està basat en la resolució recursiva d'un problema dividint en dues o més subproblemes. El procés continua fins que arriba a ser prou senzill com perquè es resolga directament.
  • Què hi hauria de fer per a que el quickSort donat ordenara l'array vec en ordre decreixent? Arnau Ruiz Fuster
private static <T extends Comparable<T>> int particio (T [] vec, int ini, int fi){
    int i= ini-1;
    int j= fi+1;

    Random gen = new Random();
    int pos_aleat = gen.nextInt(fi-ini+1);
    T piv = vec[ini+pos_aleat];

    while (i < j){        
        do{
        i++;
        } while(vec[i].compareTo(piv) < 0 );

        do{
        j--;
        }while(vec[j].compareTo(piv) > 0);

        if (i < j){
        T aux = vec[i];
        vec[i] = vec[j];
        vec[j] = aux;
        }
    }
    return j;
    }

    private static <T extends Comparable<T>> void quickSort (T [] vec, int ini, int fi){
    if (ini < fi){
        int tall=particio(vec,ini,fi);
        quickSort(vec,ini, tall);
        quickSort(vec,tall+1, fi);
    }

* Únicament caldria canviar els signes de comparació de les línies while(vec[i].compareTo(piv) < 0) i while(vec[j].compareTo(piv) > 0) pels seus contraris.

  • Quins son els passos principals a l'hora de calcular el cost d'un algoritme recursiu?Juan Carlos Asensi Cavero
    • Primerament hi ha que identificar quantes vegades es torna a cridar al mètode recursiu, identificar el cas base i per últim diferenciar entre cas pitjor i cas millor.
  • Respecte al ús de la recurrencia, en que es diferencia un problema amb una vaca esferica de radi conegut i un altre amb un conjunt de vaques a les quals hi ha que munyir? Antonio Vte. Molines Martin
    • La diferencia es que el problema es indivisible per una vaca esferica, i per tant no es pot resoldre per recurrencia, i divisible i escalable amb un conjunt de vaques( munyeixes una vaca i pases el problema a un altre que tindra una vaca menys) i , per tant, es pot resoldre amb recurrencia.
  • En qué consisteix el algorisme "bucket sort"? Antonio Manuel Sirvent Juan
  • Es un algorisme d'ordenament que distrubueix tots els elements a ordenar entre un número finit de casillers, cada casiller sols pot tindre elements que cumplixquen certes condicions, i aquestes condicions han de ser excluyents entre sí. Cada casiller s'ordena amb un algorisme de ordenació qualsevol, o també s'hi pot aplicar recursivament l'algorisme per obtindre casillers amb menys elements.
  • Quines són les ventajes que ofereix utilitzar funcions recursives per resoldre problemes recurrents i quins problemes pot produïr una funció recursiva malament implementada? Miguel Alejandro Muñoz Gil
    • La ventaja més clara d'utilitzar funcións recursives és la posibilitat de resoldre un problema que a primera vista sembla d'un cost elevat amb una solució d'ordre lineal o logarítmic (un cost reduit, generalment), utilitzant estrategies de divideix i venç.
    • El principal problema que pot generar una implementació indeguda es l'ús de memòria execssiu que es pot necessitar degut a la pila de recursió.
  • A l'hora de crear el nostre programa, la recursió ha de ser controlada? Ana Maria Adam Liberos
    • Si, massa recursió pot ser perillosa doncs hem d'aplicarla amb el menor cost possible als problemes prou complexos com pera mereixer-ho.
  • Quan s'ensenya la recursió per primera vegada es mostra com una forma molt eficient de resoldre problemes com el de les Torres de Hanoi però a eixe exemple s'usen 4 o 5 discs. Si el nombre de discs siguera molt major seguiria siguent tan eficient? Jaume Murgui Gómez
    • No, ja què la resolució del problema de les Torres de Hanoi té un cost Θ(2n)
  • Per què es important no caure en la trampa de dir que el cas millor de l'anàlisi del cost d'un algorisme es quan no hi ha elements a ordenar? Pablo de Polonia Llopis
    • Per que quan no hi ha elements a ordenar, dona igual quin algorisme uses, el cost es zero (ja que no hi ha res que ordenar). Només pots establir un cost quan hi ha un nombre suficientment gran de dades a ordenar.
  • Com implementaries l’algorisme de Selecció (cerca del k-èssim menor element) utilitzant l’estratègia Divideix i Venç? Javier Martínez Bernia
    • Dividir: Particionar el vector en dos amb pivotatge, de manera que els elements d’una part seran menors o iguals que el pivot, i els de l’altra majors.
    • Véncer: Cerquem en un dels dos subvectors (combinar) on estiga el k-èssim cridant recursivament a l’algorisme.
    • Combinar: Si el k-èssim es menor o igual que el pivot, la solució estarà en la partició on estan els elements menors o iguals que el pivot. Si no, estarà en l’altre subvector.
  • En que cosisteix el valor anomenat pivot? Pablo Pérez Mas
    • Per a separar els elements de tal manera que els menors queden a la esquerra del pivot i els major del pivot a la dreta.
  • Fes la traça per ordenar el següent array segons l'algorisme MergeSort: [27 | 14 | 3 | 8 | 17 | 5 | 21 |1]. Pilar Piqueres Matoses
  • 1-> [27 | 14 | 3 | 8] & [17 | 5 | 21 | 1]
  • 2-> [27 | 14] - [ 3 | 8] & [ 17 | 5] - [21 | 1]
  • 3-> [27] [14] [3] [8] & [17] [5] [21] [1]
  • 4-> [14 | 27] - [3 | 8] & [5 | 17] & [1 | 21]
  • 5-> [3 | 8 | 14 | 27] & [1 | 5 | 17 | 21]
  • 6-> [1 | 3 | 5 | 8 | 14 | 17 | 21 | 27]
  • Enumera almenys 5 algorismes clàssics basats en l’estratègia divideix i venceràs, ja siga per a multiplicació de grans enters, ultiplicació de matrius, càlcul de la potència d’un nombre, etc. Joan Ramon Coscollar
    • Cerca binària o dicotòmica, mergesort, quicksort, selecció (cerca del k-èssim menor element), algorisme de Strassen (multiplicació de matrius), algorisme Karatsuba(calcul de la potenciai de un nombre).
  • Quins tres aspectes es deuen tindre en compte a l'hora d'escollir un algoritme per a l'ordenació in situ de les dades d'un array? José Joaquin Rubio Iñigo
    • L'eficiència expressada en funció de la talla del problema: Inserció Directa quan el nombre de dades a ordenar és menut, o algoritmes com Merge sort o Quick Sort quan el nombre de dades és major.
    • El número i cost efectiu de les comparacions i moviments de dades que realitza: si costen més les comparacions serà preferible utilitzar Merge Sort, mentre que si costa més el moviment de dades s'utilitzarà Quick Sort.
    • L'estabilitat (o preservació de l'orde inicial de les dades idèntiques).
  • Sabent que. Sergio López Coll
    • T(n):
    • K -> n<= 1
    • T(n/2) + K -> n > 1
  • Calcula el cost que tindria l’algorisme.
    • Resposta:
    • T(i) = T(n/2i ) +i K
    • Cas base iessim(talla = 1) n/2i = 1; 2i = n ; log2 n = log2 2i ; i = log2 n
    • T(n/n) + K log2 n
    • K + K log2 n -> O (log n)
  • **¿Por qué no es recomendable hacer recursión, haciendo uso de quicksort, cuando la talla del vector es pequeña? *Tomás Ruiz Martín ## **
    • Debido a que haríamos un uso innecesario de la pila teniendo otras posibilidades mas eficientes para usar en casos como este, como inserción o selección directa.
  • Si teóricamente Quicksort tiene el mismo coste o peor (en el caso más costoso) que Mergesort, que es lo que hace que Quicksort sea más utilizado? ## Marc Gavilán Gil
  • Quicksort produce unas constantes mas eficientes que las de Mergesort lo que supone que el uso de Quicksort sea mas barato pese a tener el mismo orden de complejidad.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License