Multiplicar de la escuela es O(n^2) mierntras que el divide and conquer tiene una duracion de O(n)

cuando solo se hace mas pqueña una instancia se llama simplificacion, y en este caso se podria cambiar de recurrencia a ciclos iterativos

3 condiciones de los divide and conquer:

1. La decisión de cuando usar un subalgoritmo básico en lugar de hacer una llamada recursiva, debe ser tomada con juicio
2. Debe ser posible dividir la instancia en subistancias y recombinar subsoluciones de forma eficiente.
3. Las subintancias deben ser de tamaños similares. 

(la mayoria de las subinstancias son de tamaño n/b)

TEOREMA MAESTRO EN EL ESCRITORIO

Tomar la decisión de hacer recursion o subalgoritmo, se basa en un threshold n0. Cualquier instancia menor a este n0 debe ser resuelta por el subalgoritmo.

Encontrar el threshold óptimo es un proceso empírico, que toma mucho tiempo. Es muy difícil encontrarlo de forma teórica.

->Lo correcto es econtrar de manera teórica las ecuaciones de recurrencia, y de manera empirica encontrar el valor de las constantes de las ecuaciones

Binary Search:

Va mas por el lado de simplificacion. Es l=1, b=2,p k=0, por lo que el algoritmo es log m

 

Sorting(MergeSort):

Divide arrays a la mitad, los ordena y despues les hace merge de nuevo ya con los subarrays ordenados. Utiliza el insertion sort como subalgoritmo para instancias pequeñas

l=2, b=2, k=1. Por lo que es 8(n log n) por lo que es similar al heapsort., pero un pelin mas rapido aunque requiere mas almacenamiento por el uso de los subarrays

 

Quicksort:

*Hoare: inventor del quick-sort

Quick sort no va bien si las subinstancias no están balanceadas y si el array ya está ordenado. -------> cuadrático

R/ Quicksort en su caso promedio es O(n log n) para sortear n elementos. Y su constante escondida es menor a heap y merge

 

Encontrar la media:

Encontrar el elemento media de un arreglo, hayan n menores y n mayores a el. La técinca basica es ordenarlo con quick/heap y encontrar el n/2, lo que toma tiempo 8(n log n)

pseudomedia: Si el array tiene 5 o menos, llama a adhocmed del array, si no, entonces saca floor(n/5)  y llama  a adhocmed de subarrays. Y termina haciendo un selection de z/2 en Z(contiene los sub arrays).

Por lo que pseudomedia: lineal en su peor caso y hace lineal el selection.

 

Multiplicación matricial:

Sean A y B, dos matrices de n x n, y C su producto:

Normalmente cada entrada de C toma 8(n) en calcularse, calcular todo C es 8(n^3)

A finales de 1960, Strassen  mejoró el algoritmo, y es un punto muy importante en la historia del divide and conquer(aunque el de mult de large interegers hubiera sido una decada antes)

En lugar de hacer las multiplicaciones, el descubrió que era posible hacerlo con una multiplicacion menos(en una de 2x2 por 2x2, en vez de 8 son 7)

l=7 b=2 k=2, por lo que 8(n^log7)

Hopcroft y Kerr probaron que no es posible mejorar ese tiempo de multiplicacion. (1971). Despues Pan multiplicó dos 70x70 y lo hizo en log bas 70 de 143640. que es mejor, lo que inició la "guerra decimal"
Muchos algoritmos fueron saliendo que era mejores, hasta que en 1979 se descubrió que se podía hacer en O(n^2.521813) y despues en O(n^2.521801)
En 1986 Coppermisth y Winograd-> O(n^2.376)

 

Exponenciación:

Exponenciar a^n con n>0

Para un n pequeño se utiliza el algoritmo normal de multiplicaciones en ciclo. Este tiene un 8(n). Pero este genera integer overflow en muchas pcs. 

El algoritmo normal es O(m^2*n^2) y el algoritmo divide and conquer es 8(m^lg3n^2)

Expo con N, es eventualmente no decreciente. 

Exposeq: 8(m^lg3 n^2)

expoDC 8(m^lg3n^lg3)

 

Intro a la criptografia:

 

aritmetica modular: contar las multiplicaciones al mismo costo(calculo de modulos)

criptografia moderna, un mensaje de transforma a ciphertexto que se forma con enciphering algorithm, que se forma con el mensaje y con una key.

llave publica por Diffie, Hellman y Merkle en mitad de los 70s

Solcuion de Rivest,Shamir y Adleman: RSA cryptografy system

 

& es (p-1)(q-1)

n un numero que elige bob entre 1 y z-1 (z es p*q)

Existe un numero s entre 1 y z-1, que ns mod &=1

 

Se puede hacer publico el z y el n, pero el s es secreto.

 

Bob recibe un mensaje que paso por expo mod. y lo desencripta con expomod(c,s,z)

 

Solo se podria desencriptar el mensaje con una computadora quantica

 

 

Análisis:

 

se tiene l, b, n y k

 

l: subinstancias, cuantas varas tengo que combinar al final

b: entre cuanto se divide

n: tamaño instancia original

k: el exponente del +g(n)

 

l=10

b=2

k=3