CURSOS de Algoritmia

Documento correspondiente al mulo curso de Algoritmos realizado por Arturo Lopez Ortiz de la Universidad Nacional Abierta y a Distancia - UNAD.
En formato pdf. Contiene 127 páginas.

El presente documento ha sido elaborado originalmente como apoyo a la asignatura de “Análisis y Diseño de Algoritmos” del séptimo semestre de la carrera de Ingeniería en Gestión Informática, del Instituto Nacional de Capacitación (INACAP). Este documento engloba la mayor parte de la materia de este curso troncal e incluye ejemplos resueltos y algunos ejercicios que serán desarrollados en clases.
El manual ha sido concebido para ser leído en forma secuencial, pero también para ser de fácil consulta para verificar algún tema específico.
No se pretende que estos apuntes sustituyan a la bibliografía de la asignatura ni a las clases teóricas, sino que sirvan más bien como complemento a las notas que el alumno debe tomar en clases. Asimismo, no debe considerarse un documento definitivo y exento de errores, si bien ha sido elaborado con detenimiento y revisado exhaustivamente.
El autor pretende que sea mejorado, actualizado y ampliado con cierta frecuencia, lo que probablemente desembocará en sucesivas versiones, y para ello nadie mejor que los propios lectores para plantear dudas, buscar errores y sugerir mejoras.

Índice de Contenidos:
Presentación
1. Introducción
1.1. Motivación y Objetivos
1.2. Algunas Notas sobre la Historia de los Algoritmos
1.3. Fundamentos Matemáticos
2. Algoritmos y Problemas
2.1. Definición de Algoritmo
2.2. Formulación y Resolución de Problemas
2.3. Razones para Estudiar los Algoritmos
2.4. Formas de Representación de Algoritmos
2.5. La Máquina de Turing
3. Eficiencia de Algoritmos
3.1. Introducción
3.2. Concepto de Eficiencia
3.3. Medidas de Eficiencia
3.4. Análisis A Priori y Prueba A Posteriori
3.5. Concepto de Instancia
3.6. Tamaño de los Datos
3.7. Cálculo de Costos de Algoritmos
3.7.1. Cálculo de eficiencia en análisis iterativo
3.7.2. Cálculo de eficiencia en análisis recursivo
3.8. Principio de Invarianza
3.9. Análisis Peor Caso, Mejor Caso y Caso Promedio
4. Análisis de Algoritmos
4.1. Introducción
4.2. Tiempos de Ejecución
4.3. Concepto de Complejidad
4.4. Órdenes de Complejidad
4.5. Notación Asintótica
4.5.1. La O Mayúscula
4.5.2. La o Minúscula
4.5.3. Diferencias entre O y o
4.5.4. Las Notaciones Ω y Θ
4.5.5. Propiedades y Cotas más Usuales
4.6. Ecuaciones de Recurrencias
4.6.1. Introducción
4.6.2. Resolución de Recurrecias
4.6.3. Método del Teorema Maestro
4.6.4. Método de la Ecuación Característica
4.6.5. Cambio de Variable
4.7. Ejemplos y Ejercicios
5. Estrategias de Diseño de Algoritmos
5.1. Introducción
5.2. Recursión
5.3. Dividir para Conquistar
5.4. Programación Dinámica
5.5. Algoritmos Ávidos
5.6. Método de Retroceso (backtracking)
5.7. Método Branch and Bound
6. Algoritmos de Ordenamiento
6.1. Concepto de Ordenamiento
6.2. Ordenamiento por Inserción
6.3. Ordenamiento por Selección
6.4. Ordenamiento de la Burbuja (Bublesort)
6.5. Ordenamiento Rápido (Quicksort)
6.6. Ordenamiento por Montículo (Heapsort)
6.7. Otros Métodos de Ordenamiento
6.7.1. Ordenamiento por Incrementos Decrecientes
6.7.2. Ordenamiento por Mezclas Sucesivas
7. Algoritmos de Búsqueda
7.1. Introducción
7.2. Búsqueda Lineal
7.3. Búsqueda Binaria
7.4. Árboles de Búsqueda
7.5. Búsqueda por Transformación de Claves (Hashing)
7.6. Búsqueda en Textos
7.6.1. Algoritmo de Fuerza Bruta
7.6.2. Algoritmo de Knuth-Morris-Pratt
7.6.3. Algoritmo de Boyer-Moore
8. Teoría de Grafos
8.1. Definiciones Básicas
8.2. Representaciones de Grafos
8.2.1. Matriz y Lista de Adyacencia
8.2.2. Matriz y Lista de Incidencia
8.3. Recorridos de Grafos
8.3.1. Recorridos en Amplitud
8.3.2. Recorridos en Profundidad
8.4. Grafos con Pesos
8.5. Árboles
8.6. Árbol Cobertor Mínimo
8.6.1. Algoritmo de Kruskal
8.6.2. Algoritmo de Prim
8.7. Distancias Mínimas en un Grafo Dirigido
8.7.1. Algoritmo de Dijkstra
8.7.2. Algoritmo de Ford
8.7.3. Algoritmo de Floyd-Warshall
9. Complejidad Computacional
9.1. Introducción
9.2. Algoritmos y Complejidad
9.3. Problemas NP Completos
9.4. Problemas Intratables
9.5. Problemas de Decisión
9.6. Algoritmos No Determinísticos
Bibliografía
En formato pdf. Contiene 130 páginas.

