Lectura 1

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.