Martes 27/08/19

Al inicio de la clase el profesor se encargó de leer y explicar las especificaciones del proyecto y de evacuar dudas o preguntas que tuviéramos acerca de éste.

Tiempo de CPU; cuántas instrucciones ejecuto en x segundos.

Velocidad de reloj

Frecuencia a la que corre el CPU (Hz).

CPU Performance

✮  Ciclos por instrucción

✮  Instrucción por ciclo/segundo

✮  Instrucciones elementales vs instrucciones compuestas

Instrucciones elementales

• Siempre toman el mismo tiempo y éste no depende del tamaño del input.

• No interesa cuántos ciclos de reloj la instrucción necesita para ser ejecutada.

• T es una variable que denota el tiempo requerido para ejecutar la instrucción. Depende de la arquitectur y el hardware.

Instrucciones de tiempo constante

❀   Aritméticas (+,-,/,%,^)

❀   Operaciones de corrimiento (Bitwise) (<<,>>)

❀   Logical operators (==, !=, and, or, ~)

❀   Jumps(return values, method, calls)

❀   Asignación de una variable o acceso a estructura indexada

Time Complexity Example

boolean search(int arr[], int n){

boolean flag = false; //una declaración más una asignación = 2T

for(int i = 0; i<n, i++,){

                       //una declaración más asignación = 2T

                      //una comparación = 1T

                     //un incremento = 1T

if(arr[i] == num){ //una comparación = 1T

                //acceso a una estructura indexada = 1T

break; //un jump = 1T }

} }

En el if, se saca la complejidad de la condición y del else, la que sea mayor se la sumo al if.

Total time: 2T + N(StatementsT + T) + (N-1) T

Clase de reposición

Best, Worst and Average

Best scenario: Resource usage at least.

Worst scenario: Resource usage at most.

Average scenario: Average resource usage.

Common orders of growth

Problemas difíciles

2^N

N!

Notación asintótica

Cómo el tiempo de ejecución crece cuando crece el input.

Analizar la función

Captura el comportamimento de todos los algoritmos con input grandes.

Big O se utiliza para medir la complejidad de un programa.

Algoritmos de Búsqueda

Búsqueda Secuencial

Es el más simple.

Usado para buscar elemento en el medio del array.

Complejidad O(n).

Búsqueda Binaria

• Compara el input con el elemento en el medio del array.

• Si el input hace match, retorna el índice al elemento. De otra manera, parte el array y así lo trabaja.

• Complejidad O(logN)

• Búsqueda por interpolación

• Trata de calcular un mejor medio.

• Complejidad O(n).

Fórmula: middle = low + ((number - array[low])*(high - low) / (array[high] - array[low]));

Hashing

Permite mapear un conjunto grande de datos. Permite convertir una llave en un índice. Cada bucket (slot) en el hash table tiene asignado un set de datos. Puede mapear varias keys al mismo índice.

Aritmética Modular

• ELegir un número primo.

• El número define los buckets del hash.

Mid-Square Method

• Elevar a la 2 el key value.

• Toma los dígitos r del resultado.

• Da un valor entre 0 y (2^r) -1.

• Se toman los dígitos del centro.

Método Truncado

Ignora parte del key y usa el resto como índice.

No necesita números sucesivos.

Método Folding

• Divide la key en partes.

• Combina las partes.

• Por ejemplo, dividir un número de 8 dígitos en grupos de 3 y sumar los grupos.

¿Cuál es el problema del Hash?

Las colisiones. Dos o más keys con el mismo índice, decisión errónea de función hash.

Problemas: HashTable pequeña y muchos keys.

Tarea moral: ¿Cómo lidiar con colisiones?

Jueves 29/08/19

• Encuentra la ruta más corta.

• Usado para resolver laberintos.

• Basado en el algoritmo de Dikjstra.

• Podemos decir que su funcionalidad es explorar nodos adyacentes y seleccionando los más cercanos. Usualmente se implementa como un algoritmo basado en una matriz.

Forma más simple de aplicarlo: Que no hayan obstáculos.

Random Bouncing

• Este algoritmo tendrá un comportamiento tonto.

• Trata de ir directamente a la meta, si encuentra un obstáculo, se mueve en una posición random.

Object Tracing

• Estrategia para resolver laberintos

• Trata de bordear la pared hasta poder pasar hacia la meta.

Bread-First Search

• Basada en búsqueda de grafos.
• Se tiene una celda inicial y una final, desde la inicial se hacen saltos hacia otras celdas.
• Es ineficiente.
• Si hay un camino hacia la celda final, este algoritmo lo encontrará.

Distance-First Search

Si me muevo en diagonal, tiene un costo de dos. Esto significa un square tour.

Better heuristic pathfinding

Basado en la distancia más corta hacia la meta. El algoritmo tomará la mejor decisión, procesará menor cantidad de celdas, tomará menos tiempo para hacer el cálculo y brindará una ruta mucho más inteligente.

Este algoritmo tal vez no encuentre el camino más óptimo. Trata de tomar una mejor decisión en lugar de hacerlo como una onda expansiva. Reduce la cantidad de celdas que estoy revisando. Se calcula en menor tiempo.

A*

• Preciso

• Rápido

• Uno de los más comunes en videojuegos

• Demasiado configurable según el contexto

Funcionamiento

Se agrega el punto inicial a un openlist. Chequeo las celdas adyacentes al punto que acabo de agregar al openlist y los agrego, guardo el punto inicial como el padre. Remuevo la celda que acabo de agregar y la agrego al closedlist. Decisión: Tomar uno de los que quedaron en el open list y así iterativamente.

Yo calculo un costo asociado a cada celda:

F = G+H

G: Movimiento desde el punto inicial a cualquier otro en el grid. H: Costo estimado de moverse desde cualquier celda de la matriz hacia el punto que quiero llegar (heurístico).

Tenemos que elegir la celda que tenga el menor F del openlist.

¿Cómo calcular H?

Distancia de Manhattan

dx = abs(targetx-currentx) dy = abd(targety - currenty)

El valor de H se calcula una única vez para todas las celdas.

Cálculo de G

Costo de movimiento horizontal: 10 Costo de movimiento diagonal: 14

Actividad

Realizamos en parejas una actividad en la que hicimos un algoritmo A* sobre una matriz 10x10 en clase, debíamos terminarlo y también traerlo sin resolver para la siguiente clase.