Introducción a la Algorítmica Problemas

y Programación (3300) Resolución mediante computadoras

Prof. Ariel Ferreira Szpiniak - [email protected] No todos los problemas pueden ser resueltos por una
Departamento de Computación
computadora.
Facultad de Cs. Exactas, Fco-Qcas y Naturales
Universidad Nacional de Río Cuarto Problema

Teoría 1 Un largo camino...

Resolución de problemas Solución

2023 Lic. Ariel Ferreira Szpiniak 1 2023 Lic. Ariel Ferreira Szpiniak 2

Problemas
Pasos para solucionar un problema Pasos para solucionar un problema
Problema
Análisis
• El objetivo del análisis es entender el problema a resolver.
• Análisis • El problema debe estar bien definido para poder obtener una solución satisfactoria.
El problema debe ser claramente especificado y entendido . Especificación: datos, • Los datos de entrada y los resultados deben ser precisamente descriptos.
resultados
• Diseño
Construcción de una solución general del problema. Preguntas orientadoras
Datos de entrada: ¿Cuáles y cuántos son los valores de entrada? ¿Qué nombre significativo
• Implementación Algoritmo
puedo darle a esos datos?
Traducción del algoritmo a un lenguaje de programación de Dibujo o esquema que permita entender mejor el problema
alto nivel.
Programa fuente
• Compilación Resultados (salida): ¿Cuáles y cuántos son los valores del resultado? ¿Qué nombre significativo
Traducción del programa a un lenguaje entendido por la puedo darle a esos resultados?
computadora. Programa ejecutable

• Ejecución y Prueba Relaciones o subproblemas: en caso de existir, describir las relaciones existentes entre los
Corrida y prueba de funcionamiento del programa en la Solución datos, los resultados u otra información adicional que sea necesaria para la resolución del
computadora. problema. O suproblemas en caso de ser un problema más complejo.

2023 Lic. Ariel Ferreira Szpiniak 3 2023 Lic. Ariel Ferreira Szpiniak 4
 Pasos para solucionar un problema Problemas
Análisis (cont.) Pasos para solucionar un problema
Problema
Podemos dividir el análisis en dos etapas:
Etapa 1: se analiza el problema libremente y se trata de lograr una síntesis • Análisis
El problema debe ser claramente especificado y entendido . Especificación: datos,
del problema a resolver. resultados
• Diseño
Construcción de una solución general del problema.
Etapa 2: luego de tener en claro el problema a resolver se tratan de • Implementación Algoritmo
identificar los datos de entrada, los resultados y las relaciones que puedan Traducción del algoritmo a un lenguaje de programación de
existir entre datos, resultados u otros componentes del problema. Al alto nivel.
Programa fuente
finalizar la Etapa 2 se debe obtener lo siguiente: • Compilación
Traducción del programa a un lenguaje entendido por la
computadora. Programa ejecutable
• Dato/s:
• Resultado/s: • Ejecución y Prueba
Corrida y prueba de funcionamiento del programa en la Solución
• Relaciones o subproblemas:
computadora.

2023 Lic. Ariel Ferreira Szpiniak 5 2023 Lic. Ariel Ferreira Szpiniak 6

Pasos para solucionar un problema Pasos para solucionar un problema

Diseño Diseño
●
El objetivo del diseño es desarrollar un algoritmo que solucione el En la Etapa 2:
problema de forma genérica, sin considerar los detalles de ●
Si el problema es simple: se construye un algoritmo que lo resuelva.
implementación. ●
Si el problema es más complejo: puede ser visto como la composición
de varios (sub)problemas de menor complejidad.
Podemos dividir el diseño en dos etapas: Por ejemplo, subproblemas:
(1) obtener datos del hexágono
●
Etapa 1: definir el entorno de trabajo o léxico (tipos, variables, etc). (2) calcular área del hexágono
(3) informar el área del hexágono
●
Etapa 2: construir un algoritmo.
A cada subproblema se le vuelve a aplicar la misma técnica, es decir, un
análisis y un diseño.

2023 Lic. Ariel Ferreira Szpiniak 7 2023 Lic. Ariel Ferreira Szpiniak 8
 Noción de Algoritmo Noción de Algoritmo
