Free Essay

Optimization Algorithms

In: Computers and Technology

Submitted By maisonet92
Words 4208
Pages 17
Universidad de Puerto Rico en Bayamón
Departamento de Español

Complejidad, Rendimiento y Utilización Algorítmica

Artículo escrito por:
Hector E. Maisonet Guzmán – 841-10-3930

Curso ESCO 4005 Sección LJ1
PhD. José A. Rodríguez Valentín

21 de mayo de 2014

COMPLEJIDAD, RENDIMIENTO Y UTILIZACIÓN ALGORÍTMICA

Donald Knuth indicó: “Un algoritmo debe ser visto para ser creído”. Por lo tanto se define un algoritmo como un conjunto prescrito de instrucciones o reglas bien definidas, ordenadas y finitas, las cuales permiten realizar una actividad mediante una serie de pasos sucesivos que no generen dudas a quien deba realizar dicha actividad. Estas actividades tienen como estado; uno inicial y uno de entrada, siguiendo una serie de pasos para llegar a su estado final y obtener una solución. Los algoritmos son independientes de los lenguajes de programación. En cada problema el algoritmo puede escribirse y luego ejecutarse en un lenguaje de programación diferente. El algoritmo es la infraestructura de cualquier solución, escrita luego en cualquier lenguaje de programación. Muchos autores han señalado a estos conjuntos de instrucciones como soluciones a problemas abstractos o soluciones a problemas de cálculo. Los algoritmos pueden ser expresados de diferentes maneras, como por ejemplo: lenguaje natural, seudocódigo, flujogramas, lenguaje de programación, entre otros. Cabe destacar que la expresión de un algoritmo mediante el uso del lenguaje natural puede contener ambigüedad y ser demasiado extensa dando como resultado una descripción no muy satisfactoria. Por otro lado, el uso de seudocódigo y de flujograma hace la descripción de un algoritmo más entendible y sencillo para el programador. El flujograma es la técnica más antigua utilizada, pero a su vez es una técnica visual de entender el algoritmo. El seudocódigo permite una solución al problema mediante un algoritmo escrito en palabras normales de un idioma utilizando palabras imperativas. (Véase Apéndice 1 para ejemplo de flujograma y Apéndice 2 para ejemplo de seudocódigo). Otra forma de entender el comportamiento de algoritmos es mediante el concepto de sistema formal, y una sistema formal es aquel sistema lógico-deductivo construido por un lenguaje formal, una gramática formal. Las cuales, restringen aquellas expresiones correctamente formadas de dicho lenguaje, las reglas de inferencia y un conjunto de axiomas. La noción de estos sistemas corresponde a la formalización rigurosa y completa del concepto de sistema axiomático. Una vez que los algoritmos son creados se implementan en programas o aplicaciones. No obstante, existen otros medios para implementar estos algoritmos, como lo son: las redes neurales artificiales, circuitos eléctricos, dispositivos eléctricos o mecánicos, por lo cual, no todo los algoritmos son necesariamente para ser implementados mediantes códigos de computadora. Existen también algoritmos que son para implementarse mediante el uso de mano escritura; como lo son: la suma, la resta, y otras aritméticas simples. Además, podemos destacar los algoritmos para grafos como el algoritmo de Euclides y el algoritmo de Hamilton, entre otros. La mayoría de los algoritmos suelen escribirse con una estructura secuencial. Las estructuras secuenciales son aquellas que ejecutan cada instrucción una detrás de las otra. Cabe destacar que estas instrucciones internamente contiene bloques de código compuestos por: selecciones condicionales, ciclos y variables. Las variables en bloque de código pueden estar clasificadas como: simples, contador, acumulador o de trabajo. Las variables simples consisten en asignar un valor constate, puede ser alfanumérico o lógico como por ejemplo (var 20, var 0.5 var TRUE, var “Hello”). Las variables tipo contador consisten en tener un uso como verificación de la cantidad de veces que se realiza un proceso, este tipo de variables se pueden utilizar como control de ciclos o centinelas como por ejemplo (var 0, then: var var + 1). Las variables tipo acumuladoras tienen como función mantener una suma de procesos como por ejemplo (var var + var_2). Las variables clasificadas como de trabajos son aquellas que pueden recibir una operación matemática que implica más de una variable como por ejemplo (result 2(var + var_2) – var_3).
Algoritmos como funciones

La rama de la teoría de la compatibilidad ha comprobado y establecido que un algoritmo se puede concebir como una función que transforma los datos de un problema en los datos de una solución. No obstante, los datos se pueden representar a su vez como secuencias de bits. Cada secuencia de bits representa a un número natural, por ende los algoritmos son en esencia funciones de números naturales que en sí se pueden calcular. Aunque, un algoritmo calcula una función f: N N donde cada número natural es la codificación de un problema o de una solución al mismo. En ocasiones, los algoritmos son sustentables para nunca terminar, por lo que se denomina que se encuentra en un ciclo infinito. Cuando se da esta situación, el algoritmo nunca devuelve ningún resultado, de tal forma se denomina a la función que es indefinida. Por otro lado, se sugiere que los algoritmos son funciones parciales, es señalar, que no necesariamente están definidas por su dominio de definición. Cuando una función puede ser calculada por medios algorítmicos, sin importar la cantidad de memoria que ocupe o el tiempo de ejecución que se tome, se caracteriza dicha función como computable. La mejor forma de ver cómo los algoritmos se comportan como funciones es analizando su comportamiento mediantes aplicaciones. Estas aplicaciones son conocidas como aplicaciones matemáticas, las cuales establecen una correspondencia entre dos conjuntos de elementos de forma que todo elemento del conjunto de partida se asocie con un elemento único del conjunto de llegada. Un ejemplo de esta aplicación es aquel conjunto de partida E en un conjunto de llegada F. La aplicación asocia un elemento x dentro del conjunto E y un elemento y dentro del conjunto F. El elemento se denomina imagen del elemento x, mientras que el elemento x se llama antecedente del elemento y. Dentro de este tipo de aplicaciones existen diferentes categorías como: inyectivas, sobreyectivas o biyectivas. Las aplicaciones invectivas son todas aquellas en las que los elementos del conjunto de llegada F tiene como máximo antecedente en el conjunto de partida E. Una aplicación no es inyectivas si existen al menos dos elementos de E distintos que tienen la misma imagen en F. Las aplicaciones sobreyectivas son aquellas en las cuales los elementos de llegada F tienen al menos un antecedente en el conjunto de partida F. Por último, las aplicaciones biyectivas son la que a su vez son inyectivas y sobreyectivas. Una vez que un algoritmo sea correctamente funcional, 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. Muchas veces se piensa que un algoritmo sencillo no es 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. El uso eficiente de los recursos, éste suele medirse en función de dos parámetros: el espacio y el tiempo. El espacio lo definimos como la cantidad de memoria que utiliza, y el tiempo, se define como lo que espera en ejecutar. Ambos representan los costos que supone encontrar la solución al problema planteado mediante un algoritmo. Las funciones son estructuras que pueden tomar una serie de parámetros, y que al finalizar el proceso contenido en la función vuelve al punto seguido donde fue invocado o llamado. Las funciones usan un identificador de la misma forma que las variables, y además permiten devolver un valor. Normalmente se ejecutan de forma secuencial, mientras la función no acabe su proceso el programa que lo haya invocado espera. (Vea Apéndice 3 para ejemplo implementación de una función en el lenguaje de programación C).
Análisis de Algoritmo

Los estudios matemáticos de las propiedades de los algoritmos informáticos han abarcado un amplio espectro, desde los estudios de complejidad generales hasta los resultados analíticos específicos. Una parte importante de los análisis de algoritmos son las relaciones recurrentes. Las relaciones recurrente son ecuaciones que define una secuencia recursiva, entiéndase cada término de la secuencia es definido como una función de términos anteriores. En otras palabras, una relación recurrente es la forma específica de un proceso basado en su propia definición. No obstante, un algoritmo puede ser expresado como recursivo, lo que conlleva a que la solución de un problema en términos de una llamada a sí mismo.
Para poder codificar un algoritmo recursivo se debe tener ciertas propiedades básicas, generalmente la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteara sobre problemas, de igual naturaleza que el original, pero un tamaño menor que N, de tal forma que irá reduciendo progresivamente la complejidad de problema a resolver, hasta llegar a una solución que sea más o menos trivial.
Cabe destacar que para cada proceso iterativo controlado por ciclos existe una forma recurrente de codificarlo. La clave para construir un subprograma o rutina recurrente son: tener un caso base, para evitar que la recursión no sea infinita. Cada llamada recurrente debe definir sobre un problema de menor complejidad. (Vea Apéndice 4 para ejemplos de recurrencia e iterativa). La recurrencia de primer orden son aquellas que pueden aplicar la técnica de su propia definición hasta dejar constantes y valores iniciales, dejando una versión simple de la función. Por otra parte la iteración, se aplica directamente al siguiente tipo de recurrencia comúnmente encontrado, que se reduce inmediatamente a una suma. (Vea Apéndice 5 para ejemplos de suma). La recurrencia de primer orden no lineal surge en una amplia variedad de situaciones, y no podemos esperar a tener una solución de forma cerrada. Por lo tanto, se suele utilizar la convergencia simple. Este método permite calcular los valores iniciales de una recurrencias con un aspecto complicado, que simplemente convergen a una constante, esto es posible porque cada iteración aumenta el número de dígitos significativos, a disposición de un número constante de dígitos. La recurrencia de alto nivel o alto orden son aquellas donde el lado derecho de la ecuación es una combinación lineal y así sucesivamente, y donde los coeficientes involucrados son constantes.
Algoritmos de Ordenamiento

Un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por una relación de orden, por lo cual el resultado de salida ha de ser una permutación o reordenamiento de la entrada que satisfaga la relación de orden dada. Las relaciones de orden más usadas son el orden numérico y el orden lexicográfico. Los algoritmos de ordenación son numerosos, por ello se debe prestar especial atención en su elección. Para determinar cuál de todos es el mejor, hay que prestar atención en la eficiencia. La eficiencia es el factor que mide la calidad y rendimiento de un algoritmo. En el caso de la operación de ordenación, existen dos criterios que suelen seguir a la hora de decidir qué algoritmo, el primero es el tiempo de menor ejecución en computadora, el segundo es el menor número de instrucciones. Sin embargo, no siempre es fácil efectuar estas medidas ya que pueden no disponerse de instrucciones para medida de tiempo.
El mejor criterio para medir la eficiencia de un algoritmo es aislar una operación específica clave en la ordenación y contar el número de veces que se realiza. Así, en el caso de los algoritmos de ordenación, se utilizará como medida de su eficiencia, el número de comparaciones entre elementos efectuados. El algoritmo de ordenación A será más eficiente que el B, si requiere menor número de comparaciones. Se pueden clasificar los diferentes tipos de algoritmos de ordenamientos como básicos y avanzados. Los algoritmos de ordenamiento básicos son aquellos que son fácil de entender, fácil de implementar y para ciertas cantidades de datos son eficientes y para otras son ineficientes. La mayoría de estos algoritmos de este tipo suelen tener un rendimiento exponencial, en otras palabras va decreciendo su tiempo de ejecución si los datos son grandes; ejemplos de tipo de ordenación son: algoritmos por selección (selection sort) y algoritmos por inserción (insertion sort). (Vea Apéndice 6 para una explicación gráfica). Por otro lado, existen los algoritmos de ordenamiento avanzados los cuales son más eficientes pero, más difícil de entender y un poco más difícil de ser implementado. El rendimiento en los algoritmos de ordenamiento avanzados la mayoría son logarítmicos, quiere indicar que su tiempo de ejecución es la mitad de los exponenciales y no se ve afectado por la cantidad de datos; ejemplos de estos tipos de ordenamiento avanzado: ordenamiento rápido (quick sort), ordenación por urnas (bin sort), ordenación por unificación (merge sort), ordenación por montículo (heap sort), entre otros. (Véase Apéndice 7 para una explicación gráfica ordenamientos avanzados).
Algoritmo de Búsqueda

En ciencias de computadoras o ingeniería de informática el uso de los algoritmos de búsqueda es imprescindible y son una de las operaciones más importantes en el procesamiento de la información ya que continuamente nos vemos en la necesidad de investigar unos datos. Un algoritmo de búsqueda consiste en buscar un elemento en una estructura de datos (listas, vectores, matrices y otros), devolviendo así, un valor lógico (Cierto o Falso) en el caso de que exista o no. Los algoritmos de búsqueda tienen dos objetivos primordiales: determinar si el elemento buscado se encuentra o no en la estructura. En el caso que se encuentre el elemento, se devuelve a la posición en la que se encuentra.
Existen diferentes tipos de búsqueda una más eficiente que otras e incluso una más fácil de implementar. Cabe destacar que la implementación de los diferentes tipos de algoritmo para buscar depende de la cantidad de datos que se maneja. Algunos ejemplos de algoritmos de búsqueda son: búsqueda linear o secuencial (linear search o sequential search), búsqueda binaria (binary search), entre otros. La búsqueda secuencial o linear busca un elemento de una lista utilizando un valor destino llamado índice (key). En este tipo de búsqueda los elementos de una lista o vector se exploran uno detrás del otro. Un buen ejemplo de este tipo de búsqueda es el directorio telefónico de una ciudad. El algoritmo de búsqueda secuencial compara cada elemento de la estructura de datos con el índice deseado. Dado que la estructura de datos no está en un orden prefijado es probable que el elemento se encuentre al inicio, a la mitad o al final.
El algoritmo para búsqueda binaria a comparación de la búsqueda linear es más rápido, debido a que comienza su ejecución a mitad de la estructura de datos. Lo único que exige este tipo de algoritmo es que siempre la estructura de dato debe estar ordenada, de tal modo que proporcione una técnica de indagación mejorada. Un ejemplo para entender este tipo de búsqueda es la exploración de una palabra en un diccionario. Según la elección de palabra, se abre el diccionario cerca del principio, al centro o al final dependiendo de la primera letra de la palabra que se pretende buscar. Puede uno acertar con la página correcta; pero, normalmente, no es así y el lector se mueve a la página anterior o posterior del texto. Por ejemplo, si la palabra comienza con «J» y se está en la «L» se mueve uno hacia atrás. Este proceso continúa hasta que se encuentra la página donde está la palabra o hasta concluir que la palabra no está en la lista. (Véase Apéndice 8 para explicación gráfica).
Implementación de Algoritmos Eficientes

La implementación de un algoritmo eficiente se refiere a aquel que tenga un costo de tiempo y de recursos mínimos. Respecto al uso eficiente de los recursos, éste suele medirse en función de dos parámetros: el espacio, es decir, memoria que se utiliza, y el tiempo, lo que demora en ejecutarse. Ambos representan unos costos que supone encontrar la solución al problema planteado mediante un algoritmo. Dichos parámetros van a servir además para comparar algoritmos entre sí, permitiendo determinar el más adecuado entre varios que solucionan un mismo problema. El tiempo de ejecución de un algoritmo va a depender de diversos factores como son: los datos de entrada que se le suministre, la calidad del código generado por el compilador para crear el programa objeto, la naturaleza y rapidez de las instrucciones de la máquina del procesador concreto que ejecute el programa, y la complejidad intrínseca del algoritmo.
Para poder categorizar los diferentes tipos de algoritmos se realiza unos estudios teóricos, lo normal de este estudio es estimar su complejidad de forma asintótica, para ello se utiliza la notación de O-grande (Big-O) para representar la complejidad de un algoritmo como una función que depende del tamaño de la entrada N. (Véase Apéndice 9 para ejemplos en una tabla de las notaciones). Otra forma de medir el rendimiento algorítmico es mediante la técnica de comparativa (Benchmark). La cual es el resultado de la ejecución de un programa informático o un conjunto de programas en una máquina, con el objetivo de estimar el rendimiento de un elemento concreto y poder comparar los resultados con máquinas similares. La técnica de comparativa se puede utilizar en componentes como en la Unidad de Procesamiento Central (CPU), Memoria de Acceso Aleatorio (RAM), tarjetas gráficas, entre otros. En el caso de los algoritmos de surgir uno nuevo y ser implementado es comparado con sus predecesores para asegurar su eficiencia. Las medidas de uso de recurso de los algoritmos están dado por el tamaño de entrada N. Existen dos tipos de medidas bastante comunes que son: complejidad temporal y complejidad espacial. La complejidad temporal se define como el tiempo que tarda en demorar un algoritmo en finalizar. En el caso de la complejidad espacial está definido por cuanto uso de memoria necesita el código y la cantidad que necita los datos sobre los cuales ejecuta el algoritmo. De esta forma los ordenadores o computadoras tienen un impacto en el consumo de energía ya sea por pila o batería o conectada a una toma de electricidad. Estos consumos pueden ser directo o indirecto; un consumo directo es la energía requerida por el ordenador o computadora. Por otro lado el consumo indirecto de energía es aquella requerida por la iluminación, enfriamiento, procesamiento y otros.
No obstante, existen otros tipos de medidas que podrían ser relevante a la hora de ejecución de un algoritmo como: capacidad de transmisión, espacio externo, tiempo de respuesta. La capacidad de transmisión se entiende como las limitaciones que puede causar el ancho de banda. En el caso de espacio externo, se ve afectado por el espacio requerido en un disco o en otro dispositivo externo; esto podría ser mediante un uso temporal. En otras palabras, que utilice el espacio externo a medida que va ejecutando o podría ser una necesidad de largo plazo, como referencia. Ejemplo de este caso es el acceso a un archivo en una memoria externa. Importante y más aún el tiempo de respuesta es bastante relevante, ya que el algoritmo debería responder en un tiempo rápido para una aplicación cuyo datos deben transferidos a eventos externos.
Conclusión

Al finalizar esta investigación podemos deducir que la eficiencia de un algoritmo depende de la utilización que el usuario le va a asignar. Aunque un algoritmo sea analizado de tal forma que uno sea más eficiente sobre los otros, esto va de la mano con la cantidad de datos que se pretende trabajar. No obstante, un “algoritmo ideal” es aquel que se puede ajustar a la cantidad de datos. El cual tiene como base una correlación entre los diferentes algoritmos ya sea para buscar, ordenar, entre otros, según la necesidad del usuario. Hoy día este tipo de algoritmo es el más implementado en las aplicaciones de las empresas y modelajes matemáticos, aunque sea más complejo internamente, tiene un mejor rendimiento ya que puede ser tanto linear, como constante o logarítmico. Un ejemplo de este “algoritmo ideal” en la implantación de un algoritmo de ordenamiento en el lenguaje de programación JAVA.
Las implementaciones algorítmicas en estos tiempos buscan cumplir con lo expresado por los dos científicos de computación Donald Knuth y Tony Hoare, donde establecen que: “Debemos olvidarnos de las pequeñas eficiencias y suspender de decir que alrededor del 97% la mayoría de las veces es ser eficiente. Esto porque la optimización prematura es la raíz de todos los males”. Un buen programador debe buscar el codificar un algoritmo que sea eficiente el 100% de las veces, cuando este se puede alcanzar aunque implique un poco más de trabajo.

Bibliografía

Aguilar, L. (2003). Fundamentos de programación: algoritmos y estructura de datos y objetos. Madrid: McGraw-Hill. Impreso.
Aguilar, L., & Martínez, I. (2004). Algoritmos y estructuras de datos: una perspectiva en C. Madrid: McGraw-Hill. Impreso.
Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1974). The design and analysis of computer algorithms. Reading, Mass.: Addison-Wesley Pub. Co. Impreso.
Ausiello, G. (1999). Complexity and approximation: combinatorial optimization problems and their approximability properties. New York: Springer. Impreso.
Brassard, G., & Bratley, P. (1998). Fundamentos de algoritmos. Madrid: Prentice Hall. Impreso.
Cormen, T. H. (2001). Introduction to algorithms. Cambridge, Mass.: MIT Press. Impreso.
García, R., & Moreno, A. (1997). Técnicas de diseño de algoritmos. Málaga: Servicio de Publicaciones e Intercambio Científico de la Universidad de Málaga. Impreso.
Goldreich, O. (2008). Computational complexity: a conceptual perspective. Cambridge: Cambridge University Press. Impreso.
Greene, D. H., & Knuth, D. E. (1982). Mathematics for the analysis of algorithms. Boston: Birkäuser. Impreso.
Knuth, D. E. (1968). The art of computer programming. Reading (Mass.): Addison-Wesley. Impreso.
Lage, F. J., & Cataldi, Z. (2008). Fundamentos de algoritmos y programación. Buenos Aires: Nueva librería. Impreso.
Levitin, A. (2012). Introduction to the design & analysis of algorithms. Boston: Pearson. Impreso.
Schrijver, A. (2003). Combinatorial optimization: polyhedra and efficiency. Berlin: Springer. Impreso.
Sedgewick, R., & Flajolet, P. (2013). An introduction to the analysis of algorithms. Upper Saddle River, NJ: Addison-Wesley. Impreso.
Sedgewick, R., & Wayne, K. D. (2011). Algorithms. Upper Saddle River, NJ: Addison-Wesley. Impreso.
Sipser, M. (2006). Introduction to the theory of computation. Boston: Thomson Course Technology. Impreso.

Apéndice 1

Obtener Datos
1000
DISPLAY
“Indique el número de” +
“estudiante: ”
GET
Número Estudiante
DISPLAY
“Indique el nombre del” + estudiante: ”

GET
Nombre Estudiante

DISPLAY
“Indique la cantidad de” + créditos matriculados: ”

GET Cantidad de Créditos

RETURN
Obtener Datos
1000
DISPLAY
“Indique el número de” +
“estudiante: ”
GET
Número Estudiante
DISPLAY
“Indique el nombre del” + estudiante: ”

GET
Nombre Estudiante

DISPLAY
“Indique la cantidad de” + créditos matriculados: ”

GET Cantidad de Créditos

RETURN

Calcular Costo
2000
Costo de Matrícula Cantidad de Créditos * Costo Por Crédito
RETURN
Calcular Costo
2000
Costo de Matrícula Cantidad de Créditos * Costo Por Crédito
RETURN

Mostrar Resulatdos
3000
DISPLAY
“Nombre:” + Nombre Estudiante
DISPLAY
“Número:” + Número Estudiante DISPLAY
“Costo de la matrícula:” + Costo Matrícula
RETURN
Mostrar Resulatdos
3000
DISPLAY
“Nombre:” + Nombre Estudiante
DISPLAY
“Número:” + Número Estudiante DISPLAY
“Costo de la matrícula:” + Costo Matrícula
RETURN

Apéndice 2

Apéndice 3:

Apéndice 4

Apéndice 5

Extraído del texto “Analysis of Algorithmss” de Robert Sedwick
Extraído del texto “Analysis of Algorithmss” de Robert Sedwick

Apéndice 6
Extraído del texto “Algorithms” de Robert Sedwick
Extraído del texto “Algorithms” de Robert Sedwick
Extraído del texto “Algorithms” de Robert Sedwick
Extraído del texto “Algorithms” de Robert Sedwick

Apéndice 7

Extraído de la página personal.kent.edu
Extraído de la página personal.kent.edu
Extraído del foro de la página www.dreamcode.com
Extraído del foro de la página www.dreamcode.com

Extraído de la página de en.wikipedia.org
Extraído de la página de en.wikipedia.org

Extraído de la página de images.zhuxinquan.com

Extraído de la página de images.zhuxinquan.com

Apéndice 8

Extraído de la página www.c-sharpcorner.com
Extraído de la página www.c-sharpcorner.com

Extraído de la página csit.parkland.edu
Extraído de la página csit.parkland.edu

Notación | Nombre | Descripción | O(1) | constante | Determinar si un número es par o impar. Usar una tabla de consulta que asocia constantetamaño. Usar una función hash para obtener un elemento. | O( log n) | logarítmico | Buscar un elemento específico en un vector utilizando un árbol binario de búsqueda o un árbol de búsqueda balanceado, así como todas las operaciones en un Heap binomial. | O(n) | lineal | Buscar un elemento específico en una lista desordenada o en un árbol degenerado (peor caso). | O(n log n) | Log linear o cuasi linear | Ejecutar una transformada rápida de Fourier; heapsort, quicksort (caso peor y promedio), o merge sort | O(n2) | cuadrático | Multiplicar dos números de n dígitos por un algoritmo simple. Bubble sort (caso peor o implementación sencilla), Shell sort, quicksort (caso peor). | O(cn), c > 1 | exponencial | Encontrar la solución exacta al problema del viajante utilizando programación dinámica. Determinar si dos sentencias lógicas son equivalentes utilizando una búsqueda por fuerza bruta |
Apéndice 9

--------------------------------------------
[ 1 ]. Premisa que se considera evidente, se acepta sin demostración y permite deducción de otras fórmulas.
[ 2 ]. Paradigma de aprendizaje y procesamiento automático inspirado en la forma en que funciona el sistema nervioso de los animales.
[ 3 ]. Sistema de número binario donde se usa solo dos dígitos, el 0 y el 1.
[ 4 ]. Variable que puede ser recibida por una función, rutina o subrutina.
[ 5 ]. Elementos textuales (símbolos) que nombran identidades en los lenguajes de programación.
[ 6 ]. Repetición de un proceso hasta conseguir la meta deseada
[ 7 ]. Técnica de solución que está basada en su propia definición.
[ 8 ]. Relación de orden, se utiliza para ordenar productos cartesianos de conjuntos ordenados.…...

Similar Documents

Premium Essay

Optimization 7th Edition Sollution

...convexity and nonlinear optimization; applications of various optimization methods in manufacturing, product design, communications networks, transportation, supply chain, and financial systems. Course Objectives The course is designed to teach the concepts of optimization models and solution methods that include integer variables and nonlinear constraints. Network models, integer, dynamic and nonlinear programming will be introduced to the students. Students will be exposed to applications of various optimization methods in manufacturing, product design, communications networks, transportation, supply chain, and financial systems. Several different types of algorithms will also be presented to solve these problems. The course also aims to teach how to use computer programs such as Matlab and GAMS to solve mathematical models. Learning Outcomes Students are expected to model real life problems using mathematical models including integer variables and nonlinear equations. Students will be able to apply mathematical modeling techniques such as dynamic, integer and nonlinear programming to different types of problems. They will also be able to model and solve transportation and network problems such as shortest path, maximum flow and minimum cost network flow problems. Students are also expected to solve these models with computer programs like MATLAB and GAMS. At the end of the course, students will be able to formulate mathematical optimization models for real-life......

Words: 768 - Pages: 4

Premium Essay

Linear Optimization

...DECISION MODELING DECISION WITH WITH MICROSOFT EXCEL MICROSOFT Linear Optimization Linear Optimization A constrained optimization model takes the form of a constrained performance measure to be optimized over a range of feasible values of the decision variables. The feasible values of the decision variables are determined by a set of inequality constraints. constraints Values of the decision variables must be chosen such that the inequality constraints are all satisfied while either maximizing or minimizing the desired performance variable. These models can contain tens, hundreds, or thousands of decision variables and constraints. Linear Optimization Very efficient search techniques exist to optimize constrained linear models. constrained These models are historically called linear programs linear (LP). In this chapter we will: 1. Develop techniques for formulating LP models 2. Give some recommended rules for expressing LP models in a spreadsheet that facilitates application of Excel’s Solver 3. Use Solver to optimize spreadsheet LP models Formulating LP Models Every linear programming model has two important features: Objective Function Constraints A single performance measure to be maximized or minimized (e.g., maximize profit, minimize cost) Constraints are limitations or requirements on the set of allowable decisions. Constraints may be further classified into physical, economic, or policy limitations......

Words: 4037 - Pages: 17

Free Essay

Introduction to Algorithms

... Introduction to Algorithms Second Edition This page intentionally left blank Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest Clifford Stein Introduction to Algorithms Second Edition The MIT Press Cambridge, Massachusetts London, England Dubuque, IA St. Louis Montr´ al e Madison, WI Toronto McGraw-Hill Book Company Boston Burr Ridge, IL New York San Francisco This book is one of a series of texts written by faculty of the Electrical Engineering and Computer Science Department at the Massachusetts Institute of Technology. It was edited and produced by The MIT Press under a joint production-distribution agreement with the McGraw-Hill Book Company. Ordering Information: North America Text orders should be addressed to the McGraw-Hill Book Company. All other orders should be addressed to The MIT Press. Outside North America All orders should be addressed to The MIT Press or its local distributor. Third printing, 2002 c 2001 by The Massachusetts Institute of Technology First edition 1990 All rights reserved. No part of this book may be reproduced in any form or by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher. This book was printed and bound in the United States of America. Library of Congress Cataloging-in-Publication Data Introduction to algorithms / Thomas H. Cormen . . . [et al.].—2nd ed. p. cm. Includes bibliographical references and...

Words: 426328 - Pages: 1706

Free Essay

Genetic Algorithms

...Genetic Algorithm Approach to Solve the Shortest Path Problem for Road Maps Sachith Abeysundara*, Baladasan Giritharan+, Saluka Kodithuwakku◊ *Department of Statistics and Computer Science, Faculty of Science, University of Peradeniya, Sri Lanka Email: sachith@email.com Telephone: (+94) 81 2374652 + Department of Statistics and Computer Science, Faculty of Science, University of Peradeniya, Sri Lanka Email: bgiri@pdn.ac.lk ◊ Department of Statistics and Computer Science, Faculty of Science, University of Peradeniya, Sri Lanka Email: salukak@pdn.ac.lk Telephone: (+94) 81 2394260 Abstract—This paper presents a new genetic algorithm approach to solve the shortest path problem for road maps. This is based on the analogy of finding the shortest possible distance between two towns or cities in a graph or a map with potential connection, which means that the path distances are always positive. Typically this is represented by a graph with each node representing a city and each edge being a path between two cities and there exist some traditional algorithms that produce solutions for the problem. A new method is found to solve the shortest path problem using GAs. The algorithm has been tested for a road map containing more than 125 cities and the experimental results guarantee to provide acceptably good solutions for the given search space. HE shortest path problem is typical in the world of combinatorial systems. This research will attempt to apply a Genetic algorithm to......

Words: 2513 - Pages: 11

Free Essay

Advanced Algorithms

...Approximation Algorithms Springer Berlin Heidelberg NewYork Barcelona Hong Kong London Milan Paris Singapore Tokyo To my parents Preface Although this may seem a paradox, all exact science is dominated by the idea of approximation. Bertrand Russell (1872–1970) Most natural optimization problems, including those arising in important application areas, are NP-hard. Therefore, under the widely believed conjecture that P = NP, their exact solution is prohibitively time consuming. Charting the landscape of approximability of these problems, via polynomial time algorithms, therefore becomes a compelling subject of scientific inquiry in computer science and mathematics. This book presents the theory of approximation algorithms as it stands today. It is reasonable to expect the picture to change with time. The book is divided into three parts. In Part I we cover a combinatorial algorithms for a number of important problems, using a wide variety of algorithm design techniques. The latter may give Part I a non-cohesive appearance. However, this is to be expected – nature is very rich, and we cannot expect a few tricks to help solve the diverse collection of NP-hard problems. Indeed, in this part, we have purposely refrained from tightly categorizing algorithmic techniques so as not to trivialize matters. Instead, we have attempted to capture, as accurately as possible, the individual character of each problem, and point out connections between problems and algorithms for solving......

Words: 140657 - Pages: 563

Free Essay

Genetic Algorithm

...Classification Using Genetic Algorithm N. Suguna1, and Dr. K. Thanushkodi2 1 Professor in Computer Science and Engg, Akshaya College of Engineering and Technology, Coimbatore, Tamil Nadu, India. 2 Director, Akshaya College of Engineering and Technology, Coimbatore, Tamil Nadu, India.   Abstract k-Nearest Neighbor (KNN) is one of the most popular algorithms for pattern recognition. Many researchers have found that the KNN algorithm accomplishes very good performance in their experiments on different data sets. The traditional KNN text classification algorithm has three limitations: (i) calculation complexity due to the usage of all the training samples for classification, (ii) the performance is solely dependent on the training set, and (iii) there is no weight difference between samples. To overcome these limitations, an improved version of KNN is proposed in this paper. Genetic Algorithm (GA) is combined with KNN to improve its classification performance. Instead of considering all the training samples and taking k-neighbors, the GA is employed to take k-neighbors straightaway and then calculate the distance to classify the test samples. Before classification, initially the reduced feature set is received from a novel method based on Rough set theory hybrid with Bee Colony Optimization (BCO) as we have discussed in our earlier work. The performance is compared with the traditional KNN, CART and SVM classifiers. Keywords: k-Nearest Neighbor, Genetic Algorithm,......

Words: 3528 - Pages: 15

Premium Essay

An Adaptive Differential Evolution Algorithm with Novel Mutation and Crossover Strategies for Global Numerical Optimization

...482 IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 42, NO. 2, APRIL 2012 An Adaptive Differential Evolution Algorithm With Novel Mutation and Crossover Strategies for Global Numerical Optimization Sk. Minhazul Islam, Swagatam Das, Member, IEEE, Saurav Ghosh, Subhrajit Roy, and Ponnuthurai Nagaratnam Suganthan, Senior Member, IEEE Abstract—Differential evolution (DE) is one of the most powerful stochastic real parameter optimizers of current interest. In this paper, we propose a new mutation strategy, a fitnessinduced parent selection scheme for the binomial crossover of DE, and a simple but effective scheme of adapting two of its most important control parameters with an objective of achieving improved performance. The new mutation operator, which we call DE/current-to-gr_best/1, is a variant of the classical DE/current-to-best/1 scheme. It uses the best of a group (whose size is q% of the population size) of randomly selected solutions from current generation to perturb the parent (target) vector, unlike DE/current-to-best/1 that always picks the best vector of the entire population to perturb the target vector. In our modified framework of recombination, a biased parent selection scheme has been incorporated by letting each mutant undergo the usual binomial crossover with one of the p top-ranked individuals from the current population and not with the target vector with the same index as used in all variants of DE. A DE variant obtained...

Words: 11062 - Pages: 45

Free Essay

Algorithms

...Algorithms Assignment 1 Kent Vuong Table of Contents Question 1 3 Machine Code (First Generation or 1GL) 3 Assembler (Second Generation or 2GL) 3 Procedural (Third Generation or 3GL) 3 Non-Procedural (Fourth Generation or 4GL) 4 Object Orientated 4 Describe the purpose and functions of an OS with the following terms 4 Scheduling 4 Managing Concurrency 4 Managing Memory 4 Managing Devices 5 File Systems 5 Describe the purpose of each of the following utility software programs. 5 File Compression 5 Defragmenter 5 Anti-Virus 5 Anti-Malware 5 What is application software, give three examples 5 What are the software licensing requirements for the following types of software 6 Freeware 6 Open Source 6 Shareware 6 Question 1 Machine Code (First Generation or 1GL) Machine Code is the Language that the Computer understands and reads, following the precise instructions, which is sometimes the problem with computers and the relaxed non-procedural human brain. The MIPS architecture provides a specific example for a machine code whose instructions are always 32 bits long. The general type of instruction is given by the op (operation) field, the highest 6 bits. J-type (jump) and I-type (immediate) instructions are fully specified by op. R-type (register) instructions include an additional field function to determine the exact operation. Assembler (Second Generation or 2GL) Assembler is a program which makes object codes by encoding...

Words: 1019 - Pages: 5

Free Essay

Gnetic Algorithms

...Genetic Algorithms Basic Genetic Algorithm – Flow Chart 1. Initial Population 1. Initial Population ON ON | | GENERATE RANDOM POPULATION (POSSIBLE SOLUTIONS) | 2. Fitness Evaluation 2. Fitness Evaluation 3. Selection 3. Selection | | EVALUATE THE FITNESS OF EACH (BASED ON THE FITNESS FUNCTION) | | | CHOOSE PARENT FACTORS (BETTER FITNESS = BETTER CHANCE) | 4. Crossover 4. Crossover 5. Mutation 5. Mutation | | CROSSOVER THE PARENT TRAITS TO FORM NEW CHILDREN. (PROBABILITY) | | | MUTATION PROBABILITY APPLIED (MAINTAINS GENETIC DIVERSITY) | Acceptable? Acceptable? | | IF OPTIMIZATION CONDITIONS ARE NOT MET(REPEAT STEPS 2-5) * OR | Yes Yes End Process End Process | | IF THE MAXIMUM GENERATIONS ARE MET (TERMINATE) * OR | | | IF SATISFACTORY FITNESS LEVEL IS REACHED (END THE PROCESS) | KEY TERMS * INDIVIDUAL Any possible solution to the problem at hand, usually expressed in binary code * POPULATION Group of all individuals * CHROMOSOME Blueprint for an individual usually expressed in binary code. (Ex: 011011) * GENE An individual value in a chromosome, usually expressed as a “1” or “0” * PARENTS An original “individual” solution in the GA process that has passed the fitness function * CHILDREN A new solution to the problem formed through crossover and mutation from the parent solutions * SEARCH SPACE All possible solutions to the......

Words: 261 - Pages: 2

Free Essay

Algorithm

...Design and Analysis of Computer Algorithm Assignment 2 Name: Boyu Zhang UTD-ID: 2021226566 Email:bxz140830@utdallas.edu Contents Problem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Problem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Problem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Problem 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Problem 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Problem 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Problem 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Problem 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11 Problem1 This problem can solution by Dial’s algorithm in the lesson six. We can set up W+2 buckets with the labels of 0, 1, …, W, . Then we carry out the following steps: (a). Initial the buckets with node S be in the bucket 0 and all other nodes be in the bucket . (b). then select the node with the minimum temporary distance label. For the first time, it should be the source node S in the bucket 0. (c). Update the buckets information. Then some node should be moved from the bucket  to the corresponding distance bucket. (d). Remove the selected node from the bucket. Then repeat step 2 and 3 until there is no non-empty bucket.......

Words: 726 - Pages: 3

Free Essay

Optimization Problem

...World Academy of Science, Engineering and Technology Vol:7 2013-06-25 Optimization Using Simulation of the Vehicle Routing Problem International Science Index Vol:7, No:6, 2013 waset.org/Publication/15351 Nayera E. El-Gharably, Khaled S. El-Kilany, and Aziz E. El-Sayed Keywords—Discrete event system simulation, optimization using simulation, vehicle routing problem. points or require a solution to be found quickly. Computational time on the fastest computers for optimization methods has been too long for many practical problems. Cognitive, heuristic, or combination heuristic-optimization solution procedures have been good alternatives [8]. The aim of this work is threefold; to present a new mathematical formulation of the VRP problem that uses fewer decision variables, to show how to model the TSP problem as a discrete event simulation model, and to employ the developed simulation model in finding the optimum/near optimum solution of the problem. This paper is organized as follows: in Section II, the basic concepts of VRP and the solution techniques found in literature will be briefly discussed. In Section III, proposed problem formulations will be presented followed by the simulation model development and optimization using simulation in sections IV and V. Finally, in section VI, the conclusions drawn from this work are presented. I. INTRODUCTION II. LITERATURE REVIEW HE vehicle routing problem (VRP) is one of the most intensively studied problems in operations......

Words: 4604 - Pages: 19

Premium Essay

Optimization of Heat Exchanger Network

...com/locate/apthermeng Optimization of heat exchanger network Mofid Gorji-Bandpy, Hossein Yahyazadeh-Jelodar, Mohammadtaghi Khalili* Noshirvani University of Technology, P.O. Box 484, Babol, Iran a r t i c l e i n f o Article history: Received 6 September 2010 Accepted 26 October 2010 Available online 2 November 2010 Keywords: Heat exchanger network (HEN) Optimization Genetic algorithm Pinch Analysis Method Mathematical Optimization Method Sequential Quadratic Programming (SQP) a b s t r a c t In this paper, a new method is presented for optimization of heat exchanger networks making use of genetic algorithm and Sequential Quadratic Programming. The optimization problem is solved in the following two levels: 1- Structure of the optimized network is distinguished through genetic algorithm, and 2- The optimized thermal load of exchangers is determined through Sequential Quadratic Programming. Genetic algorithm uses these values for the determination of the fitness. For assuring the authenticity of the newly presented method, two standard heat exchanger networks are solved numerically. For representing the efficiency and applicability of this method for the industrial issues, an actual industrial optimization problem i.e. Aromatic Unit of Bandar Imam Petrochemistry in Iran is verified. The results indicate that the proposed multistage optimization algorithm of heat exchanger networks is better in all cases than those obtained using traditional optimization methods such......

Words: 4334 - Pages: 18

Free Essay

Particle Swarm Optimization

...Telecommunication Engineering Jadavpur University, Kolkata, India * Center of Excellence for Quantifiable Quality of Service, Norwegian University of Science and Technology, Trondheim, Norway ajith.abraham@ieee.org Abstract This paper describes a method for improving the final accuracy and the convergence speed of Particle Swarm Optimization (PSO) by adapting its inertia factor in the velocity updating equation and also by adding a new coefficient to the position updating equation. These modifications do not impose any serious requirements on the basic algorithm in terms of the number of Function Evaluations (FEs). The new algorithm has been shown to be statistically significantly better than four recent variants of PSO on an eight-function test-suite for the following performance matrices: Quality of the final solution, time to find out the solution, frequency of hitting the optima, and scalability. 1. Introduction The concept of particle swarms, although initially introduced for simulating human social behavior, has become very popular these days as an efficient means of intelligent search and optimization. The Particle Swarm Optimization (PSO) [1, 2], does not require any gradient information of the function to be optimized, uses only primitive mathematical operators and is conceptually very simple. PSO emulates the swarming behavior of insects, animals herding, birds flocking and fish schooling, where these swarms forage for food in a......

Words: 4201 - Pages: 17

Free Essay

Algorithm

...1. Illustrate the operation of Radix_sort on the following list of English words: cow, dog, seq, rug, row, mob, box tab, bar ear, tar, dig, big, tea, now, fox. ANSWER: It is a sorting algorithm that is used to sort numbers. We sort numbers from least significant digit to most significant digit. In the following array of words, three is the maximum number of digits a word has, hence the number of passes will be three. In pass 1, sort the words alphabetically using first letter from the right. For eg, tea has “a” as the last letter, hence it comes first, similarly mob which has “b” as the last letter comes second. In this way the remaining words are sorted. In pass 2, sort the words alphabetically using second letter from the right. For eg, tab has “a” as its middle letter which comes first, then comes bar and so on. In pass 3, sort the words alphabetically using third letter from the right. For eg, bar has “b” as its first letter from left and since no word starts with “a”, bar will appear first. Similarly, big, box, cow and so on. UNSORTED ARRAY | PASS 1 | PASS 2 | PASS 3(SORTED ARRAY) | cow | tea | tab | bar | dog | mob | bar | big | seq | tab | ear | box | rug | rug | tar | cow | row | dog | tea | dig | mob | dig | seq | dog | box | big | dig | ear | tab | seq | big | fox | bar | bar | mob | mob | ear | ear | dog | now | tar | tar | cow | row | dig | cow | row | rug | ...

Words: 1470 - Pages: 6

Premium Essay

Sub Optimization

...Sub Optimization Definition: “The result of different departments each attempting to reach a solution that is optimum for that department” (Stevenson, 2015). Unfortunately, the sub-optimization process does not always adhere to the principle “the whole is more important than the sum of its parts”. Sub optimization occurs when different departments each attempt to reach a solution that is optimal for that department, but that may not be optimum for the organization as a whole. This type of policy can actually do more harm than good. When one department is delivering faster than another department can handle this could cause what is known as a “bottleneck” in the process, which may result in lost profits and customers. “This is a typical effect of sub-optimization. If you only optimize one step in your value creation process it can deliver things faster than the rest of the organization can deal with. Either that part runs dry on input or the output of that part floods subsequent process steps. Make sure that no one department produces more than the department with the least capacity (the bottleneck) can handle” (Marschall, 2011). In the management book “The Goal, Eliyahu Goldratt gives the example of a decision to make machining centers in a factory more efficient by increasing the amount of metal taken off with each pass of the cutting tool. However, Increasing the amount of metal taken off on each pass made the parts brittle, which necessitated heat-treating. The...

Words: 400 - Pages: 2