Unidad 1 - Introduccion a Algoritmos y resolucion de problemas PDF

Preview

Summary

Introduccion a Algoritmos y resolucion de problemas...

Description

2017 Algoritmos y Resolución de Problemas

UNSJ DEPARTAMENTO DE INFORMÁTICA FACULTAD DE CIENCIAS EXACTAS, FÍSICAS Y NATURALES

Algoritmos y Resolución de Problemas

2

Índice UNIDAD 1: ALGORITMOS ...................................................................................................................... 5 INTRODUCCIÓN ..................................................................................................................................... 5 1.1 RESOLUCIÓN DE PROBLEMAS CON UNA COMPUTADORA .............................................................. 7 1.1.1 ¿QUÉ ES UN PROBLEMA? ...................................................................................................................... 7 1.1.2 ¿CUÁLES SON LOS COMPONENTES DE UN PROBLEMA? ................................................................................ 7 1.1.3 ETAPAS PARA RESOLUCIÓN DE PROBLEMAS USANDO COMO HERRAMIENTA LA COMPUTADORA. ........................... 8 Acciones básicas de una computadora................................................................................................ 8 1.2 ALGORITMOS ................................................................................................................................13 1.2.1 CONCEPTO DE ALGORITMO .................................................................................................................. 13 1.2.2 ESTRUCTURA DE UN ALGORITMO .......................................................................................................... 15 1.2.3 ELEMENTOS DE UN ALGORITMO ........................................................................................................... 15 DATOS ...................................................................................................................................................... 16 ATRIBUTOS DE LOS DATOS ............................................................................................................................ 16 VARIABLES Y CONSTANTES ............................................................................................................................ 17 IDENTIFICADOR DE VARIABLES Y CONSTANTES ................................................................................................... 17 TIPOS DE DATOS ......................................................................................................................................... 18 TIPOS DE DATOS SIMPLES ............................................................................................................................. 18 Tipo de Dato Numérico ...................................................................................................................... 18 Tipo de Dato Caracter ........................................................................................................................ 19 Tipo de Dato Lógico ........................................................................................................................... 21 TIPOS DE DATOS ESTRUCTURADOS ................................................................................................................. 22 Tipo de Dato Cadena ......................................................................................................................... 22 EXPRESIONES ............................................................................................................................................. 23 Expresiones aritméticas ..................................................................................................................... 23 Expresiones relacionales .................................................................................................................... 25 Expresiones lógicas ............................................................................................................................ 26 ACCIONES.................................................................................................................................................. 29 Acciones Simples ................................................................................................................................ 30 Acción de Lectura............................................................................................................................... 30 Acción de Asignación ......................................................................................................................... 31 Acción de Escritura ............................................................................................................................ 33 1.3 RESOLUCIÓN DE PROBLEMAS. .......................................................................................................35 CONSTRUCCIÓN DE ALGORITMOS SIMPLES........................................................................................................ 35 ANÁLISIS DEL PROBLEMA .............................................................................................................................. 35 ASERTOS, PRECONDICIONES Y POSTCONDICIONES ............................................................................................. 38 DISEÑO DEL ALGORITMO ............................................................................................................................. 39 1.4 TRAZA O SEGUIMIENTO DE UN ALGORITMO. ...............................................................................44 1.5 ACCIONES ESTRUCTURADAS ...........................................................................................................45 SECUENCIA ................................................................................................................................................ 45 SELECCIÓN................................................................................................................................................. 46 Alternativa Doble ............................................................................................................................... 46 Alternativa Simple ............................................................................................................................. 49 Estructuras Alternativas Anidadas .................................................................................................... 50 ALTERNATIVA MÚLTIPLE .............................................................................................................................. 51 ITERACIÓN ................................................................................................................................................. 54 Estructura Para - FinPara................................................................................................................... 54 Estructura Mientras - FinMientras .................................................................................................... 58 Estructura Hacer - Mientras ............................................................................................................ 64 Bucles Anidados ................................................................................................................................. 65 1.6 CONTADORES Y ACUMULADORES ..................................................................................................68 Algoritmos y Resolución de Problemas