Acción, Entorno y Procesador Acciones primitivas y descomposición
Consideremos los siguientes enunciados:
En los enunciados E1 y E2 hemos supuesto que el procesador
E1: 1/2 docena de huevos revueltos E2: Cálculo de la media de dos números sabía ejecutar las acciones enumeradas. En ese caso las
con una calculadora acciones se denominan primitivas.
a) Romper seis huevos en un plato;
b) Batir la clara y la yema con un tenedor; a) pulsar C ;
Definición: para un procesador dado, una acción es primitiva
c) Calentar el aceite en una sartén al fuego;
b) teclear el primer número; si el enunciado de dicha acción es suficiente para poder
d) Cuando el aceite esté caliente, verter el
contenido del plato;
c) pulsar + ; ejecutarla sin información suplementaria.
e) Sacar la sartén del fuego cuando el d) teclear el segundo número;
revuelto esté cocido. e) pulsar % ; Si una acción no es primitiva debe ser descompuesta en dos o
f) teclear 2; más acciones primitivas.
g) pulsar = . {Aparece el resultado}
Definición: descomponer una acción -no primitiva- es
encontrar una serie de acciones primitivas que realicen lo
requerido por dicha acción.

2023 Lic. Ariel Ferreira Szpiniak 9 2023 Lic. Ariel Ferreira Szpiniak 10

Noción de Algoritmo Noción de Algoritmo

Ejemplo de descomposición Procesador
Supongamos que en el enunciado E1, el procesador es un niño
y no comprende la acción “a) romper seis huevos en un plato”. Definición: un procesador es la entidad responsable de ejecutar las
Es necesario descomponer la acción. acciones primitivas.

a) romper seis huevos en un plato;

a1) poner seis huevos en la superficie de trabajo; a11) tomar otro huevo de la superficie de trabajo;
El procesador solo entiende las acciones primitivas, nada más.
a2) tomar un huevo de la superficie de trabajo; a12) romperlo y verter su contenido en el plato;
a3) romperlo y verter su contenido en el plato; a13) tirar las cáscaras a la basura; Una acción no primitiva puede transformarse en primitiva según
a4) tirar las cáscaras a la basura; a14) tomar otro huevo de la superficie de trabajo; quien sea el procesador.
a5) tomar otro huevo de la superficie de trabajo; a15) romperlo y verter su contenido en el plato;
a6) romperlo y verter su contenido en el plato; a16) tirar las cáscaras a la basura;
a7) tirar las cáscaras a la basura; a17) tomar el último huevo de la superficie de trabajo;
a18) romperlo y verter su contenido en el plato;
a8) tomar otro huevo de la superficie de trabajo;
a9) romperlo y verter su contenido en el plato; a19) tirar las cáscaras a la basura;
El procesador puede ser una máquina, una persona, etc.
a10) tirar las cáscaras a la basura;

2023 Lic. Ariel Ferreira Szpiniak 11 2023 Lic. Ariel Ferreira Szpiniak 12
 Noción de Algoritmo Noción de Algoritmo
Entorno de trabajo, variable y tipo Entorno de trabajo, variable y tipo
Variable
Entorno de trabajo Definición: son datos que tienen la posibilidad de cambiar su valor.
Ejemplo: saldo
Definición: el entorno de trabajo es el espacio donde conviven los
distintos utensilios que pueden ser usados por el procesador para Constante
ejecutar las acciones primitivas. El procesador modifica el entorno Definición: son datos que no pueden cambiar su valor.
de trabajo mediante la ejecución de las acciones. Ejemplo: mesesDelAnio = 12

Dato Tipo
Definición: un dato es la representación de un objeto del mundo Definición: es un conjunto de valores posibles que se encuentran
real mediante el cual podemos modelar aspectos del problema que ligados a un conjunto de operaciones para crearlos y manipularlos. Todo
dato, tanto constante como variable, debe pertenecer a un tipo.
se quiere resolver. Son los valores de información de los que se
necesita disponer y en ocasiones transformar. Ejemplos: saldo  Z (saldo pertenece a Entero). mesesDelAnio=12  Z
(mesesDelAnio es igual a 21 y pertenece a Entero)

2023 Lic. Ariel Ferreira Szpiniak 13 2023 Lic. Ariel Ferreira Szpiniak 14

Algunos Tipos Simples Noción de Algoritmo Significado de la

 Entero (Z): es el conjunto de valores numéricos más simple de
asignación
todos: ..., -2, -1, 0, 1, 2, …
• El objetivo de la asignación es cambiar el valor almacenado
Operaciones: +, -, *, /, div, mod, =, <>, <, <=, >, >= en una variable.
 Lógico: conjunto de valores lógicos: Verdadero y Falso.
x  e Guarda en x el valor de e
Operaciones: y (conjunción), o (disyunción), no (negación)
 Caracter: conjunto de caracteres: letras minúsculas, mayúsculas, • Sintaxis: <variable>  <expresion>
