Análisis

Lectura semana 1, fundamentos de algoritmia

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.                 

Martes 8 de febrero del 2022

  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    

Jueves 10 de febrero del 2021

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.     

Martes 15 de febrero del 2022

  Caso promedio y peor caso: Insert sort: ordenado no dura mucho, si está ordenado invertido, tiene que recorrerlo todo y ordernarlo todo. Dura muchisimo mas. Select sort: no es sensible al orden, por lo que durarian lo mismo en ambos casos.   Operacion elemental: tiempo acotado por una constante. Depende solo de la implementacion, no de n. Tiene un costo unitario.   ¿Por qúe eficiencia? Los recursos son mas, pero siguen siendo caros y tienen que ser optimizados todo el tiempo.   Notación asintótica:  

Jueves 17 de Febrero del 2022

  Notación asintótica.   Big O: t(n) está en el orden de f(n): t(n) está acotada por arriba por f(n) por un real positivo, llamese c. -> t(n) <= c *f(n) Se ponen los exponentes del polimonio igual al mayor exp, y se suman los coeficientes, eso nos da el C. Me quedo con el exponente mas grande, y ese es el big O del algoritmo. -Regla del máximo: El big O de la suma de dos funciones, es el big o, del maximo entre esas dos funciones.  Es decir, p(n) = f(n)+g(n), su big o es el maximo entre ellos f(n)+g(n) = max( f(n), g(n) )   -Regla del límite:   Omega Acotado por abajo por una constante d.  

Martes 22 de febrero

"Orden exacto de", utilizando la notacion zeta (diciendo cual es el o y el omega).    Notacion asintotica CONDICIONAL: ver las formulas de notacion, para O,omega y zeta   eventualmente no decreciente: existe un umbral entero n0, donde para un n, el siguiente es igual o mayor, nunca menor b-smooth: es eventualmente no decreciente, y para un b mayor o igual a 2, f(b*n)<=c f(n). Si mi b es 8, es 8-smooth, y así según el número. smooth: si es b-smooth para todo entero mayor o igual a 2. Pero no son smooth si crecen muy rapido (n^log n, 2^n, n!)   Analsis de estructuras de control: hay que tener jucio, intuicio y experiencia. Tener herramientas teoricas: -Secuencias: se suman los tiempos de cada bloque -Ciclos: tarda la cantidad de vueltas, por el coste de lo de adentro -Llamadas recursivas: hacer una ecuacion de recurrencia,  -Ciclos while/repeat: 

Jueves

  Técnica del barómetro: instruccion barometro: es una instruccion que se ejecuta igual o mas veces que las demás. Se analiza esta y se saca el orden de la función.  

Martes 1 de marzo del 2022

Torres de Hanoi/Torres de Brahma: Monjes del templo Kashi Vishwanath, que dicta la llegada del fin del mundo. Tomará 585 billones de años en llegar ese fin. Big bang, fue hace 13.8 biillones, so falta mucho xd   Funciones potencial: entre mas grande phi, está mas sucio el espacio de trabajo, mas pequeño es mas limpio. phi-0, es limpio. phi-i es el estado despues de la i-esima ejecucion o modificación.  phi- i - phi-(i-1)= delta,   

Jueves 3 de marzo del 2022

  Para la función count, en funcion potencial lo mejor es contrar el numero de bits en 1. El costo amortizado de todos los valores . Truco del conteo más facil que potencial -suponemos un valor para t (TAO)   Analisis de recurrencias: -Conjetura inteligente: intuicion del analista y experiencia.  1. se calculan los primeros valores de la recurrencia 2. Buscar una regularidad o patrón. Podemos expandir la función: despues del cambio de variable, y de ahí intentamos encontrar un patron, como una funcion  3. Hacemos la formula 4. Prueba matemática(no lo hacemos en el curso)    

Martes 8 de marzo del 2022

  Recurrencia homogenea(lineal homogenea con coeficientes constantes): tn son incognitas y los ak son constantes. (De ambos hay k.) 3 apellidos: 1. Da cero 2. Es lineal 3. Coeficientes constantes     REPASAR LAS ETAPAS: a. ecuacion caracteristica b. ecuacion caracteristica polinomial c. Obtener raíces d. solucion  general (raices por constante) e. sacar las soluciones con lo que ya tenemos(sistema ecuaciones) f. solucion a la recurrencia original       k soluciones.      

