Check the new version here

Popular channels

Programacion Algoritmica

Tema 1
PROBLEMAS
A la hora de resolver un problema mediante la utilización de una computadora no se codifica directamente un programa en un lenguaje dado; aún cuando los lenguajes de programación son inteligibles para los humanos están bastante alejados de nuestra forma de pensar y si el problema es complejo resulta muy difícil, por no decir imposible, escribir un programa en un solo paso.
Por esa razón, existen toda una serie de pasos por los que resulta necesario atravesar desde que se plantea un problema hasta que se obtiene un programa de ordenador que lo resuelve; la finalidad fundamental de esta asignatura no es convertir a los alumnos en expertos en el tema pero es necesario que conozcan unos aspectos metodológicos mínimos de cara a desarrollar su trabajo con computadoras de una forma eficaz. Esos pasos son los siguientes:
1. Entender el problema: se trata de entender la naturaleza del mismo. Cuales son los datos de entrada, cual es la posible solución, cuales son los posibles errores, etc.
2. Establecer una estrategia de resolución
3. Desarrollar un algoritmo
4. Implementación: codificación en un lenguaje de programación.
5. Prueba del algoritmo
ALGORITMOS
Un algoritmo es una combinación de instrucciones combinadas de forma adecuada para resolver un determinado problema en una cantidad finita de tiempo. Cada instrucción es una indicación sencilla y no ambigua.
Todos los días, y en todo momento ocupamos un algoritmo para realizar una tarea determinada. Ejemplo: al conducir un auto:
1. Debemos observar si el auto está en punto muerto
2. Si no está, debemos colocarlo en punto muerto o pisar el embrague
3. Debemos encender el auto
4. Debemos presionar el embrague, colocar en primera.
5. Pisamos el acelerador y soltamos el embrague.
6. Cuando el motor llega a un número determinado de revoluciones, debemos pisar el embrague y colocar en segunda.
7. Si es posible, podemos aumentar la velocidad, pero nunca acelerar más que la velocidad permitida por las normas.
8. Debemos reducir la marcha en cada esquina.
9. Debemos detenernos en cada semáforo.
10. Cuando llegamos a destino, frenar y parar el motor.
Nada más que para la persona que sabe manejar, una vez aprendido el algoritmo lo realiza en forma mecánica.
El término algoritmo, proviene del matemático persa Al Juarismi, tiene las siguientes características:
 Conjunto finito de pasos, cualquiera sea su complejidad.
 Precisión: el algoritmo debe indicar en forma precisa, y no ambigua, cual es el conjunto de pasos que resuelve el problema.
 Eficiencia: dentro de las soluciones posibles, se debe buscar la mejor o una de las mejores.
Se lo puede representar por medio de:
 Lenguaje natural
 Pseudocódigo
 Diagramas de flujo
