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 |