Jueves 10 de marzo del 2022

  Recurrencias homogeneas con raices multiples:   Recurrencias no homogeneas: a. se homogeniza b. se hace una ecuacion caracteristica c. ecuacion caracteristica homogenea (de aplicar propiedades)

Martes 15 de marzo del 2022

Teorema maestro:  dos soluciones: l y b, elevados a la k   3 opciones -l > b^k: (x-b^k)^2 -l < b^k:  -l = b^k: dos raices iguales, se hace solucion general para raices identicas.      Greedy Algs: Enfoque corto plazo: miopes, cortos de vista, optimistas Usado para un desdén por consecuencias futuras(no las tomamos en cuenta) Para problemas de optimización(no todos se pueden optimizar con voraces) No reconsidera decisiones tomadas: cuando ya hicimos pasos, no pensamos si lo que hicimos estuvo bien o no.  No registra informacion de control, no guardo que hice o por donde pasé.   -Tenemos con conjunto de candidatos iniciales -Escogidos y rechazados -Función de evaluación o solucion: evalua que hallamos llegado a la solución: si el conjunto de candidatos escogidos nos da la solucion esperada -Función de factibilidad: si agregar un candidato X a una solución (ya prometedora), si promete de escoge, sino se rechaza  -Función de selección: del conjunto que no se ha considerado aun, de esos cual es el siguiente mas prometedor -Función objetivo:    +Arboles de recorrimiento minimo: Arbol conexo y no dirigido,       

QUIZ #4: Un grafo conexo de n nodos, tiene como minimo n-1 arcos. Si tiene mas, es porque tiene cilclos Un conjunto factible es prometedor si puede producir una solución optima Kruskal: log n Prim: a log n Djisktra: n^2 Knapsack: log n minimizar tiempo: n log n schedule: n log n   GREEDY ALGORITHMS: -3 conjuntos: candidatos, aceptados, rechazados. -4 funciones: una verifica que un conjunto sea solucion, otra que un conjunto sea factible, otra de los candidatos cual es el mas prometedor, y otra que nos indica la solucion(esta puede no ser explicita). -Se selecciona el mejor, sin preocuparse por el futuro, nunca se arrepiente, si alguien está está, si se rechazó ni modo  

  DIVIDE AND CONQUER: Se divide en sub soluciones, que se combinan para una solucion final al problema original. 

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...

  DIVIDE AND CONQUER: ***tener a mano el teorema maestro*** adhoc: a la medida.    DIVIDE AND CONQUER: -Condicion de parada -Descomposicion/Recombinación -Tamaño  subinstancias        

Mediana: encontrar al medio-esimo elemento     Programación dinámica: Soluciona que las sunistancias se traslapen, porque va de bottom a up    

Dynamic programming:     -Serie mundial: P(n,n)= cuando inicia la serie P(0,0)= no tiene sentido porque ambos no pueden ser campeones   -Problema del cambio:      

