análisis de algoritmos clase 1

INGENIERIA INFORMATICA

ING. CLAUDIA LORENA DIAZ ANALISIS DE ALGORITMOS AGOSTO 2013

INTRODUCCION Y CONCEPTOS BSICOS

ING. CLAUDIA LORENA DIAZ CARDOZO

UNICIENCIA

INGENIERIA INFORMATICA

ING. CLAUDIA LORENA DIAZ ANALISIS DE ALGORITMOS AGOSTO 2013

CONCEPTOS BSICOS

Qu es un algoritmo?

Caractersticas bsicas de un algoritmo

Cualidades de un algoritmo

Tipos de algoritmos

Lenguaje Algortmico

Problemas y algoritmos

Complejidad Algortmica.

o Como se mide la eficiencia de un algoritmo, tiempo y espacio

o Peor caso, caso promedio

o Modelo de un computador

o Medidas de complejidad

Modelos de computo

Modelo Universal de la Mquina de Turing

Problemas de complejidad polinomial

INGENIERIA INFORMATICA

ING. CLAUDIA LORENA DIAZ ANALISIS DE ALGORITMOS AGOSTO 2013

QUE ES UN ALGORITMO?

Un algoritmo implica la descripcin precisa de los pasos a seguir para alcanzar la solucin de un problema

dado. Se define como una serie de pasos organizados que describen el proceso que se debe seguir, para dar

solucin a un problema especfico.

Por pasos se entiende el conjunto de acciones u operaciones que se efectan sobre ciertos objetos.

Algoritmo: Entrada ----- Proceso --- Salida

CARACTERSTICAS BSICAS DE UN ALGORITMO

Un algoritmo debe poseer las siguientes caractersticas:

Debe tener un punto particular de inicio.

Precisin: debe ser completamente definido y no debe permitir dobles interpretaciones.

General: es decir, soportar la mayora de las variantes que se puedan presentar en la definicin del

problema.

Finito: debe ser finito en tamao y tiempo de ejecucin.

Legible: claro y fcil de interpretar y entender.

Determinismo: Todo algoritmo debe responder del mismo modo antes las mismas condiciones.

INGENIERIA INFORMATICA

ING. CLAUDIA LORENA DIAZ ANALISIS DE ALGORITMOS AGOSTO 2013

CUALIDADES DE UN ALGORITMO

Un algoritmo debe ser adems:

General: Es deseable que un algoritmo sea capaz de resolver una clase de problemas lo ms amplia posible.

Eficiente: Un algoritmo es eficiente cuantos menos recursos en tiempo, espacio (de memoria) y procesadores

consume.

Por lo general es difcil encontrar un algoritmo que rena ambas por lo que se debe alcanzar un compromiso

que satisfaga lo mejor posible los requisitos del problema.

TIPOS DE ALGORITMOS

Teniendo en cuenta la forma como describen el proceso, se pueden clasificar en:

Cualitativos: Son aquellos en los que se describen los pasos utilizando palabras.

Cuantitativos: Son aquellos en los que se utilizan clculos numricos para definir los pasos del proceso.

INGENIERIA INFORMATICA

ING. CLAUDIA LORENA DIAZ ANALISIS DE ALGORITMOS AGOSTO 2013

LENGUAJE ALGORTMICO

Es una serie de smbolos y reglas que se utilizan para describir de manera explcita un proceso, que servirn de

apoyo para describir las soluciones que aqu se plantean.

Teniendo en cuenta la forma en que describen el proceso, existen dos tipos de lenguajes algortmicos:

Grficos

Es la representacin grfica de las operaciones que realiza un algoritmo (diagrama de flujo).

Tambin se puede decir que es la representacin detallada en forma grfica de cmo deben realizarse los

pasos para producir resultados.

Esta representacin grfica se presenta mediante un conjunto de smbolos que se relacionan entre s a travs

de lneas que indican el orden en que se deben ejecutar cada uno de los procesos.

Los smbolos bsicos utilizados en los diagramas de flujo son:

INGENIERIA INFORMATICA

