Al-Khowarizmi
Persa, Matemático, astrónomo, geógrafo, tratado del álgebra(ecuaciones lineales), texto sobre aritmética. La casa de la sabiduría (universidad en el califato). Uso del método científico.
Siglo 9
Algoritmo más famoso de Euclids, para el maximo comun divisor de dos numeros.
Algoritmos:
Conjunto de pasos/reglas para resolver un calculo y con eso solucionar un problema. Manual o automático. Los pasos deben ser claros, precisos y objetivos.
Heuristicos: basados en optimismo. No se puede controlar el error. Pero se puede calcular despues de dar un resultado.
Soporte teorico minimo: tomar las entradas, usando reglas, y restringimos la complejidad del problema. En caso de no encontrar una solucion, nos acercamos a una, con aproximacion, estableciendo el rango de error.
Algoritmia: ciencia que permite evaluar el efecto de los factores externos sobre algoritmos(disco, memeoria, red, cpu, tiempo) y el comportamiento
Estudio de los algoritmos, y se puede decidir correctamente cual algoritmo utilizar en un caso dado.
Se elije dependiendo de:
-Eficiencia, más rapido, menos recursos, simple y elegante. Debe resolver el problema.
Asistente Tomas Segura.
Tomás Segura
Cel: 89347661
correo: tomas.seguram@gmail.com
solucion NO general=solucion alambrada, particular
Problemas e instancias:
problema= multiplicar dos numeros cualesquiera. Conjunto infinito (o MUY grande) de instancias, podemos dar los numeros que sea, que nos da solución.
instancia= multiplicar 34x98, donde los numeros ya estan fijados, ya elejidos.
no es instancia= -12x83.7, porque el divide and conquer no usa negativos, ni float.
Podemos decir que un algoritmo no es general, si se encuentra un CONTRAEJEMPLO.
Eficiencia: qué tan rápido se ejecuta un algoritmo para una instancia tamaño n
Empíricamente: a posteriori. Elegir un algoritmo que se programa todo y se hace benchmark, se aplican las mismas instancias y se hace una comparación y se dice cual es mejor.
Teóricamente: a priori. Se determina matemáticamente la cantidad de recursos(tiempo y espacio) necesarios para cada algoritmo, en función de el tamaño de la instancia. En este enfoque, no se depende del hardware, ni del lenguaje.
Principio de invariancia:
Se habla del mismo algoritmo, pero diferentes implementaciones, pero puede variar el lenguaje, el hardware(RAM,CPU), la red. Pero el algoritmo tiene el mismo t(n) para a1 y a2.
d y c: Uno acota al otro,
d=1/c
Entre dos algoritmos, no se difere el tiempo de implementacion, en mas de una constante multiplicativa.
Orden de c*t(n)= n, n^2, n^3, n^k, c^n
No ocupo unidad de medida para la eficiencia teórica de un programa.
Caso promedio y peor caso:
Tiempo depende del tamaño de la instancia en particular.
