Buscar en el Blog

Mostrando entradas con la etiqueta algoritmos. Mostrar todas las entradas
Mostrando entradas con la etiqueta algoritmos. Mostrar todas las entradas

viernes, 1 de abril de 2016

domingo, 31 de enero de 2016

lunes, 26 de octubre de 2015

Algoritmos y códigos para cálculos numéricos Fausto Cervantes Ortiz

Algoritmos y códigos para cálculos numéricos Fausto Cervantes Ortiz


UNIVERSIDAD AUTÓNOMA DE LA CIUDAD DE MÉXICO
Enrique Dussel Ambrosini
RECTOR
Ernesto Aréchiga Córdoba
SECRETARIO GENERAL
María del Rayo Ramírez Fierro
COORDINADORA ACADÉMICA
Raúl Soto Peredo
COORDINADOR DEL COLEGIO DE CIENCIA Y TECNOLOGÍA
Eduardo Mosches Nitkin
BIBLIOTECA DEL ESTUDIANTE

El curso de m´etodos num´ericos de la UACM consta de dos partes esenciales: primera, expo-ner los fundamentos matem´aticos de los m´etodos, y segunda, desarrollar c´odigos que permitan al alumno realizar los c´alculos que se le solicitan usando las ventajas de la computadora.
Con respecto al desarrollo de los programas, es frecuente que se ignore el hecho de que el alumno tom´o un curso de programaci´on en C, y se le obligue a adoptar el programa de c´omputo que cada profesor prefiere, ll´amese Matlab, Scilab, etc. Sin embargo, esto puede provocar que el alumno tenga problemas para desarrollar los c´odigos, pues su preparaci´on previa no es la adecuada. Como consecuencia, el alumno termina considerando el curso de m´etodos num´ericos como dos cursos diferentes: uno de matem´aticas y uno de computaci´on. A consecuencia de ello, si el alumno no aprueba alguna de las dos partes, reprobar´a el curso completamente.
Con lo anterior en mente, el autor prepar´o el presente manual de algoritmos, que incluye c´odigos escritos en lenguaje C, a fin de que el alumno no se distraiga del contenido matem´atico del curso, y pueda aplicar los presentes algoritmos y c´odigos a sus problemas sin que esto ´ultimo signifique un trabajo doble. De este modo, el alumno deja de tener el problema de entender el m´etodo sin poder aplicarlo al tener problemas con el programa de c´omputo. Si entendi´o el m´etodo, no le ser´a dif´ıcil adaptar los c´odigos dados como ejemplos para resolver los ejercicios que le sean asignados.
El cap´ıtulo 1 expone los algoritmos y c´odigos para la soluci´on de ecuaciones algebraicas no lineales y trascendentes, con una inc´ognita. Se revisan los m´etodos de bisecci´on, iteraci´on de punto fijo, de las tangentes y de las secantes, ası´ como el de la posici´on falsa.
El cap´ıtulo 2 contiene los algoritmos y c´odigos para interpolaci´on de polinomios a conjuntos de datos. Se exponen los m´etodos de Lagrange, Newton, ası´ como los splines libres y sujetos.
El cap´ıtulo 3 trata los algoritmos y c´odigos para integraci´on y derivaci´on num´erica. Se revi-san los m´etodos de los rect´angulos, trapecios y par´abolas, ası´ como integrales dobles. Tambi´en la derivaci´on num´erica para funciones dadas en forma tabular.
El cap´ıtulo 4 se dedica a los algoritmos y c´odigos para integrar ecuaciones diferenciales ordinarias. Los m´etodos que abarca son los de Euler, Runge-Kutta, Fehlberg y Adams, ası´ como sistemas de ecuaciones.
El cap´ıtulo 5 contiene los algoritmos y c´odigos para resolver num´ericamente sistemas de ecuaciones, lineales o no lineales. Los m´etodos cubiertos son el de eliminaci´on, iteraci´on de punto fijo, ası´ como el de las tangentes y el de las secantes, extrapolados a varias variables.
Cada cap´ıtulo contiene ejercicios de final de secci´on. En trabajos previos, el autor ha acos-tumbrado poner la soluci´on de cada ejercicio propuesto. Por la naturaleza del tema de este libro, eso no es posible o recomendable en algunos de los ejercicios aquı´ planteados. Espec´ıfica-mente, en los cap´ıtulos de interpolaci´on y ecuaciones diferenciales, escribir las respuestas har´ıa que el volumen de este libro aumentara en forma considerable. En lugar de ello, se ha optado por dejar sin respuesta cada ejercicio de esos cap´ıtulos. El alumno no deber´ıa tener problema en verificar por sı´ mismo la certeza de sus resultados.
Este manual no pretende ser exhaustivo en modo alguno. Los m´etodos num´ericos aquı´ abor-dados son los m´as usuales, sin ser todos los que comprende un curso de m´etodos num´ericos.
Cada uno de los c´odigos dados se prob´o para verificar su funcionamiento1. A pesar de ello, no se descarta la posibilidad de errores durante la edici´on del libro. Se agradecer´a a los lectores que se sirvan se˜nalarlos para su correcci´on en futuras ediciones. Por otro lado, habr´a que tener siempre presente la posibilidad de que los c´odigos dados no sean compatibles con la versi´on del compilador o sistema operativo usado por cada quien.
Se agradece el apoyo de la Academia de Matem´aticas para que el presente libro pudiera publicarse. En particular, vayan agradecimientos a Fausto Jarqu´ın Z´arate y a Miguel ´Angel Mendoza Reyes por sus comentarios y sugerencias ´utiles. Por otro lado, a Diana Aurora Cruz Hern´andez, de la Academia de Inform´atica, cuya ayuda para revisar los c´odigos en C fue determinante. Asimismo, el autor agradece a Irma Irian Garc´ıa Salazar, del Algonquin College (en Ottawa, Canad´a) por su revisi´on y las correcciones propuestas.
El presente libro se escribi´o durante el a˜no sab´atico que el autor disfrut´o de agosto de 2011 a julio de 2012. Por ello agradece a la Universidad Aut´onoma de la Ciudad de M´exico el apoyo brindado para que este proyecto pudiera realizarse.