Este libro de VBA Notes for Professionals está compilado a partir de la documentación de Stack Overflow, el contenido está escrito por los usuarios de Stack Overflow.

En formato pdf. Contiene 257 páginas.

La búsqueda en grafos, con multitud de aplicaciones en el mundo real, ha propiciado el diseño de una gran cantidad de algoritmos centrados en el procesamiento de un único objetivo, magnitud representativa del coste. Sin embargo, un tratamiento realista de estos problemas requiere en muchas ocasiones contemplar diferentes objetivos de modo simultáneo. Además, es habitual que estos objetivos sean antagónicos, de tal modo que la optimización de uno de ellos se traduzca en el empeoramiento de uno o varios de los objetivos restantes. Esto hace que el coste óptimo no sea único, sino que generalmente existe un conjunto de soluciones óptimas cuyas componentes de coste están compensadas entre sí.

Esta naturaleza multiobjetivo de los problemas provoca que el rendimiento de los algoritmos empeore de modo considerable, ya que al procesamiento habitual de los nodos generados durante el proceso de búsqueda hay que añadir el tratamiento de vectores de coste (de dimensión igual al número de objetivos considerado) y el manejo de un conjunto de soluciones óptimas (cuyo tamaño en el peor de los casos será exponencial), siendo este tipo de operaciones muy costosas desde el punto de vista de tiempo y memoria.

De las dos principales clases de algoritmos exactos multiobjetivo, la correspondiente a un enfoque best-first ha sido ampliamente estudiada, dando lugar a una gran cantidad de algoritmos que persiguen reducir la complejidad espacial y temporal del proceso de búsqueda. Asimismo existen numerosas y detalladas comparativas de endimiento entre estos algoritmos. Sin embargo la clase de algoritmos depth-first, aún siendo de gran utilidad en la resolución de problemas con grafo de búsqueda en forma de árbol, presentaba un reducido número de propuestas, careciendo además de análisis comparativos entre las mismas.

Esta tesis pretende cubrir dicho hueco, realizando un estudio sistemático de algoritmos exactos multiobjetivo de tipo depth-first.

En formato pdf. Contiene 274 páginas.