Lenguaje natural
La primera y más sencilla forma de describir un algoritmo es empleando el lenguaje natural; por ejemplo, el algoritmo para encontrar las raíces de una ecuación de segundo grado podría describirse así:
1. Definir los coeficientes de la ecuación de segundo grado: a, b y c.
2. Determinar el valor del discriminante: b2-4ac.
3. Si el discriminante es cero sólo hay una solución: -b/(2a).
4. Si el discriminante es positivo pero no cero hay dos soluciones: (-b}√discr)/(2a).
5. Si el discriminante es negativo no hay soluciones reales.
La ventaja fundamental es la facilidad de comprensión, cualquier persona que lea dicho algoritmo podría entenderlo y aplicarlo; sin embargo, son varios los problemas que plantea describir un algoritmo de esta forma:
• El lenguaje natural no es universal, este algoritmo sería completamente inútil para los que no hablan castellano.
• El lenguaje natural es ambiguo y, por tanto, susceptible de errores.
• El lenguaje natural es demasiado amplio, lo que para una persona puede ser una instrucción sencilla puede no serlo para otra y desde luego no lo será para una computadora.
Por todo ello, se han buscado nuevas formas de describir los algoritmos que, cuando menos, sean más universales, estén mejor delimitadas y no sean ambiguas; dos técnicas que logran esto son los diagramas de flujo y las notaciones en pseudocódigo.
Pseudocódigo
El pseudocódigo (falso lenguaje) es una descripción de alto nivel de un algoritmo que emplea una mezcla de lenguaje natural con algunas convenciones sintácticas propias de lenguajes de programación, como asignaciones, ciclos y condicionales. Es utilizado para describir algoritmos en libros y publicaciones científicas, y como producto intermedio durante el desarrollo de un algoritmo.
El pseudocódigo está pensado para facilitar a las personas el entendimiento de un algoritmo, y por lo tanto puede omitir detalles irrelevantes que son necesarios en una implementación. Programadores diferentes suelen utilizar convenciones distintas, que pueden estar basadas en la sintaxis de lenguajes de programación concretos. Sin embargo, el pseudocódigo en general es comprensible sin necesidad de conocer o utilizar un entorno de programación específico, y es a la vez suficientemente estructurado para que su implementación se pueda hacer directamente a partir de él.
La definición de datos se da por supuesta, sobre todo en las variables sencillas, si se emplea formaciones: pilas, colas, vectores o registros, se pueden definir en la cabecera del algoritmo, y naturalmente cuando empleemos el pseudocódigo para definir estructuras de datos, esta parte la desarrollaremos adecuadamente.
Lenguajes de programación
Al igual que los distintos grupos humanos pueden tener lenguas distintas, la computadora también posee su propio lenguaje. Este lenguaje está diseñado para que el computador lo pueda entender con facilidad, pero desde un punto de vista humano, no es un lenguaje fácil de entender.
Mientras que nuestro alfabeto tiene 28 símbolos (letras), el alfabeto del lenguaje de la computadora sólo tiene 2: uno (1) y cero (0), y en vez de llamarlos letras le llama bits. Por lo cual se le conoce como lenguaje binario.
Mientras que nosotros usamos palabras, la computadora usa bytes y estos siempre están formados por grupos de 8 bits.
Por ejemplo la siguiente oración en lenguaje de máquina podría significar que la computadora debe apagarse o quizá que el un archivo deba grabarse en el disco rígido, etc.
00000001 00011110 10101001
Como se puede apreciar una secuencia de unos y ceros, es muy poco significativa para cualquier ser humano, por lo que los científicos de la computación diseñaron una serie de equivalencias entre números y palabras clave del lenguaje humano, a las que llamaron nemónicos. Así por ejemplo, a la secuencia 00000001 se le pudo haber llamado sumarDosNumeros, haciendo alusión a su significado. De este modo la instrucción completa quedaría escrita así:
sumarDosNumeros 00011110 10101001
Con lo que queda más claro, que la intención de la instrucción era sumar dos números (00011110 y 10101001). Este lenguaje, hecho de números y nemónicos se le llamó lenguaje ensamblador (assembler) e inicio una primera generación de lenguajes de programación conocidos como ``lenguajes de bajo nivel''. Lamentablemente, este lenguaje es demasiado simple como para construir grandes cosas (como un procesador de texto, tal como Word o una hoja de cálculo, tal como Excel) por lo que los científicos de la computación diseñaron una nueva generación de lenguajes más complejos y cercanos al lenguaje humano: los lenguajes de alto nivel.
Para que la computadora pueda entender el significado de las instrucciones de los programas escritos en un lenguaje de alto nivel se necesitó diseñar programas traductores especiales que tradujera estas complejas instrucciones a ceros y unos entendibles por la máquina.
Compiladores e Interpretes
Si necesitamos traducir un texto del inglés al castellano, deberemos hacer uso de los servicios de un traductor: una persona a la cual le entregaremos el texto en ingles y nos devolverá el texto en castellano. De otro lado, si asistimos a una conferencia y uno de los ponentes no habla castellano, es probable que necesitemos los servicios de un intérprete que realice el trabajo de traducción en línea, de modo que podamos entender el contenido de la charla.
Un programa compilador funciona como un traductor entre los programas que escribimos y el lenguaje de máquina; un interprete cumple la misma funcionalidad, aunque lo hace a la manera de un interprete humano, es decir realiza una traducción en línea.
Las diferencias son notorias, mientras que el producto de una compilación es perdurable (un texto), el resultado de un intérprete es volátil (palabras) y probablemente necesitemos reiterados procesos de traducción.
Paradigmas de Programación
Un paradigma es una forma de entender el mundo, es una forma ver las cosas y hechos que nos rodean. Los seres humanos constantemente usamos nuestros paradigmas para solucionar problemas, por ejemplo: frente a la necesidad de explicar el por qué las estrellas giran alrededor nuestro, algunos lo entendieron como voluntad divina y otros como producto de reglas predecibles y exactas.
En computación los paradigmas de programación más usados son tres:
Funcional : basado en el uso de funciones, listas y recursión como herramientas básicas para la solución de problemas. Ejemplos: Mathematica, Haskell, Scheme
Imperativo/orientado al objeto: basado en estructuras, variables e instrucciones de repetición. Ejemplos de lenguajes imperativos: C, Pascal. Ejemplos de lenguajes orientados a objetos: Java, Smalltalk, C++
Lógico: basado en reglas de inferencias (modus ponens) . Ejemplos: LISP, PROLOG
Los científicos de la computación han definido varios lenguajes, basados en estos paradigmas y se han construidos muchos programas interpretes y compiladores para cada uno de estos lenguajes.
Conceptos fundamentales:
Identificadores: Variables y constantes
Se llama identificador, a un nombre asignado a una posición de memoria o a un bloque de memoria. Pueden ser de 2 tipos:
 Constantes: si la posición de memoria no cambia en el transcurso del programa
 Variables: si la posición de memoria cambia en el transcurso del programa