lunes, 3 de agosto de 2015

Tejiendo Algoritmos



Tejiendo Algoritmos 
v 1.0b
Leandro Rabindranath León
lrleon@ula.ve
Centro de Estudios en Microelectrónica y Sistemas Distribuidos 
Universidad de Los Andes

Páginas 888.


sábado, 20 de junio de 2015

Descomponer un numero en factores primos (C++)




 Descomponer un numero en factores primos (C++)
#include <iostream>
using namespace std;
int main()
{
    int n1,n2;
    cout << "Ingrese un numero: ";
    cin >> n1  ;
    for(int i=2;i<=n1;i++)
    {
        n2=n1%i;
        if(n2==0)
        {
          cout<<"numero ->"<<n1<<endl;
          cout<<"Multiplo->"<<i<<endl;
          n1=n1/i;
        }
    }
    return 0;
}


jueves, 11 de junio de 2015

MANUAL DE ALGORITMICA - Grafos


MANUAL DE ALGORITMICA
 Grafos
Proyecto fin de carrera
Escuela Técnica Superior de Ingeniería Informática
Departamento Matemáticas Aplicadas I
Tutor: Alberto Márquez Pérez
Borrego Ropero, Rafael
rafaborrego@gmail.com
Recio Domínguez, Daniel
danird@gmail.com

1.- Introducción................................................................................................... 6
2.- Conceptos generales. ................................................................................... 8
Grafos, tipos, ejemplos................................................................................ 8
Algunas definiciones. ................................................................................ 12
Algunos grafos básicos. ............................................................................ 17
Tipos de rutas ........................................................................................... 46
Grafo complementario............................................................................... 48
Grafo de línea. .......................................................................................... 50
3.- Algoritmos implementados. ......................................................................... 54
3.1.- Algoritmos sobre caminos mínimos. ..................................................... 54
Algoritmo de Dijkstra. ................................................................................ 54
Algoritmo de Floyd. ................................................................................... 61
3.2.- Algoritmos de distancias....................................................................... 65
Excentricidad de un vértice. ...................................................................... 65
Radio de un grafo...................................................................................... 67
Diámetro de un grafo................................................................................. 69
Distancia de un vértice. ............................................................................. 70
Algoritmo de la mediana............................................................................ 72
Algoritmo del centro. ................................................................................. 73
3.3.- Conectividad......................................................................................... 75
Algoritmo de componentes conexas. ........................................................ 75
Vértices de corte. ...................................................................................... 77
Aristas puente. .......................................................................................... 78
Bloques. .................................................................................................... 79
3.4.- Algoritmos de búsquedas. .................................................................... 88
Búsqueda en profundidad (DFS) .............................................................. 88
Búsqueda en anchura (BFS) .................................................................... 90
3.5.- Árboles recubridores de peso mínimo. ................................................. 92
Algoritmo de Boruvka. ............................................................................... 92
Algoritmo de Prim...................................................................................... 98
Algoritmo de Kruskal. .............................................................................. 100
3.6.- Prufer.................................................................................................. 103
Algoritmo de codificación. ....................................................................... 103
Algoritmo de decodificación. ................................................................... 110
3.7.- Algoritmo de emparejamientos ........................................................... 120
Algoritmo de emparejamiento maximal simple........................................ 121
Algoritmo de Kuhn-Munkres.................................................................... 128
Algoritmo de Kuhn-Munkres con preprocesamiento (peso mínimo)........ 142
Algoritmo de emparejamiento maximal de peso óptimo.......................... 146
3.8.- Euler ................................................................................................... 157
¿ Es euleriano ?. ..................................................................................... 157
3.9.- Algoritmos de búsqueda de trayectorias eulerianas. .......................... 162
Algoritmo de Fleury ................................................................................. 162
Algoritmo de Tucker. ............................................................................... 183
Algoritmo de Hierholzer........................................................................... 201
Problema del cartero............................................................................... 205
3.10.- Algoritmos de vértice coloración....................................................... 212
Algoritmo de coloración Secuencial o Voraz. .......................................... 213
Algoritmo de coloración Welsh-Powell .................................................... 215
Algoritmo de coloración Matula-Marble-Isaacson ................................... 216
Algoritmo de coloración de Brelaz........................................................... 217
¿Es bipartito?.......................................................................................... 221
3.11.- Algoritmos de aristas coloración....................................................... 225
Algoritmo basado en rellenar un cuadrado latino .................................... 225
Algoritmo basado en emparejamientos maximales................................. 228
3.-12.- Hamilton .......................................................................................... 235
Algoritmo de Dirac................................................................................... 235
Búsqueda de trayectorias hamiltonianas................................................. 239
4.- Bibliografía ................................................................................................ 248