3

1.7 ESTRATEGIA PARA INTERPRETACIÓN DE ENUNCIADOS CON ITERACIÓN........................................ 71 1.8 CÁLCULO DE MÁXIMOS Y MÍNIMOS DE UN CONJUNTO DE VALORES ............................................ 75 1.9 BIBLIOGRAFÍA ............................................................................................................................... 78 PRÁCTICO 1: DATOS SIMPLES ...........................................................¡ERROR! MARCADOR NO DEFINIDO.

Algoritmos y Resolución de Problemas

4

Unidad 1: Algoritmos

Unidad 1: Algoritmos Introducción Constantemente el hombre se enfrenta a innumerables problemas que debe resolver. Muchas soluciones las logra apelando a lo aprendido con su experiencia que ha logrado internalizar con el correr del tiempo. Para otras, necesita el apoyo de herramientas aportadas por diversas ramas de la tecnología, siendo la computadora una de las de mayor influencia. La computadora permite resolver problemáticas, mediante la ejecución de programas previamente cargados en ella. La construcción de estos programas requiere una serie de etapas desde el planteamiento del problema hasta llegar a obtener los resultados del mismo. Es necesario tener en cuenta que la computadora no puede resolver problemas sin que el hombre la programe, es decir, determine la forma, y recursos necesarios para hacerlo. La computadora en sus inicios aceptaba programas con instrucciones escritas en ceros y unos (lenguaje binario). Esta condición dificultó la creación de programas más grandes y complejos lo que originó el puntapié inicial para la generación de un canal de comunicación hombre-máquina, que permitiera interpretar nuestras solicitudes y a nosotros comprender sus resultados y mensajes. Esta necesidad de comunicación llevó al desarrollo de los lenguajes de programación. Aprender un lenguaje de programación no resulta una tarea complicada, lo complejo es encontrar el camino adecuado para la resolución de la problemática planteada. Es claro, que dar respuesta a un problema utilizando una computadora exige conocimientos, reflexión, razonamiento lógico y alguna dosis de ingenio y sagacidad. Algunas personas aplican, generalmente de forma inconsciente, una serie de métodos y mecanismos que suelen resultar adecuados para abordar problemas. Estas operaciones mentales se conocen como procesos heurísticos. Una heurística es una regla práctica basada en la experiencia, sobre la cual no existe garantía de llegar a una solución. Una persona puede aprender estrategias que aumenten su capacidad para resolver problemas, que de otra manera le hubieran resultado “difíciles”. Una estrategia, es un método general, una guía que puede aplicarse para hallar la resolución de muchas clases de problemas. Existen diferentes estrategias para enfrentar la resolución de un problema.

El objetivo de esta unidad es resolver problemas utilizando como herramienta una computadora. Para ello se aprenderá a construir algoritmos, esto es, un conjunto de pasos que la computadora deberá realizar para llegar a la solución requerida.

Algoritmos y Resolución de Problemas

5

Introducción

RESOLUCIÓN DE PROBLEMAS

COMPUTADORA usando

ALGORITMOS requiere construir

Figura 1.1 Resolución de problemas con la computadora

Para cumplir con el objetivo propuesto se requiere el abordaje de los tres ejes involucrados: el concepto de problema, sus componentes y etapas necesarias para su resolución, las acciones básicas que puede realizar una computadora y el concepto de algoritmos que incluye el análisis de su estructura.

requiere

Etapas

RESOLUCIÓN DE PROBLEMAS

zusand

Computadora

Requiere construir

ALGORITMOS poseen

identifica

relacionadas

relacionados

componentes Datos Tipos de Datos

Cálculos

Expresiones

estructura

Acciones

