La presente monografía
presenta en una primera parte una introducción al diseño
de los algoritmos,
mediante una variante de seudo código
que permite luego la implementación de los algoritmos en
diferentes lenguajes de
programación y al análisis de los mismos. La segunda parte
esta dedicada al análisis de complejidad, sensibilidad y
condicionamiento de los algoritmos.
Introducción
Por "Informática" se entiende la ciencia que
estudia los procesos de
transmisión, acumulación y tratamiento de la
información. El término fue
introducido por los franceses, "Informatique", a fines de
los años 60 del siglo pasado, aunque antes los
norteamericanos habían introducido el término
"Computer Science" para asignar la ciencia sobre
la transformación de la información, basada en las
técnicas de cómputo. Hoy ambos
términos se emplean como equivalentes.
El concepto de
Informática abarca las esferas ligadas con la
elaboración, creación, empleo y
mantenimiento
material y técnico de los sistemas de
procesamiento de la información, lo que incluye el
hardware y el
software, los
aspectos de organización y sus efectos: industriales,
de servicio,
comerciales, sociales y políticos.
La Informática queda constituida por cuatro componentes
vinculados indisolublemente: información, algoritmo,
software y el hardware.
Observación 1: El material que se presenta
está dedicado al segundo de estos componentes el "
Algoritmo ".
El desarrollo
alcanzado por la Informática, su utilización en
todas las esferas de la actividad humana, hace necesario la
búsqueda de nuevos y más
eficientes algoritmos. La disciplina que
estudia los algoritmos en todos sus aspectos se ha nombrado "
Algorithmique" por Donald Knuth, en un texto
francés de 1976. Pero la comunidad
internacional ha aceptado el término "
Algorítmica ".
Diseño de
algoritmos
I.1 Noción de algoritmo:
En el estudio del Cómputo (la Informática en
general), las siguientes preguntas se presentan desde el primer
momento:
¿Qué problemas
pueden ser resueltos por un algoritmo (programa) de
cómputo?
¿Qué soluciones
pueden ser obtenidas eficientemente en la práctica?
Estas preguntas parecen ser lo suficientemente vagas para no
permitir una respuesta exacta. Por lo tanto de intentar dar una
respuesta a las mismas debemos definir, de manera precisa,
¿qué entendemos por algoritmo?, ¿qué
agente de cómputo vamos a emplear para ejecutar el
algoritmo que resuelve el problema planteado?,
¿cómo nosotros mediremos la efectividad
práctica de las soluciones?
El concepto de algoritmo procede del nombre del
matemático del Asia Central
Al-Jwarizmi en el siglo IX, se empleaba en las matemáticas de la época para
designar las reglas de las cuatro operaciones
aritméticas, convirtiéndose en una de las nociones
básicas de la Matemática. En nuestros días este
concepto es usado en muchas esferas de la actividad humana.
Antes de dar la noción de algoritmo aclaremos el
término agente de cómputo (procesador de la
información): es un medio, cuya tarea es: dada una data
inicial, ejecutar las reglas del algoritmo paso a paso,
hasta obtener la data final (resultados), este puede ser humano,
mecánico, electrónico, etc. 
La definición de algoritmo puede ser más
específica, pero de manera informal (intuitiva) puede ser
enunciado como sigue:
Un algoritmo es un procedimiento
finito y sistemático, para procesar información
simbólica discreta por un agente de cómputo, paso a
paso y sin ambigüedad.
La noción intuitiva de algoritmo por su vaguedad y
falta de rigor no puede ser aceptado como una definición
formal, por lo que ha sido objeto de estudio continuo de la
comunidad de
investigadores.
Las tareas típicas del algoritmo fueron: el cálculo
numérico, los problemas de ordenamiento y búsqueda.
En nuestros días sus esferas se han extendido a la
solución de problemas de las más variadas
áreas de la actividad humana (la ciencia, la producción, los servicios,
etc.)
En la teoría
clásica de la Informática se consideran dominios de
información discretos. El caso de conjuntos de
información continua ha sido extendido recientemente por
Blum, Shub y Smale (1989). Esta nueva extensión
teórica representa un desarrollo importante que extiende
los conceptos de recursividad y complejidad a nuevos campos
matemáticos como el análisis y la
topología.
Observación 2: Nosotros excluiremos el caso en
que la información a procesar es un conjunto
continuo.
A lo largo de la historia muchos problemas
han sido resueltos mediante técnicas de cómputo.
Sin embargo, un estudio sistemático de los algoritmos
sólo se ha desarrollado a partir de las últimas
décadas del pasado siglo.
Dos hecho han contribuido substancialmente al crecimiento de
estos estudios. Uno es el estudio de la definición formal
de algoritmo a partir de 1936, precedido por los resultados en
los estudios de la lógica
matemática de finales del siglo XIX. El otro es
el desarrollo alcanzado por las computadoras
electrónicas, cuyo uso ha invadido toda la actividad
humana lo cual ha requerido de estudios profundos para lograr un
uso eficaz de las mismas.
Página siguiente  |