Resúmen cap 8 libro

  Objetivo de dynamic programming: evitar calcular lo mismo varias veces, manteniendo una tabla de los resultados a medida que se calculan, para luego usarlos en la solución de las subinstancias Divide and conquer es una familia con un sistema top-down, porque vamos de la instancia completa, hasta llegar a subinstancias. Por otro lado, Dynamic Programming, es bottom-up, se inicia con las subinstancias mas pequeñas y simples, y combinando sus soluciones obtenemos la respuestas de otras mas grandes, hasta dar con la solución final. 1. Describir estructura: 2. Definir el valor 3. Calcular el valor 4. Calcular solución (opcional) memoización: para top-down, recursivos:  tabulacion para bottom-up, iterativos:  Se utiliza el triángulo de Pascal, como tabla de valores intermedios. No es necesaria toda la tabla: es suficiente con un vector de tamaño k, que es una línea, luego se  actualiza el vector de izquierda a derecha.   Coeficiente binomial: ->El problema de coeficiente binomial (n/k) es: tiempo a en 8(n k) y espacio 8(k).  The World Series: A= p y B =q=1-p. P(i,j) probabilidad de que el equipo A gane, cuando le faltan i ganes, y a B le faltan j ganes. P(i,j) = pP(i-1,j)+qP(i,j-1) ->El problema de la serie mundial es t(k) donde k=i+j, O(2^k). O(4^n) si j=i=n. En términos de coeficiente binomial: C(i+j,j) = C(i+j-1, j) + C(i+j-1, j-1)   -> Con triangulo de Pascal se puede hacer 8(n^2)   Cambio:   Se hace una tabla donde las filas son las denominaciones disponibles, y las columnas son de 0 a N, valor a pagar. c[i, j] menor numero de monedas para pagar j, con monedas de 1 a i. Se calcula c[i,0] y después de eso, se puede calcular de derecha a izquierda columna por columna, o de arriba a abajo fila por fila.  c[i, j] = min(c[i-1, j],1+c[i, j-di]) -> 8(n+c[n,N])   Principio de la optimalidad: en una secuencia optima de decisiones o selecciones, cada subsequencia también debe ser óptima.  O sea, si necesito un resultado optimo, todos los pequeños resultados en el camino(la tabla) deben ser óptimos. Cuando el principio no aplica, entonces probablemente no se puede usar prog dinámica. Un problema para el principio es los recursos, puedo agotar los recursos en una subinstancia del problema.  La solución óptima a cualquier instancia no trivial de un problema, es la combinación de optimas soluciones de algunas de sus subinstancias.   Problema de la mochila: vi y wi son restricciones de la instancia. Y xi (es 1 o 0 si está o no está en la mochila) son restricciones de la solución. Se hace una tabla, con filas para cada objeto y columnas para su peso. Por eso V[i,j] es la cantidad de objetos que podemos llevar en la mochila de peso j. Con objetos de 1 a i. v[i,j] = max(V[i-1, j],V[i-1,j-wi]+vi) -> construir la tabla 8(nW) y la composision se determina en tiempo o(n+W)   Camino más corto: Dk[i,j] = min(Dk[i,j],Dk-1[i,k]+Dk-1[k,j]) No entendí   Multiplicación matricial en cadena: La complejidad de una multiplicación de matrices: es pqr. La idea es encontrar la mejor forma de poner paréntesis para que sean menos multiplicaciones. Supongamos hago un corte de m1 a mi= M= (m1,m2,m3,...mi)(mi+1,mi+2,...mn) ambas deben ser optimas(principio de la optimabilidad).   Recurrencia T(n)= Suma de i=1 hasta n-1 de T(i)T(n-i). Sus valores son llamados números catalanes. -> omega(4^n/n) -> alg con diagonal, n^3   Ejemplos con recursión: -Matrices:    Se puede hacer calculando M con una función fm() que sea recursiva. Para saber cuantas multiplicaciones se ocupan se llama a fm(1,n)    -> Toma Omega(2^n), O(3^n)   Funciones de memoria: Combinar las ventajas de top down y de bottom up. Se hace con una función de memora.  Se tiene la tabla de valores, si ya esa tabla se calculó se retorna el valor correspondiente. Si no, se llama recursivamente a la función. -> tiempo: 8(nk) y espacio omega(nk)      ...

Cap 6 del lubro: Greedy Algorithms