Tipos de acciones simples

estructuradas

Figura 1.2 Esquema completo: Resolución de problemas con la computadora

Se comenzará la unidad definiendo lo que se entiende por problema, cuáles son sus componentes y se describirán las etapas necesarias para que sea resuelto por una computadora.

Algoritmos y Resolución de Problemas

6

1.1 Resolución de problemas con una computadora

1.1 Resolución de problemas con una computadora 1.1.1 ¿Qué es un Problema? Un problema es un desafío intelectual, ya que para llegar a una solución se deben desarrollar actitudes, hábitos y formas de pensamiento; se requiere aplicar y vincular conocimientos previos, probablemente de áreas diferentes, buscando nuevas relaciones. Es importante definir qué se entiende por problema, considerando que esta palabra es usada en contextos diferentes y con matices diversos. Etimológicamente, la palabra problema deriva del griego proballein y significa algo lanzado hacia delante. Un problema es un asunto o un conjunto de cuestiones que se plantean para ser resueltas. El diccionario de la Real Academia Española da cinco acepciones diferentes para la palabra problema, pero la más adecuada en el contexto de este documento es: “Planteamiento de una situación cuya respuesta desconocida debe obtenerse a través de métodos científicos”. Otras definiciones son: …"Tener un problema significa buscar, conscientemente, alguna acción apropiada para alcanzar o lograr el propósito claramente concebido; pero no inmediatamente alcanzable. Resolver un problema significa encontrar tal acción." (Polya, 1965) "...es una situación en la cual un individuo actúa con el propósito de alcanzar una meta utilizando para ello una estrategia particular " (Chi y Glaser, 1983). En este último caso, lograr una meta significa alcanzar una solución. Resolver el problema significa realizar actividades que operen sobre un estado inicial para lograr la solución. En general se habla de un problema, cuando se plantea una situación cuya solución no es evidente, representa un obstáculo. 1.1.2 ¿Cuáles son los componentes de un Problema? En los problemas se pueden distinguir cuatro componentes (Mayer, 1983): Meta: lo que se desea lograr. Datos: información disponible para comenzar a analizar la situación problemática. Esto es, el conjunto de elementos que representa el conocimiento relacionado con el problema. Restricciones: factores que limitan la vía para llegar a la solución. Métodos: se refieren a los procedimientos utilizados para resolver el problema. Datos + Restricciones

para alcanzar

Meta

utilizando

Métodos

Figura 1. 4

Algoritmos y Resolución de Problemas

Componentes de un Problema

7

1.1 Resolución de problemas con una computadora Existen problemas de distinta naturaleza: matemáticos, químicos, filosóficos, etc. En este libro, se analizarán problemas cuyas soluciones se deben obtener utilizando una serie de órdenes que se introducen a la computadora para que ésta las ejecute. 1.1.3 Etapas para resolución de problemas usando como herramienta la computadora. La computadora es un dispositivo electrónico programable capaz de almacenar y procesar información. Pero, por sí sola no es capaz de resolver un problema; es necesario considerar tres elementos en el proceso:

Figura 1.5 Elementos que intervienen en la resolución de un problema con una computadora.

 



Elemento humano: llamado programador, es el elemento más importante, sin él la computadora no podría resolver ningún problema. Elemento lógico: llamado Software: es el conjunto de programas, datos, información, que hacen posible el uso y funcionamiento del computador. Se clasifica en Software de base (Sistemas operativos, que controla el funcionamiento del equipo físico y gestiona todos sus recursos) y los software de aplicación (conjunto de programas diseñados con el fin de resolver distintos problemas). Elemento físico: llamado Hardware: conformado por los componentes propios de la computadora. Entre sus principales componentes citamos: las unidades o dispositivos de entrada y de salida, la unidad central de proceso (unidad de control, unidad aritmética lógica y memoria). (Ver Fig. 1.6)