ING. CLAUDIA LORENA DIAZ ANALISIS DE ALGORITMOS AGOSTO 2013

Este se utiliza para representar el inicio o el fin de un algoritmo. Tambin puede representar una parada o una interrupcin programada que sea necesaria realizar en un programa.

Este se utiliza para un proceso determinado, es el que se utiliza comnmente para representar una instruccin, o cualquier tipo de operacin que origine un cambio de valor.

Este smbolo es utilizado para representar una entrada o salida de informacin, que sea procesada o registrada por medio de un perifrico.

Este es utilizado para la toma de decisiones, ramificaciones, para la indicacin de operaciones lgicas o de comparacin entre datos.

Este es utilizado para enlazar dos partes cualesquiera de un diagrama a travs de un conector de salida y un conector de entrada. Esta forma un enlace en la misma pgina del diagrama.

Este es utilizado para enlazar dos partes de un diagrama pero que no se encuentren en la misma pgina.

INGENIERIA INFORMATICA

ING. CLAUDIA LORENA DIAZ ANALISIS DE ALGORITMOS AGOSTO 2013

Recomendaciones para el diseo de Diagramas de Flujo:

Se deben usar solamente lneas de flujos horizontales y/o verticales. Se deben usar conectores solo cuando sea necesario. No deben quedar lneas de flujo sin conectar. Se deben trazar los smbolos de manera que se puedan leer de arriba hacia abajo y de izquierda a derecha. Todo texto ubicado dentro de un smbolo deber ser escrito claramente.

Pseudo cdigo

Mezcla de lenguaje de programacin y un idioma como el espaol, que se emplea dentro de la programacin

estructurada, para especificar el diseo de un programa. Se puede definir como un lenguaje de

especificaciones de algoritmos, utilizando palabras que indican el proceso a realizar.

Las palabras ms comunes son:

Inicio, fin, leer, escribir, si, sino, fin si, para, fin para, mientrasque, fin mientrasque, repita, hasta, regresar.

INGENIERIA INFORMATICA

ING. CLAUDIA LORENA DIAZ ANALISIS DE ALGORITMOS AGOSTO 2013

PROBLEMAS Y ALGORITMOS

1. Realizar un diagrama de flujo que calcule e imprima la edad de una persona dado el ao en que naci.

Anlisis

Suministrar el ao en que naci

Suministrar el ao actual

Restar el ao actual con el ao en que naci

Imprimir la edad

Algoritmo

Inicio

Suministrar ao en que naci (A)

Suministrar el ao actual (B)

Restar el ao en que naci con el ao actual

Generar el resultado

Imprimir la edad

Fin

INGENIERIA INFORMATICA

ING. CLAUDIA LORENA DIAZ ANALISIS DE ALGORITMOS AGOSTO 2013

2. Realizar un diagrama de flujo que calcule e imprima la nota final de un alumno tomando en cuenta lo siguiente.

1 semestre consta de 4 cortes

El primer corte con 25%

El segundo corte con 30%

El tercer corte con 30%

El cuarto corte con 15%

Anlisis

Calcular la nota final

Suministrar nota del primer corte (W)

Suministrar nota del segundo corte (X)

Suministrar nota del tercer corte (Y)

Suministrar nota del cuarto Corte (Z)

Realizar el algoritmo con base al anlisis y el diagrama de flujo

INGENIERIA INFORMATICA

ING. CLAUDIA LORENA DIAZ ANALISIS DE ALGORITMOS AGOSTO 2013

3. Realizar el diagrama de flujo que dado dos nmeros impriman el mayor de ellos

Anlisis

Dado dos nmeros imprimir el mayor de ellos

Darle valores a los nmeros

Comparar si X > Y

Algoritmo

1. Inicio

2. Suministrar variable x

3. Suministrar variable Y

4. Determinar si X>Y

X > Y?

SI: ir al paso 5

NO: ir al paso 6

5. Imprimir X

6. Imprimir Y

7. Fin

Realizar el diagrama de flujo teniendo en cuenta el anlisis y el algoritmo