FPR Potencia Pot(x,y)=x*pot(x,y-1) Pot(x,0)=1
La recursión desde el punto de vista de C Como se crean funciones (tamaños y tipos de datos. Se puedo aproximar el numero de veces que una Recursión se va ha realizar. El Stack (over flow y underflow) Esqueleto de una función Funciones Vacías Ejercicios Imprimir números del 1 al 10 Hacia delante Hacia atrás
Que procesos hace la recursión en la computadora Bajo una llamada recursiva el sistema reserva espacio (tabla de activación, también llamada Stack o Pila) donde almacenar una copia de los objetos locales y parámetros del subprograma en ese momento (variables locales, parámetros y la dirección de reingreso). La tabla de activación se amontona sobre las llamadas recursivas anteriores formando lo que se conoce como pila recursiva. Este proceso termina cuando un nuevo valor del parámetro no produce una nueva llamada recursiva (se alcanza el caso base). Una vez alcanzada esta situación el sistema va liberando el espacio reservado conforme los subprogramas se van ejecutando sobre su tabla de activación. Este proceso finaliza con la llamada inicial.
Como Funciona la memoria de la computadora
Función que busca un dato en un arreglo (tarea modificarlo para que busque en un arreglo bidimensional) Función que imprime una cadena al revés (ejemplo de cuando no usar la recursión)
Procesos recursivos e iterativos x=0 0; x=1 1 Fibonacci(X) x>2 fibonacci(x-1) + fibonacci(x-2)
int fbI(int z) { int R,i,a,b; R=1; a=0; b=1; i=1; while(i< z) { R=a+b; a=b; b=R; i++ } } int fbR(int z) { if (z==0) return 0; else if (z==1) return 1; else return fbR(z-1)+fbR(z-2); }
Números de catalán Uso de los números de Catalán. El juego de la vida problemas poblacionales
Número Aureo
Particiones y combinatorias Como obtener las combinatorias de un conjunto de términos o de un conjunto
Búsqueda en profundidad y anchura
Particiones de números Dado un número natural n llamamos “particiones de n” a todas las maneras de escribir n como suma de números naturales. Por ejemplo: hay 11 particiones del número 6: 1+1+1+1+1+1 2+1+1+1+1 2+2+1+1 2+2+2 3+1+1+1 3+2+1 3+3 4+1+1 4+2 5+1 6
Diversos matemáticos han propuesto teorías de cómo calcular el numero de formas de partir un número en sumas, el más conocido de ellos fue Leonard Euler quien expuso una serie de conjeturas al respecto
Particiones de números De las teorías de Euler se desprende que la suma de valores anteriores de la serie de números nos establece el numero de particiones de un numero. Por ejemplo si p(n) representa el numero de particiones de un numero “n” es decir p(n) son el total de formas distintas de obtener “n”, haciendo sumas temenos que: p(4)= p(3)+p(2) p(6)= p(5)+p(4)-p(1) P(5)=p(4)+p(3)-p(1) p(9)=p(8)+p(7)-p(4)-p(2)
Particiones de números Estos valores provienen de la formula matemática
En donde el limite ó paro de la sumatoria esta dado por el hecho de que la resta de n con el término debe de ser positivo o cero, y conocemos que p(0)=1;
Dos problemas
Particiones de números Como se representaría de forma 100% recursiva esta formula? Como se pueden obtener las combinaciones en si?, es decir todas las sumas? Planteando el problema desde otro punto de vista: tenemos a un conjunto formado por números del 1 hasta n, que combinación con repetición podemos hacer de ese conjunto de elementos de tal suerte que la suma de los elementos de cada combinación sumen n. 1,2,3, 4,5,6 Conjunto de elementos para n=6, el problema de esto es la cantidad de combinaciones a evaluar, 46656 combinaciones.
Particiones de conjuntos Una partición de un conjunto X es una colección {A1,A2, . . . ,An} de subconjuntos de X, no vacíos y disjuntos dos a dos, tales que A1 U A2 U .. . U An = X. A cada uno de los conjuntos Ai se le llama bloque de la partición. Las particiones del conjunto {a, b, c} son: {a, b, c} (un solo bloque), {a, b}, {c} (2 bloques), {a, c}, {b} (2 bloques), {b, c}, {a} (2 bloques), {a}, {b}, {c} (3 bloques).
Particiones de conjuntos Para un conjunto de 3 elementos tenemos 5 formas diferentes de partir el conjunto. El número total de particiones que admite un conjunto de n elementos se denomina número de Bell de orden n y se denota Bn. Se sabe que Los primeros números de Bell son B0 = 1, B1 = 1, B2 = 2 B3 = 5. SE puede obtener el numero de particiones de un conjunto a partir de la siguiente formula
Coeficientes Binomiales Los coeficientes binomiales, que son los coeficientes enteros de la expansión de (a+b)n fueron conocidos en el siglo XII. El triángulo de Pascal que es un arreglo triangular de los coeficientes binomiales fue desarrollado en el siglo XIII. En donde cada entrada de la tabla es la suma de los dos números que están inmediatamente encima de ella
Particiones de conjuntos Por otra parte, el número de particiones que admite un conjunto de n elementos con exactamente k bloques se denomina número de Stirling de segunda clase con índices n y k y se denota mediante el símbolo
Cuya relación de recurrencia es la siguiente :
Torres de Hanoi El problema consiste en mover n discos (todos ellos de diferente tamaño) de un poste a otro siguiendo las reglas Solo se puede mover un disco a la vez Un disco grande no puede quedar encima de otro de menor tamaño
Torres de Hanoi
Posibilidades de 4 discos
Torres de Hanoi Solución: No seguir un proceso ordenado podría llevarnos a un camino cerrado o a un serie de pasos redundantes. Realmente la solución viene dada por el hecho de solucionar un problema previo, es decir antes de mover el último disco necesitamos mover todos los de arriba de él a otro poste.
Torres de Hanoi Solución 1- Mover n-1 discos de A a B 2- Mover 1 disco de A a C 3- Mover n-1 discos de B a C
Torres de Hanoi void Hanoi( n, inicial, aux, final ) { if ( n>0 ) { Hanoi(n-1, inicial, final, aux ); printf("Mover %d de %c a %c", n, inicial, final ); Hanoi(n-1, aux, inicial, final ); } }
Josephus Problem Cuenta una leyenda sobre el historiador Josephus Flavius que, durante las guerras judeo-romanas, él y otros 40 soldados judíos quedaron atrapados en una cueva rodeados por los romanos. Visto que tenían pocas posibilidades de salir con vida, decidieron suicidarse. Josephus y un amigo suyo no estaban muy felices con esa idea. Así pues, propusieron que si había que hacerlo, se hiciera con cierto orden: se colocarían en círculo y se irían suicidando por turno cada tres empezando a contar por uno determinado. Josephus y su amigo se colocaron de tal forma que fueron los dos últimos y así, como ya nadie les podía llevar la contraria, decidieron seguir viviendo.
Fractales Un fractal es un objeto semi geométrico cuya estructura básica se repite a diferentes escalas. El término fue propuesto por el matemático Benoît Mandelbrot en 1975 y deriva del Latín fractus, que significa quebrado o fracturado. Los fractales pueden ser generados por un proceso recursivo o iterativo, capaz de producir estructuras auto-similares a cualquier escala de observación. Los fractales son estructuras geométricas irregulares y de detalle infinito. Muchas estructuras naturales son de tipo fractal.
Fractales LA CONSTRUCCIÓN de un fractal, esta la posibilidad de utilizarlo para producir, almacenar, analizar o transmitir una imagen se simplifica considerablemente haciendo uso de la computadora. De hecho, el efecto y la utilidad que ha demostrado tener la geometría fractal no se hubieran manifestado sin las facilidades de cálculo y representación gráfica que proporciona el trabajo en computadora; parecen estar hechos el uno para el otro. Los fractales se generan a través de procesos en los que una misma operación se repite un sin número de veces, y eso es precisamente lo que una computadora sabe hacer mejor.
Tipos de fractales IFS, sistemas de funciones iteradas Lindermayer y Sierpinsky Orbitas Caóticas Aleatorios y Celulares Algoritmos de escape, Malderbrot y Julia
Fractales La mayoría de los métodos desarrollados para construir imágenes fractales se basan en procedimientos muy sencillos que en cualquier lenguaje computacional se expresan en unos cuantos renglones; de ahí la sorpresa que provoca observar la complejidad de la imagen que hacen surgir en la pantalla.
Fractales Los fractales más simples de crear se basan en las teorías de Lindermayer y Sierpinski, normalmente son procesos recursivos o iterativos que van creando una estructura simétrica basa en procesos pendientes.
Dentro de este grupo de fractales se encuentran los de Niels Helge von Koch y David Hillbert, el primero para la simulación de copos de nieves y el segundo para la creación de semilaberintos.
Fractales Que se necesita para hacer un fractal de éste tipo? Un proceso recursivo o iterativo Un determinado numero de repeticiones que permitan ver el efecto, con un paro determinado por las condiciones del problema Un número de ramificaciones dentro del proceso que permita representar mejor el problema que se plantea
Solución Ec. No Lineales Raíces de ecuaciones Sea f(x)=y. Los valores de x que hacen que y=0 se denominan raíces de la ecuación.
Solución Ec. No Lineales Raíces de ecuaciones Las raíces de un polinomio pueden ser reales o complejas. Si un polinomio tiene coeficientes a0, a1, a2, a3, .. an-1, an reales, entonces todas las raíces complejas siempre ocurrirán en pares conjugados complejos. Por ejemplo, un polinomio cúbico tiene la siguiente forma general:
El teorema fundamental del álgebra indica que un polinomio de grado n, tiene n raíces. En el caso del polinomio cúbico pueden darse los siguientes casos: Tres raíces reales distintas. Una raíz real con multiplicidad 3. Una raíz real simple y una raíz real con multiplicidad 2. Una raíz real y un par conjugado complejo.
Solución Ec. No Lineales Raíces de ecuaciones Ejemplo1 3 Raíces reales diferentes f(x)= x3-3×2-x+3 (x-3)(x+1)(x-1) x1=3, x2=-1, x3=1
Solución Ec. No Lineales Raíces de ecuaciones Ejemplo 2 1 Raíz real simple y 1 raíz Real con multiplicidad 2 f(x)= x3-12x+16 (x-4)(x-2)2 x1=4, x2=2, x3=2
Solución Ec. No Lineales Raíces de ecuaciones Ejemplo 3 1 Raíz real simple y 1 par conjugado complejo f(x)= x3-2×2-3x+10 (x+2)(x-(2+i)) (x-(2-i)) x1=-2, x2=2+i, x3=2-i Tarea investigar cuales son las Ecuaciones trascendentales.
Solución Ec. No Lineales Raíces reales de ecuaciones algebraicas y trascendentales En general, los métodos para encontrar las raíces reales de ecuaciones algebraicas y trascendentales se dividen en métodos de intervalos y en métodos abiertos.
Solución Ec. No Lineales Raíces reales de ecuaciones algebraicas y trascendentales Los métodos de intervalos aprovechan el hecho de que una función en forma típica cambia de signo en la vecindad de una raíz. Reciben dicho nombre debido a que se necesita de dos valores iniciales que deben “encapsular” a la raíz. A través de este tipo de métodos se va reduciendo gradualmente el tamaño del intervalo de manera que la aplicación repetida de los métodos siempre generan aproximaciones cada vez más cercanas al valor real de la raíz, por lo que se dice que son métodos convergentes.
Solución Ec. No Lineales Raíces reales de ecuaciones algebraicas y trascendentales Los métodos abiertos, en contraparte, se basan en fórmulas que requieren de un solo valor inicial x (aproximación inicial a la raíz). Algunas veces, estos métodos se alejan del valor real de la raíz conforme crece el número de iteraciones, es decir, divergen .
Solución Ec. No LinealesBisección El método de Bisección es un método recursivo donde se empieza a analizar el intervalo (x0,x) . Bisección(x0,x) Calcular xr Si f(xr)=0 ó muy pequeño ó se tiene definido un margen de error relativo xr es la solución Si no Si f(x0)*f(xr)< 0 Bisección(x0,xr) sino Bisección(xr,x)
Solución Ec. No Lineales Bisección
Solución Ec. No Lineales Bisección Ejemplo encuentre una raíz que calcule la función x2-9=0, puede ser obvio que la respuesta es -3 ó 3 Si consideramos el intervalos de -5 y 3 estos serían los pasos mab= (a+b)/2=(-5+3)/2=-1 f(a)=16; f(mab)=-8; f(b)=0 Aunque hay dos cambios de signo lo cual ya nos dice que hay por lo menos 2 soluciones tomamos la 1a. b=mab osea b=-1
Solución Ec. No Lineales Bisección Como no encontramos la solución y el error no lo estamos considerando hacemos otra vuelta de cálculos mab= (a+b)/2=(-5-1)/2=-3 f(a)=16; f(mab)=0; f(b)=-8 Como el cambio de signo se da entre el medio y b cambiamos a a=mab osea a=-3 Pero como f(mab)=0 el método termina
Solución Ec. No Lineales Bisección Sin embargo el método no es exacto y tiene muchos error de aproximación aplique el método para el intervalo -5 y 4. Que sucede. Que desventajas presenta el método de Bisección, dedúzcalas e investíguelas.
Solución Ec. No Lineales Regla Falsa
Solución Ec. No Lineales Regla Falsa Basados en la teoría de la línea recta ((x1 –x0 )*f(x1)) xnew = x1 – ——————- f(x1)-f(x0) Si f(xnew)=0 ó el margen de error es aceptabe, xnew es la solución Si no se calculan f(x0) y f(x1), hay que observar el cambio de signo como en bisección y ajustar el punto x0 ó x1 al xnew según sea el caso. El error se puede calcular en términos relativos |x new (actual) – x new (anterior) | —————————————– X 100 x new (actual)
Este forma de calculo del margen de error no es exclusivo de este método se puede utilizar en cualquier calculo que se busque una aproximación
Coeficientes binomiales negativos Cuando el Exponente a que se va a elevar un binomio es Negativo ó Fraccionario el proceso para obtener los coeficientes es el mismo que para una potencia positiva, con la variación de que su desarrollo es Infinito.
La razón de que su desarrollo tiende a infinito, es que de acuerdo con el “Teorema del Binomio”, en un binomio elevado a cualquier potencia el ultimo término del desarrollo es aquel que tiene el primer término del binomio elevado a la potencia cero por lo tanto cuando se tiene un exponente negativo cada vez que calculamos un término nos alejamos cada vez mas del cero, y si tuviéramos un exponente fraccionario al ir calculando los términos lo brincaríamos.
Coeficientes binomiales negativos Los CBN son un resultado estándar de las teorías combinacionales, el cual fue derivado por Planck en 1900, y se relacionan con el método de Poisson para el pronostico de comportamientos de eventos.
http://books.google.com.mx/books?id=-pZX2KS2KqMC&pg=PA141&lpg=PA141&dq=%22negative+binomial+coefficient%22&source=web&ots=_RkqEmTqAn&sig=uvQt3bbRYwbUacjf2jpg0FlV2ew&hl=es&sa=X&oi=book_result&resnum=1&ct=result
Funciones enteras y diferencias finitas
Operadores Sigma S, Sumatoria Delta ?, incremento Nabla ? , Gradiente (como delta pero invertido) Corrimiento , mover los elementos
Ecuaciones Recursivas Homogéneas Las recurrencias lineales homogéneas tienen la forma: a0tn + a1tn-1 + … + aktn-k = 0 [1] Donde los ti son los valores buscados (aplicamos el adjetivo de lineal por que no hay términos de la forma titi+j ó ti2, por ejemplo), los coeficientes ai son constantes y la recurrencia es homogénea por que la combinación lineal de los ti es igual a 0. Soluciones buscadas de la forma tn=xn, donde x es una constante. Si sustituimos esta solución en [1] obtenemos: a0xn + a1xn-1 + … + ak xn-k = 0 [2] Esta ecuación tiene dos soluciones: x=0, que no nos sirve, y
Ecuaciones Recursivas Homogéneas Esta ecuación tiene dos soluciones: x=0, que no nos sirve, y a0xk + a1xk-1 + … + ak= 0, ecuación característica asociada a la ecuación recurrente inicial. Supongamos que las k raíces de esta ecuación característica son r1, r2, …, rk, entonces cualquier combinación lineal
Ecuaciones Recursivas Homogéneas
de términos rin es solución para la ecuación recurrente lineal homogénea
Ecuaciones Recursivas Homogéneas Por una relación recursiva lineal homogénea de segundo orden con coeficientes constantes entenderemos una expresión definida para todo n número natural positivo de la forma x n+2 =ax n+1 + bxn , donde a y b son dos números reales no nulos y para la que están dados dos valores reales iniciales x0 y x1 .
Ecuaciones Recursivas Homogéneas Esta expresión nos permite obtener una sucesión de números reales. Tiene el inconveniente de que para conocer el valor de la función en un número natural k arbitrario hay que conocer cuando menos los dos anteriores. Por esto es deseable encontrar una regla de correspondencia que nos indique cómo calcular el n -ésimo valor de la sucesión sin necesidad de conocer los valores previos. A esta regla de correspondencia se le llama “forma cerrada” de la relación de recurrencia.
Raíces de la ecuación característica Las raíces de la ecuación característica nos van a proporcionar un sistema fundamental de soluciones. Estas raíces pueden ser de varios tipos: • Si ? es una raíz real simple de la ecuación característica, proporciona una solución y = e?x de la ecuación diferencial lineal homogénea con coeficientes constantes. • Si ? es una raíz real múltiple de orden m de la ecuación característica, proporciona las soluciones (independientes) y = e?x, y =xe?x, … , y =xm-1e?x de la ecuación diferencial. • Si ?= a ± bi son raíces complejas conjugadas de la ecuación característica, proporciona las soluciones y =eaxcos bx, y =eaxsen bx. • Si ?= a ± bi son raíces complejas conjugadas de multiplicidad m de la ecuación característica, proporciona las soluciones y =eaxcos bx, y =eaxsen bx, y =xeaxcos bx, y =xeax sen bx, … , y =xm-1eaxcos bx , y =xm-1eaxsen bx
Búsqueda de polinomios ajustados a puntos El análisis de regresión es una técnica estadística para la investigación de la relación entre dos o mas variables, puede emplearse para construir un modelo que permita predecir el comportamiento de una variable y (dependiente, respuesta) en función de una o mas variables (independientes, predictivas) x. Los comportamientos de estas variables pueden estar definidos en un modelo teórico, o no.
Búsqueda de polinomios ajustados a puntos Lo anterior se puede lograr usando un diagrama de dispersión lo que nos conduciría a desarrollar un modelo empírico de la relación que mantienen las variables en estudio.
Funciones y Diferencias finitas Ejemplo : Tenemos un sensor que nos arroja los siguientes datos .
¿Que ecuación nos representa mejor el comportamiento del dispositivo?
Funciones y Diferencias finitas Que pasa si tenemos que el mismo el sensor da diferentes valores en muestreos diferentes? Que ecuación representa este comportamiento
Funciones y Diferencias finitas Cuando conocemos la expresión que denota el comportamiento de cualquier problema encontrar un valor de “y”no es mucho problema. Que pasa si solo conocemos el comportamiento y no el polinomio que lo representa?
Regresion Lineal Un polinomio con solamente una variable es cualquier expresión que se puede escribir de la forma anxn + an-1xn-1 + · · · + a1x1 + a0 donde x es una variable, los exponentes son números enteros no negativos, y los coeficientes son números reales. Una función de la forma Pn(x)= anxn + an-1xn-1 + · · · + a1x1 + a0 es una función polinomial.
Calculo del error El problema de ajuste consiste en encontrar los coeficientes ai que hagan que este polinomio se parezca lo más posible a los datos de acuerdo a alguna definición de error. Definimos el error ei del polinomio en el punto xi como la diferencia entre el valor que toma el polinomio y el valor fi, es decir: ei = yi – Pn(xi) Como lo que se busca es minimizar el error hay que sumar todos los errores, de cada punto, la forma final es una ecuación de la forma:
Calculo del error La importancia de un ajuste radica mas el comportamiento de los datos que en el ajuste de los puntos. Si tenemos los puntos rojos como la muestra conocida y las líneas verde (Ec. Lineal) y azul (Ec. Cubica o transendental) me muestran 2 ecuaciones, debe de ser obvio que el mejor ajuste lo tiene la azul.
Calculo del error Que pasa si calculamos un valor fuera del rango conocido? Las ecuaciones deberían mostrar tendencias claras sobre el comportamiento de la muestra, y en nuestro ejemplo mostrar una tendencia hacia arriba. ¿Cuál ecuación muestra una mejor tendencia? La respuesta es muy relativa, pero con la información que se tiene la respuesta debería ser la verde. De aquí se puede desprender que a mayor cantidad de puntos en el muestreo es mejor para establecer el comportamiento de los datos.
El método de diferencias finitas Este método sirve para encontrar el grado de un polinomio hipotético con el cual se puede representar el comportamiento del dispositivo o problema. Consiste en empezar a obtener las diferencias entre los valores obtenidos de la variable dependiente. La variable dependiente puede ser cualquiera de las 2 (x ó y) normalmente es y.
El método de diferencias finitas Primer diferencia
El método de diferencias finitas Segunda diferencia, esta se obtiene de los valores de la 1ª diferencia.
El método de diferencias finitas Se repite el proceso hasta que las diferencias entre los valores disminuye a un rango aceptable. Que es lo que buscamos encontrar, una linealidad, con lo cual hemos encontrado el grado aparente del comportamiento del problema.
El método de diferencias finitas Lo que sigue es igual de fácil, es determinar el polinomio, para ellos necesitamos puntos conocidos y la ecuación general del grado del polinomio que creemos que es, en nuestro ejemplo la ecuación sería a2x2+a1x+a0=0. Tomemos 3 puntos y creemos un sistema simultaneo de ecuaciones. a2(0)2+a1(0)+a0=2 a2(0.2)2+a1(0.2)+a0=1.804 a2(0.45)2+a1(0.35)+a0=1.008
El método de diferencias finitas Utilice los datos siguientes para encontrar la f(x), utilice la desviación estándar como paro, valor esperado de la Desviación estándar 0.04 (se pudo haber utilizado la varianza) La respuesta esta dada cuando la desviación estándar llega a : 0.030038 , siendo un polinomio de grado 3, parecido a : 0.9973 – 0.8044 x – 0.4878 x2 + 0.5327×3
Método de mínimos cuadrados Es una técnica de optimización matemática que, dada una serie de mediciones, intenta encontrar una función que se aproxime a los datos (un "mejor ajuste"). Supóngase que el conjunto de datos consiste en los puntos (xi,yi) siendo i=1,2,3,..,n. Queremos encontrar f(xi) ? yi Para llegar a este objetivo, necesitamos obtener los coeficientes de la ecuación hasta un grado razonable. Se utiliza la suma de los residuos al cuadrado, es decir la diferencia del valor obtenido menos la evaluación de la función en el punto x
Esto explica el nombre de mínimos cuadrados.
Mínimos cuadrados Sin embargo el primer problema es encontrar la ecuación para evaluarla, por lo tanto utilizando derivadas hipotéticas sobre la función hipotética se obtiene que tales derivadas se obtienen de la suma de la incógnita en las subecuaciones derivadas. De lo cual se deriva una tabla en forma matricial que nos da una razón de coeficientes.
Mínimos cuadrados
Mínimos cuadrados x={0.05, 0.11, 0.15, 0.31, 0.46, 0.52, 0.7, 0.74, 0.82, 0.98, 1.17} y={0.956, 0.89, 0.832, 0.717, 0.571, 0.539, 0.378, 0.37, 0.306, 0.242, 0.104} ?xi=6.01 N=11 ?xi2=4.6545 ?Yi=5.905 ?xi3= 4.1150 ?xiYi=2.1839 ?xi4= 3.9161 ?xi2Yi=1.3335 F(x)=0.998-1.018x+0.225×2
Mínimos cuadrados Como saber a que grado se debe ajustar el polinomio? En cuanto se aumente el grado del polinomio se reduce el margen de error de los puntos involucrados, pero esto no es bueno. La respuesta esta en la estadística. El grado del polinomio se incrementa mientras haya un decremento estadístico SIGNIFICATIVO de la varianza.
Mínimos cuadrados Para el ejemplo anterior tenemos la siguiente tabla
| Página siguiente |