Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

B2 Sistemas Operativos > B2 Tema 3 Algoritmos > Flashcards

B2 Tema 3 Algoritmos Flashcards

1
Q

Dí métodos de expresión de algoritmos.

A
  • Diagramas de flujo
  • Pseudocódigo
  • Sistemas Formales (Matemáticas)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Técnicas de Análisis y Diseño de algoritmia

A
  • Divide y vence Recursividad (Top-Down)→ Reduce el problema al caso más pequeño solucionable y lo aplica al caso general.
  • Voraces (Opción óptima en cada caso)→ Búsqueda heurística
  • Probabilísticos→ Se toman decisiones al azar. Las Vegas, MonteCarlo.
  • Backtracking→ Recursividad. No conoce una solución concreta, así que explora todo el árbol, para dar con la adecuada. Es el caso de prueba y error. Casos resueltos: Sudoku, Las ocho reinas.
  • Ramificación y poda→ Backtracking mejorado. Marca los sitios ya visitados.
  • Programación dinámica. (Bottom-up)→ Al revés de TOP-down. Va resolviendo casos pequeños y los va agrupando. Usa MEMOIZACIÓN.
  • Paralelos→ Puede ser ejecutado por partes en el mismo espacio de tiempo, por diferentes máquinas y luego unir las partes y obtener la solución.
  • Determinísticos→ Cuando la respuesta se puede conocer a partir de los datos de entrada.
  • No Determinísticos→ Cuando no son Deterministicos
  • Metaheurísticas→ Método heurístico.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

¿Qué es la COMPLEJIDAD ASINTÓTICA ESPACIAL de un algoritmo?

A

Es la cantidad de recursos de tiempo y almacenamiento que usa un algoritmo.

Se representa en terminos de Big O notation.

Ejemplo: O (1), O (log N), O (N), O (NlogN), O (N2)…. etc

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Dí ejemplos de algoritmos voraces:

A
  • Alg. de Kruskal.
  • Alg. de Prim.
  • Alg. de Dijkstra.
  • Alg. de triangulación voraz.
  • Alg. para la ubicación óptima.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

¿Qué es un algoritmo Voraz?

A

También conocido como GOLOSO, ÁVIDO, DEVORADOR O GREEDY.

Es una estrategia por la cual, se elige la mejor solución local, con la esperanza de poder aplicarla al problema global.
De forma clara, hace lo que le parece mejor en cada momento, resolviendo el caso menor que puede resolver, sin importar lo que queda del problema aún por solucionar.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

¿En qué consiste DIVIDE y VENCE?

A

Consiste en dividir el problema en otros más pequeños, hasta llegar al problema pequeño que podemos resolver y de ahí vamos aplicando la solución, pero ahora en orden ascendente.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Dí cuatro algoritmos Probabilísticos:

A
  • Numéricos - Devuelven un resultado aproximado, normalmente un intervalo.
  • Monte Carlo - Siempre devuelven una solución, aunque no sea correcta.
  • Las Vegas - Nunca devuelve una solución errónea, a costa de llegar a no funcionar.
  • Sherwood - Siempre devuelven una respuesta, la cual es forzosamente correcta.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

¿Qué es la Aguja de Buffon?

A

Algoritmo numérico

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

¿Qué tipos de clasificaciones hay para los algoritmos de ordenación?

A
  • Por ubicación:
    / Internos (se guardan en memoria)
    / Externos (se guardan en un archivo)
  • Por el tiempo:
    / Natural (tarda lo mínimo si la entrada está ordenada)
    / No natural (tarda lo mínimo si la entrada está inversamente ordenada)
  • Estable: (mantiene el orden de los elementos con claves iguales) Ejemplo de un array: 1, 3, 5, 3, 7. Al haber dos “3”, los reordenará, pero respetando cual es primero y cual es segundo.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Dí algoritmos de ordenación:

A
  • Exchange sorts - Intercambio→ Mueven datos de una lado para el otro: Burbuja, Quicksort, Cocktail, Burbuja Bidireccional.
  • Selection sorts - Selección→ Ordena desde el menor, que lo coloca a la izquierda y busca el siguiente menor que va después. Un ejemplo es Heapsort.
  • Insertion sorts - Inserción→ La forma natural de ordenar del ser humano: Shellsort. Usando un GAP entre los valores.
  • Merge sorts - Divide en sublistas como casos tribiales (Los que si puede resolver directamente). Resuelve el caso tribial y va mezclando sublistas.
  • Distribution sorts - No comparativos→ van colocando los datos en otra zona de la memoria siguiendo una estrategia. Averiguamos el mayor valor y creamos una lista a 0, desde 0 al mayor valor y vamos contando cuantas veces se repite cada campo:Bucketsort o Binsort/Radixsort
  • Stupid sort - “Gnome” → Como el burbuja, pero ampliando el intercambio.
  • Quicksort - Elemento PIVOTEhttps://youtu.be/ZHVk2blR45Q
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Dí nombres de algoritmos de Intercambio:

