Introducción

Question 1

¿Qué tipos de problemas hay?

Answer 1

1. Evaluación: determinar el valor de una solución óptima para I
2. Optimización: encontrar una solución óptima del problema P para I (de valor mínimo o máximo)
3. Decisión: dado un número k, responder si existe una solución factible de P para I tal que c(s) <= k (minimización) o c(s) >= k (maximización).
4. Localización: dado un número k, determinar una solución factible de P para I tal que c(s) <= k

Question 2

Definición de Algoritmo

Answer 2

Conjunto dfinito de reglas que da una secuencia de operaciones para resolver un tipo específico de problema.

Question 3

¿Qué 5 requerimientos cumple un algoritmo?

Answer 3

1. Finito
2. Preciso
3. Que tenga entrada (recibe valores iniciales)
4. Que tenga salida (emite resultado)
5. Eficaz (todo debe poder resolverse por alguien a lapiz y papel.

Question 4

¿Qué se debe analizar después de los problemas?

Answer 4

1. Optimización
2. Eficiencia en tiempo
3. Eficiencia en espacio
4. Características

Question 5

¿Qué característica tiene un buen algoritmo respecto del tiempo?

Answer 5

Un algoritmo es bueno si su comportamiento en tiempo es proporcional al tamaño de la entrada.

Question 6

Indique un ejemplo para la complejidad O(1)

Answer 6

Insertar un elemento a una pila

Question 7

Indique un ejemplo para la complejidad O(logn)

Answer 7

Búsqueda de un elemento en una lista ordenada

Question 8

Indique un ejemplo para la complejidad O(n)

Answer 8

Sumar n elementos de una lista

Question 9

Indique un ejemplo para la complejidad O(n logn)

Answer 9

Ordenar n elementos utilizando heapSort

Question 10

Indique un ejemplo para la complejidad O(n^2)

Answer 10

Gale-Shapley de n parejas

Question 11

Indique un ejemplo para la complejidad O(n^3)

Answer 11

Mutiplicación naive de matrices n x n

Question 12

Indique un ejemplo para la complejidad O(2^n)

Answer 12

Problema del viajante de nciudades por programación dinámica

Question 13

Indique un ejemplo para la complejidad O(n!)

Answer 13

Problema del viajante de n ciudades por fuerza bruta

Question 14

Cuando se tiene una complejidad O(n!), ¿qué se prefiere?

Answer 14

Se prefiere una complejidad de O(n logn)