27/08/2019

Actividad para recordar que vimos la clase anterior. Pasaron 2 compañeros adelante e iban preguntando que temas se enseñaron.

¿Que es tiempo?

Instrucciones por unidad de tiempo. Medido en hertz o en gigahertz.

CPU Perifericamente

• Cuantas instrucciones pueden ejecutar por ciclo de reloj.
• Instrucciones por segundo.
• Instrucciones complejas vs. Instrucciones elementales.
• Instrucciones por ciclo de reloj.

Instrucciones elementales

Siempre toman la misma cantidad de tiempo.

Contar las instrucciones elementales por ciertos ciclos.

T es una variable que depende de la arquitectura y del hardware.

La operación aritmética siempre vale un valor de T.

El T para cada arquitectura sera el mismo.

Operaciones que valen un 1T

Operadores aritméticos

Operadores de corrimiento

Operadores lógicos

Jumps (retornos de valores, llamadas de métodos)

Asignación de una variable

Ejemplo:

boolean search

//varios statements

int a = 2;		2T

int b = a+2;		3T

arr[2] = b;		2T

Total: 7T

if(cond){ //solo complejidad del i

block of state1 // solo la complejidad 

}else{

block state 2

}

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

Total time:

2T+N(Statements + T) + (N+1)T

Tarea

i+1 // 1T

i = i+1 // 2T

por ejemplo, si hace n = n + 1 en dicho lenguaje, muchos de ellos harán como mínimo una copia de memoria adicional y eso disminuirá el rendimiento general.

Usar n ++ en lugar de n = n + 1 siempre es beneficioso:

mayor o igual velocidad de ejecución

código binario de menor o igual tamaño

código fuente más compacto

movilidad de rendimiento (incluso si lo recompila en otro lugar con el compilador sin optimizaciones, todavía va a ganar)

Notación Asintotica

*Como crece el logaritmo mientras aumento N

*Analiza la función del limite

*Captura el algoritmo con grandes entradas

Big O

Para sacar la mayor complejidad. Ejemplo: O(n³)

Hash:

Permite mapear un gran conjuntos de datos en uno pequeño.

Cada slot permite asignar un conjunto de datos.

Cada slot es llamado un bucket.

La función básica es cuando se usa una función identidad.

Hash(restas recursivas)

Usar la formula de aritmética modular.

*Use un número primo.

*El número prime define la cantidad de slots.

Mid square method

*Da una cantidad desde el 0 hasta (2^r)-1

Método de trucar:

Ignore parte de la llave y use el resto del indice del array.

*No se necesita usar métodos sucesivos.

Folding method:

*Divide la llave en partes.

Combina las partes, usando el operador /*+-

Por ejemplo, divide el número de 8 dígitos en grupos de 3, se suma y se obtiene el indice.

¿Cúal el es problema principal de los indices?

Las colisiones

Hay dos llaves en un mismo lugar. Dos llaves en un mismo indice.

*Las colisiones no se pueden evitar

*Hay que gestionarlas.

Tarea moral: ¿Como lidiar con las colisiones de indices?

Propagar los registros: Buscar funciones que distribuyan muy aleatoriamente los registros podemos evitar "agrupaciones" de llaves que produzcan las mismas direcciones

Usar memoria extra: se basa en proponer un espacio de direcciones posibles mucho más grande que el número de registros a usar, de modo que si vamos a insertar 100 registros un espacio de 500 direcciones nos una mejor opción de esparcir mejor.

Colocar más de un registro en una dirección:
este concepto se basa en "buckets" o cubetas de datos en cada dirección, ahí se colocan algunos (casi todos) los registros que colisionan de manera que al hacer una búsqueda debemos recuperar la cubeta entera y ahi buscar por el registro deseado.

---

29/08/19

---

Algoritmo Pathfinding

*Encuentra la ruta más corta entre dos puntos.

*Usado para resolver laberintos

*Es basando en dijkdtra algoritmo(calcular la ruta más corta de un nodo a cualquiera de los demás).

*Implementado para ejecutarse sobre una matriz Pathfinding

La forma más simple de aplicar Pathfinding es que no hayan obstaculos.

Random Bouncing

*La más simple con obstaculos. *No es recomendable porque utiliza soluciones random.

Object Traicing

*Ir al objetivo y tratar de bordear la pared.

Breath-Fisrt Search

El problema tiene una celda inicial y una celda objetivo. *Es ineficiente *Si hay un camino a la meta la va a encontrar. *Permite movimiento horizontal y vertical.

Distance-First Search

Dice que hay una diferencia entre horizontal, vertical y la diagonal.

BFS es distinto a DFS

Pathfinding Euristico

//Euristico = no necesariamente con la misma entrada obtiene la misma salida.

*Basado en la distancia más corta para el objetivo.

*El algoritmo va a hacer una mejor decisión, va a procesar pocas celdas, va a tomar menos tiempo para realizar el calculo y usted va a tener una ruta más inteligente.

*Este algoritmo puede no encontrar la ruta más optima (Es voraz, podría no encontrarla).

Pathfinding A*

*Preciso *Rapido *Configurable de acuerdo al tipo y juego a aplicar. *Es de los más usados en programación. *Las celdas tienen un estado de si ya pase o no por ahí. ¿Como funciona?

1. Agrega el punto donde inicia a una lista de puntos abiertos.
2. Ese punto se agrega como el padre y pasa a la open lista, también se agregan los adyacentes.
3. Quito el padre de la openList y lo paso a una closed List. Luego escojo otro de la open List.

Costo asociado a una celda

F es el costo total G es el costo de moverme desde el punto inicial a cualquier otro punto de la matriz. H el resto de la ruta, el costo de una posicion cualquiera al objetivo. Costo de cualquier celda de la matriz al punto donde quiero llegar.

Elegir la celda que tenga el menor valor de F. Los adyacentes pasados siguen estando en una closed list. Puede que no sea parte de la ruta. Solo dice que ya se analizó.

Se le asigna un valor más grande a la diagonal para que no se mueva en diagonal, sino solo en horizontal y vertical.

Como calcular H

La distancia de Euclides dx = distancia Objetivo X - distancia Actual X dy = distancia Objetivo Y - distancia Actual Y h = sqrt((dxdx=+(dydy)

Manhatan

dx = abs(targetX - currentX) dy = abs(targetY - currentY) h = dx + dy

Valor Vertical y horizontal = 10 Moviemiento diagonal = 14

G Valor Moviemiento H y V 10 y 14