cifras, y signos especiales. ‘M’ ‘m’ ‘5’ ‘%’
Operaciones: =, <>, >, <, >=, <=, ord, chr • Ejemplos:
 Cadena: conjunto de cadenas de caracteres: “promNotas” Sean i,j  Z
“5mentarios”. Deben coincidir los tipos de la
i  9 variable y la expresión
Operaciones: =, <>, >, <, >=, <=, + j  3 + 4

2023 Lic. Ariel Ferreira Szpiniak 15 2023 Lic. Ariel Ferreira Szpiniak 16
 Noción de Algoritmo Significado de la Noción de Algoritmo Significado de
asignación la asignación
Una asignación x  e es ejecutada siguiendo estos
• Al producirse la asignación el valor anterior se pierde.
pasos:
• La ocurrencia de una variable en el lado derecho de una
1. Se evalúa la expresión e asignación denota su valor actual.
• Una misma variable puede aparecer en la parte izquierda y
2. Se reemplaza el valor almacenado en la variable x, por
derecha de una asignación.
el valor de e.
Por ejemplo: x1
x  e { x=X0 ^ X0=eval(e) }
¿Qué valor tiene x aquí?

x valor I  9 { i=9 } xx+1

¿Qué valor tiene x aquí?

j  3+2 { j=5 ^ 5=eval(3+2) } x  x + 1 NO debe interpretarse como una ecuación matemática!

x eval(e) Sólo significa que estamos usando el valor actual de la variable x para calcular su
nuevo valor.

2023 Lic. Ariel Ferreira Szpiniak 17 2023 Lic. Ariel Ferreira Szpiniak 18

Algoritmo Algoritmo
Definición Definición (cont.)
Algoritmo: del árabe al-Jwarizmi, matemático del siglo IX
Definición 1: Un algoritmo es una sucesión finita de
instrucciones o pasos no ambiguos que se pueden ejecutar
Características:
en un tiempo finito para resolver un problema.
• Debe ser preciso e indicar el orden de realización de cada
paso.
Definición 2: Dado un procesador, un entorno de trabajo y un • Se debe obtener el mismo resultado cada vez que se aplica a
tratamiento a ejecutar por dicho procesador sobre ese entorno, los mismo datos.
un algoritmo es el enunciado de una secuencia finita de • Se debe terminar en algún momento.
acciones que resuelve un problema determinado.
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.)

2023 Lic. Ariel Ferreira Szpiniak 19 2023 Lic. Ariel Ferreira Szpiniak 20
 Algoritmo Notación Algorítmica
Estructura y Notación Acciones conocidas por el Procesador

Algoritmo <nombre> nada No produce cambio alguno en el entorno

Léxico x  e Guarda en la variable x el valor de e

<declaración de variables, tipos, Entrada:x Guarda en la variable x un valor

acciones, funciones, etc> Entrada:x y Guarda en la variable x un valor y en la variable y
otro valor (se puede generalizar a más variables)
Inicio Salida:e Informa un resultado a través del valor de e.
<secuencia de acciones> Donde e puede ser una o más variables
Fin // Comentario (el procesador lo ignora). Pueden ir
en cualquier lugar del algoritmo

2023 Lic. Ariel Ferreira Szpiniak 21 2023 Lic. Ariel Ferreira Szpiniak 22

Noción de Algoritmo Noción de Algoritmo

Ejemplo Ejemplo (2)

Algoritmo SumarUno Algoritmo SumarDosNumeros

Léxico Léxico
x, a  Z //números enteros x, y, a  Z //números enteros
Inicio Inicio
Entrada:x comentarios Entrada:x y comentarios

a  x+1 a  x+y
// a contiene la suma de x más 1 // a contiene la suma de x e y
Salida:a Salida:a
Fin Fin

2023 Lic. Ariel Ferreira Szpiniak 23 2023 Lic. Ariel Ferreira Szpiniak 24
 Pasos para solucionar un problema Problemas