lunes, 1 de junio de 2015

Técnicas de Diseño de Algoritmos

 Técnicas de Diseño de Algoritmos
UNIVERSIDAD DE MALAGA

326 Pag. 




INTRODUCCIÓN
En un sentido amplio, dado un problema y un dispositivo donde resolverlo, es
necesario proporcionar un método preciso que lo resuelva, adecuado al dispositivo.
A tal método lo denominamos algoritmo.
En el presente texto nos vamos a centrar en dos aspectos muy importantes de los
algoritmos, como son su diseño y el estudio de su eficiencia.
El primero se refiere a la búsqueda de métodos o procedimientos, secuencias
finitas de instrucciones adecuadas al dispositivo que disponemos, que permitan
resolver el problema. Por otra parte, el segundo nos permite medir de alguna forma
el coste (en tiempo y recursos) que consume un algoritmo para encontrar la
solución y nos ofrece la posibilidad de comparar distintos algoritmos que resuelven
un mismo problema.
Este capítulo está dedicado al segundo de estos aspectos: la eficiencia. En
cuanto a las técnicas de diseño, que corresponden a los patrones fundamentales
sobre los que se construyen los algoritmos que resuelven un gran número de
problemas, se estudiarán en los siguientes capítulos.

EFICIENCIA Y COMPLEJIDAD
Una vez dispongamos de un algoritmo que funciona correctamente, es necesario
definir criterios para medir su rendimiento o comportamiento. Estos criterios se
centran principalmente en su simplicidad y en el uso eficiente de los recursos.
A menudo se piensa que un algoritmo sencillo no es muy eficiente. Sin
embargo, la sencillez es una característica muy interesante a la hora de diseñar un
algoritmo, pues facilita su verificación, el estudio de su eficiencia y su
mantenimiento. De ahí que muchas veces prime la simplicidad y legibilidad del
código frente a alternativas más crípticas y eficientes del algoritmo. Este hecho se
pondrá de manifiesto en varios de los ejemplos mostrados a lo largo de este libro,
en donde profundizaremos más en este compromiso.



