ALGORITMOSALGORITMOS Y Y
ESTRUCTURAS DE ESTRUCTURAS DE DATOSDATOS
Lic. María Verónica BaldaLic. María Verónica Balda
E.E.M. Nº 7 E.E.M. Nº 7
ITINERARIO FORMATIVO: ASISTENCIA EN INFORMÁTICA
Capacidad para encontrar soluciones informáticas a Capacidad para encontrar soluciones informáticas a problemas mediante la modelización disciplinada de problemas mediante la modelización disciplinada de soluciones y descomposición en módulos.soluciones y descomposición en módulos.
Habilidad en el uso del Visual Basic.Habilidad en el uso del Visual Basic. Habilidad en el uso de buenos hábitos de programación.Habilidad en el uso de buenos hábitos de programación. Capacidad para documentar técnicamente los programas Capacidad para documentar técnicamente los programas
desarrollados (análisis, diseño, implementación, prueba, desarrollados (análisis, diseño, implementación, prueba, manuales para el usuario, etc).manuales para el usuario, etc).
Capacidad para trabajar en grupo.Capacidad para trabajar en grupo.
ObjetivosObjetivos
Solución de problemas
Solución de problemas
IntroducciónIntroducción
Pasos para la solución de un
problema
Algoritmo:concepto, ejemplos
Computadora
Unidad 1
HW SW
ComputadoraComputadoraDefinición: Máquina capaz de aceptar datos a través de un medio de entrada, procesarlos automáticamente bajo el control de un programa y proporcionar la información resultante a través de un medio de salida.
Entrada SalidaComputadora
ComponentesComponentes
HW SWBase (S.O.)
Aplicación Unidad Central de Proceso
Unidad de Memoria
Dispositivos de Entrada/Salida
Utilitarios
Lenguajes de programación
Esparcimiento
Educativos
Otros
DOS, UNIX, Windows,
MAC, etc.
HWHWModelo Refinado de ComputadoraModelo Refinado de Computadora
E S
Mem UCP
UC UAL
SWSWLenguajes de ProgramaciónLenguajes de Programación
Tipos de instrucciones ejecutadas por una computadora:
• de E/S: lectura/escritura de información
• Lógico-aritméticas
• Secuencia: Primero ejecutar una instrucción y luego otra
• Selección: si ... entonces ... sino ...
• Ciclo: Repetición de una secuencia de instrucciones
• Procedimiento: Grupo de instrucciones que pueden ser
referenciadas y ejecutadas
SWSWLenguajes de bajo nivelLenguajes de bajo nivel
Lenguajes con un pobre nivel de abstracción, en el sentido de que sus instrucciones se asemejan mucho a
las de máquina
Ejemplo: Lenguaje de Ensamblado (Assembler)
• En este tipo de lenguajes las instrucciones son nombradas por códigos mnemotécnicos.Por ejemplo: ADD, SUB, MPY, DIV, etc.
• Las instrucciones son traducidas a código de máquina mediante un ensamblador.
SWSWLenguajes de alto nivelLenguajes de alto nivel
• Lenguajes con un mayor nivel de abstracción, en el sentido de que sus instrucciones asemejan al lenguaje natural.
• Pueden ser independientes de la máquina. Por lo tanto, pueden ser traducidos a distintos lenguajes de máquina.
EjemplosPascal, C, C++, Java, Visual BASIC, COBOL, Fortran.
Prog.Fuente Compilador
Prog.Objeto
SWSW Características de un buen programaCaracterísticas de un buen programa
• Confiabilidad
• Adaptabilidad
• Legibilidad
ProblemasProblemasSolución mediante computadorasSolución mediante computadoras
No todos los problemas pueden ser resueltos por una computadora.
Problema
Solución
Un largo camino...
ProblemasProblemasPasos para solucionar un problemaPasos para solucionar un problema
ProblemaEspecificación:
datos, resultados
División del problema
Algoritmo
Programa fuente
Programa ejecutable
Solución
• AnálisisAnálisis El problema debe ser claramente especificado y entendido.
• DiseñoDiseñoConstrucción de una solución general del problema.
• Especificación de algoritmosEspecificación de algoritmosObtener la secuencia de pasos a seguir para resolver el problema• Escritura de programasEscritura de programasTraducción del algoritmo a un lenguaje de programación de alto nivel
• Compilación y VerificaciónCompilación y VerificaciónTraducción del programa a un lenguaje entendido por la computadora. Corrida y prueba de funcionamiento del programa.
ProblemasProblemasPasos para solucionar un problemaPasos para solucionar un problema
•El proceso de resolución de problemas no es una lista de pasos que se ejecuta en forma lineal.
•Tiene una naturaleza dinámica y cíclica.
•La detección de errores en cualquiera de las etapas puede llevar a revisar aspectos analizados previamente
ProblemasProblemasPasos para solucionar un problemaPasos para solucionar un problema
ProblemaEspecificación:
datos, resultados
División del problema
Algoritmo
Programa fuente
Programa ejecutable
Solución
• AnálisisAnálisis El problema debe ser claramente especificado y entendido.
• DiseñoDiseñoConstrucción de una solución general del problema.
• Especificación de algoritmosEspecificación de algoritmosObtener la secuencia de pasos a seguir para resolver el problema• Escritura de programasEscritura de programasTraducción del algoritmo a un lenguaje de programación de alto nivel
• Compilación y VerificaciónCompilación y VerificaciónTraducción del programa a un lenguaje entendido por la computadora. Corrida y prueba de funcionamiento del programa.
Pasos para solucionar un problemaPasos para solucionar un problemaAnálisisAnálisis
• El problema debe estar bien definido para poder obteneruna solución satisfactoria.• Los datos de entrada y los resultados (salida) deben ser precisamente descriptos.
Preguntas concernientes a la entrada:
- ¿Cuáles y cuántos son los valores de entrada?
- ¿Cuáles son valores válidos de entrada?
Preguntas concernientes a los resultados (salida):
- ¿Cuáles y cuántos son los valores del resultado?
- ¿Cuáles son valores válidos del resultado?
- ¿Cómo se llega a esos resultados (fórmulas, ecuaciones, etc.)?
Pasos para solucionar un problemaPasos para solucionar un problemaAnálisis Análisis (cont.)(cont.)
Ejemplo de ProblemaDesarrollar un algoritmo que calcule el área de un cuadrado.
Preguntas concernientes a la entrada:
- ¿Cuáles y cuántos son los valores de entrada? Lado del cuadrado
- ¿Cuáles son valores válidos de entrada? Números reales+
Preguntas concernientes a los resultados (salida):
- ¿Cuáles y cuántos son los valores del resultado? Area del cuadrado
- ¿Cuáles son valores válidos del resultado? Números reales+
- ¿Cómo se llega a esos resultados? Fórmula área de un cuadrado
Dato/s: lado del cuadrado es número real+ (lado)
Resultado/s: área del cuadrado es número real+ (areaCuad)Además debo saber que (adicionales): área = lado * lado
Cuando los problemas adquieren cierta complejidad puede ser visto como la composición de varios (sub)problemas de menor complejidad.
Subproblemas:
(1) lectura de datos
(2) cálculo del área
(3) exhibir resultados
Nota: en este caso la complejidad del problema no justifica los subproblemas. Es sólo a modo de ejemplo.
Pasos para solucionar un problemaPasos para solucionar un problemaDiseñoDiseño
Algoritmo AreaCuadrado
Var
lado R {variables datos}
areaCuad R {variables resultados}
Inicio
leer lado
areaCuad = lado * lado
escribir(’El area es: ', areaCuad)
Fin
Pasos para solucionar un problemaPasos para solucionar un problemaEspecificación de algoritmosEspecificación de algoritmos
• Compilar el programa construido. - Detección de errores (mayoritariamente sintácticos).
• Ejecutar el resultado de la compilación. - Procesamiento de datos de entrada. - Detección de errores semánticos.• Testeo - Probar el programa con una serie de valores de entrada y verificar que produce el resultado esperado en todos los casos.
Pasos para solucionar un problemaPasos para solucionar un problemaCompilación yCompilación y VerificaciónVerificación
Salida
Fuente
Compilador
Programa Objeto
Linkeador
Bibliotecas, Units, Obj
ProgramaEjecutable
Datos
Pasos para solucionar un problemaPasos para solucionar un problemaCompilación y Verificación Compilación y Verificación (cont.)(cont.)
Programa
Programa Assembler
Ensamblador
Turbo Pascal
ProblemasProblemasPasos para solucionar un problemaPasos para solucionar un problema
ProblemaEspecificación:
datos, resultados
División del problema
Algoritmo
Programa fuente
Programa ejecutable
Solución
• AnálisisAnálisis El problema debe ser claramente especificado y entendido.
• DiseñoDiseñoConstrucción de una solución general del problema.
• Especificación de algoritmosEspecificación de algoritmosObtener la secuencia de pasos a seguir para resolver el problema• Escritura de programasEscritura de programasTraducción del algoritmo a un lenguaje de programación de alto nivel
• Compilación y VerificaciónCompilación y VerificaciónTraducción del programa a un lenguaje entendido por la computadora. Corrida y prueba de funcionamiento del programa.
AlgoritmoAlgoritmo
Definición: Un algoritmo es una sucesión finita de instrucciones o pasos no ambiguos que se pueden ejecutar en un tiempo finito para resolver un problema.
Algoritmo: del árabe Al-Khuwarizmi, matemático del siglo IX
Definición
AlgoritmoAlgoritmo
Características:
• Debe ser preciso e indicar el orden de realización de cada paso. • Se debe obtener el mismo resultado cada vez que se aplica a los mismos datos.• Se debe terminar en algún momento.
En la vida cotidiana empleamos algoritmos en multitud de ocasiones. También existen ejemplos de índole matemática (algoritmo de la división, Euclides, Gauss, Valor Medio, etc.)
Definición (cont.)
AlgoritmoAlgoritmo
Ejemplo
Cambiar una lámpara
•Ubicar la escalera debajo de la lámpara quemada
•Tomar una lámpara nueva
•Subir por la escalera
•Girar la lámpara hacia la izquierda hasta sacarla
•Enroscar la lámpara nueva hasta ajustarla
•Bajar de la escalera
•Fin
EjemplosEjemplos
Ejemplo 1:Ejemplo 1:
ProblemaProblema: Indique la manera de salar una : Indique la manera de salar una masamasa
MaloMalo: Ponerle algunas especies a la masa: Ponerle algunas especies a la masa
BuenoBueno: Agregarle una cucharadita de sal la : Agregarle una cucharadita de sal la masamasa
EjemplosEjemplos
Ejemplo 2Ejemplo 2::
ProblemaProblema: Determinar si el número 7317 es primo: Determinar si el número 7317 es primo
MaloMalo: Divida el número 7317 entre sus anteriores : Divida el número 7317 entre sus anteriores buscando aquellos que lo dividan exactamentebuscando aquellos que lo dividan exactamente
BuenoBueno: Divida el número 7317 entre cada uno de : Divida el número 7317 entre cada uno de los números 2,3,4,…., 7315,7316. Si una de las los números 2,3,4,…., 7315,7316. Si una de las divisiones es exacta, la respuesta es no. Si no divisiones es exacta, la respuesta es no. Si no es así, la respuesta es sí.es así, la respuesta es sí.
EjemplosEjemplos
Ejemplo 3:Ejemplo 3:
ProblemaProblema: Obtener un millón de pesos: Obtener un millón de pesos
MaloMalo: Ir a las Vegas y obtener un millón de : Ir a las Vegas y obtener un millón de pesos en fichaspesos en fichas
BuenoBueno: Hacer apuestas con la máquina : Hacer apuestas con la máquina “tragamonedas” hasta obtener: a) un “tragamonedas” hasta obtener: a) un millón de pesos o b) ninguna fichamillón de pesos o b) ninguna ficha
EjemplosEjemplos
Ejemplo 4:Ejemplo 4:
ProblemaProblema: Llene esta zanja con ese montón : Llene esta zanja con ese montón de arenade arena
AlgoritmoAlgoritmo: Tome una pala y empiece a : Tome una pala y empiece a echar arena en la zanja. Cuando se llene echar arena en la zanja. Cuando se llene la zanja, deténgasela zanja, deténgase
Este algoritmo es simple, no es ambiguo y tiene fin
Para practicarPara practicar
Escribir un algoritmo que te permita llegar Escribir un algoritmo que te permita llegar desde tu casa a la escueladesde tu casa a la escuela
Escribir un algoritmo que describa la Escribir un algoritmo que describa la manera de preparar un sandwichmanera de preparar un sandwich
Escribir un algoritmo que determine si un Escribir un algoritmo que determine si un número ingresado es par o imparnúmero ingresado es par o impar