Mediante el hardware -elemento físico- y el software de base -sistemas operativos- la computadora es capaz de realizar las siguientes acciones básicas:

Acciones básicas de una computadora 1. Reconocer distintos tipos de datos 2. Almacenar los datos en memoria. 3. Realizar operaciones aritméticas, relacionales y lógicas, mediante un subsistema conocido como Unidad Aritmético-Lógica (UAL). 4. Reconocer y ejecutar acciones simples y estructuras lógicas de control.

Algoritmos y Resolución de Problemas

8

1.1 Resolución de problemas con una computadora UNIDAD CENTRAL DE PROCESO

UNIDADES O DISPOSITIVOS DE

ENTRADA (Teclado)

UAL (Unidad Aritmético lógica)

Unidad de Control

UNIDADES O DISPOSITIVOS DE

SALIDA (Monitor, impresora)

MEMORIA

Figura 1.6 Componentes de hardware de una computadora

A partir de estas acciones básicas es posible que el programador pueda construir programas (software de Aplicación) que permitan resolver problemas de la vida real. Buscar la solución de problemas es una tarea compleja de sistematizar, puede pensarse como un proceso de búsqueda en un espacio de soluciones potenciales, y para ello se pueden tener en cuenta ciertas pautas para facilitarla Así, George Polya, considerado el padre de las Estrategias para la Solución de Problemas fue un matemático húngaro cuyos aportes incluyen documentos y libros que promueven un acercamiento al conocimiento y desarrollo de estrategias en la solución de problemas. Su famoso libro Cómo Plantear y Resolver Problemas, introduce su método de cuatro pasos y estrategias específicas útiles en la solución de problemas: Los cuatro pasos propuestos por Polya son los siguientes: 1. Entender el problema. 2. Configurar un plan. 3. Ejecutar el plan. 4. Mirar hacia atrás (verificar procedimientos y comprobar resultados) La teoría de Polya brinda bases sobre las cuales se pueden establecer las etapas para resolver un problema con una computadora. Para llegar a ser un programador eficaz se necesita aprender a resolver los problemas de un modo riguroso y sistemático. Existen diversas estrategias para configurar el plan que resuelve un problema, la que se adecua y se utilizará es la de construcción de algoritmos.

Algoritmos y Resolución de Problemas

9

1.1 Resolución de problemas con una computadora A partir de las etapas que define Polya se proponen las siguientes etapas para la resolución de problemas con una computadora.

Etapas resolución de problemas utilizando computadoras

Objetivo

Análisis del problema

Ayuda a la comprensión del problema, a comprender ¿qué se debe hacer?

Diseño del Algoritmo

Se determina ¿cómo se debe hacer? Permite indicar cómo el algoritmo realizará la tarea

Codificación: Construcción del programa Compilación y ejecución

Se traduce el algoritmo a un lenguaje de programación para que pueda ser interpretado y ejecutado por una computadora.

Validación

Permite comprobar la solución obtenida

Documentación

Se registra lo que se realiza durante todo el proceso, y en cada una de las distintas etapas.

Tabla 1.1 Etapas resolución de problemas utilizando computadoras

Análisis del problema Diseño del algoritmo PROBLEMA

Construcción del Programa Validación

Compilación y Ejecución

Validación de resultados

Documentación Figura 1.7 Temporalidad de las etapas en la resolución de problemas con la computadora

Si bien el objetivo de este libro está centrado las dos primeras etapas, se describirá brevemente en qué consiste cada una de ellas.

Algoritmos y Resolución de Problemas

10

1.1 Resolución de problemas con una computadora Etapa I: Análisis del problema La primera condición al momento de resolver un problema, es contar con un enunciado preciso y claro, que no contenga ningún tipo de ambigüedades. Esto es fundamental ya que la correcta resolución de un problema viene determinada en gran medida por el planteamiento inicial, no se puede abordar una solución mientras no se tenga claro a donde se q...