Este libro está principalmente dirigido a estudiantes universitarios que se inician en las carreras de Ingeniería. Son los que deben interiorizarse en el manejo de ciertos recursos propios de la disciplina sin orientarse a ningún lenguaje en particular. La finalidad de este enfoque es ampliarles la perspectiva para que en su vida profesional no solo puedan implementar programas en los lenguajes clásicos de programación sino que también sean capaces de manejar las nuevas herramientas de software que, en muchos casos, permiten optimizar su rendimiento mediante el desarrollo de macroinstrucciones especiales. Es así que en la elaboración del libro hemos decidido tratar los conceptos de manera no muy extensa y, en la forma más sencilla posible. No solo para que se constituya en un soporte de los contenidos a desarrollar por los docentes sino para que les permita a los estudiantes reflexionar sobre la forma de llegar a un algoritmo como solución a un problema. A los fines didácticos, representamos los algoritmos en algunos casos con pseudocódigo y en otros, con diagrama de flujo o con ambos tipos de representaciones.

El libro está constituido por nueve capítulos. Se inicia con una introducción a los recursos de la algoritmia desde los conceptos básicos, pasando por la organización de las acciones según la técnica de programación estructurada y la implementación de subalgoritmos. Se incluye también el concepto y uso apropiado de estructuras de datos como arreglos, registros y cadenas, como así también el de archivo de datos y su tratamiento. En un capítulo aparte desarrollamos algunos procesos específicos para el ordenamiento e intercalación de conjuntos de valores y para la búsqueda en los mismos. Presentamos la temática referida a las Estructuras de Selección y a las Estructuras de Iteración en tres capítulos cuyos contenidos se complementan, pues fueron abordados desde distintos enfoques (teórico, práctico y teórico-práctico) a partir de la visión de diferentes autores. El libro culmina con una descripción de la representación interna de la información numérica y de carácter,nociones imprescindibles para la comprensión del funcionamiento interno de una computadora.

En formato pdf. Contiene 206 páginas.

El propósito general de este libro, es el de introducir al lector en la resolución de problemas de programación así como en el diseño de algoritmos.

Índice de Contenidos:
1.- Inducción Matemática
2.- Definición y Características de la Recursión
3.- Recursión con Memoria o Memorización
4.- Divide y Vencerás
5.- Búsqueda Exhaustiva
6.- Técnicas Básicas de Conteo
7.- Funciones
8.- Análisis de Complejidad
9.- Reglas para Medir la Complejidad
10.- Complejidades Logarítmicas
11.- Complejidades en Funciones Recursivas
12.- Ordenamiento
13.- Pilas, Colas y Listas
14.- Árboles Binarios
15.- Montículos
16.- Grafos
17.- Árboles y Ordenamiento
18.- ¿Más rápido que O (N log N)?
19.- Estructura de la Solución y Espacio de Búsqueda
20.- Programación Dinámica en los Espacios de Búsqueda
21. - Programación Dinámica en Cortes
22.- Entendiendo el Problema
23.- Encontrando la solución

En formato pdf. Contiene 315 páginas

Este libro está principalmente dirigido a estudiantes universitarios que se inician en las carreras de Ingeniería. Son los que deben interiorizarse en el manejo de ciertos recursos propios de la disciplina sin orientarse a ningún lenguaje en particular. La finalidad de este enfoque es ampliarles la perspectiva para que en su vida profesional no sólo puedan implementar programas en los lenguajes clásicos de programación sino que también sean capaces de manejar las nuevas herramientas de software que, en muchos casos, permiten optimizar su rendimiento mediante el desarrollo de macroinstrucciones especiales. Es así que en la elaboración del libro hemos decidido tratar los conceptos de manera no muy extensa y, en la forma más sencilla posible. No sólo para que se constituya en un soporte de los contenidos a desarrollar por los docentes sino para que les permita a los estudiantes reflexionar sobre la forma de llegar a un algoritmo como solución a un problema. A los fines didácticos, representamos los algoritmos en algunos casos con pseudocódigo y en otros, con diagrama de flujo o con ambos tipos de representaciones.

