Facultad Politcnica Departamento de Informtica
Algoritmo Ao: 2015
Prof. Victor E. Hermosilla M.
CLASE #1 / CLASE #2 27-julio-2015 27-julio-2015
Informacin sobre la ctedra
Asistencia: opcional pero recomendable
Derecho a examen final:
Entregar al menos 70% de las tareas entregadas
Obtener el puntaje requerido en los exmenes parciales
Promedio ponderado (puntaje final = EF*0,6 + PP*0,4)
70% Evaluaciones parciales
30% Tareas (como trabajo prctico)
Entrega de tareas:
En forma individual
Se har va EDUCA (educa.pol.una.py). Para ello cada alumno debe
registrarse.
En Educa podr obtener algunos ejemplo de exmenes
anteriores
Algoritmo Dpto. Informtica 2
Informacin sobre la ctedra
Exmenes:
Se podrn utilizar todos los materiales
Se har todo lo posible para que los exmenes se hagan en mquina dependiendo de la cantidad de personas y disponibilidad en sala de mquinas.
Recomendaciones para el curso:
Buscar un grupo de estudio
Practicar, practicar y practicar.. el xito que pueda tener en esta
materia es directamente proporcional al tiempo y esfuerzo que
dedica para realizar los ejercicios.
Herramientas
Utilizaremos SL como medio para representar algoritmos. Puede
encontrar el manual y el entorno en: http://www.cnc.una.py/sl
Para las prcticas de lenguaje C utilizaremos un entorno de
distribucin gratuita Dev-C++
http://www.bloodshed.net/devcpp.html
Algoritmo Dpto. Informtica 3
Contenido de la materia
Introduccin: conceptos bsicos sobre problemas, algoritmos, programas, anlisis de problemas,
representacin de algoritmos
Tipo de datos simples, operaciones primitivas y
expresiones.
Estructura de un programa Estructuras de control.
Cadenas
Subprogramas
Tipo de datos estructurados y definidos por el usuario
Archivos
Breve introduccin a la programacin utilizando
lenguaje C
Algoritmo Dpto. Informtica 4
Qu veremos hoy y la prxima clase?
Introduccin conceptual
Problemas, algoritmos y programas
Anlisis de problemas
Caractersticas y representacin de algoritmos
Conceptos bsicos
Variables, constantes, expresiones, entrada/salida de datos.
asignacin, tipo de dato,
Algoritmos lineales
Algoritmo Dpto. Informtica 5
Problema:
Es una tarea a ser realizada. La definicin de un problema no
incluye las restricciones o la forma de resolverlo. Un mtodo de
solucin debe ser desarrollado solo despus de que el problema
sea suficientemente definido y comprendido.
En algunas ocasiones la definicin del problema puede incluir
ciertas restricciones. Por ejemplo la cantidad de recursos que
deben ser utilizados para una solucin aceptable.
Desde el punto de vista matemtico:
Un problema es una funcin que mapea ciertos valores de entrada (llamado dominio) a (llamado rango)
ciertos valores de salida
F dominio rango
Algoritmo Dpto. Informtica 6
Algoritmo:
Palabra viene del nombre de un matemtico y astrnomo rabe
Abu Ja'far Mohammed ibn Musa al-Khowarizmi (825) (Padre de Ja'far, Mohammed, hijo de Moiss, natural de Khowarizm).
Escribi el clebre libro Kitab al jabr w'al-muqabala(Reglas de restauracin y reduccin -- > algebra)
Concepto: Es una posible solucin a un problema. Es un mtodo o
proceso sistemtico para resolver el problema (siempre que cumpla
ciertas condiciones).
Otra definicin(RAE): conjunto ordenado y finito de operaciones que
permite hallar la solucin de un problema
Propiedades de un algoritmo
Es correcto: logra resultados correctos.
Tiene pasos concretos, donde cada paso es realizado en una cantidad finita de tiempo. Esta bien definido.
No es ambiguo. Siempre se obtiene los mismos resultados con los mismos datos de entrada.
Compuesta por una cantidad finita de pasos.
Debe terminar: no debe quedar funcionando indefinidamente
Algoritmo Dpto. Informtica 7
Ejemplo de problema y algoritmo
Problema:
Dado dos nmeros enteros positivos que representan la base
altura de un tringulo, encontrar la superficie del mismo.
y la
Algoritmo (pasos bien definidos)
a) inicio del algoritmo
b) obtener la base y altura
c) calcular la superficie:
d) mostrar superfice
s = ( base * altura) / 2
e) fin del algoritmo
Algoritmo Dpto. Informtica 8
Datos de Entrada
Datos de Salida
base y altura Algoritmo superficie
superficie = base . altura
2
Algoritmo Dpto. Informtica 9
Procesamiento
Observaciones sobre un algoritmo
Tiene siempre datos de entrada ( ejemplo:.. base y altura )
Siempre se especifica la cantidad de datos de entrada...
Se especifica exactamente el tipo de datos de entrada (ejemplo:
entero positivo..).
Tiene siempre un resultado que es producto del algoritmo aplicado de acuerdo a los datos de entrada (ejemplo: superficie )
Algoritmo Dpto. Informtica 10
Ejercicio:
Disee como solucionara el siguiente problema. Escrbalo paso a paso.
Encuentre el rea sombreada que representa un anillo.
Que datos son necesarios?
Representacin de un algoritmo
Diagramas : de flujo o Nassi-Shneiderman(N-S)
Semi-hablado: pseudocdigo
Pseudocdigo Diagrama de Flujo
leer base, altura
escribir sup
SL
sup = (base*altura)/2
Algoritmo Dpto. Informtica 11
var
base, altura,sup : numerico
inicio
leer(base,altura)
imprimir(sup)
fin
Inicio
sup
Solucin de un problema algortmico
L.P.=> Lenguaje de Programacin
solucin
rueba y depuracin n mquina
Algoritmo Dpto. Informtica 12
sol
Anlisis
Codificacin en algn L.P.
Traduccin
Ejecucin
Verificacin
Depuracin
Cdigo depurado
P
e
Diseo de
Verificacin manual de la solucin
Resolucin del problema
Programa
Una instancia de un algoritmo. Es la representacin concreta de un
algoritmo en algn lenguaje de programacin (para el curso seria
SL).
Lenguaje de programacin
Medio para comunicar el algoritmo a la computadora. Es un
conjunto de smbolos y las reglas para combinarlos.
Existen tres categoras de lenguajes
Intrpretes
Compiladores
Hbridos ( generadores de cdigo intermedio)
segn su implementacin:
Algoritmo Dpto. Informtica 13
Representacin en SL. Por qu?
Es un lenguaje concebido e implementado en la UNA.
Su sintaxis es muy similar a pseudocdigo. Mucho ms simple que otros lenguajes tradicionales, obvindose detalles innecesarios para un curso introductorio de programacin.
El alumno puede probar y depurar sus algoritmos en computadora. No se le limita simplemente al papel. Se acostumbra al alumno a las caractersticas reales
la
de cualquier lenguaje de programacin permitiendo la transicin a un lenguaje inconvenientes.
tradicional sin mayores
Algoritmo Dpto. Informtica 14
No obstante el alumno puede usar pseudocdigo u otra
representacin en la fase de resolucin del problema
Problemas y algoritmos
Algoritmo Dpto. Informtica 15
Recordar que:
Un algoritmo es una posible solucin a un problema planteado. Desde el punto de vista de la materia, este problema puede ser resuelto por una computadora.
Un problema puede ser resuelto por ms de un algoritmo.
Un problema siempre consta de:
Datos de entrada: cantidad y naturaleza de los datos.
Informacin de la salida requerida resultado de aplicar un procesamiento especfico.
Antes de elaborar un algoritmo se debe hacer un anlisis del
problema, esto es : interpretar el problema.
Para ello es recomendable leer al menos 3 o mas veces el problema
de manera a:
Tratar de encontrar la forma de reducir el problema en otros menores (divide y vencers). Sobre todo para el caso de problemas complejos.
Tener en claro cuales son los datos de entrada, en qu cantidad y cual es su naturaleza de cada uno (tipo o dominio del dato).
Tener en claro las restricciones del problema...(siempre que se expliciten los mismos).Entender perfectamente la salida requerida.
Conceptos bsicos
Memoria
Componente del computador destinado a almacenar programas y datos.
Variable
Regin de la memoria (principal) que puede ser accedida mediante un
nombre. El contenido de esta regin puede ser cambiada.
Constante literal
Cualquier nmero o cadena de caracteres que forma parte del texto del
programa. Es un valor en s mismo y no puede cambiar. Es almacenado
(generalmente ) como parte del programa.
Identificador
Nombre que es asignado a las variables o subprogramas. Existen identificadores que se denominan reservados y que tienen un significado especial dentro de un programa.
Para nuestro curso un identificador:
Comienza con una letra o con un _ (guin bajo). No debe tener espacios
Pueden tener hasta 32 caracteres. Las maysculas y minsculas son diferentes.
Algoritmo Dpto. Informtica 16
Conceptos bsicos
Expresin
Combinacin de constantes, variables y operadores.
Ejemplo: a + b + 10 * c ^ 2
Permite indicar un clculo especfico as como usualmente lo hacemos en matemticas.
Existen varios tipos de expresiones que utilizaremos: aritmticas,
relacionales, lgicas y otras.
Operadores
Indica un clculo especfico en una expresin. Por ejemplo: sumar, multiplicar, dividir, etc dos operandos. Se representan mediante smbolos : + , - , *, /, etc.
Existen varios tipos: aritmticos, lgicos, relaciones, especiales.
Algoritmo Dpto. Informtica 17
Conceptos bsicos
Operadores (continuacin)
Aritmticos: +, - , /, * , ^ (exponenciacin), % (mdulo).
Requieren operandos numricos.
Lgicos: and, or, not. Permiten implementar operaciones del lgebra de Boole. Requieren operandos lgicos.
Relacionales: ==, < , > , =, . Permiten comparar
contenido de variables. (mayor, igual, menor, distinto, etc).
Evaluacin de operandos
Para que una expresin pueda evaluarse (determinar el valor
de la misma) debe tenerse en cuenta qu pasa cuando existe
de un operador en la expresin, en qu orden se evaluar?
final ms
Reglas de precedencia: cada operador tiene un peso de precedencia. Por ejemplo el * (multiplicacin) tiene precedencia sobre el + (suma).
Reglas de asociatividad: cuando un operador tiene el mismo peso de precedencia me permite determinar cual evaluar primero. Generalmente es de izquierda a derecha.
Puedo forzar las reglas de arriba mediante la utilizacin de parntesis. Ejemplo (10+20 ) * 5 (Primero se evaluara la suma y luego la multiplicacin)
Algoritmo Dpto. Informtica 18
Conceptos bsicos
Ejemplo de expresin algortmica
A + B * C ^ 2 100 + 55
Algoritmo Dpto. Informtica 19
Operadores
Expresin algebraica correspondiente
A+B . C 2100+55
Constantes literales
Variables
Conceptos bsicos
Evaluacin de expresin. reglas de precedencia y asociatividad Uso de
A + B * C ^ 1
2 100 + 55
2
3
4
5
- - -
En En En
1 2 3,
se aplica la se aplica la
precedencia mayor precedencia mayor
de de
^ sobre los dems operadores * sobre el + y -
4 y 5 todas las precedencias son iguales y se aplica la regla de asociatividad (de izquierda a derecha).
Ejercicio: y C = 5, Cul es el resultado? Si A = 2 , B = 10
Algoritmo Dpto. Informtica 20
Expresiones algortmicas y algebraicas
Dada las siguientes expresiones algebraicas, escriba su correspondiente expresin algortmica:
b2 +4.(a+c) a)
x +1
a . b b) 100+c
( x 2+ y 2)3
c) z b
Algoritmo Dpto. Informtica 21
Conceptos bsicos
Tipo de datos
Los tipos de datos indican la naturaleza del dato. Delimita el rango
posible de valores (dominio) y las operaciones posibles aplicables
al dato.
En el curso distinguiremos tres tipos de datos bsicos o primitivos:
Numrico (numerico): representa informacin numrica ya sea entera o fraccionaria. En SL de -1.7E-308 a 1.7E+308 Por ejemplo: 1912, 18121000, 0.0002, 0.152, 1e-10, 14e+30
Cadena de caracteres (cadena): representa informacin textual. Por ejemplo: hola esto es una prueba (fjese que se encierra entre comillas dobles).
Lgico (logico) : representa datos que pueden tomar dos valores posibles : verdadero o falso. Por ejemplo: NO, SI, TRUE, FALSE.
Algoritmo Dpto. Informtica 22
Conceptos bsicos
Asignacin
Es la operacin que me permite acceder a cierta posicin de
memoria y cambiar el valor all guardado.
El operador de asignacin esta definido por el smbolo =. A la derecha debe aparecer una variable y a la izquierda una expresin.
Ejemplo:
a = 10 + 5 . Indica que a la variable de nombre a se le asignar el resultado de evaluar 10 + 5.
Operacin de asignacin
Memoria a = 10 + 5
La asignacin es la operacin fundamental realizar clculos con la computadora.
para lograr
Algoritmo Dpto. Informtica 23
15
a Me
a Memoria
Instrucciones
Instruccin:
Una accin a ser realizada por la computadora. Un programa puede
verse como un conjunto de instrucciones.
Hasta ahora vimos : expresiones y asignacin, que son
instrucciones simples. De qu forma?
Tipos de instrucciones
Simples: evaluacin de expresiones y asignacin. Permiten tener
algoritmos lineales, con un solo camino de ejecucin.
Seleccin: permiten tener alternativas de ejecucin bajo ciertas
condiciones.
Iteracin: permiten repetir un conjunto de instrucciones bajo
ciertas condiciones.
Entrada/Salida: permiten interactuar con el usuario ya sea para
la lectura de datos como la salida de los mismos.
Algoritmo Dpto. Informtica 24
Estructura bsica de un programa en SL
Opcional
Opcional si n variables
Algoritmo Dpto. Informtica 25
programa O
var : ...
O si n var
o hay
inicio
Inst
rucciones
fin
Archivo .sl
Comparando pseudocdigo con SL
Problema :
Dada dos variables numricas enteras a y b, asignar 10
a b el valor 1000 y a la variable a el valor contenido en b ms
Pseudocdigo SL
Algoritmo Dpto. Informtica 26
inicio b = 1000 a = b + 10
fin
Inicio b = 1000 a = b + 10
Fin
var
a, b: numerico
programa suma_1010
Estructura bsica de un programa en SL - partes
programa sumar_1010 var
a, b : numerico inicio
b a
fin
= =
1000 b + 10
Algoritmo Dpto. Informtica 27
Estructura bsica de un programa en SL - partes
programa sumar_1010 var
a, b : numerico inicio
b a
fin
= =
1000 b + 10
Algoritmo Dpto. Informtica 28
Palabra reservada que indica que
continuacin se encuentra el nombre
del programa.
Estructura bsica de un programa en SL - partes
programa sumar_1010 var
a, b : numerico inicio
b a
fin
= =
1000 b + 10
Algoritmo Dpto. Informtica 29
Identificador del programa
Estructura bsica de un programa en SL - partes
programa sumar_1010 var
a, b : numerico inicio
b a
fin
= =
1000 b + 10
Algoritmo Dpto. Informtica 30
Indica que a continuacin se
declararn las variables
Estructura bsica de un programa en SL - partes
programa sumar_1010 var
inicio b a
fin
= =
1000 b + 10
Algoritmo Dpto. Informtica 31
Para qu declarar las variables?
a, b : numerico
Declaracin de variables
dos variables numricas
identificadas como a y b.
Estructura bsica de un programa en SL - partes
programa var
sumar_1010
a, b : numerico inicio
b a
fin
= =
1000 b + 10
Algoritmo Dpto. Informtica 32
Palabra reservada inicio que indica que se iniciara el
cuerpo principal del
programa
Estructura bsica de un programa en SL - partes
programa var
sumar_1010
a, b : numerico inicio
fin
Algoritmo Dpto. Informtica 33
b = 1000
a = b + 10
Cuerpo del programa
Cada sentencia o instruccin esta
separada por un ENTER
Para el ejemplo existen dos
instrucciones de asignacin
Estructura bsica de un programa en SL - partes
programa var
sumar_1010
a, b : numerico inicio
b a
fin
= =
1000 b + 10
Algoritmo Dpto. Informtica 34
Palabra reservada fin
que indica que se termina el
cuerpo principal del programa
Vista del entorno de programacin SL
Algoritmo Dpto. Informtica 35
Algoritmos lineales
Caractersticas
nico flujo de ejecucin.
Se especifican las cmputos
secuencial.
instrucciones uno tras otro de forma
Por s solos, resuelven problemas muy simples y cortos.
Son usados en conjuncin en iterativos.
Inicio
otros algoritmos con procesos selectivos e
Fin
Algoritmo Dpto. Informtica 36
Paso N
Paso 2
...
Paso 1
Algoritmos lineales ejemplo ya visto
Problema:
Dado dos nmeros enteros positivos que representan la base y la
altura de un tringulo, encontrar e imprimir mismo.
la superficie del
Para encontrar una solucin, asumimos que se sabe geometra bsica.
plana
Por tanto
Un posible algoritmo de solucin (hablado)
inicio del algoritmo
Leer los datos de base y altura
Calcular la superficie que es igual a base por altura entre dos.
Imprimir o mostrar el contenido de superfice
fin del algoritmo
Algoritmo Dpto. Informtica 37
base . altura superficie=
2
Algoritmos lineales ejemplo en SL (1)
Para llevar a SL tendramos que tener en cuenta
Definicin de las variables necesarias que usaremos
base, altura y superfice
Funciones de entrada/salida de datos
leer (para entrada de datos) e imprimir (para salida de datos)
Expresin de la operacin aritmtica que indica el clculo
( base * altura ) / 2 (en representacin algortmica)
Guardar el resultado del
operador de asignacin =
clculo en otra variable (asignacin)
Algoritmo Dpto. Informtica 38
Algoritmos lineales ejemplo en SL (2)
SL
Pasos secuenciales
Algoritmo Dpto. Informtica 39
inicio leer(base,altura) superficie = (base * altura)/2 imprimir(superficie)
fin
var
base, altura : numerico
superficie : numerico
programa calc_superfice_triang
Algoritmos lineales paso a paso en SL
Algoritmo Dpto. Informtica 40
Algoritmos lineales paso a paso en SL
Algoritmo Dpto. Informtica 41
Algoritmos lineales paso a paso en SL
Algoritmo Dpto. Informtica 42
Algoritmos lineales paso a paso en SL
Algoritmo Dpto. Informtica 43
Funciones matemticas usuales en SL
Algoritmo Dpto. Informtica 44
Frmula Funcin en SL Descripcin
sin ( x)
sen(x)
seno de x expresado en radianes
cos ( x )
cos(x)
coseno de x expresado en radianes
tan ( x)
tan(x)
tangente de x expresado en rad.
ln ( x)
log(x)
logaritmo natural de x
x
abs(x)
valor absoluto de x
arctan ( x )
arctan(x)
arco tangente de x expresado en rad.
x
sqrt(x)
raiz cuadrada de x
e x
exp(x)
el valor de e elevado a x
Bibliografa
Joyanes Aguilar, Luis. Fundamentos de programacin: algoritmos, estructura de datos y objetos. McGraw-Hill, 2003.
Joyanes Aguilar, Luis. Fundamentos de Programacin-
Algoritmos y Estructuras de Datos. McGraw-Hill, 1996.
Segovia Silvero, Juan. SL. Introduccin al lenguaje- Referencia de subrutinas predefinidas-Ejemplos selectos. Centro Nacional de Computacin, Universidad Nacional
de Asuncin. 1999.
Rodriguez Almeida, Miguel Angel. Metodologa de la
programacin a travs del pseudocdigo. McGraw-Hill, 1991.
Kernighan & Pike. La prctica de la programacin.
Prentice-Hall. 1999.
Algoritmo Dpto. Informtica 49
Recommended