Características generales: -Set de candidatos: a tomar en cuenta. -Set de candidatos considerados: fueron elegidos para la solución. -Set de candidatos rechazados: fueron rechazados y ya no serán tomados en cuenta. +Función solución: verifica que los candidatos den una solución al problema.  +Función factibilidad: verifica si los candidatos son factibles para obtener una solución. +Función de selección: selecciona de los candidatos aún no seleccionados, cuál es el más prometedor. +Función objetiva: nos da la solución que hemos encontrado. Esta puede no estar explícitamente en el código.   MSTs: Grafo conexo, pesado y no dirigido. Debe tener n-1 arcos, n es la cantidad de nodos totales. Esto para que no hayan ciclos.   Kruskal: Algoritmo para MST, que comienza vacío, y va agregando T resultado. Agrega de forma creciente según el peso, y no le importa los nodos, solo no formar ciclos. -> 8(a log n). n nodos y a arcos.   Prim: Se inicia de una raíz arbitraria, cada paso agrega un nuevo nodo, hasta que todos los nodos se hayan incluído. -> 8(n^2) Es mejor usar Prim que Kruskal cuando a>n^2/log n, a es cantidad de arcos   Camino más corto(Dijkstra): Se selecciona un nodo, y se quiere saber el camino más corto para llegar a todos los otros nodos. C es nodos candidatos, D es solución (largos). -> Normal: 8(n^2)   Problema de la mochila: Se busca llenar una mochila con un peso máximo, con objetos con un peso y un valor, se busca el mayo valor respetando ese peso. Se pueden dividir objetos. ->O(n log n)   Planificación: Minimizar tiempo en el sistema: Un solo servicio, como un mae en un banco, procesador, etc. Tiene n clientes que atender, se sabe cuanto va a durar cada cliente. Se quiere minimizar el tiempo promedio de espera. El caso óptimo es atender primero a los de menor tiempo primero.  Sólo es necesario ordenar esos tiempos. Los nuevos que lleguen se acomodan al final y se vuelve a poner en orden creciente. -> solo es ordenar, O(n log n)   Planificación con tiempos de entrega: Tenemos trabajos con valor y tiempo. Se elije una secuencia que se pueda hacer en el tiempo indicado y nos de mayor ganancia.                                    

  Grafos y backtracking:   Ancestralidad: v ancestro de w si: -(prenum de v <= prenum de w) y (postnum de v >= de postnum de w)   Busqueda en profundidad:                                                      