El libro está constituido por nueve capítulos. Se inicia con una introducción a los recursos de la algoritmia desde los conceptos básicos, pasando por la organización de las acciones según la técnica de programación estructurada y la implementación de subalgoritmos. Se incluye también el concepto y uso apropiado de estructuras de datos como arreglos, registros y cadenas, como así también el de archivo de datos y su tratamiento. En un capítulo aparte desarrollamos algunos procesos específicos para el ordenamiento e intercalación de conjuntos de valores y para la búsqueda en los mismos. Presentamos la temática referida a las Estructuras de Selección y a las Estructuras de Iteración en tres capítulos cuyos contenidos se complementan, pues fueron abordados desde distintos enfoques (teórico, práctico y teórico-práctico) a partir de la visión de diferentes autores. El libro culmina con una descripción de la representación interna de la información numérica y de carácter,nociones imprescindibles para la comprensión del funcionamiento interno de una computadora.

En formato pdf. Contiene 206 páginas.

El propósito de este libro es proporcionar a los alumnos que recién inician sus estudios en el área de computación una serie de problemas representativos, los cuales están resueltos algorítmicamente con detalle. En el área de programación existen diferentes herramientas que auxilian en la solución de problemas, pero seleccionar una de ellas para comenzar a introducir al estudiante en el área se vuelve un poco complicado, dado que cada una posee ventajas y desventajas; éstas son percibidas por los estudiantes, y si adoptan alguna herramienta con mayor facilidad, presentan cierto rechazo hacia las otras, por considerarlas más complicadas. Por tal motivo, en este libro se presentan tres herramientas para tratar de ayudar a los estudiantes a desarrollar una lógica apropiada para el planteamiento y solución de un problema (pseudocódigo, diagramas de flujo y diagramas Nassi-Schneiderman).

Los problemas que se plantean están enfocados en utilizar las tres estructuras básicas de la programación (secuencias, decisiones y ciclos), de tal forma que el alumno se vaya enrolando paso a paso en la solución de problemas cada vez más complejos, de aquí que el formato de este libro dedique una unidad a cada tipo de estructura, concluyendo finalmente con un capítulo del tratamiento de arreglos, tan útiles en la solución de problemas.

Definitivamente el objetivo de este libro no es establecer un patrón para resolver los problemas, tan sólo es el de proporcionar ayuda a los alumnos para desarrollar una lógica apropiada mediante la utilización de una de las herramientas para la solución de problemas, los cuales, posteriormente, podrán ser implementados en la computadora mediante un lenguaje de programación.

Queremos agradecer a todas aquellas personas que contribuyeron para la realización de este proyecto, especialmente a las autoridades de la Universidad Autónoma de Aguascalientes, por darnos las facilidades para poder realizar este trabajo. A las profesoras Ma. Guadalupe Mendoza y Lorena Pinales Delgado, por apoyar en la revisión de este libro; a Luz Patricia Pinales Delgado, por su colaboración en la realización de esta obra.

Realizado por:
Francisco Javier Pinales Delgado
César Eduardo Velázquez Amador

Contenidos:
Prólogo
UNIDAD I. HERRAMIENTAS DE PROGRAMACIÓN
PARA LA SOLUCIÓN DE PROBLEMA CON COMPUTADORAS
Herramientas
Identificadores
Pseudocódigo
Diagramas de flujo
Diagramas Nassi-Schneiderman N/S
UNIDAD II. SOLUCIÓN DE PROBLEMAS CON ESTRUCTURAS SECUENCIALES
Introducción
Estructuras de control
Estructuras secuenciales
Problemas resueltos
Problemas propuestos
UNIDAD III. SOLUCIÓN DE PROBLEMAS CON ESTRUCTURAS SELECTIVAS
Introducción
Estructuras selectivas
Problemas resueltos
Problemas propuestos
UNIDAD IV. SOLUCIÓN DE PROBLEMAS CON ESTRUCTURAS REPETITIVAS
Introducción
Estructuras repetitivas o de ciclo
Problemas resueltos
Problemas propuestos
UNIDAD V. INTRODUCCIÓN A LOS ARREGLOS UNIDIMENSIONALES Y MULTIDIMENSIONALES (VECTORES Y MATRICES)
Introducción
Arreglos unidimensionales (vectores)
Arreglos bidimensionales (tablas)
Problemas resueltos
Problemas propuestos
APÉNDICE. Solución de problemas propuestos
Soluciones de la unidad dos
Soluciones de la unidad tres
Soluciones de la unidad cuatro
Soluciones de la unidad cinco