A
  • Burbuja→Dos elementos contiguos. Intercambia su posición, el de mayor valor pasa a la derecha y el menor a la izquierda. Sus casos estandar suelen ser O(N2), pero el caso mejor sería O(N).
    http: //lwh.free.fr/pages/algo/tri/tri_bulle_es.html
  • Quicksort→ PIVOTE. Caso estandar O (n log n). Su caso peor sería O(N2)
    http: //lwh.free.fr/pages/algo/tri/tri_rapide_es.html
  • Cocktail (burbuja bidireccional)→ Como el burbuja, pero al llegar al final, hace el recorrido a la inversa.
    http: //lwh.free.fr/pages/algo/tri/tri_shaker_es.html
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Dí nombres de algoritmos de selección:

A
  • Heapsort (montículos)→En un árbol, cada padre puede ser mayor que sus dos hijos o menor, según si es MaxHeap o MinHeap.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Dí algoritmos de Inserción:

A
  • Shell sort -> Comparamos valores, con un espacio entre ellos grande y los ordenamos. Luego reducimos el espacio y los volvemos a ordenar y así hasta que llegamos al espaciado mínimo y ya en ese caso, hacemos un ordenamiento por inserción, normal. https://youtu.be/ddeLSDsYVp8
  • ÁRBOL BINARIO
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Dí nombres de algoritmos de distribución / no comparativos:

A
  • Bucket sort: Se ordena por casilleros con diferentes rangos.
  • Radix sort: Hay dos versiones:
    / LSD -> Least Significant Digit.
    / MSD -> Most Significant digit.
    Crea Buckets o Colas, donde va ordenando los dígitos.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Tipos de algoritmos según su función.

A
  • Ordenamiento
  • Búsqueda
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

¿Como es el Ordenamiento por Inserción o Insertion-Short?

A

Es la forma más natural de ordenar para el ser humano.

Se asume que el primer elemento es la parte ordenada y se van colocando los demás en orden, comparando con la parte que se va ordenando.

http://lwh.free.fr/pages/algo/tri/tri_insertion_es.html

17
Q

¿Qué es Programación Dinámica?

A

Es un método para REDUCIR el tiempo de ejecución de un algoritmo mediante la utilización de SUBPROBLEMAS SUPERPUESTOS y SUBESTRUCTURAS ÓPTIMAS.

18
Q

¿Qué dos enfoques puede tomar la programación?

A
  • TOP-DOWN: El problema se divide. Es una combinación de memoización y recursión.
  • BOTTOM-UP: Se buscan y resuelven todos los subproblemas necesarios, para aplicar a problemas mayores.
19
Q

¿Qué es MEMOIZACIÓN?

A

Es una técnica de optimización de los tiempos de cálculo.
De forma sencilla de entender, es que guarda el resultado de una operación y si esa operación vuelve a salir, no la vuelve a calcular, porque ya sabe el resultado y lo pone.
Almacena los calculos de la llamada a una subrutina en una memoria interna o búfer y devuelve esos mismos valores cuando se llame de nuevo a la subrutina con los mismos parámetros de entrada.

20
Q

¿Cual es el nivel de un árbol?

A

No hay nada oficial, donde ponga si el nivel de la raíz es 1 o 0.
Es igual que la altura.
https://youtu.be/BzQGPA_v-vc?list=PLpPXw4zFa0uKKhaSz87IowJnOTzh9tiBk

21
Q

¿Qué es un algoritmo?

A

Es un conjunto de reglas que, aplicadas SISTEMÁTICAMENTE a unos datos de entrada apropiados, resuelven un problema en un NÚMERO FINITO de pasos elementales.

22
Q

Rendimiento de la Big O Notation

A

De mejor a peor:
* O(1) -> ORDEN CONSTANTE
* O(Log n) -> ORDEN LOGARÍTMICO
* O(n) -> ORDEN LINEAL
* O(nLogn) -> ORDEN LINEAL LOGARÍTMICO
* O(n2) -> ORDEN CUADRÁTICO
* O(nc) -> ORDEN POTENCIAL FIJO
* O(cn) -> ORDEN EXPONENCIAL

23
Q

Complejidad de algunos algoritmos.

A

Bucketsort o Binsort -> O (n)
Quicksort -> O (n log n)
Mergesort -> O (n log n)
Heapsort o montículo -> O (n log n)
Burbuja -> O (n2)
Inserción directa -> O (n2)
Selección -> O (n2)
Radixsort -> O (n x K)

24
Q

En el algoritmo Burbuja, que son Conejos y Tortugas??

A

Los Conejos son los datos de mayor valor colocados al principio de la lista.
Las Tortugas son los elementos de menor valor colocados al final de la lista.

25
Q

Los algoritmos de búsqueda pueden ser…

A
  • INFORMADOS
  • No INFORMADOS o CIEGOS: Más ineficientes.
26
Q

¿Qué es un algoritmo de ordenamiento?

A

Es un algoritmo que pone una lista de elementos en una secuencia dada por una relación de orden. La salida es una permutación de la entrada.

B2 Sistemas Operativos (7 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions