Download - U2.Algoritmos Computacion 1
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
1
1
Universidad Abierta y a Distancia de México
Licenciatura en Matemáticas
Computación I
6° Cuatrimestre
Unidad 2. Algoritmos
Clave:
050920621/060920621
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
2
2
Índice
Presentación de la unidad ...................................................................................... 3
Propósitos ............................................................................................................... 3
Competencia general .............................................................................................. 3
2.1. Fundamentos .................................................................................................... 3
2.1.1. Conceptos Básicos ....................................................................................... 4
2.1.2. Características .............................................................................................. 8
2.1.3 Complejidad ................................................................................................. 9
2.1.4. NP-Completo ............................................................................................. 19
Actividad 1. Representaciones de Algoritmos .................................................... 23
2.2. Representación de Algoritmos ...................................................................... 24
2.2.1. Pseudocódigo ............................................................................................. 24
2.2.2. Diagrama de Flujo ...................................................................................... 26
Actividad 2. Parámetros para comparación de algoritmos ............................... 28
2.3. Tipos de Algoritmos ....................................................................................... 29
2.3.1. Algoritmo de Búsqueda .............................................................................. 31
2.3.2. Algoritmo de Ordenamiento ........................................................................ 35
2.3.3. Algoritmos Glotones ................................................................................... 39
2.4. Programación ................................................................................................. 44
2.4.1. Programación de Algoritmos en C .............................................................. 44
2.4.2. Programación de Algoritmos en Java ......................................................... 52
Actividad 3. Desarrollo de Algoritmos Típicos ................................................... 61
Autoevaluación ..................................................................................................... 62
Evidencia de Aprendizaje. Programación de algoritmos típicos en C y Java .. 63
Cierre de la Unidad ................................................................................................ 63
Para saber más ...................................................................................................... 64
Fuentes de consulta .............................................................................................. 64
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
3
3
Presentación de la unidad
En esta unidad tendrás la oportunidad de aprender los fundamentos de los algoritmos. Además de los
conceptos básicos y sus características, te introducirás a la comparación de algoritmos considerando sus
tiempos de ejecución y otros elementos de complejidad.
Conocerás los problemas NP-Completos para los cuales nadie ha sido capaz de encontrar un algoritmo
eficiente que se ejecute en una computadora convencional.
Estudiarás los detalles de dos representaciones comunes para los algoritmos: pseudocódigo y diagramas
de flujo.
Finalmente estudiarás algoritmos prácticos de búsqueda y ordenamiento, así como unos más avanzados
llamados “glotones.” Te mostraremos el código en lenguaje C y en Java de estos algoritmos, para que los
pruebes y experimentes con ellos.
Propósitos
Al finalizar esta unidad serás capaz de:
Identificar las representaciones de algoritmos que utilizan pseudocódigo y diagramas de flujo.
Determinar la complejidad de los algoritmos para seleccionar los más apropiados para la solución
que se está desarrollando.
Utilizar algoritmos para resolver problemas matemáticos.
Programar algoritmos que resuelven problemas matemáticos utilizando los lenguajes de
programación C y Java.
Competencia general
Utilizar procesos informáticos para crear algoritmos y representarlos por medio de pseudocódigo y
diagramas de flujo.
2.1. Fundamentos
Informalmente un algoritmo es un procedimiento computacional bien definido que toma algún valor, o
conjunto de valores, cómo entrada y produce algún valor, o conjunto de valores, cómo salida.
Podemos considerar también a un algoritmo como una herramienta para resolver un problema
computacional bien especificado.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
4
4
Por ejemplo, podemos querer ordenar de manera creciente una secuencia de números. Este problema se
presenta frecuentemente en la práctica y también es útil para introducir técnicas estándares de diseño y
herramientas de análisis.
Definamos formalmente el problema del ordenamiento de la manera siguiente:
Entrada: Una secuencia de n números ⟨ ⟩
Salida: Una permutación (reordenamiento) ⟨ ⟩ de la secuencia de entrada tal que
.
Por ejemplo, dada la secuencia de entrada ⟨ ⟩, un algoritmo de ordenamiento devuelve
como salida la secuencia ⟨ ⟩. Una secuencia de entrada como la planteada se denomina
una instancia del problema de ordenamiento. En general, una instancia de un problema consiste de la
entrada necesaria para calcular una solución del problema.
Muchos programas utilizan el ordenamiento en alguno de sus pasos, así que esta operación es
fundamental para la Informática. Como resultado, se ha desarrollado una buena cantidad de algoritmos
de ordenamiento.
El algoritmo que es mejor para una determinada aplicación depende –entre otros factores, del número de
elementos que van a ser ordenados, de cuánto ordenamiento ya tienen, de las posibles restricciones de los
valores de los elementos, de la arquitectura de la computadora, y de la clase de dispositivos de
almacenamiento que van a ser utilizados: memoria principal, discos, o aún cintas magnéticas
Existen muchos tipos de algoritmos que resuelven problemas en casi todas las áreas de la actividad
humana.
Se dice que un algoritmo es correcto si, para cada instancia de entrada, entrega la salida correcta.
Decimos que un algoritmo correcto resuelve el problema computacional dado. Un algoritmo incorrecto
puede entregar una respuesta incorrecta o puede continuar sin detenerse para algunas instancias de
entrada.
Un algoritmo puede ser especificado en español, como un programa de computadora, o inclusive como un
diseño de hardware. El requerimiento es que la especificación debe proporcionar una descripción
precisa del procedimiento computacional a ser realizado.
2.1.1. Conceptos Básicos
La palabra algoritmo proviene del nombre de al-Khwārizmī, matemático, astrónomo y geógrafo persa
nativo de una ciudad que fue parte de lo que actualmente es Uzbekistán.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
5
5
Antes de que hubiera computadoras, había algoritmos. Pero ahora que hay computadoras, hay aún más
algoritmos, pues son parte del núcleo de la computación.
¿Qué Clase de Problemas son Resueltos Utilizando Algoritmos?
El problema del ordenamiento que mencionamos anteriormente no es, por supuesto, el único problema
computacional para el que los algoritmos han sido desarrollados. Las aplicaciones prácticas de los
algoritmos se encuentran actualmente en casi cualquier área:
El proyecto del genoma humano continúa siendo desarrollado. La identificación de los 100,000
genes en el ADN humano, la determinación de las secuencias de los 3,000 millones de pares de
base química que forman el ADN, el almacenamiento de la información y el desarrollo de
herramientas para el análisis de datos requiere algoritmos sofisticados. Muchos métodos para
resolver estos problemas biológicos obtienen ideas de los algoritmos más simples, permitiendo a los
científicos realizar sus tareas al mismo tiempo que utilizan eficientemente los recursos disponibles.
Internet permite a las personas de todo el mundo acceder y obtener rápidamente grandes
cantidades de información. Con la ayuda de buenos algoritmos, los sitios son capaces de
administrar y manipular un gran volumen de datos. Otro tipo de algoritmos se utilizan para encontrar
las mejores rutas por las que deben viajar los datos.
El comercio electrónico permite la compra-venta e intercambio de bienes y servicios, y depende
de la privacidad de información personal tal como números de tarjetas de crédito, contraseñas y
estados de cuenta bancarios. Las tecnologías incluyen la criptografía y las firmas digitales, las
cuales se basan en algoritmos numéricos y en la teoría de números.
Las compañías de manufactura y de otras actividades comerciales necesitan a menudo asignar
recursos escasos de la forma más conveniente. Una compañía petrolera puede desear saber dónde
instalar sus pozos para maximizar sus utilidades.
Un político quiere determinar dónde comprar anuncios de campaña para maximizar sus
oportunidades de ganar una elección.
Una línea aérea desea asignar tripulaciones a los vuelos de la forma menos costosa posible,
asegurándose de que cada vuelo sea cubierto y de que las regulaciones gubernamentales sean
cumplidas.
A partir de un mapa de caminos, en el que la distancia entre cada par de intersecciones adyacentes
está indicada, puede quererse determinar la ruta más corta entre dos intersecciones.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
6
6
Considerando un diseño mecánico dado en términos de una biblioteca de partes, donde cada
elemento puede incluir instancias de otras partes. Puede necesitarse listar los componentes de
modo que cada uno aparezca antes de cualquier otro elemento que la utiliza.
La lista puede continuar indefinidamente, pero exhibe dos características que son comunes a muchos
problemas algorítmicos:
1. Tienen muchos candidatos de solución, la mayoría de los cuales no resuelve el problema
específico. Encontrar la respuesta correcta, o la “mejor”, puede llegar a ser muy desafiante.
2. Son o pueden ser aplicaciones prácticas.
¿Puede ser definida rigurosamente la noción de Algoritmo?
Elegimos contestar la pregunta de la siguiente forma: sí y no.
¿Por qué no?
De acuerdo a fuentes consultadas, la noción de Algoritmo no puede ser definida rigurosamente de manera
general, al menos por el momento. La razón es que la noción se está expandiendo.
Muchas clases de algoritmos han sido introducidas. Adicionalmente a los algoritmos secuenciales clásicos
en uso desde la antigüedad, tenemos ahora algoritmos paralelos, interactivos, distribuidos, en tiempo real,
analógicos, híbridos, cuánticos, etc. Nuevas clases continúan creándose, así que una definición formal
completa no ha podido ser cristalizada.
¿Por qué la respuesta es sí?
Sin embargo, el problema de la definición rigurosa de los algoritmos no carece de esperanza. Algunos
estratos han madurado lo suficiente para soportar definiciones ortodoxas..
Esto aplica a los algoritmos clásicos (o secuenciales clásicos), esencialmente los únicos algoritmos en uso
desde la antigüedad hasta la década de 1950. “Los algoritmos se ejecutan en pasos de complejidad
limitada”, escribió Andrei Kolmogorov en 1953. Esta es una buena definición informal de los algoritmos
secuenciales.
Una definición axiomática de los algoritmos secuenciales puede ser encontrada en Gurevich, Y. Sequential
Abstract State Machines Capture Sequential Algorithms, ACM Transactions on Computational Logic 1:1
(2000) 77-111. Esta definición fue utilizada para derivar la tesis Church-Turing y hace suponer que
Church y Turing tenían en mente solamente algoritmos secuenciales.
La definición axiomática fue extendida más tarde a los algoritmos paralelos síncronos y a los algoritmos
secuenciales interactivos.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
7
7
¿Qué definición de Algoritmo podemos utilizar?
Después de haber comentado informalmente acerca de los algoritmos, explorado los campos de aplicación
y mostrado el umbral para introducirnos a las definiciones formales, expondremos los detalles de algunos
algoritmos prácticos que pueden ser ejecutados en una computadora.
Este será un buen punto de partida para que más adelante puedas desarrollar algoritmos propios que
resuelvan problemas específicos y estar en posibilidad para definir un algoritm, desde un punto de vista
práctico, como:
“Un algoritmo es un método para resolver problemas, adecuado para ser implementado en una
computadora.”
Por su parte, Schneider and Gersting, lo definen como:
“Un algoritmo es una colección bien ordenada de operaciones no-ambiguas y computables
efectivamente que cuando son ejecutadas producen un resultado y se detienen en una cantidad
finita de tiempo.”
Ambas definiciones describen adecuadamente la esencia de un algoritmo, pero la segunda también expone
detalles que nos serán útiles más adelante para derivar características de los algoritmos.
Presentaremos algunos algoritmos “fundamentales” importantes e interesantes p Te recomendamos que
los implementes los pruebes y e experimentes con variantes, para su aplicación en problemas reales.
Problemas Difíciles
Los algoritmos que discutiremos suelen ser eficientes (considerando que son básicos). Nuestra medida
usual de eficiencia es la velocidad, esto es, el tiempo que necesita un algoritmo para producir su resultado.
Existen algunos problemas para los cuales no se conoce una solución eficiente. Más adelante estudiarás
un subconjunto interesante de este tipo de problemas: los NP-completos.
¿Por qué son interesantes los problemas NP-completos?
En primer lugar, aunque no ha sido encontrado un algoritmo eficiente para un problema NP-
completo, no se ha probado que ese algoritmo no pueda existir. En conclusión: no se sabe si
existen o no algoritmos eficientes para problemas NP-completos.
En segundo lugar, el conjunto de problemas NP-completos tiene la notable propiedad de que si un
algoritmo eficiente existe para cualquiera de ellos, entonces hay algoritmos eficientes para todos
ellos (¿No te parece tentador tratar de encontrar un algoritmo eficiente para este conjunto?)
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
8
8
En tercer lugar, varios problemas NP-completos son similares, aunque no idénticos, a problemas
para los cuales conocemos algoritmos eficientes. Los científicos de la informática están intrigados
al observar cómo un pequeño cambio en la declaración del problema puede ocasionar una gran
alteración en la eficiencia del algoritmo mejor conocido.
Es necesario saber acerca de los problemas NP-completos porque algunos de ellos aparecen a menudo en
las aplicaciones reales. Si en el futuro eres requerido para producir un algoritmo eficiente para un problema
y logras demostrar que el problema es NP-completo, podrás dedicar tu tiempo a desarrollar un algoritmo
que produzca una buena, aunque no la más eficiente, solución.
2.1.2. Características
Para que un algoritmo sea ejecutable en una computadora, debe poseer ciertas características. La
definición de algoritmo de Schneider and Gersting que incluimos en la sección anterior, exhibe cinco
características importantes de los algoritmos:
1. Están bien ordenados.
2. Contienen operaciones no-ambiguas.
3. Contienen operaciones computables efectivamente.
4. Producen un resultado.
5. Se detienen en una cantidad finita de tiempo.
Discutimos a continuación detalles de cada una de estas características.
1. Los algoritmos están bien ordenados
Un algoritmo es una colección de operaciones o instrucciones y debe conocerse el orden correcto en el que
deben procesarse. Si el orden no es claro, puede ejecutarse la instrucción equivocada o ser incierta qué
instrucción debe ejecutarse a continuación. Esta característica es especialmente importante para las
computadoras. Una computadora solamente puede ejecutar un algoritmo si conoce el orden exacto de los
pasos a seguir.
2. Los algoritmos contienen operaciones no-ambiguas
La instrucción “ordena esta lista de números” es adecuada para una persona, pero ambigua para una
computadora, así que debe ser simplificada. Cada operación en un algoritmo debe ser lo suficientemente
clara de manera que no necesite ser simplificada.
Los algoritmos que van a ser ejecutados en una computadora deben escribirse con operaciones básicas
conocidas como operaciones primitivas. Cuando un algoritmo es escrito usando operaciones primitivas, el
algoritmo es no-ambiguo y la computadora puede ejecutarlo.
3. Los algoritmos contienen operaciones computables efectivamente
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
9
9
Cada operación en un algoritmo debe poder ejecutarse. . Existen operaciones que las computadoras no
pueden hacer, como por ejemplo dividir entre cero o encontrar la raíz cuadrada de un número negativo.
Este tipo de operaciones no son computables efectivamente, así que no pueden ser usadas para escribir
algoritmos.
4. Los algoritmos producen un resultado
En la definición simple de algoritmo, establecimos que se trata de un método para resolver problemas. A
menos que un algoritmo produzca un resultado, nunca se podrá estar seguro que la solución es correcta.
Si alguna vez alimentaste con un comando a una computadora y nada ocurrió, seguramente pensaste que
la computadora estaba funcionando mal: tu comando no produjo ningún resultado o cambio visible. . Lo
mismo se aplica a los algoritmos, solamente aquellos que producen resultados pueden ser verificados
como correctos o erróneos.
5. Los algoritmos se detienen en una cantidad finita de tiempo
Los algoritmos deben estar compuestos de un número finito de operaciones y deben completar su
ejecución en una cantidad determinada de tiempo. Vamos a suponer que se desea escribir un algoritmo
que muestre en pantalla todos los enteros mayores que 1.
Los pasos se escribirían como sigue:
1. Muestra el número 2
2. Muestra el número 3
3. Muestra el número 4
El algoritmo luce muy claro, pero tiene dos problemas:
En primer lugar, contiene un número infinito de pasos porque existe un número infinito de enteros
mayores que 1.
En segundo lugar, el algoritmo continuará ejecutándose para siempre tratando de alcanzar un número
infinito.
Estos problemas violan la consideración de que un algoritmo debe detenerse en una cantidad finita de
tiempo y deben alcanzar alguna operación que los obligue a detenerse.
2.1.3 Complejidad
Después de obtener un algoritmo que funciona correctamente y de haberlo trasladado a un programa, es
necesario definir criterios para medir su rendimiento, los cuáles consideran la sencillez del algoritmo y el
uso eficiente que hace de los recursos.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
10
10
La sencillez en el diseño de un algoritmo facilita su verificación, el estudio de su eficiencia y su
mantenimiento. Es recomendable, mantener el algoritmo tan simple como sea posible y cuidar que
el código que se genere sea legible.
El uso eficiente de los recursos, suele medirse en función de dos parámetros:
o Espacio (memoria o almacenamiento que se utiliza)
o Tiempo (lo que tarda la ejecución)
Los parámetros representan el costo de encontrar la solución al problema planteado utilizando un algoritmo
y son útiles también para comparar diferentes algoritmos que solucionan el mismo problema. La eficiencia
temporal se considera más comúnmente y es la que estudiaremos a continuación.
El tiempo de ejecución de un algoritmo depende de varios factores.
Los datos de entrada
La calidad del código generado por el compilador
La naturaleza y rapidez de las instrucciones del procesador específico
La complejidad intrínseca del algoritmo
Existen dos formas de estudiar los tiempos de ejecución:
1. La que proporciona una medida teórica y consiste en obtener una función que limite (superior o
inferior) el tiempo de ejecución del algoritmo para determinados valores de entrada.
2. La que ofrece una medida real y consiste en medir el tiempo de ejecución del algoritmo para
determinados valores de entrada en una computadora específica.
La primera medida ofrece una estimación del comportamiento del algoritmo de forma independiente de la
computadora sin necesidad de ser ejecutado.
La segunda representa las medidas reales del comportamiento del algoritmo y se consideran funciones
temporales de los datos de entrada.
El tamaño de la entrada es el número de componentes sobre los que va a actuar el algoritmo. Ejemplos
de este tamaño serían la dimensión de un vector a ordenar o el tamaño de las matrices a multiplicar.
Denotaremos con T(n) el tiempo de ejecución de un algoritmo para una entrada de tamaño n.
Teóricamente T(n )indicaría el número de instrucciones ejecutadas por una computadora ideal. Deben
establecerse, entonces, medidas simples y abstractas independientes de la computadora. Para esto debe
acotarse de alguna manera la diferencia que se puede producir entre distintas implementaciones de un
mismo algoritmo.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
11
11
Puede tenerse el mismo código ejecutado por dos máquinas de velocidad diferente o dos códigos
implementando el mismo método. La diferencia da lugar al siguiente principio:
Principio de Invarianza
Dado un algoritmo y dos de sus implementaciones I1 e I2, que consumen T1(n) y T2(n) segundos
respectivamente, el Principio de Invarianza afirma que existen una constante real c > 0 y un número
natural n0 tales que para todo .
Es decir, el tiempo de ejecución de dos implementaciones distintas de un mismo algoritmo, no va a diferir
más que en una constante multiplicativa.
De acuerdo a lo anterior podemos afirmar que un algoritmo tarda un tiempo del orden de T(n) si existen
una constante real c > 0 y una implementación I del algoritmo que tarda menos que cT(n), para todo
tamaño n de la entrada.
Deben tenerse en cuenta tanto la constante multiplicativa como el n0 para los que se verifican las
condiciones porque si, en principio, un algoritmo de orden cuadrático es mejor que uno de orden cúbico, al
tener, por ejemplo, dos algoritmos con tiempos de ejecución de 106n2 y 5n3 respectivamente, el primero
sólo será mejor que el segundo para tamaños de entrada superiores a 200,000.
El comportamiento de un algoritmo puede cambiar notablemente para diferentes entradas. Si se utiliza, por
ejemplo, un algoritmo de ordenamiento, su comportamiento va a cambiar dependiendo de lo ordenado que
se encuentren los datos de entrada. Para muchos programas el tiempo de ejecución es una función de la
entrada específica y no sólo de su tamaño.
Casos de Estudio
Para un mismo algoritmo, suelen estudiarse tres casos:
Mejor caso. Corresponde a la secuencia del algoritmo que realiza menos instrucciones.
Peor caso. Corresponde a la secuencia del algoritmo que realiza más instrucciones.
Caso promedio. Corresponde a la secuencia del algoritmo que realiza un número de instrucciones
igual a la esperanza matemática de la variable aleatoria definida por todas las posibles secuencias
del algoritmo para un tamaño de entrada, con las probabilidades de que éstas ocurran para esa
entrada.
La medición del tiempo se hace en función del número de operaciones elementales que realiza el
algoritmo.
Consideramos operaciones elementales (OPEL) aquellas que realiza la computadora en un tiempo
acotado por una constante.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
12
12
Las operaciones elementales incluyen: operaciones aritméticas básicas, las asignaciones a variables de
tipo predefinido por el compilador, los saltos, las llamadas a funciones y procedimientos (así como sus
retornos), el acceso a estructuras básicas indexadas (como vectores y matrices), y las comparaciones
lógicas. Cada una de ellas cuenta como 1 OPEL.
Tomando en cuenta lo anterior, el tiempo de ejecución de un algoritmo es una función que mide el
número de operaciones elementales que realiza el algoritmo para un determinado tamaño de entrada.
Podemos analizar un ejemplo típico: la búsqueda de un número c dentro de un arreglo de tamaño n.
Suponemos que el algoritmo ha sido codificado con un lenguaje de programación y lo expresaremos en
pseudocódigo para facilitar el análisis.
Empezamos con las declaraciones:
Constante n = un número entero (int) // núm máximo de elementos de un vector;
Type vector = Array[1..n] de int
Y ahora, la implementación del algoritmo:
Programa Busca (VAR a: vector; c: int)
int j
BEGIN
j = 1 // 1
WHILE (a[j] < c) AND (j < n) do // 2
j = j + 1 // 3
END WHILE
IF a[j] = c then // 4
return j // 5
ELSE return 0 // 6
ENDIF
END Busca
Para determinar el tiempo de ejecución, se calcula primero el número de operaciones elementales (OPEL)
que se efectúan:
Línea 1: se ejecuta una asignación (1 OPEL).
Línea 2: se prueba la condición del ciclo y ocurren dos comparaciones, un acceso alvector y un AND (4
OPEL).
Línea 3: ocurre un incremento y una asignación (2 OPEL).
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
13
13
Línea 4: existe una condición y ocurre un acceso al vector (2 OPEL).
Línea 5: contiene un return (1 OPEL) si la condición se cumple.
Línea 6: contiene un return (1 OPEL), cuando la condición del IF es falsa.
No se toma en cuenta la copia del vector al área de ejecución del programa porque se está pasando por
referencia y no por valor (es lo que indica la palabra VAR). Si se decidiera pasar el vector por valor
(copiando su contenido al área de ejecución) tendría que tomarse en cuenta el costo de hacer esto, o sea
agregar n OPEL.
Los casos serían:
Mejor caso donde el algoritmo encuentra el número c inmediatamente en la primera posición del vector,
con lo que el programa termina. Se ejecuta entonces la línea 1 y la primera mitad de la condición lo que
representa 2 OPEL (el comportamiento normal del código implica que las expresiones se evalúan de
izquierda a derecha y se detiene la evaluación de la expresión lógica en el momento en que se conoce su
valor (aunque falten términos por evaluar). Como la condición es falsa porque el contenido de la celda del
vector es igual al número buscado, no se entra al cuerpo del WHILE. Después de esto, el programa ejecuta
las líneas 4 (2 OPEL) y 5 (1 OPEL). Por lo tanto,
T(n) = 1+2+2+1 = 6.
Peor caso. Donde el programa recorre todo el vector y no encuentra el número buscado. El programa
termina al agotarse las posiciones del vector. Se efectúa la línea 1 (1 OPEL), luego el ciclo WHILE se repite
n-1 veces hasta que se cumple la segunda condición. Después se efectúa la condición de la línea 4 y la
función acaba al ejecutarse la línea 6. Cada iteración del ciclo incluye las líneas 2 y 3, además de una
ejecución adicional de la línea 2 que provoca la salida del ciclo.
((∑
) )
Caso promedio. Cualquier otro caso que no sea el mejor ni el peor. El ciclo WHILE se ejecutará un
número de veces entre 0 y n-1. Suponemos que cada número tiene la misma probabilidad de suceder.
Como existen n posibilidades (puede ser que el número buscado no esté en el vector) cada una tendrá una
probabilidad asociada de 1/n. De acuerdo a esto, el número de veces que se efectuará el ciclo es de
∑
Se tiene entonces que
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
14
14
(( ∑
) )
No es necesario conocer el propósito del algoritmo para analizar su tiempo de ejecución y determinar sus
tres casos. Basta con estudiar su código. No debe caerse en el error de determinar los casos basándose en
el propósito del algoritmo; el código implementado es el que los determina.
Análisis de Algoritmos
Después de la revisión de este caso típico sencillo, pueden discutirse elementos que dan paso al análisis
de algoritmos más complejos.
Para la mayoría de los problemas suelen estar disponibles diversos algoritmos, y aunque ha sido
estudiado el rendimiento de muchos de ellos, su comparación continúa siendo desafiante. Por esta razón,
se han desarrollado guías que ayudan a hacer las comparaciones.
Como lo mencionamos antes, los problemas que resolvemos normalmente tienen un tamaño natural
considerando la cantidad de datos a procesar y llamamos n a esta cantidad. Deseamos describir los
recursos utilizados como una función de n y estamos interesados en el caso promedio: la cantidad de
tiempo que un programa necesite para procesar datos "típicos" de entrada y en el peor caso: la cantidad
de tiempo que requiere un programa para ejecutar la peor configuración de entrada posible.
Algunos algoritmos han sido bien estudiados, así que existen fórmulas matemáticas precisas para ambos
casos. Las fórmulas se desarrollaron estudiando el programa para encontrar el tiempo de ejecución en
términos de cantidades matemáticas fundamentales y luego realizando el análisis de las cantidades
involucradas.
En el otro extremo se encuentran los algoritmos cuyas propiedades de rendimiento no han podido ser
determinadas adecuadamente. Quizás su análisis arrojó preguntas matemáticas que no han sido
contestadas, o tal vez las implementaciones son demasiado complejas como para que sea factible un
análisis detallado, o quizás su tipo de datos de entrada no ha podido ser caracterizado adecuadamente. La
mayoría de los algoritmos se encuentra entre ambos extremos.
Aunque existen factores importantes para el análisis, èstos quedan fuera del control de quien analiza:
Los programas se traducen al código de máquina de una determinada computadora y puede ser
difícil establecer el tiempo de ejecución de las instrucciones, especialmente en entornos de recursos
compartidos.
Muchos programas son muy sensibles a sus datos de entrada y su rendimiento puede variar mucho
dependiendo de los datos.
Otros programas no están bien entendidos, así que resultados matemáticos específicos pueden no
estar disponibles.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
15
15
A menudo los programas no pueden ser comparados porque corren bajo circunstancias diferentes.
A pesar de las dificultades, es posible predecir el tiempo de ejecución de un programa, o si un programa
será más eficiente que otro en ciertas situaciones. El analista descubrirá la información del rendimiento de
los algoritmos y el programador aplicará esa información en su selección de algoritmos para aplicaciones
particulares.
Con los siguientes pasos es posible realizar una primera estimación del tiempo de ejecución de un
algoritmo:
Primer paso
Caracterizar los datos que se usarán como entrada y decidir el tipo de análisis que es apropiado. Se
pretende determinar la distribución de los posibles tiempos de ejecución de un algoritmo , de acuerdo a la
distribución de la probabilidad de ocurrencia de las posibles entradas.
Como no es posible lograr esto para cualquier algoritmo no trivial, más bien se intenta probar que el tiempo
de ejecución es siempre menor que alguna "cota superior" sin depender de la entrada, así como derivar el
tiempo de ejecución promedio para una entrada "aleatoria".
Segundo paso
Identificar operaciones abstractas en las que se basa el algoritmo con el fin de separar el análisis de la
implementación.
Por ejemplo, se separa el estudio del número de comparaciones que realiza un algoritmo de ordenamiento,
de la determinación del tiempo que requiere una computadora para ejecutar una instrucción de
comparación.
Ambos elementos son necesarios para determinar el tiempo real de ejecución de un programa.
Tercer paso
Proceder al análisis matemático teniendo como meta encontrar valores del caso promedio y del peor
caso para cada una de las cantidades fundamentales. No es difícil encontrar una cota superior para el
tiempo de ejecución de un programa, el desafío es encontrar la mejor cota superior, una que sería
alcanzada si se diera el peor caso.
El caso promedio requiere normalmente un análisis matemático más sofisticado.Después de que se siguen
estos pasos, el tiempo asociado con cada cantidad fundamental puede ser determinado y obtener
expresiones para el tiempo total de ejecución.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
16
16
El rendimiento de un algoritmo puede llegar a ser analizado de forma precisa y estar limitado solamente
por la incertidumbre en el rendimiento de la computadora o por la dificultad de determinar las propiedades
matemáticas de algunas de las cantidades abstractas.
Rara vez vale la pena efectuar un análisis detallado completo, así que se suele estimar para suprimir los
detalles.
El análisis de un algoritmo es un proceso cíclico: analizar, estimar y refinar el análisis hasta que se
obtenga una respuesta del nivel de detalle deseado.
El parámetro n que hemos estado manejando y que representa el número de elementos de datos a ser
procesados, afecta significativamente el tiempo de ejecución.
Este parámetro puede ser el grado de un polinomio, el tamaño de un archivo que va a ser ordenado o
explorado, el número de nodos de un grafo, etc.
La mayoría de los algoritmos fundamentales tiene un tiempo de ejecución proporcional a una de las
siguientes funciones:
1 La mayoría de las instrucciones de gran parte de los programas se ejecuta sólo
una vez, o máximo unas cuantas veces. Si todas las instrucciones de un programa
tienen esta propiedad, se dice que su tiempo de ejecución es constante.
Log n Cuando el tiempo de ejecución de un programa es logarítmico, el programa se
hace un poco más lento a medida que crece n. Este tiempo de ejecución ocurre
comúnmente en programas que resuelven un problema grande transformándolo en
uno más pequeño, reduciendo el tamaño por una fracción constante.
n Cuando el tiempo de ejecución de un programa es lineal, que es generalmente el
caso en el que una pequeña cantidad de procesamiento se efectúa en cada
elemento de entrada. Esta es la situación óptima para un algoritmo que debe
procesar n entradas (o producir n salidas).
n log n Este tiempo de ejecución se presenta para algoritmos que resuelven un problema
dividiéndolo en sub-problemas, resolviéndolos independientemente, y luego
combinando las soluciones.
n2 Cuando el tiempo de ejecución de un algoritmo es cuadrático, es práctico utilizarlo
solamente en problemas relativamente pequeños. Los tiempos de ejecución
cuadráticos se presentan típicamente en algoritmos que procesan todos los pares
de elementos de datos (quizás en un ciclo doblemente anidado).
n3 Un algoritmo que procesa tripletas de elementos de datos (quizás en un ciclo
triplemente anidado) tiene un tiempo de ejecución cúbico y es práctico para ser
utilizado solamente en problemas pequeños.
2n Pocos algoritmos con un tiempo de ejecución exponencial son apropiados para
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
17
17
usos prácticos, aunque tales algoritmos surgen naturalmente como soluciones de
“fuerza bruta” para los problemas.
El tiempo de ejecución de un programa en particular puede considerarse como algún coeficiente constante
multiplicado por uno de los términos de la tabla anterior (“término principal”) más algunos términos más
pequeños. Los valores de estos elementos dependen de los resultados del análisis y de los detalles de
implementación.
De forma aproximada, el coeficiente constante depende del número de instrucciones del ciclo interno (es
prudente limitar este número). Para n grande domina el efecto del término principal; para n pequeño otros
términos contribuyen y las comparaciones son más difíciles.
Complejidad
Un enfoque para estudiar el rendimiento de los algoritmos es estudiar el rendimiento del peor caso,
ignorando factores constantes, con el fin de determinar la dependencia funcional del tiempo de ejecución
del número de entradas o alguna otra variable.
Primero hay que hacer la noción de “proporcional a” matemáticamente precisa, separando al mismo tiempo
el análisis de un algoritmo de cualquier implementación particular. La idea es ignorar los factores
constantes en el análisis: en la mayoría de casos, si queremos saber si el tiempo de ejecución de un
algoritmo es proporcional a n o proporcional a log n, no importa en qué computadora va a ocurrir la
ejecución o la manera en que el ciclo interno será implementado.
El artefacto matemático para hacer precisa esta noción se denomina notación-O, y se define como sigue:
Notación: Una función se dice que es si existen constantes y tales que es menor
que para todo .
Informalmente, esto encapsula la noción de “es proporcional a” y libera al analista de considerar los detalles
de características de máquina particulares. Además, la declaración de que el tiempo de ejecución de un
algoritmo es es independiente de la entrada del algoritmo.
Estamos interesados en estudiar el algoritmo, no la entrada o la implementación, así que la notación-O es
útil para establecer límites superiores de ejecución que son independientes tanto de las entradas como de
los detalles de implementación.
Esta notación ha sido muy útil para que los analistas clasifiquen los algoritmos por rendimiento y para guiar
a los diseñadores de algoritmos en la búsqueda de los “mejores” algoritmos para problemas importantes.
La meta del estudio de la complejidad de un algoritmo es demostrar que su tiempo de ejecución es
para alguna función f, y que no puede haber un algoritmo con un tiempo de ejecución de O(g(n)) para
cualquier función más “pequeña” (una función con ).
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
18
18
Intentamos proporcionar tanto un límite superior como uno inferior para el tiempo de ejecución del peor
caso. Probar los límites superiores es a menudo una cuestión de contar y analizar frecuencias de
instrucciones; probar los límites inferiores implica la construcción cuidadosa de un modelo y la
determinación de cuáles operaciones fundamentales deben ser efectuadas para resolver un problema.
Cuando los estudios muestran que el límite superior de un algoritmo coincide con su límite inferior,
podemos inferir que es infructuoso tratar de diseñar un algoritmo que sea fundamentalmente más rápido,
así que podemos concentrarnos en la implementación. Este punto de vista ha demostrado ser muy útil para
los diseñadores de algoritmos en años recientes.
Sin embargo, hay que ser extremadamente cuidadosos al interpretar los resultados expresados utilizando
la notación-O, por al menos cuatro razones:
1. Es un límite superior y la cantidad en cuestión puede ser mucho menor.
2. La entrada que produce el peor caso es improbable que ocurra en la práctica.
3. La constante c0 es desconocida y no necesita ser pequeña.
4. La constante n0 es desconocida y no necesita ser pequeña.
La declaración de que el tiempo de ejecución de un algoritmo es O(f(n)) no implica que éste alguna vez
requiera ese tiempo: solamente quiere decir que el analista ha sido capaz de probar que nunca va a
requerir más tiempo. El tiempo real de ejecución puede ser menor.
Aún si la entrada para el peor caso es conocida, puede ser que en la práctica consuma menor tiempo de
ejecución. Muchos algoritmos útiles tienen un mal peor caso. Por ejemplo, quizás el algoritmo de
ordenamiento más ampliamente usado, Quicksort, tiene un tiempo de ejecución de pero es posible
arreglar las cosas para que el tiempo de entradas encontradas en la práctica sea proporcional a
Las constantes c0 y n0 implícitas en la notación-O esconden a menudo detalles de implementación que son
importantes en la práctica. Obviamente, decir que un algoritmo tiene un tiempo de ejecución no
significa nada si n es menor que n0, y c0 , pues puede estar escondiendo una gran cantidad de sobrecarga
(“overhead”) diseñada para evitar un mal peor caso. Preferiríamos un algoritmo que utilizara n2
nanosegundos por sobre uno que utilizara log n siglos, pero no podríamos hacer esta selección con la base
de la notación-O.
Análisis del Caso Promedio
Otro enfoque para estudiar el rendimiento de los algoritmos consiste en examinar el caso promedio. En la
situación más simple, podemos caracterizar las entradas del algoritmo, por ejemplo, un algoritmo de
ordenamiento puede operar en un arreglo de n enteros aleatorios, o un algoritmo geométrico puede
procesar un conjunto de n enteros aleatorios, o un algoritmo geométrico puede procesar un conjunto de n
puntos aleatorios en el plano con coordenadas entre 0 y 1.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
19
19
Calculamos el número de veces promedio que cada instrucción es ejecutada y el tiempo de ejecución
promedio del programa multiplicando cada frecuencia de instrucción por el tiempo requerido por la
instrucción y sumando todo. Hay; sin embargo, al menos tres dificultades con este enfoque.
1. En algunas computadoras puede ser difícil determinar la cantidad de tiempo requerida para cada
instrucción. Esto está sujeto a cambio y mucho del análisis detallado para una computadora puede
no ser relevante para otra. Este es el tipo de problema que los estudios de complejidad están
diseñados para evitar.
2. El análisis del caso promedio a menudo es un difícil desafío matemático que requiere argumentos
intrincados y detallados. Por su naturaleza, las matemáticas involucradas en probar límites
superiores son normalmente menos complejas, porque no necesitan ser tan precisas. El
rendimiento del caso promedio de muchos algoritmos es desconocido.
3. En el análisis del caso promedio, el modelo de entrada puede que no caracterice las entradas
encontradas en la práctica o que no exista un modelo de entrada natural. ¿Cómo podríamos
caracterizar la entrada a un programa que procesa texto en lenguaje español? Por otro lado, pocos
argumentarían contra el uso de modelos de entrada tales como un “archivo ordenado
aleatoriamente” para un algoritmo de ordenamiento, o un “conjunto de puntos aleatorios” para un
algoritmo geométrico. Para estos modelos es posible derivar resultados matemáticos que pueden
predecir el rendimiento de programas en aplicaciones reales.
2.1.4. NP-Completo
Los algoritmos que estudiaremos más adelante se utilizan para resolver problemas prácticos, así que
consumen una razonable cantidad de recursos; para varios de estos retos se tienen diferentes algoritmos
eficientes para escoger. Desafortunadamente, otros problemas prácticos no tienen soluciones eficientes,
incluso, hay casos en los que no podemos decir si existe o no una solución idónea .
Esta situación causa frustración tanto a programadores y diseñadores de algoritmos, quienes no pueden
encontrar algún algoritmo eficiente para un amplio rango de problemas prácticos y teóricos. Estos expertos
han sido incapaces de encontrar la raíz de esos problemas.
A veces la línea entre problemas “fáciles” y “difíciles” es muy fina. Por ejemplo, existe un algoritmo eficiente
para el siguiente problema: “Encontrar la trayectoria más corta del vértice x al vértice y en un grafo
ponderado dado.”
Pero si se pregunta por la trayectoria más larga (sin ciclos) de x a y , tenemos un problema para el que
nadie conoce una solución mejor que la de revisar todas las trayectorias posibles. La línea fina resalta aún
más cuando consideramos problemas similares que solamente piden respuestas “sí o no”:
Problema fácil: ¿Existe una trayectoria de x a y con ?
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
20
20
Problema difícil (?): ¿Existe una trayectoria de x a y con ?
Algoritmos existentes entregan una solución para el primer problema en tiempo lineal, pero todos los
algoritmos conocidos para el segundo problema pueden requerir un tiempo exponencial.
Por lo general, es útil pensar que un algoritmo de tiempo exponencial para una entrada de tamaño n
requiere un tiempo proporcional a 2n (por lo menos).
Algoritmos Determinísticos y No- Determinísticos de Tiempo Polinomial
La gran diferencia de rendimiento entre los algoritmos “eficientes” y los algoritmos “exponenciales” de
fuerza bruta que revisan cada posibilidad permite estudiar la interfaz entre ellos con un modelo simple.
En este modelo, la eficiencia de un algoritmo es una función del número de bits utilizados para codificar la
entrada, con algún esquema de codificación. Nos interesa identificar algoritmos que garanticen ejecutarse
en un tiempo proporcional para algún polinomio de acuerdo al número de bits de entrada (“tiempo
polinomial”).
Cualquier problema que puede ser resuelto por un algoritmo de este tipo se dice que pertenece a:
P: El conjunto de todos los problemas que pueden ser resueltos por
algoritmos determinísticos en tiempo polinomial.
Por determinístico queremos decir que en cualquier momento, sin importar lo que el algoritmo esté
elaborando, existe solamente una cosa que puede hacer a continuación.
Esta noción considera la forma en que los programas se ejecutan en computadoras reales. Los algoritmos
de ordenamiento pertenecen a P porque (por ejemplo) el ordenamiento por inserción se ejecuta en un
tiempo proporcional a n2.
Asimismo, el tiempo tomado por un algoritmo depende de la computadora utilizada pues usar una
computadora diferente afecta el tiempo de ejecución por solamente un factor polinomial (suponiendo
límites razonables).
Puedes notar que estamos usando descripciones de naturaleza informal para exponer las ideas centrales
de la teoría, no estamos desarrollando definiciones rigurosas o teoremas.
Una manera “no razonable” de extender la potencia de una computadora es dotarla con la capacidad del
“no-determinismo”: asegurar que cuando un algoritmo se enfrenta con una selección de varias opciones,
tiene la facultad de “adivinar” la correcta.
Para los propósitos de esta discusión, podemos pensar en un algoritmo no-determinístico que “conjetura” la
solución a un problema y luego verifica que la solución es correcta.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
21
21
Tenemos entonces que:
NP: El conjunto de todos los problemas que pueden ser resueltos por
algoritmos no-determinísticos en tiempo polinomial.
Obviamente, cualquier problema que pertenezca a P también pertenece a NP. Parece que debería haber
otros problemas pertenecientes a NP: para demostrar que un problema pertenece a NP, necesitamos
encontrar un algoritmo de tiempo polinomial para probar que una solución dada (la conjeturada) es válida.
Por ejemplo, la versión “sí o no” del problema de la trayectoria más larga pertenece a NP. Otro ejemplo de
un problema que pertenece a NP es el problema de satisfabilidad. Dada una fórmula lógica de la forma
Donde las representan variables booleanas (verdadero o falso), “+” representa or, “*” representa and, y
representa not, el problema de satisfabilidad es determinar si existe o no una asignación de valores a las
variables que hace que la fórmula sea verdadera (que la “satisfaga”).
El no-determinismo es una operación que no puede ser considerada con seriedad ¿Por qué tomar en
cuenta esta herramienta imaginaria que hace que los problemas difíciles parezcan triviales? Porque ¡nadie
ha sido capaz de demostrar que ayuda en algún problema en particular!
No ha sido posible encontrar un problema que pueda demostrarse que pertenece a NP pero que no
pertenece a P (o aún probar que alguno existe): no sabemos si P = NP o no.
Esta es una situación frustrante porque muchos problemas prácticos importantes pertenecen a NP (podrían
ser resueltos eficientemente en una máquina no-determinística) pero puede que pertenezcan o no, a P (no
conocemos algoritmos eficientes para ellos en una máquina determinística).
Si pudiéramos probar que un problema no pertenece a P, se puede abandonar la búsqueda de una
solución eficiente para él. A falta de tal prueba, existe la posibilidad de que algún algoritmo eficiente no ha
sido descubierto. Incluso podría existir un algoritmo eficiente para cada problema de NP, lo cual implicaría
que muchos algoritmos eficientes han permanecido sin ser descubiertos.
Virtualmente nadie cree que P = NP, y un esfuerzo considerable ha sido realizado para probar lo contrario,
pero esto permanece aún bajo investigación en la informática.
NP-Completos
Veremos una lista de problemas que pertenecen a NP, pero que pueden o no pertenecer a P. Estos
problemas son fáciles de resolver en una máquina no-determinística pero, nadie ha sido capaz de
encontrar un algoritmo eficiente para una máquina convencional (o probar que existe) para cualquiera de
ellos.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
22
22
Estos problemas tienen una propiedad adicional que aporta evidencia convincente de que : si
cualquiera de los problemas puede ser resuelto en un tiempo polinomial en una máquina determinística,
entonces todos los problemas en NP pueden ser resueltos (esto es, P = NP).
La falla del esfuerzo de los investigadores para encontrar algoritmos eficientes puede ser vista como una
falla colectiva para demostrar que P = NP.
Estos problemas son NP-completos. Gran número de problemas prácticos tienen esta característica.
La herramienta primaria utilizada para probar que los problemas son NP-completos emplea la idea de
reductibilidad polinomial. Cualquier algoritmo para resolver un nuevo problema en NP puede ser usado
para resolver algún problema NP-completo conocido a través del proceso siguiente:
1. Transformar cualquier instancia del problema NP-completo conocido a una instancia del nuevo
problema.
2. Resolver el problema utilizando el algoritmo dado.
3. Transformar la solución de vuelta a una solución del problema NP-completo.
Por “polinomialmente reducible”, queremos decir que las transformaciones pueden ser hechas en tiempo
polinomial: así la existencia de un algoritmo de tiempo polinomial para el nuevo problema implicaría la
existencia de un algoritmo de tiempo polinomial para el problema NP-completo, y esto implicaría (por
definición) la existencia de algoritmos de tiempo polinomial para todos los problemas de NP.
La reducción puede aplicarse a problemas como:
El vendedor viajero: Dado un conjunto de ciudades y distancias entre todos los pares, encontrar una ruta
de distancia menor que M, que visite todas las ciudades.
Ciclo de Hamilton: Dado un grafo, encontrar un ciclo simple que incluya todos los vértices.
Supón que sabemos que el problema del ciclo de Hamilton es NP-completo y deseamos determinar si el
dilema del vendedor viajero es también NP-completo. Cualquier algoritmo para resolver éste puede ser
usado para solucionar el del ciclo de Hamilton, a través de la siguiente reducción: dada una instancia del
problema del ciclo de Hamilton (un grafo) se construye una instancia del problema del vendedor viajero (un
conjunto de ciudades, con distancias entre todos los pares) como sigue: para las ciudades del vendedor
viajero se usa el conjunto de vértices del grafo; para las que hay entre cada par de ciudades usamos 1 si
hay una arista entre los vértices correspondientes del grafo, y 2 si no hay arista.
Luego hay que hacer que el algoritmo para el problema del vendedor viajero encuentre una ruta de
distancia menor que o igual a n, el número de vértices del grafo. Esa ruta debe corresponder precisamente
a un ciclo de Hamilton.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
23
23
Un algoritmo eficiente para el problema del vendedor viajero también sería idóneo para el ciclo de Hamilton
que se reduce al problema del vendedor viajero, así que lo NP-completo del problema del ciclo de
Hamilton implica lo NP-completo del problema del vendedor viajero.
Algunos problemas NP-completos.
Se sabe que miles de problemas son NP-completos. La lista empieza con las dificultades del vendedor
viajero y del ciclo de Hamilton e incluye los siguientes:
Partición: Dado un conjunto de enteros, ¿puede ser dividido en dos conjuntos cuya suma sea igual?
Programación lineal entera: Dado un programa lineal, ¿existe una solución con enteros?
Programación multiprocesador: Dado un tiempo límite y un conjunto de tareas de longitud variable a ser
ejecutadas en dos procesadores idénticos, ¿Pueden las tareas ser desarrolladas de manera que se
cumpla el tiempo límite?
Cobertura de vértices: Dado un grafo y un entero n, ¿Existe un conjunto de menos de n vértices que
toquen todas las aristas?
Actividad 1. Representaciones de Algoritmos
A través de esta actividad podrás identificar la utilidad y relevancia de las representaciones para los
algoritmos: una de texto y la otra gráfica.
De acuerdo a lo descrito en el tema anterior.
1. Ingresa al Foro de discusión que lleva por nombre “Representaciones de Algoritmos”.
2. Participa activamente en el Foro de discusión, contestando la pregunta:
¿Cuál representación es la más conveniente para los algoritmos: el pseudocódigo o los diagramas
de flujo?
Recuerda que debes redactar tu respuesta con claridad, precisión y respeto.
3. Comenta la respuesta de dos de tus compañeros argumentando tu punto de vista.
4. Consulta la Rúbrica de participación del foro que se encuentra en la sección Material de apoyo
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
24
24
2.2. Representación de Algoritmos
Para representar un algoritmo se debe utilizar algún método que permita independizar su desarrollo del
lenguaje de programación que se pretenda usar y que permita, al mismo tiempo, describir claramente los
pasos que van a resolver el problema.
Dos métodos simples para representar algoritmos han sido utilizados durante varias décadas: uno que usa
texto (pseudocódigo), y otro que utiliza gráficas (diagrama de flujo).
2.2.1. Pseudocódigo
El pseudocódigo es un lenguaje de especificación de algoritmos que utiliza palabras similares al inglés o
al español (el inglés se suele usar en informática por ser más universal). Esto quiere decir que se pueden
desarrollar los algoritmos de una manera más cercana a un lenguaje de programación como C o Java, pero
sin alejarse de las palabras que se utilizan comúnmente; esto lo hace simple, conciso y entendible.
No existe una sintaxis estándar para el pseudocódigo, pero para desarrollar un algoritmo utilizando este
método se acostumbra seguir una serie de convenciones:
Nombrar al pseudocódigo.
Agregar números a las líneas del pseudocódigo (a todas o a las más relevantes).
Usar sangrías después de una estructura como for, while, if, etc. Esto ayuda a referir que las líneas
siguientes son parte de la estructura.
Terminar cada estructura con un end-nombre de estructura.
Utilizar la flecha “←” o el signo “=” para asignarle un valor a una variable, por ejemplo j←2, lo que
significa que se le va a asignar el valor de 2 a j, (j vale 2).
Para definir el límite de la estructura for se emplea la expresión length[a] (duración[a] en español)
lo cual indica que “a” es el número de veces que se repite la estructura for. Esta expresión puede
usarse para cualquier estructura cíclica.
Para representar algún elemento “i” de un arreglo “A” se utilizan los corchetes [ ], es decir, el
elemento A[i].
Para hacer un comentario se puede usar la doble diagonal: // Comentario.
Para separar dos o más condiciones, se puede utilizar and.
Para terminar cada paso se puede finalizar con un punto (.)
Siempre hay que indicar cuáles son las entradas y salidas del programa.
Se muestra a continuación el desarrollo del algoritmo para la función f(x) = ln x usando el Teorema de
Taylor y pseudocódigo.
Paso 1. Nombre
Nombre del pseudocódigo: Teorema de Taylor.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
25
25
Paso 2. Entradas y Salidas
Entradas: Valor de x, valor de tolerancia, valor de iteraciones i.
Salidas: Grado del polinomio n o mensaje de error.
Paso 3. Algoritmo
1. Inicio.
2. Inicialización de variables
n ← 1
y ← x - 1
suma ← 0
potencia ← y
término ← y
signo ← -1. // para ejecutar alternancia de signos en la serie
3. while n ≤ I // estructura while, for, etc., necesaria
signo ← -signo // esto es para alternar signos
suma ← suma + signo * término // acumulador de términos
potencia ← potencia * y
término ← potencia / (n + 1). // calcula el término siguiente
if |término| < tolerancia entonces // verifica la precisión (if, case, etc.)
Salida (n)
Fin // el procedimiento tuvo éxito
else-if
n ← n + 1.
end-while.
4. if n = i entonces
Salida („ERROR‟) // el procedimiento no tuvo éxito
fin
end-if.
5. Fin.
Ventajas del Pseudocódigo
Presenta la solución del problema de una forma clara.
Ocupa menos espacio que el diagrama de flujo.
Permite representar de forma sencilla operaciones repetitivas complejas.
Es más fácil pasar del pseudocódigo a un lenguaje de programación.
Cuando se hace correctamente la indentación, es fácil determinar los niveles en la estructura del
programa.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
26
26
2.2.2. Diagrama de Flujo
Los diagramas de flujo son una herramienta desarrollada en la industria de la computación, para mostrar
los pasos de un proceso. Consiste en una representación gráfica construida con cajas, diamantes y otras
formas, conectadas por medio de flechas. Cada forma representa un paso en el proceso y las flechas
muestran el orden en el que ocurren. Un diagrama de flujo combina símbolos y líneas para mostrar
gráficamente la operación de un algoritmo.
En informática, existen diferentes símbolos para los diagramas de flujo, existen, inclusive,estándares
nacionales e internacionales para los diagramas de flujo.
Puedes localizar en internet los documentos de algunos de los primeros estándares que fueron creados
para estos diagramas, por ejemplo:
ECMA-4, 2nd Edition. Standard for Flow Charts. European Computer Manufacturers Association.
September 1966.
GC20-8152-1. Flowcharting Techniques. International Business Machines Corporation. 1969.
Se muestran a continuación algunos de los símbolos más comunes:
Estos símbolos suelen utilizarse en los casos siguientes:
Terminador: Inicio, fin, detener, espera, terminar una subrutina del proceso.
Proceso: Se refiere a cualquier función de procesamiento, cambio de valor, localización, etc., de la
información usada.
Decisión: Elemento en el que se selecciona el camino que debe seguir el flujo. Las opciones
pueden ser tan simples como un SI o NO resultante de la evaluación de una expresión.
Conector: Punto de continuación del diagrama.
Entrada/Salida: Elemento que representa las variables de entrada y salida.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
27
27
Entrada manual: Para que el usuario introduzca los valores de las variables de entrada.
Pantalla: Elemento que ayuda a indicar los datos que van a ser mostrados.
Flecha de flujo: Se utiliza para indicar el sentido en el que ocurre el flujo entre procesos y otros
elementos
Consideraciones para el Uso de los Símbolos
No debe haber flechas cruzadas (usar un arco para pasar una línea sobre otra cuando sea
necesario con el fin de evitar confusiones).
No se deben dejar los conectores vacíos, siempre deben de contener un indicador.
Las flechas tienen que tocar al elemento al que apuntan en ambos lados.
Las estructuras de decisión deben tener indicado el valor del camino que vana tomar, por ejemplo SI
y NO.
Presentamos a continuación un ejemplo de diagrama de flujo. Este diagrama fue desarrollado para
representar el algoritmo que calcula las raíces de un polinomio de segundo grado (x2 + 2x + 5 = 0) por
medio de la ecuación general:
√
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
28
28
Los diagramas de flujo fueron muy populares en sus inicios para representar algoritmos y aunque aún se
utilizan con el mismo fin, su popularidad ha disminuido. Métodos como el pseudocódigo son más
adecuados para los nuevos lenguajes de programación.
Por otro lado, los diagramas de flujo se convirtieron en instrumentos comunes en el mundo empresarial, al
igual que en otros campos. En lo que respecta a la Informática, los nuevos diagramas UML pueden
considerarse como diagramas de flujo evolucionados.
Ventajas de los Diagramas de Flujo
Favorecen la comprensión del algoritmo al representarlo en una gráfica.
Permiten identificar problemas y oportunidades de mejora en los algoritmos.
Son fáciles de trazar.
Actividad 2. Parámetros para comparación de algoritmos
Al finalizar esta actividad compararas las técnicas de compresión de archivos, mediante el estudio de uno
de los parámetros que intervienen en la evaluación de los algoritmos al utilizar sus recursos. Además de
identificar algunos aspectos del otro parámetro: el uso del espacio.
1. Escribe un reporte que llevará por nombre “Parámetros para comparación de algoritmos”
2. Investiga sobre los siguientes temas:
a. Técnicas de compresión de archivos
i. Run-Length Encoding
ii. Variable-Length Encoding
iii. Construcción del Código Huffman
3. El documento deberá contener los siguientes elementos: introducción, desarrollo (información
generada por ti), explicación del funcionamiento de la compresión, descripción de las técnicas de
compresión listadas, dos links para conocer más algunos de los temas, conclusiones, las fuentes
de información que consultaste para el desarrollo de la misma.
1. Guarda tu documento con la nomenclatura MCOM1_U2_A2_XXYZ. Y envía tu archivo de
evidencias. Recuerda sustituir las XX por las dos primeras de tu primer nombre, la Y por la inicial
de tu apellido paterno y la por la inicial de tu apellido materno.
4. Espera la retroalimentación de tu Facilitador(a).
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
29
29
2.3. Tipos de Algoritmos
No existe una clasificación “correcta” para los algoritmos, así que discutiremos una clasificación con base
en la funcionalidad de los más conocidos. Algunos algoritmos se utilizan en programas pequeños para
resolver problemas específicos. Otros tienen un lugar en sistemas grandes. Muchos algoritmos
fundamentales encuentran aplicación en ambos dominios.
Algoritmos de Ordenamiento. Reciben datos que no tienen un orden en particular y entregan
datos arreglados en el orden especificado.
Algoritmos Elementales. Apropiados para archivos pequeños o con una estructura especial. En muchas
aplicaciones de ordenamiento es mejor usar estos métodos simples que los métodos de propósito general.
Ordenamiento por Selección. Primero encuentra el elemento más pequeño en el arreglo y lo intercambia
con el elemento en la primera posición, luego localiza el segundo elemento más pequeño y lo intercambia
con el elemento en la segunda posición; continúa de esta forma hasta que el arreglo completo está
ordenado.
Ordenamiento por Inserción. considera los elementos uno a la vez, insertando cada
uno en su lugar apropiado entre aquellos ya considerados (manteniéndolos
ordenados).
El Método de la Burbuja. Se enseña a menudo en las clases introductorias . Se
mantiene recorriendo el archivo intercambiando elementos adyacentes, si es
necesario.
Shellsort. Extensión simple del ordenamiento por inserción que gana velocidad
permitiendo intercambios de elementos que están separados.
o Quicksort. Algoritmo recursivo muy utilizado. No es difícil de implementar y consume menos
recursos que cualquier otro método de ordenamiento..
o Ordenamiento Radix. Método que toma ventaja de las propiedades digitales de las llaves al
considerarlas como números de un rango restringido.
o Colas de Prioridad. Método de ordenamiento que utiliza estructuras de datos que soportan
las operaciones de insertar un nuevo elemento y eliminar el más grande.
o Mergesort. Método que utiliza un proceso complementario de la operación de selección
para combinar dos archivos ordenados y obtener uno más grande.
o Ordenamiento Externo. Método apropiado para aplicaciones de ordenamiento que implican
el procesamiento de archivos muy extensos para ser guardados en la memoria primaria de
cualquier computadora.
Algoritmos de Búsqueda. Realizan una operación fundamental intrínseca en muchas tareas
computacionales: la búsqueda. Esta operación recupera alguna pieza (o piezas) de información de
un gran acervo previamente almacenado.
o Algoritmos Elementales. Son muy útiles para tablas pequeñas y en otras situaciones
especiales, e incorporan técnicas fundamentales explotadas por algunos métodos más
avanzados.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
30
30
Búsqueda Secuencial. El método más simple de búsqueda es almacenar los
registros en un arreglo. Cuando un nuevo registro es insertado, se pone al final del
arreglo; cuando una búsqueda es efectuada se revisa el arreglo secuencialmente.
Búsqueda Binaria. Si el conjunto de registros es grande, el tiempo total de
búsqueda puede ser reducido significativamente utilizando un procedimiento que
aplica el paradigma de "divide y vencerás": dividir el conjunto de registros en dos
partes, determinar a cuál de las dos partes pertenece la llave, y concentrarse ahì.
Búsqueda de Arbol Binario. Método de búsqueda simple, eficiente y dinámico,
considerado como un algoritmo fundamentalde la Informática.
o Àrboles Balanceados. En la búsqueda de árbol binario se puede utilizar una técnica
llamada balanceo que permite garantizar que el peor caso no ocurrirá.
o Hashing. Estos algoritmos utilizan un método para referenciar registros directamente en una
tabla realizando transformaciones aritméticas en las llaves que las convierte en direcciones
de tabla.
o Búsqueda Radix. Estos métodos examinan las llaves de búsqueda de un bit a la vez, en
lugar de utilizar comparaciones completas entre las llaves a cada paso.
o Búsqueda Externa. Algoritmos de búsqueda apropiados para acceder elementos de
archivos muy grandes.
Procesamiento de Cadenas (strings). Los datos que van a ser procesados a menudo no se
descomponen lógicamente en registros independientes con pequeñas piezas identificables.
Este tipo de datos se caracteriza porque pueden ser escritos como una cadena,o secuencia lineal
de caracteres.
o Búsqueda de Cadenas.
Algoritmo de Fuerza Bruta
Algoritmo Knuth-Morris-Pratt
Algoritmo Boyer-Moore
Algoritmo Rabin-Karp
Búsquedas Múltiples
o Localización de Patrones. Es deseable a menudo realizar la búsqueda de cadenas cuando
no se tiene una información completa acerca del patrón a ser encontrado.
o Parsing (análisis). Se han desarrollado varios algoritmos fundamentales para descomponer
programas de computadora en formas más adecuadas para procesamiento adicional. La
operación de parsing tiene aplicación más allá de la Informática, dado que está directamente
relacionado al estudio de la estructura del lenguaje en general.
o Compresión de Archivos. Algoritmos diseñados para reducir el consumo de espacio sin
invertir mucho tiempo.
o Criptología. La codificación de cadenas de caracteres con el fin de mantenerlas secretas.
Algoritmos Geométricos. Las computadoras están siendo utilizadas para resolver problemas a
gran escala que son inherentemente geométricos como puntos, líneas y polígonos que son la base
de una amplia variedad de importantes aplicaciones y dan origen a un interesante conjunto de
problemas y algoritmos.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
31
31
o Algoritmos Geométricos Elementales
o Determinación de la ConvexHull
o Búsqueda de Rango
o Intersección Geométrica
o Problemas del Punto Más Cercano
Algoritmos de Grafos. Una gran cantidad de problemas son naturalmente formulados en términos
de objetos y conexiones entre ellos. Por ejemplo, dado un mapa de rutas para una línea aérea
pueden formularse preguntas como “¿Cuál es la forma más rápida de ir de esta ciudad a esta otra?”
Un grafo es un objeto matemático que modela precisamente este tipo de situaciones.
o Algoritmos Elementales de Grafos
o Conectividad
o Grafos Ponderados
o Grafos dirigidos
o Flujo de Red
o Matching.
Algoritmos Matemáticos.
o Números Aleatorios
o Aritmética
o Eliminación Gaussiana
o Aproximación de curvas
o Integración
Técnicas Avanzadas de Diseño y Análisis.
o Algoritmos Glotones o Avidos (Greedy)
2.3.1. Algoritmo de Búsqueda
Los algoritmos de búsqueda recuperan elementos de información de una gran cantidad de datos
previamente almacenados. Existen diversos algoritmos para efectuar búsquedas. Presentamos a
continuación dos de ellos: el Método secuencial y el Método Hash.
Búsqueda de Elementos por el Método Secuencial
El método consiste en buscar un número dentro de un arreglo de números. Esto se hace comparando el
número deseado con cada uno de los elementos dentro del arreglo.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
32
32
Encontrarás a continuación la representación en pseudocódigo y en un diagrama de flujo, del algoritmo de
búsqueda secuencial.
Pseudocódigo.
Paso 1.
Búsqueda de un elemento por el método secuencial.
Paso 2.
Entradas: Tamaño de la lista dimensión, lista para buscar a[i], elemento a
buscar busk.
Salidas: Mensaje („Número encontrado‟) o („Número no encontrado‟).
1. Inicio.
2. Inicialización de variables
i← 0
j← 0 // Variables usadas en los ciclos.
3. for i <dim // Comienza la búsqueda
if a[i] == buskentonces // Comparación elemento por elemento
Salida („Número encontrado‟)
j++
end-if
end-for
4. if j == 0 entonces
Salida, valores ordenados a[i].
5. Fin.
Diagrama de flujo. Búsqueda Secuencial.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
33
33
Búsqueda de un Número por el Método Hash.
Este método también busca un número dentro de un arreglo de números. La diferencia con el método de
búsqueda secuencial es que se divide el arreglo en partes.
Esto se logra dividiendo un número del arreglo entre un número dado “n”, con la operación obtendremos un
residuo, el cual te ayudará a separar los números del arreglo en partes.
Después de dividir en partes el arreglo principal, podrás buscar el número deseado más rápidamente en un
arreglo que depende del residuo del número que buscas. ¡Divide y conquistarás!
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
34
34
A continuación se muestra la representación gráfica del método. En este ejemplo n = 3 y el número que
buscamos es 7.
Encontrarás a continuación la representación en pseudocódigo y en un diagrama de flujo, del algoritmo de
búsqueda por el método Hash.
Pseudocódigo.
Paso 1.
Búsqueda de un elemento por el método Hash.
Paso 2.
Entradas: Tamaño de la lista dimensión, lista para buscar a[i], elemento a buscar busk.
Salidas: Mensaje („Número encontrado‟) o („Número no encontrado‟).
1. Inicio.
2. Inicialización de variables
residuo← 0
i← 0
j← 0 // Variables usadas en los ciclos.
k← 0 //en este caso usamos “tres” variables j, k y l.
l← 0
cont← 0 //Variable usada para el despliegue del mensaje de salida
3. for i <dim //Comienza la búsqueda
residuo ← a[i] % 3 //El número tres, así como la cantidad de variables
Acomoda los valores de a[i] en // como j en los ciclos, dependen del número
de
alma[j][residuo] // divisiones deseadas de la lista de valores
en la
j++ // que se va a buscar.
end-for.
4. residuo ← busk % 3.
5. for i < j entonces
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
35
35
Busca el valor busk en alma[i][residuo]
Salida („Número encontrado‟)
cont++
end-for.
6. ifcont == 0 entonces
Salida(„Número no encontrado‟).
7. Fin.
Diagrama de flujo. Método Hash.
2.3.2. Algoritmo de Ordenamiento
Los algoritmos de ordenamiento reciben datos que no tienen un orden en particular y entregan datos
arreglados en el orden especificado. Existen diversos algoritmos para este tipo de procesos; presentamos a
continuación dos de ellos: el de la Burbuja y el de Selección de Elementos.
Ordenamiento por el Método de la Burbuja
Este es uno de los métodos más conocidos y simples. Funciona comparando dos elementos a la vez;
recorre todo el arreglo varias veces de manera secuencial comparando e intercambiando (si es el caso) un
primer elemento con su consecutivo inmediato. El ordenamiento puede realizarse de forma ascendente o
descendente.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
36
36
La representación gráfica siguiente muestra lo que hace el método:
El proceso continúa hasta que el arreglo está ordenado.
Encontrarás a continuación la representación en pseudocódigo y en un diagrama de flujo, del algoritmo de
ordenamiento por el método de la burbuja.
Pseudocódigo
Paso 1.
Ordenamiento por el método de la burbuja.
Paso 2.
Entradas: Cantidad de números dimensión, valores a ordenar de a[i].
Salidas: Valores ordenados a[i].
1. Inicio.
2. Inicialización de variables
i← 0
j← 0 // Variables usadas en los ciclos.
aux ← 0 // Variable utilizada en el intercambio de datos.
3. for i <dim //Inicia el ordenamiento
for j <dim
if a[j] ≥ a[j+1] entonces //Ordenamiento elemento por elemento
Intercambia valores de a[j] por a[j+1]
end-if
end-for
end-for.
4. Salida, valores ordenados a[i].
5. Fin.
Diagrama de flujo. Método de la Burbuja.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
37
37
Ordenamiento por el Método por Selección de Elementos
Este método selecciona dentro de todo arreglo al elemento de menor valor y lo intercambia por el de mayor
valor consecutivo. De forma similar al Método de la Burbuja, recorre el arreglo completo varias veces, y lo
puede hacer de forma ascendente y descendente.
A continuación se muestra la representación gráfica de lo que hace el método:
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
38
38
Encontrarás a continuación la representación en pseudocódigo y en un diagrama de flujo, del algoritmo de
ordenamiento por el método de selección de elementos.
Pseudocódigo.
Paso 1.
Ordenamiento por selección de elementos.
Paso 2.
Entradas: Cantidad de números dimensión, valores a ordenar de a[i].
Salidas: Valores ordenados a[i].
1. Inicio.
2. Inicialización de variables
i← 0
j← i+1 // Variables usadas en los ciclos.
aux1 ← 0
aux2 ← 0 // Variable utilizada en el intercambio
de datos.
3. for i <dim //Comienza el ordenamiento
aux2 ← i
for j <dim
if a[j] < a[aux2] entonces //Ordenamiento en donde se
selecciona el
aux2 ← j //elemento de mayor valor y se
end-if //intercambia con el de menor
end-for //valor y así sucesivamente
Intercambia valores de a[i] por a[aux2]
end-for.
4. Salida, valores ordenados a[i].
5. Fin.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
39
39
Diagrama de flujo. Método por Selección de Elementos.
2.3.3. Algoritmos Glotones
La Aproximación Glotona
Este tipo de algoritmo funciona tomando decisiones que parecen localmente las mejores, sin embargo
globalmente pueden no serlo. El algoritmo no reconsidera su decisión, simplemente la toma y ahí
permanece.
Como ejemplo, abordaremos un caso muy común de los algoritmos glotones: el “cambio de dinero”. La
representación gráfica de este método se muestra a continuación (utilizamos dólares y centavos
americanos):
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
40
40
Pseudocódigo.
Paso 1.
Algoritmo de cambio de dinero
Paso 2.
Entradas: El dinero en dólares “n”.
Salidas: El número de monedas que se necesitan “cambio”.
1. Inicialización de variables
Monedas ← {100, 25, 10, 5, 1} //Constante
i ← 0
j ← 0
sum ← 0
x ← 0
sol ← {} // Arreglo que contiene la cantidad de cada
tipo de moneda
cont ← 0 // Contador de monedas
2. while sum != n
x = Monedas[i]
for sum + x ≤ n // Inicia el conteo de monedas y de dinero.
sum ← sum + x
end-for
sol [i]← cont // Almacena la cantidad de monedas
end-while
3. Salida (“La cantidad de monedas de Monedas[i] es cont”)
4. Fin
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
41
41
Diagrama de flujo.
Método Glotón para la Selección de Actividades
Este método se refiere al problema de la programación o calendarización de actividades que se encuentran
en intervalos de tiempo definidos. Los intervalos tienen un tiempo “si” de inicio y un tiempo “fi” de término.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
42
42
Con este método se pretende encontrar el conjunto de actividades de tamaño máximo y que sean
mutuamente compatibles entre ellos; asimismo, para que el resultado sea óptimo, los intervalos no deben
traslaparse unos con otros.
Se muestra a continuación la representación gráfica del método:
Pseudocódigo.
Paso 1.
Método glotón para la selección de actividades.
Paso 2.
Entradas: La cantidad de intervalos “n”, los intervalos con inicio en “s” y
término “f ” a(si , fi).
Salidas: Intervalos con compatibilidad óptima “alma(si , fi)óptimos”.
1. Inicio.
2. Inicialización de variables.
i ← 0.
j ← 0.
k ← 1.
aux1 ← 0.
aux2 ← 0.
3. Ordenamiento de los intervalos, considerando el valor “f ” de cada
intervalo de forma ascendente, es decir:f1 ≤ f2 ≤ . . . ≤fn
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
43
43
NOTA: Para este paso puedes utilizar alguno de los métodos de ordenamiento
que vimos anteriormente.
4. k ← 1.
5. alma (s0 ,f0) ← a(s0 ,f0).
6. for i< n
ifsi ≥ fj
alma (sk ,fk) ← a(si ,fi)
j ← i
k++.
end-if
end-for
7. Salida alma(si ,fi).
8. Fin.
Diagrama de flujo.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
44
44
2.4. Programación
En las secciones anteriores presentamos detalles de varios algoritmos, incluyendo su representación con
pseudocódigo y un diagrama de flujo. Con el fin de que puedas entender mejor el funcionamiento de esos
algoritmos, te presentamos a continuación su código en C y en Java. Como lo mencionamos al principio, te
recomendamos que estudies y experimentes con los códigos. Para hacerlo, puedes utilizar el IDE Eclipse
que instalaste y utilizaste en la asignatura de Herramientas Computacionales.
2.4.1. Programación de Algoritmos en C
Algoritmo de Búsqueda Secuencial
#include <stdio.h>
main()
{
setvbuf(stdout, NULL, _IONBF, 0);
intdim = 40, aux1 = 0, i = 0,j = 0; //Declaración de variables
charbusk, a[40],o[20];
puts("Búsqueda de elementos, Método secuencial."); //Inicio del programa
printf("Dame el elemento a buscar:\n"); //Adquisición de datos
scanf("%c",&busk);
printf("Dame los datos (menos de 40 elementos):\n");
scanf("%s",&a[i]);
printf("\n");
for (i = 0; i <dim; i++){ //Inicia búsqueda del
if (a[i] == busk){ //elemento deseado
printf("Está en la posición: %d\n",(i+1)); //comparando cada uno
j++; //dentro del arreglo
}
}
if (j == 0)
printf("El número %d no está.",num);
}
Búsqueda de elementos, Método secuencial.
Dame el elemento a buscar:
2 <ENTER>
Dame los datos (menos de 40 elementos):
234567898765432 <ENTER>
Está en la posición: 1
Consola
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
45
45
Está en la posición: 15
Algoritmo de Búsqueda Hash
#include<stdio.h>
#include<math.h>
main()
{
setvbuf(stdout, NULL, _IONBF, 0);
//Declaración de variables
int residuo, i, arreglo[50], num, dim, alma[50][50], j = 0, k = 0, l = 0,
cont = 0;
//Inicio de programa
printf("Método de búsqueda hash\n");
//Adquisición de datos
printf("Dame el número que quieres buscar:");
scanf("%d",&num);
printf("Dame la cantidad de números (menos de 50 elementos): ");
scanf("%d",&dim);
printf("Dame los datos:\n");
for (i = 0; i< dim; i++){
printf("dato %d:",i+1);
scanf("%d",&arreglo[i]);
}
//Dividimos la lista de números dependiendo de su residuo
for (i = 0; i< dim; i++){
residuo = arreglo[i] % 3;
if (residuo == 0){
alma[j][residuo] = arreglo[i];
j++;
}
if (residuo == 1){
alma[k][residuo] = arreglo[i];
k++;
}
if (residuo == 2){
alma[l][residuo] = arreglo[i];
l++;
}
}
residuo =num % 3;
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
46
46
//Buscamos el número en la lista dividida, basándonos en su residuo
if (residuo == 0){
for (i = 0; i< j; i++){
if (alma[i][0] == num)
++cont;
}
}
elseif (residuo == 1){
for (i = 0; i< k; i++){
if (alma[i][1] == num)
++cont;
}
}
elseif (residuo == 2){
for (i = 0; i< l; i++){
if (alma[i][2] == num)
++cont;
}
}// Una vez encontrado el número que buscamos se despliega el número de
//coincidencias en la consola
printf("Hay %d coincidencia(s) del número que buscas.\n",cont);
}
Método de búsqueda hash:
Dame el número que quieres buscar:
1 <ENTER>
Dame la cantidad de números (menos de 50 elementos): 8 <ENTER>
Dame los datos:
dato 1:25 <ENTER>
dato 2:3 <ENTER>
dato 3:12 <ENTER>
dato 4:19 <ENTER>
dato 5:2 <ENTER>
dato 6:1 <ENTER>
dato 7:9 <ENTER>
dato 8:6 <ENTER>
Hay 1 coincidencia(s) del número que buscas.
Consola
Algoritmo de Ordenamiento por el Método de la Burbuja
#include <stdio.h>
main()
{
setvbuf(stdout, NULL, _IONBF, 0);
intdim, aux1 = 0, i = 0,j = 0; //Declaración de variables
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
47
47
puts("Método de ordenamiento burbuja"); //Inicio del programa
puts("Dame la cantidad de datos que vas a ordenar:");//Cantidad de números
a ordenar
scanf("%d",&dim);
printf("Dame los números a ordenar:\n");
int a[dim];
for (i = 0; i <dim; i++){ //Valores que se van a ordenar
scanf("%d",&a[i]);
}
for (i = 0; i <dim; i++){ //Impresión en pantalla
printf("%d-",a[i]); //de los valores a ordenar
}
printf("\n");
for (i = 0; i <dim; i++){ //Inicio de ordenamiento
for (j = 0; j <dim; j++) //en el que se recorre todo el
if (a[j] >= a[j + 1]) { //arreglo de valores,
comparando
aux1 = a[j]; //cada uno de ellos con todos
los
a[j] = a[j + 1]; //los demás.
a[j + 1] = aux1;
}
}
for (i = 0; i <dim; i++){ //Impresion en pantalla de los
printf("%d-",a[i]); //valores ya ordenados
}
}
Método de ordenamiento burbuja
Dame la cantidad de datos que vas a ordenar: 8 <ENTER>
Dame los números a ordenar:
25 <ENTER>
3 <ENTER>
12 <ENTER>
19 <ENTER>
2 <ENTER>
1 <ENTER>
9 <ENTER>
6 <ENTER>
25-3-12-19-2-1-9-6-
1-2-3-6-9-12-19-25-
Consola
Algoritmo de Ordenamiento por Selección de Elementos
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
48
48
#include <stdio.h>
main()
{
setvbuf(stdout, NULL, _IONBF, 0);
intdim=8, aux1 = 0, i = 0,j = 0, aux2=0; //Declaracion de variables
puts("Metodo de ordenamiento por seleccion"); //Inicio del programa
puts("Dame la cantidad de datos que vas a acomodar:"); //Cantidad de valores a
//ordenar
scanf("%d",&dim);
printf("Dame los numeros a ordenar:\n");
int a[dim];
for (i = 0; i< dim; i++){ //Valores a ordenar
scanf("%d",&a[i]);
}
for (i = 0; i <dim; i++){ //Impresión en pantalla de
printf("%d-",a[i]); //los valores a ordenar
}
printf("\n");
for (i = 0; i< dim; i++){ //Proceso de ordenamiento
aux2=i;
for (j = i+1; j <dim ; j++) //comparacion y seleccion
if (a[j] < a[aux2]) //de valores
aux2=j;
aux1 = a[i];
a[i] = a[aux2];
a[aux2] = aux1; //ordenamiento
//printf("%d",a[i]);
}
for (i = 0; i <dim; i++){ //Impresion en pantalla de
printf("%d-",a[i]); //los valores ordenados
}
}
Método de ordenamiento por selección
Dame la cantidad de datos que vas a acomodar: 8 <ENTER>
Dame los números a ordenar:
25 <ENTER>
3 <ENTER>
12 <ENTER>
19 <ENTER>
2 <ENTER>
1 <ENTER>
9 <ENTER>
6 <ENTER>
Consola
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
49
49
25-3-12-19-2-1-9-6-
1-2-3-6-9-12-19-25-
Algoritmo de Aproximación Glotona
#include<stdio.h>
#include<math.h>
main()
{
setvbuf(stdout, NULL, _IONBF, 0);
intMonedas[5],i = 0,j = 0, sol[5],sum = 0,cont=0, x=0;
float n;
Monedas[0]=100;
Monedas[1]=25; //Declaración de monedas (centavos americanos)
Monedas[2]=10;
Monedas[3]=5;
Monedas[4]=1;
//Adquisición de dinero
printf("Dame la cantidad de dinero en dólares (con centavos): $");
scanf("%f",&n);
i=0;
if (n < 0.01)
printf("¡¡ERROR!!");
n=n*100;
while (sum != n){ //Inicia conteo de dinero
cont=0;
x = Monedas[i];
for (j = 0;sum + x <= n;j++){ //Conteo de monedas
sum = sum + x;
cont++;
}
sol[i]=cont;
i++;
}
for(j=0;j<i;j++){ //Despliegue de resultados
printf("Se necesitan %d moneda(s) de ",sol[j]);
printf("%d centavo(s)\n",Monedas[j]);
}
}
Dame la cantidad de dinero en dólares (con centavos): $6.89 <ENTER>
Se necesitan 6 moneda(s) de 100 centavo(s)
Se necesitan 3 moneda(s) de 25 centavo(s)
Se necesitan 1 moneda(s) de 10 centavo(s)
Consola
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
50
50
Se necesitan 0 moneda(s) de 5 centavo(s)
Se necesitan 4 moneda(s) de 1 centavo(s)
Algoritmo Glotón para la Selección de Actividades
#include<stdio.h>
main()
{
setvbuf(stdout, NULL, _IONBF, 0);
intdim, aux1 = 0, i = 0,j = 0, aux2=0,k = 0; //Declaracion de variables
puts("Método glotón de selección de actividades."); //Inicio del programa
puts("Dame la cantidad de datos: "); //Cantidad de valores a
scanf("%d",&dim); //ordenar
printf("Dame los intervalos de las actividades (s,f):\n");
int a[dim][dim],alma[dim][dim];
for (i = 0; i< dim; i++){ //Valores a ordenar
for (j = 0;j < 2;j++)
scanf("%d",&a[i][j]);
printf("\n");
}
for (i = 0; i <dim; i++){ //Impresión en pantalla de
for (j = 0;j < 2;j++) //los valores a ordenar
printf("%d-",a[i][j]);
printf("\n");
}
printf("\n");
for (i = 0; i< dim; i++){ //Proceso de ordenamiento
aux2=i;
for (j = i+1; j <dim ; j++) //comparación y selección
if (a[j][1] < a[aux2][1]) //de valores
aux2=j;
aux1 = a[i][1];
a[i][1] = a[aux2][1];
a[aux2][1] = aux1; //ordenamiento de los valores i,0
aux1 = a[i][0];
a[i][0] = a[aux2][0];
a[aux2][0] = aux1;
}
for (i = 0; i <dim; i++){ //Impresión en pantalla de
for (j = 0;j < 2;j++) //los valores ordenados
printf("%d-",a[i][j]);
printf("\n");
}
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
51
51
j=0;
k=1;
alma[0][0] = a[0][0];
alma[0][1] = a[0][1];
for (i = 1; i <dim; i++){ //Generación de la matriz que
if (a[i][0] >= a[j][1]){ //contiene los intervalos más
alma[k][0] = a[i][0]; //óptimos
alma[k][1] = a[i][1];
k++;
j=i;
}
}
puts("Los intervalos más óptimos son: \n.");
for (i = 0; i < k; i++){ //Impresión en pantalla de
for (j = 0;j < 2;j++) //la matriz con los
printf("%d-",alma[i][j]); //intervalos óptimos
printf("\n");
}
}
Método glotón de selección de actividades.
Dame la cantidad de datos:
11 <ENTER>
Dame los intervalos de las actividades (s,f):
0 <ENTER>
4 <ENTER>
4 <ENTER>
6 <ENTER>
6 <ENTER>
10 <ENTER>
0 <ENTER>
1 <ENTER>
1 <ENTER>
5 <ENTER>
5 <ENTER>
9 <ENTER>
9 <ENTER>
10 <ENTER>
0 <ENTER>
3 <ENTER>
0 <ENTER>
Consola
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
52
52
2 <ENTER>
7 <ENTER>
10 <ENTER>
8 <ENTER>
10 <ENTER>
0-4-
4-6-
6-10-
0-1-
1-5-
5-9-
9-10-
0-3-
0-2-
7-10-
8-10-
0-1-
0-2-
0-3-
0-4-
1-5-
4-6-
5-9-
6-10-
9-10-
7-10-
8-10-
Los intervalos más óptimos son:
0-1-
1-5-
5-9-
9-10-
2.4.2. Programación de Algoritmos en Java
Algoritmo de Búsqueda Secuencial
package algoritmos;
importjava.util.Scanner;
publicclassBusqueda {
publicstaticvoid main(String[] args) {
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
53
53
Scanner entrada = newScanner(System.in);
//Inicio del programa
System.out.println("Búsqueda de elementos, Método secuencial.");
//Adquisición de datos
System.out.print("Dime la cantidad de elementos en los que vas a buscar:
");
intdim = entrada.nextInt();
int[] a = newint[dim]; //Se declara el arreglo “a”
//Adquisición del arreglo que va a contener los arreglos
System.out.print("Dame los números en los que voy a buscar: ");
for (inti = 0; i< dim; i++)
a[i] = entrada.nextInt();
System.out.print("Dame el número a buscar: ");
int busca = entrada.nextInt();
//Impresión de los datos almacenados en el arreglo
for (inti = 0; i< dim; i++)
System.out.print(a[i]);
System.out.println(" ");
int j = 0;
//Inicia búsqueda del elemento deseado comparando cada uno dentro del
arreglo
for (inti = 0; i< dim; i++) {
if (a[i] == busca){
System.out.printf("Esta en la posición: %d\n",(i+1));
j++;
}
}
if (j == 0)
System.out.printf("¡ERROR! El número no fue encontrado\n");
}
}
Búsqueda de elementos, Método secuencial.
Dime la cantidad de elementos en los que vas a buscar: 10
<ENTER>
Dame los números en los que voy a buscar: 1 2 3 4 5 6 7 6 5 4
<ENTER>
Dame el número a buscar: 6 <ENTER>
1234567654
Está en la posición: 6
Está en la posición: 8
Consola
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
54
54
Búsqueda de elementos, Método secuencial
Dime la cantidad de elementos en los que vas a buscar: 10
<ENTER>
Dame los números en los que voy a buscar: 1 2 3 4 5 6 7 6 5 4
<ENTER>
Dame el número a buscar: 8 <ENTER>
1234567654
¡ERROR! El número no fue encontrado
Consola
Algoritmo de Búsqueda Hash
package algoritmos;
importjava.util.Scanner;
publicclassBusquedaHash {
public static void main(String[] args) {
Scanner entrada = new Scanner(System.in);
//Declaración de variables
int residuo, num, i,j = 0, k = 0, l = 0, cont = 0;
int[][] alma = new int[50][50];
int[] a = new int[50];
//Inicio del programa
System.out.println("Búsqueda de elementos, Método Hash.");
//Adquisición de datos
System.out.print("Dame la cantidad de números (menos de 50
elementos): ");
intdim = entrada.nextInt();
System.out.print("Dame los números en los que voy a buscar: ");
for (i = 0; i< dim; i++)
a[i] = entrada.nextInt();
System.out.print("Dame el número a buscar: ");
num = entrada.nextInt();
System.out.println(" ");
//Inicia la división de nuestra lista de números con respecto a su
residuo,
// en este caso utilizamos tres residuos diferentes, esto va a
depender de
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
55
55
// la cantidad de partes en las que queremos dividir nuestra lista de
datos.
for(i = 0; i< dim; i++){
residuo = a [i] % 3;
if (residuo == 0){
alma[j][0] = a[i];
j++;
}
else if (residuo == 1){
alma[k][1] = a[i];
k++;
}
else if (residuo == 2){
alma[l][2] = a[i];
l++;
}
}
//Obtenemos el residuo del número que estamos buscando
residuo = num % 3;
System.out.println(" ");
//Buscamos el número en la lista dividida, basándonos en su residuo
if (residuo == 0){
for (i = 0; i< j-1; i++){
if (alma[i][0] == num)
cont++;
}
}
else if (residuo == 1){
for (i = 0; i< k-1; i++){
if (alma[i][1] == num)
cont++;
}
}
else if (residuo == 2){
for (i = 0; i< l-1; i++){
if (alma[i][2] == num)
cont++;
}
} // una vez encontrado el número que buscamos y este se
despliega en la consola
System.out.println("Hay " + cont + " número(s) " + num + " en la
lista.");
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
56
56
if (cont == 0) //Si el número no fue encontrado, arroja un error en
la consola.
System.out.printf("¡ERROR! El número no fue encontrado\n");
}
}
Búsqueda de elementos, Método Hash.
Dame la cantidad de números (menos de 50 elementos): 20
<ENTER>
Dame los números en los que voy a buscar: 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 4
3 2 5 6 <ENTER>
Dame el número a buscar: 2 <ENTER>
Hay 3 número(s) 2 en la lista.
Consola
Algoritmo de Ordenamiento por el Método de la Burbuja
packagealgoritmos;
importjava.util.Scanner;
publicclass Bubble {
publicstaticvoid main(String[] args) {
Scanner entrada = newScanner(System.in);
//Declaración de variables
int aux1, i, j;
//Inicio del programa
System.out.println("Ordenamiento de elementos, Método Burbuja.");
//Adquisición de datos
System.out.print("Dame la cantidad de números: ");
int dim = entrada.nextInt();
int[] a = newint[dim];
System.out.print("Dame los números a ordenar: ");
for (i = 0; i< dim; i++)
a[i] = entrada.nextInt();
for (i = 0; i <dim; i++) //Impresión en pantalla de los
System.out.printf("%d-", a[i]); //valores ya ordenados
System.out.println(" ");
for (i = 0; i< dim-1; i++){ //Inicio de ordenamiento
for (j = 0; j < dim-1; j++) //en el que se recorre todo el
if (a[j] >= a[j + 1]){ //arreglo de valores, comparando
aux1 = a[j]; //cada uno de ellos con todos los
a[j] = a[j + 1]; //los demás.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
57
57
a[j + 1] = aux1;
}
}
for (i = 0; i <dim; i++) //Impresión en pantalla de los
System.out.printf("%d-", a[i]); //valores ya ordenados
}
}
Ordenamiento de elementos, Método Burbuja.
Dame la cantidad de números: 10 <ENTER>
Dame los números a ordenar: 1 2 3 4 1 2 3 4 1 2 <ENTER>
1-2-3-4-1-2-3-4-1-2-
1-1-1-2-2-2-3-3-4-4-
Consola
Algoritmo de Ordenamiento por Selección de Elementos
packagealgoritmos;
importjava.util.Scanner;
public class SortSelection {
public static void main(String[] args) {
Scanner entrada = new Scanner(System.in);
//Declaración de variables
int aux1, aux2, i, j;
//Inicio del programa
System.out.println("Ordenamiento de elementos, Método de selección.");
//Adquisición de datos
System.out.print("Dame la cantidad de números: ");
int dim = entrada.nextInt();
int[] a = new int[dim];
System.out.print("Dame los números a ordenar: ");
for (i = 0; i< dim; i++)
a[i] = entrada.nextInt();
for (i = 0; i <dim; i++) //Impresión en pantalla de los
System.out.printf("%d-", a[i]); //valores ya ordenados
System.out.println(" ");
for (i = 0; i< dim; i++){ //Proceso de ordenamiento
aux2=i;
for (j = i+1; j <dim ; j++) //comparación y selección
if (a[j] < a[aux2]) //de valores
aux2=j;
aux1 = a[i];
a[i] = a[aux2];
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
58
58
a[aux2] = aux1; //ordenamiento
}
for (i = 0; i <dim; i++) //Impresión en pantalla de
System.out.printf("%d-",a[i]); //los valores ordenados
}
}
Ordenamiento de elementos, Método de selección.
Dame la cantidad de números: 10 <ENTER>
Dame los números a ordenar: 11 33 2 4 5 33 66 60 23 0
<ENTER>
11-33-2-4-5-33-66-60-23-0-
0-2-4-5-11-23-33-33-60-66-
Consola
Algoritmo de Aproximación Glotona
packagealgoritmos;
importjava.util.Scanner;
publicclassGreedyApproach {
publicstaticvoid main(String[] args) {
// TODO Auto-generated method stub
Scanner entrada = newScanner(System.in);
inti = 0,j = 0, sum = 0,cont=0, x=0;
int[] Monedas= newint [5];
int[] sol= newint [5];
//Declaración de monedas (centavos americanos)
Monedas[0]=100; //Dollar
Monedas[1]=25; //Quarter
Monedas[2]=10; //Dime
Monedas[3]=5; //Nickel
Monedas[4]=1; //Penny
//Adquisición de dinero
System.out.print("Dame la cantidad de dinero en dólares (con centavos):
$");
float n = entrada.nextFloat();
i=0;
if (n < 0.01)
System.out.println("¡¡ERROR!!");
n=n*100;
while (sum != n){ //Inicia conteo de dinero
cont=0;
x = Monedas[i];
for (j = 0;sum + x <= n;j++){ //Conteo de monedas
sum = sum + x;
cont++;
}
sol[i]=cont;
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
59
59
i++;
}
for(j=0;j<i;j++){ //Despliegue de resultados
System.out.printf("Se necesitan %d moneda(s) de ",sol[j]);
System.out.printf("%d centavo(s)\n",Monedas[j]);
}
}
}
Dame la cantidad de dinero en dólares (con centavos): $10.24
<ENTER>
Se necesitan 10 moneda(s) de 100 centavo(s)
Se necesitan 0 moneda(s) de 25 centavo(s)
Se necesitan 2 moneda(s) de 10 centavo(s)
Se necesitan 0 moneda(s) de 5 centavo(s)
Se necesitan 4 moneda(s) de 1 centavo(s)
Consola
Algoritmo Glotón de Selección de Actividades
packagealgoritmos;
importjava.util.Scanner;
publicclassGreedySelection {
publicstaticvoid main(String[] args) {
Scanner entrada = newScanner(System.in);
//Declaracion de variables
intdim, aux1 = 0, i = 0,j = 0, aux2=0,k = 0;
//Inicio del programa
System.out.println("Método glotón de selección de actividades.");
System.out.println("Dame la cantidad de datos: "); //Cantidad de valores
a
dim = entrada.nextInt(); //ordenar
System.out.println("Dame los intervalos de las actividades (s,f):");
int[][] a = newint [dim][dim];
int[][] alma = newint [dim][dim];
for (i = 0; i< dim; i++){ //Valores a ordenar
for (j = 0;j < 2;j++)
a[i][j] = entrada.nextInt();
System.out.println(" ");
}
for (i = 0; i <dim; i++){ //Impresión en pantalla de
for (j = 0;j < 2;j++) //los valores a ordenar
System.out.printf("%d-",a[i][j]);
System.out.println(" ");
}
System.out.println("");
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
60
60
for (i = 0; i <dim; i++){ //Proceso de ordenamiento
aux2=i;
for (j = i+1; j <dim ; j++) //comparación y selección
if (a[j][1] < a[aux2][1]) //de valores
aux2=j;
aux1 = a[i][1];
a[i][1] = a[aux2][1];
a[aux2][1] = aux1; //ordenamiento de los valores i,0
aux1 = a[i][0];
a[i][0] = a[aux2][0];
a[aux2][0] = aux1;
}
for (i = 0; i <dim; i++){ //Impresión en pantalla de
for (j = 0;j < 2;j++) //los valores ordenados
System.out.printf("%d-",a[i][j]);
System.out.println(" ");
}
j=0;
k=1;
alma[0][0] = a[0][0];
alma[0][1] = a[0][1];
for (i = 1; i <dim; i++){ //Generación de la matriz que
if (a[i][0] >= a[j][1]){ //contiene los intervalos más
alma[k][0] = a[i][0]; //óptimos
alma[k][1] = a[i][1];
k++;
j=i;
}
}
System.out.println("Los intervalos más óptimos son: ");
for (i = 0; i < k; i++){ //Impresión en pantalla de
for (j = 0;j < 2;j++) //la matriz con los
System.out.printf("%d-",alma[i][j]); //intervalosóptimos
System.out.println(" ");
}
}
}
Método glotón de selección de actividades.
Dame la cantidad de datos:
5 <ENTER>
Dame los intervalos de las actividades (s,f):
3 <ENTER>
5 <ENTER>
6 <ENTER>
Consola
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
61
61
8 <ENTER>
1 <ENTER>
4 <ENTER>
4 <ENTER>
7 <ENTER>
7 <ENTER>
10 <ENTER>
3-5-
6-8-
1-4-
4-7-
7-10-
1-4-
3-5-
4-7-
6-8-
7-10-
Los intervalos más óptimos son:
1-4-
4-7-
7-10-
Actividad 3. Desarrollo de algoritmos típicos
A través de esta actividad podrás analizar otros dos algoritmos útiles: “Búsqueda Binaria” (binary search) y
“QuickSort” (uno de los más populares y estudiados).
Instrucciones: Toma en cuenta los lineamientos que se te presentan en el documento descargable
1. Descarga el documento llamado “Act. 3. Desarrollo de algoritmos típicos”.
2. Analiza cada instrucción que se presenta y síguelo de manera ordenada.
2. Guarda tu documento con la nomenclatura MCOM1_U2_A2_XXYZ. Y envía tu archivo de
evidencias. Recuerda sustituir las XX por las dos primeras de tu primer nombre, la Y por la inicial
de tu apellido paterno y la por la inicial de tu apellido materno.
3. Espera la retroalimentación de tu Facilitador(a).
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
62
62
Autoevaluación
Felicidades! Haz llegado al final de la Unidad. Es momento de realizar la autoevaluación para medir el
grado conocimiento obtenido durante la unidad. Par eso resuelve la actividad de Autoevaluación que
corresponde a un conjunto de reactivos:
Instrucciones: elige la respuesta correcta que corresponda a la pregunta planteada.
1. Conjunto de instrucciones o reglas que se organizan de manera finita para realizar una actividad
mediante pasos sucesivos para resolver un problema.
a) Algoritmo b) Procesos c) Instrucciones d) Base de datos
2. Se Caracterizan por ser todos iguales en el sentido de que si se descubriera una solución P para
algunos de ellos
a) P b) NP c) NP completos d) Q
3. El uso eficiente de los recursos de cómputo suele medirse en función de los siguientes parámetros
a) Tiempo e
instrucciones
b) Memoria y
cantidad de
almacenamiento
c) Espacio y tiempo d) Tiempo y
longitud del
código
4. Las representaciones más comunes para los algoritmos son
a) Pseudocódigo y
diagramas de
flujo
b) Diagramas de
flujo y
diagramas de
rutas
c) Lenguajes de
programación y
diagramas de
flujo
d) Pseudocódigo y
lenguajes de
programación
5. Para qué tipo de algoritmos se utiliza el método de Hash
a) Geométricos b) De búsqueda c) De
ordenamiento
d) Glotones
Para comparar tus respuestas, revisa el documento “Respuestas_autoevaluación_U2, ubicada en la
pestaña de material de apoyo.
RETROALIMENTACION
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
63
63
Evidencia de Aprendizaje. Programación de algoritmos típicos en C y Java
Al finalizar esta actividad serás capaz de analizar los tiempos de ejecución de los algoritmos, así como
desarrollar, modificar algoritmos, y construir sus representaciones.
1. Descarga el siguiente documento “EA. Presentación de resultados”
2. Elabora un archivo en donde presentes los resultados que obtuviste.
3. Guarda tu documento con la nomenclatura MCOM1_U2_EA_XXYZ. Y envía tu archivo al Portafolio
de Evidencias. Recuerda sustituir las XX por las dos primeras de tu primer nombre, la Y por la
inicial de tu apellido paterno y la por la inicial de tu apellido materno.
3. Espera la retroalimentación de tu Facilitador(a), atiende sus comentarios y reenvía la nueva
versión de tu evidencia, en caso de que sea requerido.
4. Consulta la Escala de Evaluación para conocer los criterios con que será evaluado tu trabajo.
Cierre de la Unidad
En esta unidad tuviste la oportunidad de aprender los fundamentos de los algoritmos. Además de los
conceptos básicos y sus características, te introdujiste a la comparación de algoritmos considerando sus
tiempos de ejecución y otros elementos de complejidad.
También conociste los problemas NP-Completos para los cuales nadie ha sido capaz de encontrar un
algoritmo eficiente que se ejecute en una computadora convencional.
Estudiaste los detalles de dos representaciones comunes para los algoritmos: pseudocódigo y diagramas
de flujo.
Finalmente revisaste algoritmos prácticos de búsqueda y ordenamiento, así como unos más avanzados
llamados “glotones.” Analizaste el código en lenguaje C y Java de estos algoritmos y podrás continuar
probándolos y experimentando con ellos para que seas capaz de resolver problemas de la vida real.
1-3 aciertos. Los conocimientos obtenidos no fueron suficientes, debes revisar nuevamente el contenido
de la unidad.
4-5 aciertos. Tienes un conocimiento claro de los conceptos manejados en la Unidad. ¡Sigue adelante!.
Programa desarrollado Unidad 2. Algoritmos
Educación Abierta y a Distancia * Ciencias Exactas, Ingenierías y Tecnologías
64
64
Para saber más
Consulta los siguientes links:
Acerca de algoritmos de ordenamiento: http://www.sorting-algorithms.com/
Aplicaciones de algoritmos: http://elpais.com/diario/2008/04/10/ciberpais/1207791626_850215.html
Acerca de complejidad: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=complexity1
Acerca de algoritmos avanzados:http://www.xataka.com/otros/un-nuevo-algoritmo-mejora-el-manejo-de-
miembros-artificiales-con-la-mente
Fuentes de consulta
Cormen, T. H., Leiserson, C. E., Rivest, R. L. , Stein, C. (2009). Introduction to Algorithms (3rd. ed.). USA:
The MIT Press.
Heineman, G. T.,Pollice, G., and Selkow, S. (2009). Algorithms in a NutShell. (1st. Ed.). USA: O’Reilly
Media, Inc.
Dasgupta S., Papadimitriou, C. H., and Vazirani, U. V.(2006). Algorithms(1st.ed.). No publisher info
ECMA-4, 2nd Edition.(1966) Standard for Flow Charts. European Computer Manufacturers Association.
September 1966
GC20-8152-1.(1969) Flowcharting Techniques. International Business Machines Corporation.