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



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



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.



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.



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.



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.



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?)



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



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



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.



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.



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.



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).



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



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.



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.



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



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 ).



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.



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 ?



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.



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.



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.



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



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.



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.



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.



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:

√



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).



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.



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.



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.



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.


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.



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!



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.


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.


residuo← 0

i← 0


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



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.



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.


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.


i← 0


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.



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:



38

38


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.


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.



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):



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”.


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



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.



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



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.



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



45

45


Algoritmo de Búsqueda Hash

#include<stdio.h>

#include<math.h>

main()

{


//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;



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++){


++cont;

}

}

elseif (residuo == 2){

for (i = 0; i< l; i++){


++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()

{


intdim, aux1 = 0, i = 0,j = 0; //Declaración de variables



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



48

48

#include <stdio.h>

main()

{


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



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()

{


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)



Consola



50

50



Algoritmo Glotón para la Selección de Actividades

#include<stdio.h>

main()

{


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 (j = 0;j < 2;j++)

scanf("%d",&a[i][j]);

printf("\n");

}


for (j = 0;j < 2;j++) //los valores a ordenar

printf("%d-",a[i][j]);

printf("\n");

}

printf("\n");


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 (j = 0;j < 2;j++) //los valores ordenados

printf("%d-",a[i][j]);

printf("\n");

}



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



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) {



53

53

Scanner entrada = newScanner(System.in);

//Inicio del programa

System.out.println("Búsqueda de elementos, Método secuencial.");


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



Consola



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>


1234567654

¡ERROR! El número no fue encontrado

Consola

Algoritmo de Búsqueda Hash

package algoritmos;


publicclassBusquedaHash {

public static void main(String[] args) {

Scanner entrada = new Scanner(System.in);


int residuo, num, i,j = 0, k = 0, l = 0, cont = 0;

int[][] alma = new int[50][50];

int[] a = new int[50];


System.out.println("Búsqueda de elementos, Método Hash.");


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++)


System.out.print("Dame el número a buscar: ");

num = entrada.nextInt();


//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



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++;

}


alma[l][2] = a[i];

l++;

}

}

//Obtenemos el residuo del número que estamos buscando

residuo = num % 3;


//Buscamos el número en la lista dividida, basándonos en su residuo

if (residuo == 0){

for (i = 0; i< j-1; i++){


cont++;

}

}


for (i = 0; i< k-1; i++){


cont++;

}

}


for (i = 0; i< l-1; i++){


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.");



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>


Hay 3 número(s) 2 en la lista.

Consola

Algoritmo de Ordenamiento por el Método de la Burbuja

packagealgoritmos;


publicclass Bubble {




int aux1, i, j;


System.out.println("Ordenamiento de elementos, Método Burbuja.");


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++)


for (i = 0; i <dim; i++) //Impresión en pantalla de los

System.out.printf("%d-", a[i]); //valores ya ordenados


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.



57

57

a[j + 1] = aux1;

}

}



}

}

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;


public class SortSelection {

public static void main(String[] args) {

Scanner entrada = new Scanner(System.in);


int aux1, aux2, i, j;


System.out.println("Ordenamiento de elementos, Método de selección.");


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++)






aux2=i;


if (a[j] < a[aux2]) //de valores

aux2=j;

aux1 = a[i];

a[i] = a[aux2];



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;


publicclassGreedyApproach {


// TODO Auto-generated method stub


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;



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>






Consola

Algoritmo Glotón de Selección de Actividades

packagealgoritmos;


publicclassGreedySelection {



//Declaracion de variables

intdim, aux1 = 0, i = 0,j = 0, aux2=0,k = 0;


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 (j = 0;j < 2;j++)

a[i][j] = entrada.nextInt();


}


for (j = 0;j < 2;j++) //los valores a ordenar

System.out.printf("%d-",a[i][j]);


}

System.out.println("");



60

60

for (i = 0; i <dim; i++){ //Proceso de ordenamiento

aux2=i;


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 (j = 0;j < 2;j++) //los valores ordenados

System.out.printf("%d-",a[i][j]);


}

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


}

}

}

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



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).



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



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!.



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.

http://www.sorting-algorithms.com/

http://elpais.com/diario/2008/04/10/ciberpais/1207791626_850215.html

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=complexity1

http://www.xataka.com/otros/un-nuevo-algoritmo-mejora-el-manejo-de-miembros-artificiales-con-la-mente

http://www.xataka.com/otros/un-nuevo-algoritmo-mejora-el-manejo-de-miembros-artificiales-con-la-mente

Documents

U2.Algoritmos Computacion 1