GRAFOS: -Juego de Nim(Marieband game): Misere: juego similar pero el que toma el último es el que pierde. Juego con fósforos. Se quitan de 1 a n fósforos. El siguiente jugador puede quitar de 1 al doble de la cantidad que el otro quitó. Gana el que quita el último. Se utiliza un grafo dirigido. En ajedrez se usa como reporte de movimiento, la acción de un jugador y la respuesta del otro. Medio movimiento: la jugada de sólo un jugador.  Para el juego los nodos son pares (i,j) donde i es la cantidad de fósforos que quedan en la mesa, y j es los que se pueden tomar en el siguiente turno.  El juego es simétrico porque cada jugador tiene las mismas reglas. Es determinístico porque el azar no es parte del juego. Posiciones terminales: no ofrece posiciones legales, no tiene sucesores. 1. Etiquetar las posiciones terminales. Significa que perdió.  2. Nodo posición ganador: el siguiente nodo es perdedor (al menos uno).  3.Nodo posición perdedor: Todos los nodos sucesores son ganadores. 4. Nodo no terminal que lleva a empate. Uno de los sucesores da empate.   -Atravesar árboles: Preorden: nodo - hijo izq - hijo der Enorden: hijo izq - nodo - hijo der Postorden: Hijo izq - hijo der - nodo Todos recorren en tiempo lineal. T(n). -Preacondicionamiento: invertir tiempo en calcular resultados auxiliares con antelación para acelerar el cálculo de la solución. a: tiempo en encontrar solución sin precondicionamiento. n*a b: tiempo con información auxiliar. p: tiempo que se tarda en encontrar esa info. p+n*b Entonces nos beneficia usar pre cuando n > p/(a-b) -Ancestralidad de nodos: Se recorre el árbol en preorden y después en postorden. Prenum y postnum se asignan en cada caso respectivamente.   prenum(v) <= prenum(w) = v es ancestro de w, o v está a la izquierda de w. postnum(v) >= postnum(w) = v es ancestro de w o v está a la derecha de w. prenum(v) <= prenum(w) y además postnum(v) >= postnum(w) = v es ancestro de w Búsqueda en profundidad para grafos no dirigidos: Se elige cualquier nodo como inicial y se marca como visitado. Si hay un nodo adyacente a este, se elige como nuevo punto de inicio, entonces se llama recursivamente a este nodo. Se llama recursivamente a todos los nodos adyacentes al inicial, y así sucesivamente. Se vuelve a llamar a la función si un nodo no se llega a recorrer.  8(max(a,n)) Se pude hacer un MST, del recorrido, los nodos usados son los que hace el recorrido, los punteados son los que no se usaron. Si el grafo no es conexo, se forma un bosque en lugar de un árbol. Se puede colocar un número, que es el orden en que se recorrieron los nodos.  Puntos de articulación:  Los puntos de articulación, el subgrafo que queda cuando ese nodo se elimina ya no es conexo. -Grafo es biconexo o inarticulado, si es conexo y no tiene puntos de articulación. -Bicoherente o libre de istmo o conexo doble arco, si cada punto de articulación es unido por al menos dos arcos a cada componente del subgrafo resultante. Algoritmo para encontrar puntos de articulación: 1. Hacer una búsqueda por profundidad desde cualquier nodo. El prenum es el numero asignado por esta búsqueda. 2. Atravesar el árbol de 1, en postorden, para cada nodo v calcular highest, como en mínimo entre:       a) prenum de v       b) prenum de w, cada nodo con arcos punteados.       c) highest de x, para cada hijo x de v. 3. Determinar puntos de articulación:       a) La raíz es punto articulación si y sólo si tiene más de un hijo.       b) Cada otro nodo v es articulación si y sólo sí tiene un hijo tal que highest de hijo es >= que prenum de padre.   Búsqueda por profundidad para grafos dirigidos:  Similar pero basándose en la dirección, pues se puede formar bosque si no es conexo. Igual se mantienen líneas para las conexiones de la búsqueda y punteadas las que no se usaron pero existían....

  Un determinístico no se desvía, no se cicla, no hay división por 0, etc.   Si estas cosas pasan en el probabilístico, se reinicia hoping que no pase eso. (reset). Aunque el hardware falle el algoritmo no se equivoca.   Monte Carlo: Dan la respuesta correcta con una probabilidad alta. Pero se pueden equivocar. No puede saber si es correcto o no el resultado que obtuvo.      Las Vegas:   Se sabe si se falló o se obtuvo la solución. Cuando falla se vuelve a llamar el algoritmo hasta encontrarlo.      Complejidad: Se usa el tiempo esperado, sobre las instancias, tiempo medio que toma resolver esa instancia una y otra vez.  Tiempo esperado en el peor de los casos: el tiempo que toma la instancia que toma más tiempo, esto sin contar que tome las peores decisiones, sino tomando la peor instancia y ejecutandola una y otra vez.                   

  Algoritmos probabilísticos:   Pueden comportarse(resultado y tiempo) diferente en varias llamadas para una misma instancia. Puede ciclarse, división entre cero, etc. porque nada mas se reinicia esperando que ahora salga bien. Puede tener varias respuestas correctas. Mayor ventaja de darle un toque aleatorio a un determinístico con buen average a pesar de su mal worst case es: hacerlo menos vulnerable a una distribución de probabilidad inesperada de las instancias que debe resolver. Monte Carlo: Dan respuesta que puede ser acertada con una probabilidad alta o puede ser errónea. No se puede saber si la respuesta es correcta, pero se puede disminuir la probabilidad de error arbitrariamente dándole más tiempo. No puede haber una instancia para la cual la probabilidad de error sea alta. Se puede verificar que la respuesta sea correcta, y si es incorrecta decir que lo es.   Las Vegas: Su respuesta siempre es correcta, se sigue llamando el algoritmo hasta que de respuesta correcta. Pueden ser más eficientes que los deterministas en tiempo esperado. A veces puede tomar tiempo excesivo si tenemos mala suerte. Por ejemplo encontrar la mediana.    Tiempo: El tiempo esperado se determina para cada instancia: el tiempo medio que toma resolver la misma instancia una y otra vez. Peor caso: el caso que toma la peor instancia posible de un tamaño dado.  Las Vegas    Generación pseudo aleatoria: Buffon aguja: Siglo 18, Georges Louis Leclerc, probabilidad de tirar una aguja (que mide la mitad del ancho de las tablas) y que quede sobre las rayas de unión es de 1/pi. Para n agujas n/pi. Para obtener un decimal más de precisión se debe de tener un n 100 veces más grande.  Dos parámetros: -La confianza p y la precisión E. El algoritmo cuenta k , la cantidad de agujas que cayeron en las rayas y dice el intervalo de pi.  Integración numérica: Área bajo la curva de una función. Un I que es la integral de b a a de la función es el área bajo la curva. Rectángulo de ancho b-a y altura I/(b-a) Cuenta probabilística:  En un registro binario de n bits, se puede contar hasta 2^n-1 con número entero seguidos, pero más si se saltan valores intermedios.    Monte Carlo:  Dado un p entre 0 y 1. Un algoritmo es p-correcto si su probabilidad es de al menos p, para cualquier instancia (a veces puede depender del tamaño de la instancia pero no de ella en sí). Se puede reducir la probabilidad de error sacrificando un poco de tiempo de ejecución (amplificar la ventaja estocástica).   Verificar la multiplicación de matrices: Se dice que A*B = C. Normalmente sería n^3, o n^2.37 con Strassen. Se puede hacer en n^2 con un E, como máxima probabilidad de error.  Freivalds.    Amplificación de la ventaja estocástica: Los algoritmos vistos son sesgados, al menos una respuesta obtenida es correcta.  Gracias a esto podemos reducir la probabilidad de error arbitrariamente repitiendo el algoritmo varias veces.   Las Vegas: Nunca retornan una respuesta incorrecta.  1. Usan aleatoriedad para guiarse a la respuesta correcta, aunque ocurran situaciones unfortunate, aunque si eso pasa toma mas tiempo (eg quicksort, con el random pueden eliminar la diferencia entre buenas y malas instancias, nos salvan de los casos catastróficos que crean los determinísticos.). Las que en determinístico duraban mucho ya no duran tanto, pero las rápidas se vuelven más lentas. Hacen efecto Robin Hood, roban tiempo de las rápidas para hacer mejor las más lentas.  2. Pueden tener turnos erróneos, que los llevan a puntos muertos, que no logran encontrar solución en ese turno. Se dan cuenta y admiten que fallaron. Ocurren con muy poca probabilidad, por lo que se puede llamar de nuevo el algoritmo para que esta vez lo haga bien. Tiene que tener un buen tiempo para cada instancia. Cuando puede fallar se debe representar como procedimiento NO como función. Se repite hasta que haya éxito.   ...

  Algoritmos paralelos: Se tienen n CPUs físicos, corriendo tareas o threads.  Calcular de árbol binario en arreglo:  

  Modelo para computación paralela: Máquina de von Neumann es una por una instrucción, uno por uno item de data, siguiendo un programa en memoria.  En el libro se usa el modelo "parallel random-access machine" o p-ram. También llamado "single-instruction multiple-data-stream" Se tienen varios procesadores, que se asume que comparten una memoria global. Todos ejecutan el mismo programa dado por un punto central de control. Trabajan en la misma instrucción al mismo tiempo. En cada paso lee o escribe en la memoria global que todos comparten, pero en no mas de una ubicación de esta. Dos pueden leer lo mismo, pero no escribir en lo mismo, ni leer mientras el otro escribe.   concurrent-read, exclusive-write(CREW). Usado en el libro   También existen: -exclusive-read,exclusive-write(EREW) -concurrent-read,concurrent-write(CRCW). En el modelo, leer o escribir, es tiempo constante, sin importar el número de procesadores. Para términos del libro, en la realidad no funciona así. No se permite que el statement sea llamadas a función, ni loops que el largo dependa de la data.  Si tenemos p procesadores, toma 8(log p) en que comience, para decirle a todos que hacer.   Técnicas básicas: 1-Árbol binario completo: Todas las hojas de un mismo nivel se ejecutan en paralelo. La solución se da en el paso lg-n.  Por lo que le toma 8(log n) en hacer la operación con un arreglo con todos los valores. Se ocupan n/2 procesadores como máximo. 2- Pointer doubling: Técnica más simple, para listas. En la lista cada item tiene un puntero al siguiente s[i]. Y el ultimo tiene un puntero a nulo s[n]=nil.    No hay problemas de escritura, pues cada procesador escribe en un solo nodo, pero si de lectura, hay que asegurarse que antes de leer, los anteriores deben haber terminado su proceso.  Cada vez que se corre se dobla el puntero al que apunta. 8(log n) cada procesador hace tiempo constante por las operaciones elementales que realiza.    Trabajo y eficiencia: Trabajo: p*t, p=cantidad de procesadores, t=el tiempo Dos algoritmos son work-efficient, si están en el orden del otro. Dos reglas para que sea eficiente: -La cantidad de procesadores para una instancia de tamaño n debe estar en O(n^a) a siendo una constante. -El tiempo requerido para resolver una instancia de tamaño n deber estar en O(log^b n)b siendo una constante.   Un algoritmo paralelo eficiente tiene número polinomial de procesadores y tiempo poligarítmico. Es óptimo si work-efficient con el mejor algoritmo secuencial o con el mejor conocido. Se puede decir que tiene aceleración óptima (optimal speed-up) Se cree que hay problemas que se solucionan con secuencial, pero no se puede con paralelo.    Ejemplos con grafos: 1. Camino más corto: En la iteración k, da los caminos más cortos entre nodos usando no mas de 2^k arcos. Orden: 8(log^2 n)   2. Componentes conexos: Se encarga de ver que componentes se encuentran conexos de un grafo, dejando un árbol o bosque de resultado. Utiliza conjuntos disjuntos y los une después.  Orden: 8(n^2)   Evaluación de expresiones paralelas: suma, resta, multiplicación y división. Árbol binario nodos internos son operadores y las hojas son los operandos.   Redes de ordenamiento paralelo: Comparador: circuito con dos entradas y dos salidas, izquierda y derecha respectivamente. Si son iguales se cambian de arriba a abajo. Se crean redes se comparadores que ordenan los números que les demos en paralelo. N = cantidad de comparadores a usar (tamaño de la red) Funciona en 8(n)   El principio cero-uno: VER IMAGEN   Redes unidoras paralelas: Una red unidora consiste de comparadores, con dos grupos de n entradas y un grupo de 2n salidas. Cada grupo está ya ordenado, sale todo el conjunto ordenado.    Redes unidoras mejoradas: Se implementa divide and conquer a lo anterior.    Ordenamiento paralelo: Lo anterior puede ordenar n elementos en 8(log^2 n) y...

  Computación evolucionaria se encarga aplicar las características de la evolución para encontrar soluciones óptimas a problemas.  -Búsqueda exhaustiva: se examinan todas las posibles soluciones. 4 paradigmas bases:             -Algoritmos genéticos, Holland 1975             -Programación genética, Koza 1992 1994             -Estrategias evolucionarias Recheuberg 1973             -Programación evolucionaria Forgel et al 1966   Algoritmos genéticos: La más popular. Usa un string de bits de tamaño fijo, cada posición es una característica del individuo y su valor es como se expresa en la solución. Tienen poca o nula interacción entre ellos.  -El mayor operador de reproducción es el "bit-string crossover" o cruce de string de bits. Dos strings son usados como padres y tienen strings hijos haciendo combinaciones entre los padres.  -Otro es mutación por cambio de bits. Donde un bit es cambiado para formar uno nuevo.  -Otra menos usada es inversión. La secuencia de bits es invertida. Es importante ver si los operadores introducen nueva información en la población, cosa que mutación hace pero el cruce no. Y los operadores tienen que producir cambios válidos en las restricciones de genes.   Programación genética: En un programa genético, la representación usada es un árbol de funciones y valores. Cada hoja es una etiqueta de un conjunto de etiquetas funciones disponible.  El árbol completo es una sola función que será evaluada. Es evaluada por profundidad desde la parte de más a la izquierda. Una función es evaluada usando argumentos que son el resultado de evaluar a los hijos. -El operador más usado es el cruce de árboles. Un subárbol entero es cambiado entre dos padres. Todas las funciones y valores deben retornar el mismo tipo, pero los argumentos pueden variar en cantidad. Este principio de cierre (Koza 1994) permite a cualquier subárbol ser considerado a la par con cualquier otro, y que los operadores generarán descendencia permitida.     Estrategias evolucionarias: Se usa un vector de tamaño fijo con valores reales. Cada posición del vector corresponde a una característica del individuo. Pero son características mas de comportamiento que de estructura.  -El operador principal es la mutación Gaussiana. Donde un valor aleatorio de la distribución de Gauss es agregada a cada elemento del vector de un individuo para crear descendencia. -Otro operador es recombinación intermedia. Donde los elementos de dos vectores padres son promediados elemento por elemento para generar descendencia.    Programación evolucionaria: Idea de fenotipo y de responder a estímulos y desarrollar operadores para afectar cambios de comportamiento y estructura. Para problemas de predicción, optimización y machine learning. Su representación es adaptada al dominio del problema. Una común es vector de tamaño fijo con valores reales. La diferencia de las demás es que no hay intercambio de material entre los individuos. Sólo se permite mutar.  Una operación común es agarrar N padres, mutarlos para hacer N descendencia y seleccionar probabilísticamente por fitness solo N de los 2N que tendríamos.      Características de la computación evolucionaria:  Esquema de representación: lo que elige el investigador como conjunto de soluciones para el algoritmo. Un número de soluciones es creada para ser población inicial. Luego se itera repetidamente hasta encontrar una solución que satisfaga el criterio de termino. Cada individuo se evalúa usando una función de fitness para el problema específico. Basados en su fitness se eligen individuos que serán padres, que generarán descendencia basados en operadores de reproducción. Se crean nuevas generaciones con supervivientes y descendencia. El método de selección es el que determina cuántos...

