Resumen

Tema N°2

Algorítmica elemental o fundamentos de programación

Introducción.-En este capitulo empezamos el estudio de los algoritmos. Empezaremos definiendo algunos términos tales como algoritmo, problema, instancia como eficiencia e investigaremos métodos para probar la eficiencia de los mismos.
Existen métodos formales para realizar pruebas rigurosas sobre la corrección de los programas,esta temática esta fuera del alcance del texto pero será mencionada mas adelante solo como referencia.
Algoritmo.- Definimos como algoritmo a un conjunto de pasos necesarios para resolver un problema ya sea manualmente o por métodos mecanizado que, son los más usuales en la actualidad. El concepto de algoritmo fue definido inicialmente por el matemático persa Al-Khowarizmi en el siglo 19 laejecución de un algoritmo no debe incluir procedimientos intuitivos o que requieran creatividad. Por ejemplo una receta de cocina puede denominarse un algoritmo si contiene las instrucciones precisas para preparar algo, siempre y cuando no tenga detalles tales como sal al gusto, o cocinar hasta que este suave, que son apreciaciones subjetivas del que prepara la receta.
Debemos indicar que losalgoritmos deben cumplir con un requisito fundamental y es que todo algoritmo debe terminar en un número finito de pasos, si consideramos el sistema operativo que no es un algoritmo porque ni termina nunca dado que esta en un círculo infinito.
Podemos dar algunos ejemplos conocidos de algoritmos dados el método de multiplicar que aprendimos en la escuela, el algoritmo para verificar si un número esprimo y muchos otros.
Problemas e instancias.- si pensamos en los procedimientos para multiplicar números reconocemos que hay varias formas veremos que hay varias formas de resolver el problema de multiplicación. Tenemos los métodos que aprendimos en la escuela, métodos por división y multiplicación por 2 denominado multiplicación a la rusa y otros. ¿Cuál de estas posibles soluciones hay queimplementar? Esta decisión corresponde a un área muy desarrollada en el campo de la informática denominada análisis de algoritmos.
Una instancia particular seria por ejemplo multiplicar el numero 123 por el 4567 pero un algoritmo debe ser capaz de funcionar correctamente no solo en una instancia del método sino mas bien en todas las instancias posibles.
Para demostrar que un algoritmo es incorrectoes suficiente demostrar que es incorrecto para iuna instancia. Así como es difícil probar que un teorema es correcto también es difícil probar que un algoritmo es correcto.
Existen limitaciones propias de la computadora que ponen restricciones en los algoritmos. Estas pueden ser debido al tamaño de los números, espacio de memoria o almacenamiento.
En el análisis de los algoritmos se trata deanalizarlos en forma abstracta inicialmente, pero en el transcurso del texto también tocaremos aspectos específicos sobre la implementación y la eficiencia de los mismos
Eficiencia.- cuando tenemos que resolver un problema pueden existir muchos algoritmos disponibles obviamente quisiéramos escoger el mejor. De aquí nos viene la pregunta ¿Cuál es el mejor si tenemos un problema sencillo si tenemosunas pocas instancias escogemos, lo mas fácil y nos despreocupamos de la eficiencia . Para analizar esto tenemos 2 métodos: el método empírico también llamado posterior, consiste en programar todos los métodos y probarlos con diferentes instancias y con la ayuda de la computadora analizaremos y escogeremos algunos. El segundo llamado método a priori es el análisis teórico del algoritmo, quecon la ayuda del as matemáticas podemos determinar la cantidad de los recursos requeridos por cada algoritmo en base al tamaño de las instancias consideradas. El tamaño de una instancia considerada. El tamaño normalmente esta definida por el número de BITS en el caso de un grafo por el número de nodos y vértices, o en otros por el número de elementos a procesar la ventaja del método teórico es...