Implementación Pasos para solucionar un problema
Es la traducción del algoritmo a un lenguaje entendido por la computadora. ¿Qué lenguaje Problema
entiende la computadora?
• Análisis
Código binario Bajo nivel Alto nivel Bloques
El problema debe ser claramente especificado y entendido . Especificación: datos,
01100001 01110110 ADD ECX, R9D if username == user1: resultados
01100001 01101110
01111010 01100001
ADD ECX, R8D
ADD ECX, EDX
print "Access granted"
elif username == user2:
• Diseño
MOVD XMM0, ECX
CVTDQ2PD XMM0, XMM0 print "Welcome" Construcción de una solución general del problema.
MOVSD XMM1, realVal else:
print "Access denied" • Implementación Algoritmo
Traducción del algoritmo a un lenguaje de programación de
Implementar consiste en traducir el algoritmo a un lenguaje de alto nivel.
programación de alto nivel (C, BASIC, COBOL, Pascal, Java, Programa fuente
PHP, C++, FORTRAN, Perl, Pyton, Ruby). Pero hay muchos • Compilación
lenguajes, por lo tanto pueden haber varios programas que Traducción del programa a un lenguaje entendido por la
computadora. Programa ejecutable
solucionen el mismo problema resuelto por un algoritmo.
• Ejecución y Prueba
Corrida y prueba de funcionamiento del programa en la Solución
La gran ventaja de los lenguajes de alto nivel es que consiguen distanciarse del
lenguaje máquina y se aproximan al lenguaje algorítmico. computadora.

2023 Lic. Ariel Ferreira Szpiniak 25 2023 Lic. Ariel Ferreira Szpiniak 26

Pasos para solucionar un problema Pasos para solucionar un problema

Compilación Compilación
“Compilar” (traducir) el programa fuente al lenguaje entendido por la
computadora. Detección de errores (sintácticos, …). Este programa muestra por pantalla el mensaje “Hola mundo!”
#include <stdio.h>
P int main()
r F
Compilador { Nombre del archivo:
o u Bibliotecas, holaMundo.c
Obj S printf("Hola mundo! ");
g e
r n a return 0;
Programa Assembler
a t l }
m e i
a Linkeador Programa
Ejecutable d
D
Ensamblador
Entornos de
a ¿Y la “computadora” entiende eso?
a Desarrollo
Integrado (IDE)
t Programa Objeto
o
s
https://pxhere.com/es/photo/1584997.
2023 Lic. Ariel Ferreira Szpiniak 27 2023 Lic. Ariel Ferreira Szpiniak 28
 Pasos para solucionar un problema Pasos para solucionar un problema
Compilación Compilación
El compilador gcc El compilador gcc
GCC GNU Compiler Collection es un compilador integrado del
proyecto GNU para C, C++ y otros lenguajes. ●
gcc -c holaMundo.c
Recibe un programa fuente en cualquiera de estos lenguajes y No genera el archivo ejecutable, sino el código objeto, en el
generar un programa ejecutable binario en el lenguaje de la archivo holaMundo.o. Si no se indica un nombre para el archivo
máquina del dispositivo donde se ejecutará. objeto, usa el nombre del archivo en C y le cambia la extensión por
●
gcc holaMundo.c .o
Compila el programa holaMundo.c, y genera un archivo
ejecutable llamado a.out ●
gcc -c -o objeto.o holaMundo.c
genera el código objeto indicando el nombre de archivo.
●
gcc -o holaMundo holaMundo.c
Compila el programa holaMundo.c, y genera un archivo
ejecutable llamado holaMundo

2023 Lic. Ariel Ferreira Szpiniak 29 2023 Lic. Ariel Ferreira Szpiniak 30

Problemas
Pasos para solucionar un problema Pasos para solucionar un problema
Compilación Problema
Compilador (y depurador) on line para C y C++
www.onlinegdb.com/online_c_compiler • Análisis
El problema debe ser claramente especificado y entendido . Especificación: datos,
resultados
• Diseño
Construcción de una solución general del problema.
• Implementación Algoritmo
Traducción del algoritmo a un lenguaje de programación de
alto nivel.
Programa fuente
• Compilación
Traducción del programa a un lenguaje entendido por la
computadora. Programa ejecutable

• Ejecución y Prueba
Corrida y prueba de funcionamiento del programa en la Solución
computadora.

2023 Lic. Ariel Ferreira Szpiniak 31 2023 Lic. Ariel Ferreira Szpiniak 32
 Pasos para solucionar un problema Pasos para solucionar un problema
Ejecución y Prueba Ejecución y Prueba
• Ejecutar (o “correr”) el resultado de la compilación, es decir, el Si compilo el programa holaMundo.c de la siguiente manera:
programa ejecutable.
gcc holaMundo.c (compila el programa holaMundo.c, y genera un
• Cuando se ejecuta un programa, la computadora (el sistema archivo ejecutable llamado a.out)
operativo) crea un proceso donde pone a funcionar ese programa.
- Procesamiento de datos de entrada. Lo ejecuto así: ./a.out
- Detección de errores semánticos.
Si compilo el programa holaMundo.c de la siguiente manera:
• Prueba o Testeo
- Probar el programa con una serie de valores de
gcc -o holaMundo holaMundo.c (compila el programa holaMundo.c, y
entrada y verificar que produce el resultado
genera un archivo ejecutable llamado holaMundo)
esperado en todos los casos.
Lo ejecuto así: ./holaMundo