Charles Darwin: teoría de la evolución natural en "El origen de las especies" Organismos evolucionan según selección natural o el más fitness. Combinación de las mejores características de cada padre hacen a lo fittest. Se adaptan cada vez más al ambiente. John Holland en 1975 - "Adaptación en sistemas artificiales y naturales": se plantea esta idea para optimizar y hace el primer algoritmo genético. Se basan en genética y evolución.   Trasfondo biológico:   Genética: ciencia que estudia similitudes y diferencias en las especies. Del griego "génesis" que significa crecer o convertir.   Célula: Todo animal y humano tiene pequeñas industrias que trabajan juntas. Estas son las células, su centro se llama núcleo, donde se encuentra la información genética.   Cromosomas: La información genética se encuentra en el cromosoma, hecho de ADN. Tiene 23 pares. Los cromosomas tienen partes llamadas genes, que tienen las propiedades/características de las especies, llamadas alelos. Los genes pueden tener varios alelos. Por ejemplo el gen del color de ojos, tiene los alelos café, negro, celeste, verde. El conjunto de alelos en una población se llama reserva genética, que determina todas las posibles variaciones.  El conjunto de genes de una especie se llama genoma. Cada gen tiene una posición en el genoma llamado locus.  En la vida real guardan el genoma en varios cromosomas en AG será en uno solo.   Genética: Para individuo particular, la combinación completa de genes se llama genotipo. El fenotipo describe el aspecto físico de decodificar el genotipo.  SELECCIÓN sobre fenotipo, y combinación de reproducción sobre genotipo. Cromosomas tienen dos conjuntos de genes, a esto se le llama diploides. Donde gana el dominante sobre el recesivo. AG se concentra en cromosomas haploides.    Reproducción: -Mitosis: La misma información es copiada a la descendencia, sin intercambio.  -Meiosis:  base de reproducción sexual, donde hay 2 gametos, se conjugan en una cigota, que se convierte en un individuo.   Selección natural: Preservar las variaciones favorables y rechazar las no favorables. *VER IMAGEN DE LO NATURAL VS AG*   Algoritmos genéticos: *Espacio de búsqueda/espacio de estado: El espacio de todas las soluciones prometedoras. Cada una puede ser marcada por su valor fitness, según la definición del problema.     *Mundo de algoritmos genéticos: Es un algoritmo estocástico: debe ser aleatorio, en reproducción y selección. Siempre considera una población de solución. Hay que mantener mas que sólo la solución en cada iteración. Pues la recombinación puede darnos un buen resultado. Debe ser robusto: ser consistente en un rango amplio de problemas de todo tipo. Algoritmo de población base puede ser paralelo.  No dan una solución globalmente óptima, pero si una aceptablemente buena.    Evolución y optimización: Caso de la ballena rara, se van produciendo cambios para hacerse más fuerte, y así crear más descendencia.   Evolución y algoritmos genéticos: La idea de John es: la solución existe en la reserva genética, pero está separada entre los individuos. Incluía mutación y recombinación para esto. La recombinación es el operador clave de la evolución natural. Toma dos genotipos y crea uno nuevo combinando estos dos. Usa mutación y crossover (recombinación)   Técnicas de búsqueda y optimización convencional: El objetivo de optimizar es encontrar un algoritmo que resuelva una clase dada de problemas. Se combina la creatividad humana con los procesos computacionales. 1. Optimización con método local basado en gradiente: Hessian Based. La confianza y desempeño varía mucho. Debe ser una función smooth.  Busca por mínimo, no por máximo. Problema de una dimensión. Usa conjugada, Newton, secante. 2. Búsqueda aleatoria: Busca de forma aleatoria y evalúa su fitness. Es un método tonto. Usado para comparar con resultados de un método mejor. Nunca se...