CAPÍTULO 1: LA COMPLEJIDAD DE LOS ALGORITMOS........................ 1
1.1 Introducción ................................................................................................ 1
1.2 Eficiencia y complejidad............................................................................. 1
1.3 Cotas de complejidad. Medidas asintóticas................................................. 6
1.4 Resolución de ecuaciones en recurrencia.................................................. 10
1.5 Problemas propuestos................................................................................ 16
1.6 Solución a los problemas propuestos ........................................................ 22
CAPÍTULO 2: ORDENACIÓN........................................................................... 57
2.1 Introducción .............................................................................................. 57
2.2 Ordenación por Inserción .......................................................................... 60
2.3 Ordenación por Selección ......................................................................... 61
2.4 Ordenación Burbuja .................................................................................. 62
2.5 Ordenación por Mezcla (Mergesort) ......................................................... 63
2.6 Ordenación mediante Montículos (Heapsort) ........................................... 65
2.7 Ordenación Rápida de Hoare (Quicksort) ................................................. 67
2.8 Ordenación por Incrementos (Shellsort) ................................................... 70
2.9 Otros algoritmos de ordenación ................................................................ 71
2.10 Problemas propuestos.............................................................................. 74
2.11 Solución a los problemas propuestos ...................................................... 77
CAPÍTULO 3: DIVIDE Y VENCERÁS........................................................... 105
3.1 Introducción ............................................................................................ 105
3.2 Búsqueda binaria..................................................................................... 108
3.3 Búsqueda binaria no centrada ................................................................. 109
3.4 Búsqueda ternaria.................................................................................... 110
3.5 Multiplicación de enteros ........................................................................ 112
3.6 Producto de matrices cuadradas (1)......................................................... 114
3.7 Producto de matrices cuadradas (2)......................................................... 116
3.8 Mediana de dos vectores ......................................................................... 117
3.9 El elemento en su posición...................................................................... 119
3.10 Repetición de cálculos en Fibonacci ..................................................... 120
3.11 El elemento mayoritario ........................................................................ 121
3.12 La moda de un vector ............................................................................ 124
3.13 El torneo de tenis................................................................................... 127
3.14 Divide y Vencerás multidimensional .................................................... 132
3.15 La subsecuencia de suma máxima......................................................... 137
CAPÍTULO 4: ALGORITMOS ÁVIDOS........................................................ 141
4.1 Introducción ............................................................................................ 141
4.2 El problema del cambio........................................................................... 143
4.3 Recorridos del caballo de ajedrez............................................................ 147
4.4 La división en párrafos............................................................................ 150
4.5 Los algoritmos de Prim y Kruskal........................................................... 155
4.6 El viajante de comercio ........................................................................... 160
4.7 La mochila............................................................................................... 164
4.8 La mochila (0,1) ...................................................................................... 165
4.9 El fontanero diligente.............................................................................. 166
4.10 Más fontaneros ...................................................................................... 167
4.11 La asignación de tareas ......................................................................... 168
4.12 Los ficheros y el disquete...................................................................... 171
4.13 El camionero con prisa.......................................................................... 173
4.14 La multiplicación óptima de matrices ................................................... 175
CAPÍTULO 5: PROGRAMACIÓN DINÁMICA............................................ 177
5.1 Introducción ............................................................................................ 177
5.2 Cálculo de los números de Fibonacci...................................................... 178
5.3 Cálculo de los coeficientes binomiales ................................................... 180
5.4 La subsecuencia común máxima............................................................. 181
5.5 Intereses bancarios .................................................................................. 184
5.6 El viaje más barato por río ...................................................................... 186
5.7 Transformación de cadenas..................................................................... 187
5.8 La función de Ackermann ....................................................................... 189
5.9 El problema del cambio........................................................................... 191
5.10 El algoritmo de Dijkstra ........................................................................ 194
5.11 El algoritmo de Floyd............................................................................ 196
5.12 El algoritmo de Warshall....................................................................... 197
5.13 Ordenaciones de objetos entre dos relaciones....................................... 198
5.14 El viajante de comercio ......................................................................... 200
5.15 Horarios de trenes.................................................................................. 201
5.16 La mochila (0,1) .................................................................................... 202
5.17 La mochila (0,1) con múltiples elementos ............................................ 205
5.18 La multiplicación óptima de matrices ................................................... 206
CAPÍTULO 6: VUELTA ATRÁS..................................................................... 211
6.1 Introducción ............................................................................................ 211
6.2 Las n reinas ............................................................................................. 212
6.3 Recorridos del rey de ajedrez .................................................................. 219
6.4 Recorridos del rey de ajedrez (2) ............................................................ 222
6.5 Las parejas estables ................................................................................. 224
6.6 El laberinto .............................................................................................. 226
6.7 La asignación de tareas ........................................................................... 229
6.8 La mochila (0,1) ...................................................................................... 231
6.9 Los subconjuntos de suma dada .............................................................. 234
6.10 Ciclos Hamiltonianos. El viajante de comercio .................................... 236
6.11 El continental ........................................................................................ 239
6.13 La asignación de tareas en paralelo....................................................... 244
6.14 El coloreado de mapas........................................................................... 246
6.15 Reconocimiento de grafos..................................................................... 249
6.16 Subconjuntos de igual suma.................................................................. 251
6.17 La múltiples mochilas (0,1)................................................................... 253
CAPÍTULO 7: RAMIFICACIÓN Y PODA..................................................... 255
7.1 Introducción ............................................................................................ 255
7.2 Consideraciones de implementación ....................................................... 257
7.3 El puzzle (n2–1)....................................................................................... 262
7.4 El viajante de comercio ........................................................................... 270
7.5 El laberinto .............................................................................................. 278
7.6 La colocación óptima de rectángulos ...................................................... 285
7.7 La mochila (0,1) ...................................................................................... 291
7.8 La mochila (0,1) con múltiples elementos .............................................. 296
7.9 La asignación de tareas ........................................................................... 298
7.10 Las n reinas ........................................................................................... 303
7.11 El fontanero con penalizaciones............................................................ 307
BIBLIOGRAFÍA Y REFERENCIAS ............................................................... 315

miércoles, 30 de abril de 2014