2023 Lic. Ariel Ferreira Szpiniak 33 2023 Lic. Ariel Ferreira Szpiniak 34

Ejemplo Ejemplo
Programa Fuente en C Programa Assembler
.section .bss
# [1] int k,l,m
.lcomm _K,2
int k, l, m; .lcomm _L,2
int k, l, m; .lcomm _M,2
.comm HEAP,262144#
void main(){ [3] void main(){
void main(){ .globl _main
l = 3; _main:
l = 3; .globl CMAIN
m = 5; CMAIN:
m = 5; .globl program_init
k = l + m; program_init:
k = l + m; pushl %ebp
} movl %esp,%ebp
} movb $1,U_SYSWIN32_ISCONSOLE
call FPC_INITIALIZEUNITS
# [4] l=3;
movw $3,_L
# [5] m=5;
movw $5,_M
# [6] k=l+m;
movswl _L,%eax
movswl _M,%edx
addl %eax,%edx
movw %dx,_K
# [7] }
2023 Lic. Ariel Ferreira Szpiniak 35 2023 Lic. Ariel Ferreira Szpiniak 36
 Ejemplo Ejemplo
Programa Objeto Programa Ejecutable
Archivo visto a
través de un editor
de texto.

Código de máquina y lenguaje assembler del Intel 8088

Archivo visto a través
direcciones de
de un editor
memoria hexadecimal.
donde se
encuentra el La mayoría de los clones del IBM
código
PC y XT usaron el Intel 8088
código de código assembler
máquina

2023 Lic. Ariel Ferreira Szpiniak 37 2023 Lic. Ariel Ferreira Szpiniak 38

Problemas Pasos para solucionar un problema

Pasos para solucionar un problema Análisis
Problema
Ejemplo de Problema: Calcular cuánto espacio ocupa una
• Análisis baldosa cuadrada
El problema debe ser claramente especificado y entendido . Especificación: datos,
resultados Etapa 1 (síntesis): calcular el área de una baldosa cuadrada
• Diseño
Construcción de una solución general del problema.
• Implementación Algoritmo
Etapa 2 (identificar los datos de entrada, los resultados y las relaciones o
Traducción del algoritmo a un lenguaje de programación de subproblemas):
alto nivel.
Programa fuente
• Compilación • Dato: lado de la baldosa. Es un número. Nombre: lado
Traducción del programa a un lenguaje entendido por la
Programa ejecutable • Resultado: área ocupada por la balsosa. Es un número. Nombre:
computadora.
areaCuad
• Ejecución y Prueba • Relaciones o subproblemas: el área de un cuadrado es lado por lado
Corrida y prueba de funcionamiento del programa en la Solución
computadora. (areaCuad=lado*lado)

2023 Lic. Ariel Ferreira Szpiniak 39 2023 Lic. Ariel Ferreira Szpiniak 40
 Pasos para solucionar un problema Pasos para solucionar un problema
Diseño Implementación
Traducción del algoritmo a C (lenguaje que utilizaremos en la
Algoritmo AreaBaldosa asignatura)
Léxico
#include <stdio.h>
lado  Z+ // variable dato /* léxico */
int lado;
areaCuad  Z+ // variable resultado
int areaCuad;
Inicio
/* función principal (main) en todo programa C */
Entrada:lado void main(){
areaCuad  lado * lado scanf("%d",&lado); // dir de memoria de la var lado
areaCuad = lado * lado;
Salida:areaCuad printf("%d",areaCuad );
Fin /* otra forma: printf("El area es: %d \n",areaCuad );* /
}

2023 Lic. Ariel Ferreira Szpiniak 41 2023 Lic. Ariel Ferreira Szpiniak 42

Pasos para solucionar un problema Ejemplo de problema más complejo

Implementación Doña Rosa tiene un patio de forma rectangular y quiere cubrirlo con
Traducción del algoritmo a Pascal (otro lenguaje) cerámicos cuadrados. ¿Puedes ayudarla a calcular cuántos cerámicos
necesitará?
PROGRAM AreaBaldosa;
Análisis
VAR
lado: Integer; Etapa 1 (síntesis):
areaCuad: Integer;
BEGIN
Read(lado); Calcular la cantidad de cerámicos
areaCuad := lado * lado; cuadrados necesarios
Writeln(areaCuad) para un patio rectangular
END.

2023 Lic. Ariel Ferreira Szpiniak 43 2023 Lic. Ariel Ferreira Szpiniak 44
 Ejemplo de problema más complejo Ejemplo de problema más complejo
Doña Rosa tiene un patio de forma rectangular y quiere cubrirlo con cerámicos
cuadrados. ¿Puedes ayudarla a calcular cuántos cerámicos necesitará? Doña Rosa tiene un patio de forma rectangular y quiere cubrirlo con
cerámicos cuadrados. ¿Puedes ayudarla a calcular cuántos cerámicos
Análisis (cont)
necesitará?
Etapa 2 (identificar los datos de entrada, los resultados y las relaciones o
Diseño
subproblemas):
Etapa 1 (definir el entorno de trabajo o léxico: tipos y variables)
●
Dato: Largo y ancho del patio. Son números. Nombres: largoPatio y anchoPatio.
Lado del cerámico. Es un número. Nombre: ladoCeramico.
ladoCeramico  R+ // dato de entrada
• Resultado: cantidad de cerámicos. Es un número. Nombre: cantCeramicos. largoPatio  R+ // dato de entrada
• Relaciones o subproblemas: anchoPatio  R+ // dato de entrada
- Calcular el área del patio (areaPatio) areaPatio  R+ // intermedio
areaCeramico  R+ // intermedio
- Calcular el área de un cerámico (areaCeramico) cantCeramicos  R+ // resultado
- Calcular la cantidad de cerámicos: cantCeramicos es igual a areaPatio dividido
areaCeramico

2023 Lic. Ariel Ferreira Szpiniak 45 2023 Lic. Ariel Ferreira Szpiniak 46

Ejemplo de problema más complejo Ejemplo de problema más complejo

Doña Rosa tiene un patio de forma rectangular y quiere cubrirlo con cerámicos Algoritmo PatioDeBalsodas
cuadrados. ¿Puedes ayudarla a calcular cuántos cerámicos necesitará? Léxico
ladoCeramico  R+ // dato de entrada
Diseño (cont) largoPatio  R+ // dato de entrada
Etapa 2 (división en subproblemas). A cada subproblema se le vuelve a aplicar la anchoPatio  R+ // dato de entrada
misma técnica, es decir, un análisis y un diseño.
areaPatio  R+ // intermedio
●
Calcular el área total del patio rectangular areaCeramico  R+ // intermedio
Un breve análisis del problema nos lleva a que: cantCeramicos  R+ // resultado
areaPatio = largoPatio * anchoPatio Inicio
// Obtener los datos de entrada
●
Calcular el área ocupada por cada cerámico
Entrada:ladoCeramico largoPatio anchoPatio
Un breve análisis del problema nos lleva a que: AreaCeramico  ladoCeramico*ladoCeramico // área ocupada por cada cerámico
areaCeramico = ladoCeramico * ladoCeramico AreaPatio  largoPatio*anchoPatio // área total del patio rectangular
CantCeramicos  areaPatio/areaCeramico // cantidad de cerámicos necesarios
●
Calcular la cantidad de cerámicos necesarios
// Informar el resultado
cantCeramicos = areaPatio / areaCeramico Salida:cantCeramicos
Fin
Nota: Observar la similitud entre este algoritmo y la descripción refinada de la solución del problema.

2023 Lic. Ariel Ferreira Szpiniak 47 2023 Lic. Ariel Ferreira Szpiniak 48
 Ejemplo de problema más complejo Ejemplo de problema más complejo
Traducción del algoritmo a C Compilación (gcc -o patio patio.c)

#include <stdio.h>
/* léxico */
float ladoCeramico, largoPatio, anchoPatio, areaPatio,
areaCeramico, cantCeramicos;

/* función principal (main) en todo programa C */

void main(){
scanf("%f",&ladoCeramico);
scanf("%f",&largoPatio);
scanf("%f",&anchoPatio);
areaCeramico = ladoCeramico * ladoCeramico;
areaPatio = largoPatio * anchoPatio;
cantCeramicos = areaPatio / areaCeramico;
printf("%f",cantCeramicos);
}

2023 Lic. Ariel Ferreira Szpiniak 49 2023 Lic. Ariel Ferreira Szpiniak 50

Ejemplo de problema más complejo Problemas

Ejecución y prueba (./patio)
Pasos para solucionar un problema
Problema

• Análisis
El problema debe ser claramente especificado y entendido . Especificación: datos,
resultados
• Diseño
Construcción de una solución general del problema.
• Implementación Algoritmo
Traducción del algoritmo a un lenguaje de programación de
alto nivel.
Programa fuente
• Compilación
Traducción del programa a un lenguaje entendido por la
computadora. Programa ejecutable

• Ejecución y Prueba
Corrida y prueba de funcionamiento del programa en la Solución
computadora.

2023 Lic. Ariel Ferreira Szpiniak 51 2023 Lic. Ariel Ferreira Szpiniak 52
 Computadora Componentes
Definición: Máquina capaz de aceptar
datos a través de un medio de entrada, HW SW
procesarlos automáticamente bajo el
control de un programa y proporcionar la Base (S.O.)
DOS, UNIX, Windows,
información resultante a través de un MAC, etc.
medio de salida.  Unidad Central de Proceso
Aplicación
Utilitarios
 Unidad de Memoria
Entrada Computadora Salida Lenguajes de
programación
 Dispositivos de Entrada/Salida Esparcimiento
Educativos
Otros

2023 Lic. Ariel Ferreira Szpiniak 53 2023 Lic. Ariel Ferreira Szpiniak 54

HW HW
Unidad Central de Proceso Unidad de Memoria
(UCP/CPU) Memoria principal (o primaria):
• Conjunto de celdas de memoria direccionables vía un único
Controla el procesamiento de la información nombre
• Acceso directo por referencia para:
Unidad de Control: - Carga
• Carga instrucciones en memoria - Recuperación de información
• Interpreta y devuelve el resultado de la ejecución • Programas residen en este tipo de memoria al ser ejecutados

Unidad Aritmética y Lógica: Memoria secundaria:

• Proceso de operaciones aritméticas y lógicas • Permiten almacenar gran cantidad de información
• Provee decisión a la Unidad de Control • Información persistente
• Ejemplos: Discos duros, diskettes, CDRom, ZIP.

2023 Lic. Ariel Ferreira Szpiniak 55 2023 Lic. Ariel Ferreira Szpiniak 56
 HW
Dispositivos de Entrada/Salida HW
(Input/Output) Modelo Refinado de Computadora
Los dispositivos de E/S permiten la comunicación ente el usuario
y el computador.
Mem UCP
Dispositivos de entrada: Dispositivos de entrada/salida:
• Teclados
• Placa de red E S
• Ratón
• Lectores de disco • Modem
UC UAL
• etc.
• Placa de sonido
Dispositivos de salida: • etc.
• Impresoras
• Pantalla
• etc.
2023 Lic. Ariel Ferreira Szpiniak 57 2023 Lic. Ariel Ferreira Szpiniak 58

SW SW
Lenguajes de Programación Instrucciones para la computadora
Tipos de instrucciones ejecutadas por una computadora:
• de E/S: lectura/escritura de información • Contenido de memoria expresado en bits (dígitos binarios)

• Lógico-aritméticas • Datos e instrucciones en el mismo lenguaje

• Secuencia: Primero ejecutar una instrucción y luego otra
• Selección: si ... entonces ... sino ... • El lenguaje de máquina depende del diseño y del hardware del

• Ciclo: Repetición de una secuencia de instrucciones computador (por ej., diferentes máquinas pueden representar
las instrucciones con códigos diferentes)
• Procedimiento: Grupo de instrucciones que pueden ser
referenciadas y ejecutadas
2023 Lic. Ariel Ferreira Szpiniak 59 2023 Lic. Ariel Ferreira Szpiniak 60
 SW SW
Lenguajes de bajo nivel Ejemplo de lenguaje Assembler
Lenguajes con un pobre nivel de abstracción, en el sentido
de que sus instrucciones se asemejan mucho a las de ...
máquina lealU_SYSWIN32_OUTPUT,%edi
movl %edi,-4(%ebp)
Ejemplo: Lenguaje de Ensamblado (Assembler) pushl $.L7
pushl -4(%ebp)
• En este tipo de lenguajes las instrucciones son pushl $0
nombradas call FPC_WRITE_TEXT_SHORTSTR
por códigos mnemotécnicos. pushl -4(%ebp)
Por ejemplo: ADD, SUB, MPY, DIV, etc. call FPC_WRITELN_END
pushl $.L4
• Las instrucciones son traducidas a código de máquina call FPC_IOCHECK
mediante un ensamblador. ...
2023 Lic. Ariel Ferreira Szpiniak 61 2023 Lic. Ariel Ferreira Szpiniak 62

SW SW
Lenguajes de alto nivel Lenguaje C
• Lenguaje de alto nivel que usaremos en la materia.
• Lenguajes con un mayor nivel de abstracción, en el sentido
de que sus instrucciones asemejan al lenguaje natural. • Fue creado en 1972 por Dennis Ritchie, en los Laboratorios Bell, como
evolución del lenguaje B.
• Pueden ser independientes de la máquina. Por lo tanto,
pueden ser traducidos a distintos lenguajes de máquina. • En 1983 el Instituto de Estándares Americanos estableció un estándar
que definiera al lenguaje C, conocido como ANSI C.

Ejemplos • Los principales compiladores de C llevan implementado el estándar

Pascal, C, C++, Java, Visual BASIC, COBOL, Fortran. ANSI C.

• Utilizado para la implementación del sistema UNIX, y

muchas aplicaciones complejas.

2023 Lic. Ariel Ferreira Szpiniak 63 2023 Lic. Ariel Ferreira Szpiniak 64
 SW SW
Ejemplo de un programa C Características de un buen programa
Este programa muestra por pantalla el mensaje “Hola mundo”.
• Confiabilidad
#include <stdio.h>

int main() • Adaptabilidad

{
printf("Hola mundo"); • Legibilidad
return 0;
}

2023 Lic. Ariel Ferreira Szpiniak 65 2023 Lic. Ariel Ferreira Szpiniak 66

SW Bibliografía para la Teoría 1

Fracasos - Crisis del software • Scholl, P. y Peyrin, J.-P. “Esquemas Algorítmicos Fundamentales:
• Sistema de Control de Tráfico Aéreo: FAA-IBMcancelado: 144 M$ - Secuencias e iteración”:
resto: atraso 5 años, 1.400 M$ - Introducción, Algoritmo, Léxico, Notación algorítmica (pags. 1 - 34)
• Sonda Mariner 1 (Venus) fallo: error de software - Composición secuencial (pags. 35 - 55)
• Taxi espacial: 5 computadoras redundantes: demora 2 días ('81), un • Biondi, J. y Clavel, G. “Introducción a la Programación. Tomo 1:
día ('85), pierde Intelsat 6 ('92),... Algorítmica y Lenguajes”:
• Sistema telefónico de AT&T: corte de 1 día, error de tipos • Notación algorítimica (pags. 1 – 12)
• Sistema de trenes alemán: bloqueo de 1 día por Memoria llena • Entorno, Tipos, Variables, Constantes, Notación algorítmica (pags. 13 – 34)
• American Airlines+Marriott+Hilton+Budget: 1992 Integración de • Composición condicional (35 - -53)
• Procesadores, Lenguajes (pags. 127 – 140)
reservas, abandonado, 165 M$ • Introducción a Lógica (pags. 203 – 204)
• 6 fantasmas en el radar: aeropuerto de San Francisco (EE.UU.)
9/1/01. • Wirth, N. “Algoritmos + Estruturas de Datos = Programas”: Presentación
• Tren noruego se detuvo el 31 Dic 2000: el 2000 tenía 54 semanas y Prólogo muy interesantes. Tipos (pags. 1 – 12).
en vez de 53. • Kernighan, B. W y Ritchie, D. M. “El lenguaje de programación C”. 1991.
• Cohete ucraniano Tsiklon-3: motores del cohete se apagaron a • Quetglás, Toledo, Cerverón. "Fundamentos de Informática y
367s. del despegue, 6 satélites (Ene/01) Programación“. Capítulos 1 y 2. http://robotica.uv.es/Libro/Indice.html

2023 Lic. Ariel Ferreira Szpiniak 67 2023 Lic. Ariel Ferreira Szpiniak 68
Citar/Atribuir: Ferreira, Szpiniak, A. (2023) Teoría 1: Introducción.
Introducción a la Algorítmica y Programación (3300). Departamento de Computación.
Facultad de Cs. Exactas, Fco-Qcas y Naturales. Universidad Nacional de Río Cuarto.

Usted es libre para:

Compartir: copiar y redistribuir el material en cualquier medio o formato.
Adaptar: remezclar, transformar y crear a partir del material.
El licenciante no puede revocar estas libertades en tanto usted siga los términos de la
licencia.
Bajo los siguientes términos:
Atribución: Usted debe darle crédito a esta obra de manera adecuada, proporcionando un
enlace a la licencia, e indicando si se han realizado cambios. Puede hacerlo en cualquier forma
razonable, pero no de forma tal que sugiera que usted o su uso tienen el apoyo del licenciante.

Compartir Igual: Si usted mezcla, transforma o crea nuevo material a partir de esta obra,
usted podrá distribuir su contribución siempre que utilice la misma licencia que la obra original.

Este material está bajo una Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional

2023 Lic. Ariel Ferreira Szpiniak 69