Fundamentos de algoritmia, pagina de la 1 a la 56.
Algoritmo nombrado por un persa en el siglo 9 - al-Khowarizmi. Algoritmo más famoso de Euclids, para el máximo común divisor de dos números, época de los griegos.
Algoritmo: conjunto de reglas para llevar a cabo un calculo, a mano o en computadora. No tiene decisiones subjetivas, uso de creatividad o intuición.
Algoritmos heurísticos: no nos dan una solución exacta, pero si una cercana con la que nos podemos conformar. Algoritmos aproximados, podemos decir cuanto error vamos a aceptar, heurísticos solo podemos calcular cuan grande es el error.
Multi a la russe: el de la izquierda se divide entre 2, el de la derecha se multiplica por 2. Se multiplican esos, y solo se suman los que en la izquierda son impares.
Cálculo proposicional:
Booleano= True y False. Conjunción, disjunción, negación, implica, doble implica.
Teoría de conjuntos:
suma u, intersección n, resta A\B.
Enteros, reales e intervalos:
Z enteros, N naturales, R reales.
(a,b) es intervalo abierto, [a,b] es cerrado.
Funciones y relaciones:
Todo conjunto p. de un producto cartesiano XxY es una relacion.
Una relación es función si para cada x hay un y, que f(x,y).
x dominio y y es imagen.
-Inyectiva si es uno a uno.
-Suyectiva si para cada x hay un y.
Biyectiva si pasan ambos.
Cuantificadores:
Para todo y existe.
Principio de dualidad de los cuantificadores:
Sumas y productos:
Su respectivo símbolo con inicial y límite.
Misceláneos:
Función piso, función techo, factorial, módulo.
Pruebas por contradicción:
-Prueba por contradicción/prueba indirecta. Demostrar la verdad de un argumento, probando que su negación lleva a una contradicción.
Prueba por inducción:
Inducción: inferir algo general de instancias particulares.
-Principio de la inducción: p(a) holds entonces P(n) debe holdear siempre que p(n-1) para cada n>a.*imagen*
-Inducción matemática generalizada: es mas poderosa, *imagen*(PROPIEDADES). Base extendida, probar en más de un punto. A veces se necesita independientemente la validez de varios puntos antes del paso de inducción.
Inducción constructiva: mostramos si es verdad, y encontramos las especificaciones faltantes.
Teoría de límites:
31 a 33
Teoría de probabilidad:
42 a 47
Selection sort: el peor caso es cuando esta acomodado de forma decreciente.
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