Tipos de datos:
Los datos a procesar por una computadora pueden clasificarse en:
 Simples
 Estructurados
La principal característica de los datos simples es que ocupan solo una celda de memoria, por lo tanto, una variable simple hace referencia a un único valor a la vez. Dentro de este grupo de datos se encuentran: enteros, reales, caracteres, booleanos, enumerados y subrangos (los dos últimos no existen en algunos lenguajes de programación).
Los datos estructurados se caracterizan por el hecho de que con un nombre (identificador de variable estructurada) se hace referencia a un grupo de celdas de memoria. Es decir, un dato estructurado tiene varios componentes. Cada uno de los componentes puede se a su vez un dato simple o estructurado. Sin embargo, los componentes básicos (los de nivel mas bajo) de cualquier tipo estructurado son datos simples. Dentro de este grupo de datos se encuentran: arreglos, cadena de caracteres, registros y conjuntos.

Datos numéricos:
Dentro de los tipos de datos numéricos encontramos los enteros y los reales. Los enteros son números que pueden estar precedidos del signo + o -, y que no tienen parte decimal. Por ejemplo: 128 1528 -714 8530 16235 -14780
Los reales son números que pueden estar precedidos del signo + o -, y que tienen una parte decimal. Por ejemplo: 7.5 128.0 -37.865 129.7 16000.50
Datos alfanuméricos:
Dentro de este tipo de datos encontramos los de tipo carácter (simple) y cadena de caracteres (estructurados). Son datos cuyo contenido pueden ser letras del abecedario (a, b, c, ….., z), dígitos (0, 1, 2, ……, 9) o símbolos especiales (#, $, ^, * %, /, !, +, -, …., etc.). Debemos remarcar que aunque este tipo de datos pueden contener números, no pueden ser utilizados para realizar operaciones aritméticas.
Un dato tipo caracter contiene un solo caracter, y se escribe entre apostrofes. Por ejemplo: ‘a’ ‘B’ ‘$’ ‘9’ ‘-’ ‘#’ ‘f’
Un dato tipo cadena de caracteres contiene un conjunto de caracteres, y se escribe entre comillas. La longitud de una cadena depende de los lenguajes de programación, aunque normalmente se acepta una longitud máxima de 255.
“abcde” “$9#7” “Carlos Gómez” “Rosario” “754-27-22”
Datos lógicos:
Dentro de este tipo de datos encontramos los booleanos. Son datos que solo pueden tomar dos valores: verdadero (true) o falso (false).
Identificadores, constantes y variables:
Identificadores:
Los datos a procesar por una computadora, ya sean simples o estructuradas, deben almacenarse en casillas o celdas de memoria para su posterior utilización. Estas casillas o celdas de memoria (constante o variable) tienen un nombre que permite su identificación.
Se llama identificador al nombre que se les da a las casillas de memoria. Un identificador se forma de acuerdo a ciertas reglas (las mismas pueden tener alguna variante dependiendo del lenguaje de programación utilizado):
 El primer caracter que forma un identificador debe ser una letra (a, b, c, …, z).
 Los demás caracteres pueden ser letras (a, b, c, …, z), dígitos (0, 1, 2, …, 9) o el siguiente símbolo especial: _
 La longitud del identificador es igual a 7 en la mayoría de los lenguajes de programación.

Constantes:
Las constantes son datos que no cambian durante la ejecución de un programa. Para nombrar las constantes utilizamos los identificadores que mencionamos anteriormente. Existen tipos de constantes como tipos de datos, por lo tanto, puede haber constantes de tipo entero, real, caracter, cadena de caracteres, etc.
En la siguiente figura se observa que la constante NUM es de tipo entero, NREAL y NUMREA son de tipo real, y RESU de tipo cadena de caracteres. Estas constantes no cambiaran durante la ejecución del programa. Es muy importante que los nombres de las constantes sean representativos de la función que tienen las mismas en el programa.

Variables:
Las variables son objetos que pueden cambiar su valor durante la ejecución de un programa. Para nombrar las variables Se utiliza los identificadores que se explicó anteriormente. Al igual que las constantes, pueden existir tipos de variables como tipos de datos.
En la siguiente figura, la variable I es de tipo entero, tiene un valor inicial 0 y cambiará su valor durante la ejecución del programa. Las variables SUEL y SUMA son de tipo real, están inicializadas con el valor de cero y cambiarán su valor durante la ejecución del programa.

Operaciones aritméticas:
Para poder realizar operaciones aritméticas necesitamos de operadores aritméticos. Estos operadores nos permitirán realizar operaciones aritméticas entre operandos: números, constantes o variables. El resultado de una operación aritmética será un número.
Al evaluar expresiones que contienen operadores aritméticos debemos respetar la jerarquía en el orden de la aplicación. Es decir, si tenemos en una expresión más de un operador, debemos aplicar primero el operador de mayor jerarquía, resolver esa operación, y así sucesivamente. Es importante señalar que el operador ( ) es un operador asociativo que tiene la prioridad más alta en cualquier lenguaje de programación.

Las reglas para resolver una expresión aritmética son las siguientes:
1. Si una expresión contiene subexpresiones entre paréntesis, éstas se evalúan primero; respetando la jerarquía de los operadores aritméticos en ésta su
Operador Aritmético
Operación
Jerarquía
Ejemplo
Resultado
**
Potencia
(mayor)
4**3
64
*
/
mod
div
Multiplicación
División
Módulo (residuo)
División entera
8.25*7
15/4
15 mod 2
17 div 3
57.75
3.75
1
5
+
-
Suma
Resta
(menor)
125.78+62.50
65.30-32.33
188.28
32.97
0
0
0
expresión. Si las subexpresiones se encuentran anidadas por paréntesis, primero se evalúan las subexpresiones que se encuentran en el último nivel de anidamiento.
2. Los operadores aritméticos se aplican teniendo en cuenta la jerarquía y de izquierda a derecha.
Expresiones lógicas:
Las expresiones lógicas o booleanas, llamadas así en honor del matemático George Boole, están constituidas por números, constantes o variables, operadores lógicos o relaciones. El valor que pueden tomar estas expresiones es el de verdadero o falso. Se utilizan frecuentemente en las estructuras selectivas (dependiendo del resultado de la evaluación se toma por un determinado camino alternativo) y en las estructuras repetitivas (dependiendo del resultado de la evaluación se continua con el ciclo o se interrumpe al mismo).
Operadores relacionales:
Los operadores relacionales son operadores que permiten comparar dos operandos. Los operandos pueden ser números, alfanuméricos, constante o variables. Las constantes o variables, a su vez, pueden ser de tipo entero, real, caracter o cadena de caracteres. El resultado de una expresión con operadores relacionales es verdadero o falso.

Operadores lógicos:
Los operadores lógicos son operadores que permiten formular condiciones complejas a partir de condiciones simples. Los operadores lógicos son de conjunción (y), disyunción (o) y negación (no).
0
0
0
0No comments yet