En formato pdf. Contiene 172 páginas.

La algoritmia es uno de los pilares de la programación y su relevancia se muestra en el desarrollo de cualquier aplicación, más allá de la mera construcción de programas. Este es un libro introductorio sobre análisis y diseño de algoritmos que pretende exponer al lector las técnicas básicas para su diseño e implementación, así como presentar unas herramientas que le permitan medir su efectividad y eficiencia.

Esta obra nace con la intención de llenar un vacío en la bibliografía existente. En primer lugar ofreciendo un método de diseño general aplicable a cada una de las técnicas, y en segundo lugar proporcionando un enfoque eminentemente práctico a través de una amplia selección de ejemplos y problemas resueltos (más de 100).

El diseño del libro se ha realizado de manera que pueda ser utilizado como base para cualquiera de las asignaturas introductorias de la algoritmia. De ahí su estructura y organización, así como la didáctica con la que se desarrollan los temas. En el texto se estudian las principales técnicas de diseño: Divide y Vencerás, algoritmos ávidos, Programación Dinámica, Vuelta Atrás y Ramificación y Poda. Cada tema comienza con una breve introducción teórica en la que se exponen los fundamentos de la técnica tratada y el tipo de problemas que resuelve. A continuación se presenta el esquema general de funcionamiento de los algoritmos que produce. Finalmente, se desarrolla una colección de problemas que permiten mostrar las distintas formas de aplicación de la técnica estudiada. Conforme se avanza en los problemas se discuten los pormenores de su diseño, los detalles de implementación, y el análisis de su eficiencia.

En definitiva, una obra que puede ser de gran utilidad no sólo a los alumnos de carreras técnicas, sino a todos aquellos profesionales de la informática que deseen profundizar en el apasionante estudio de la algoritmia.

Contenidos:
1.- La complejidad de los algoritmos.
2.- Ordenación.
3.- Divide y vencerás.
4.- Algoritmos ávidos.
5.- Programación dinámica.
6.- Vuelta atrás.
7.- Ramificación y poda.
8.- [Prólogo y bibliografía.]
En formato pdf. Dividido en 8 capítulos

La algoritmia es uno de los pilares de la programación y su relevancia se muestra en el desarrollo de cualquier aplicación, más allá de la mera construcción de programas. Este es un libro introductorio sobre análisis y diseño de algoritmos que pretende exponer al lector las técnicas básicas para su diseño e implementación, así como presentar unas herramientas que le permitan medir su efectividad y eficiencia.

Esta obra nace con la intención de llenar un vacío en la bibliografía existente. En primer lugar ofreciendo un método de diseño general aplicable a cada una de las técnicas, y en segundo lugar proporcionando un enfoque eminentemente práctico a través de una amplia selección de ejemplos y problemas resueltos (más de 100).

El diseño del libro se ha realizado de manera que pueda ser utilizado como base para cualquiera de las asignaturas introductorias de la algoritmia. De ahí su estructura y organización, así como la didáctica con la que se desarrollan los temas. En el texto se estudian las principales técnicas de diseño: Divide y Vencerás, algoritmos ávidos, Programación Dinámica, Vuelta Atrás y Ramificación y Poda. Cada tema comienza con una breve introducción teórica en la que se exponen los fundamentos de la técnica tratada y el tipo de problemas que resuelve. A continuación se presenta el esquema general de funcionamiento de los algoritmos que produce. Finalmente, se desarrolla una colección de problemas que permiten mostrar las distintas formas de aplicación de la técnica estudiada. Conforme se avanza en los problemas se discuten los pormenores de su diseño, los detalles de implementación, y el análisis de su eficiencia.

En definitiva, una obra que puede ser de gran utilidad no sólo a los alumnos de carreras técnicas, sino a todos aquellos profesionales de la informática que deseen profundizar en el apasionante estudio de la algoritmia.

En formato pdf. Contiene 326 páginas.