Resumen sobre Analisis de Algoritmo



Capítulo I
Fundamentos matemáticos
Monotonicidad
Una función f es monótona si es creciente o decreciente.

Conjuntos
Un conjunto es una colección de miembros o elementos distinguibles. Los miembros se toman típicamente de alguna población más grande conocida como tipo base.

Permutación
Una permutación de una secuencia es simplemente los elementos de la secuencia arreglados encualquier orden. Si la secuencia contiene n elementos, existe n! permutaciones.

Funciones Piso y Techo
Piso (floor) y techo (ceiling) de un número real x. Son respectivamente el mayor entero menor o igual que x, y el menor entero mayor o igual a x.

Operador Modulo
Esta función regresa el residuo de una división entera. Generalmente se escribe n mod m, y el resultado es el entero r, tal que n=qm+r para q un entero y/0 menor o igual que r y r < m.

Propiedades de los Logaritmos
log nm = log n + log m
log n/m = log n – log m
log nr = r log n
loga n = logb n/ logb a (para a y b enteros)






Números de Fibonacci
Los números de Fibonacci se definen por la siguiente recurrencia:
F0 = 0
F1 = 1
Fi = Fi-1 + Fi-2 para i ≥ 2

Entonces cada número deFibonacci es la suma de los números previos, produciendo la sucesión:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...

Recursión
Un algoritmo es recursivo si se llama a sí mismo para hacer parte del trabajo.

Un algoritmo recursivo tiene dos partes:
El caso base, que maneja una entrada simple que puede ser resuelta sin una llamada recursiva
La parterecursiva, que contiene una o más llamadas recursivas al algoritmo, donde los parámetros están en un sentido más cercano al caso base, que la llamada original.

Sumatorias y Recurrencias
Las sumatorias se usan mucho para el análisis de la complejidad de programas, en especial de ciclos, ya que realizan conteos de operaciones cada vez que se entra al ciclo.

Una relación de recurrencia defineuna función mediante una expresión que incluye una o más instancias (más pequeñas) de sí misma.

Técnicas de Demostración Matemática
Prueba por Contradicción
Para probar un teorema por contradicción, primero suponemos que el teorema es falso. Luego encontramos una contradicción lógica que surja de esta suposición. Si la lógica usada para encontrar la contradicción es correcta, entonces laúnica forma de resolver la contradicción es suponer que la suposición hecha fue incorrecta, esto es, concluir que el teorema debe ser verdad.

Prueba por Inducción Matemática
La inducción proporciona una forma útil de pensar en diseño de algoritmos, ya que lo estimula a pensar en resolver un problema, construyendo a partir de pequeños sub problemas.

Estimación
Consiste en hacer estimacionesrápidas para resolver un problema. Puede formalizarse en tres pasos:
Determine los parámetros principales que afectan el problema.
Derive una ecuación que relacione los parámetros al problema.
Seleccione valores para los parámetros, y aplique la ecuación para obtener una solución estimada.


Capítulo II
Algoritmos y problemas
¿Qué es un algoritmo?
Un algoritmo es una serie finita depasos para resolver un problema.

¿Qué es un problema?
Es una función o asociación de entradas con salidas. Un problema puede tener muchos algoritmos.

Aspectos para que un algoritmo exista:
1. El número de pasos debe ser finito. De esta manera el algoritmo debe terminar en un tiempo finito con la solución del problema.
2. El algoritmo debe ser capaz de determinar la solución del problema.Características de un algoritmo
1. Entrada: definir lo que necesita el algoritmo
2. Salida: definir lo que produce.
3. No ambiguo: explícito, siempre sabe qué comando ejecutar.
4. Finito: El algoritmo termina en un número finito de pasos.
5. Correcto: Hace lo que se supone que debe hacer. La solución es correcta
6. Efectividad: Cada instrucción se completa en tiempo finito....