Resolución de problemas
Método científico
Método computacional
Terminología computacional
Algoritmos
Programas
ALGORITMO - DEFINICIÓN
Es un conjunto prescrito de instrucciones o
reglas bien definidas, ordenadas y finitas
que permite realizar una actividad
mediante pasos sucesivos que no generen
dudas a quien deba realizar dicha actividad.
Conjunto ordenado y finito de operaciones
que permite hallar la solución de un
problema. (Real Academia Española © Todos los derechos reservados)
ALGORITMOS - PROPIEDADES
Tiempo secuencial
Estado abstracto
Exploración acotada
ALGORITMOS - EJEMPLOS
Receta de cocina.
Instrucciones para armar un juguete
Algoritmo de búsqueda
Algoritmo de compresión de archivos
Algoritmo de reconocimiento facial
Algoritmo de detección de intrusos
Etc.
DISEÑO – ENFOQUE ALGORÍTMICO
Fuerza Bruta: En la práctica es una de las más usadas, y aunque no
conduce a algoritmos óptimos, pueda aplicarse a un sin fin de
problemas.
Dividey vencerás: Técnica basada en la partición de un problema en
subproblemas más pequeños; del mismo tamaño y tipo; se resuelven los
subproblemas y sus soluciones se combinan para obtener la solución del
problema original.
Disminuye y vencerás: Consiste en resolver un problema, reduciendo el
tamaño de las instancias lo más posible y luego resolver recursivamente
hasta obtener la solución de la instancia original.
Transforma y vencerás: Se basa en transformar una instancia dada en
otra para un mismo problema, facilitando de esta manera su solución.
ALGORITMOS – FORMAS DE REPRESENTACIÓN
Lenguaje natural.
Pseudocódigo
Diagrama de flujo
Lenguajes de programación.
ALGORITMOS - MEDIOS DE EXPRESIÓN
Se realizan en tres niveles:
1. Descripción de alto nivel
2. Descripción formal
3. Implementación
ALGORITMO - EJEMPLO
Conocimentos previos para diseño de algoritmos
Aritmética computacional
Lógica proposicional
TRABAJO: (PPT + aplicación (vídeo y/o pizarra)
Pesudocódigo (3)
Diagrama de Nassi Shenierderman (4)
Lenguaje tipado y no tipado (1)
Lenguaje de especificación (2)
Diagramas de flujo (5)
Software de diseño de algoritmos. (8)
Estructuras de datos (7)
Estructuras de control (6)
Teoría automatas, lenguajes formales (9)
PREGUNTAS
Tipos de datos
Es un atributo de los datos.
¿Qué valores puede tomar?
¿Qué operaciones se pueden realizar?
Los más comunes:
Números enteros
Números con signo
Números decimales: coma flotante
Cadenas alfanuméricas
Tipos de datos
CARÁCTER
Char 0-255 8 bits por caracter
NUMÉRICO
Byte 8 bits
Short 16 bits
Int 32 bits
Long 64 bits
DECIMAL
Float 32 bits
Double 64 bits
BOOLEANOS
Boolean 8 bits
En java: …
¿Preguntas de aplicación?
¿En qué casos de variables usamos los tipos de
datos siguientes?
Booleano
Float
Double
Int
LENGUAJE NO TIPADO
Característica de un lenguaje de programación que no controla o tiene débiles controles en
los tipos de datos en un código e programación.
Los lenguajes de programación no tipados o débilmente tipados no controlan los tipos de las
variables que declaran, de este modo, es posible usar variables de cualquier tipo en un mismo
escenario. Por ejemplo, una función puede recibir como parámetro un valor entero, cadena de
caracteres, flotante, etc.
No son necesarias las conversiones de tipos, por lo tanto el siguiente ejemplo es correcto:
a = 2 //a es un entero
cad = "prueba de texto" //cad es una cadena de caracteres
resultado = cad + a //resultado es una cadena de
caracteres (las conversiones dependen del lenguaje)
Lenguaje tipado y no tipado
Loslenguajes tipado definen la característica propia del tipo
de dato de la variable.
funcion bizzbuzz para (i <- 1; i<=100; i++) { …
int i = 1; ...
Los lenguajes débilmente tipado no requieren que se designe un
tipo de variable.
Ejemplos de lenguaje no tipado
PHP:Una variable que es un Array luego se convierta en un
entero o un String sin ningún problema.
Los lenguajes no tipados, o débilmente tipados, al definir una variable
no requieren de que se les asigne un tipo de variable, es mas pueden
cambiar el tipo de variable en cualquier momento, el caso más
conocido en un lenguaje muy popular es en PHP, no hay ningún
problema en que una variable sea una Array y luego se convierta en un
entero o un String.
Ejemplo en Matlab
El lenguaje M tiene tipado débil a la hora de
trabajar con valores lógicos.
En muchas situaciones donde se requiere un
valor de tipo lógico, el lenguaje M admite
valores de otros tipos.
Por ejemplo, si es un valor numérico, si es
igual a 0 asume que es equivalente a un valor
lógico falso.
Si tiene cualquier otro valor, es verdadero.
Si lo que se encuentra es un vector, asume
que es falso si el vector está vacío, y
verdadero si no lo está.
El valor numérico cero es siempre falso. Al ejecutar este código, que espera
siempre un valor lógico a continuación de if
1. if 0
2. disp('Es verdadero');
3. else
4. disp('Es falso');
5. end
obtenemos el mensaje Es falso.
Si lo cambiamos a 18 (por poner un valor diferente a cero):
1. if 18
2. disp('Es verdadero');
3. else
4. disp('Es falso');
5. end
obtenemos el mensaje Es verdadero.
Lo mismo ocurre con valores negativos:
1. if -7
2. disp('Es verdadero');
3. else
4. disp('Es falso');
5. end
obtenemos el mensaje Es verdadero.
Si probamos ahora con vectores, cualquier vector no vacío se entiende como
verdadero:
1. if [1 2 3]
2. disp('Es verdadero');
3. else
4. disp('Es falso');
5. end
obtenemos el mensaje Es verdadero.
En cambio, el vector vacío se entiende como falso:
1. if []
2. disp('Es verdadero');
3. else
4. disp('Es falso');
5. end
obtenemos el mensaje Es falso.
¿Pero qué ocurre por ejemplo con un vector todo de ceros?
1. if [0 0 0]
2. disp('Es verdadero');
3. else
4. disp('Es falso');
5. end
obtenemos el mensaje Es falso.
Es decir, si el vector no está vacío, pero todos los elementos que contiene se
pueden evaluar como falso, el intérprete le asigna el valor falso. Sin
embargo, en ocasiones puede ser complicado adivinar qué va a entender el
intérprete.
¿Se entenderá como verdadero o como falso?
1. if [0 1 0]
2. disp('Es verdadero');
3. else
4. disp('Es falso');
5. end
obtenemos el mensaje Es falso.
El vector no está vacío, y uno de sus elementos no se entendería como falso.
Sin embargo, se muestra el mensaje Es falso.
Definición:
Se dice que un lenguaje de programación fuertemente tipado
es cuando no se permiten variaciones sobre los tipos de datos,
esto quiere decir que, necesitamos una variable de un tipo
concreto, no se puede usar como si fuera de otro tipo, solo
que se haga una conversión.
La mayoría de los lenguajes que vimos en la clase de
imperativos son fuertemente tipados a diferencia de los
lenguajes declarativos que suelen no estar tipado.
TIPOS:
Tipado estático.
Tipado dinámico.
TIPADO ESTÁTICO:
Se dice de un lenguaje de programación que usa un tipado
estático cuando la comprobación de tipificación se realiza
durante la compilación, y no durante la ejecución.
Ejemplos de lenguajes que usan tipado estático son C, C+
+ , Java y Haskell. Comparado con el tipado dinámico, el
estático permite que los errores de programación sean
detectados antes, y que la ejecución del programa sea
más eficiente.
TIPADO DINÁMICO:
Se dice de un lenguaje de programación que usa un tipado dinámico cuando
la comprobación de tipificación se realiza durante su ejecución en vez de
durante la compilación.
Ejemplos de lenguajes que usan tipado dinámico son Perl , Python y Lisp .
Comparado con el tipado estático, o sistema de enlazado temprano, el
tipado dinámico es más flexible (debido a las limitaciones teóricas de la
decidibilidad de ciertos problemas de análisis de programas estáticos, que
impiden el mismo nivel de flexibilidad que se consigue con el tipado
estático), a pesar de ejecutarse más lentamente y ser más propensos a
contener errores de programación.
CARACTERÍSTICAS DE TIPADO
DINÁMICO
• Una misma variable puede tomar valores de distinto tipo en distintos momentos.
• La mayoría de lenguajes de tipado dinámico son lenguajes interpretados.
Por ejemplo, en C# o java, para utilizar una variable de nombre "i" que
contenga un entero
//en C# o java
int i; //Primero se declara
i=3; //y luego se utiliza
No es posible asignar un valor de otro tipo a una variable de un tipo
concreto:
//en C# o java
int i;
i=3; //correcto
i="hola"; //incorrecto
EJEMPLO: C
TIPADO FUERTE
A=2
B= “2”
Concatenar (A,B) { error de tipo}
Sumar (A,B) {error de tipos}
Concatenar (srt (A),(B)) {retorna “22”}
Sumar (A, int (B)) { retorna 4}
VENTAJAS DEL TIPADO ESTÁTICO
Y TIPADO DINÁMICO
La ventaja del tipado estático es que se pueden evitar muchos errores en tiempo de
compilación, sin necesidad de esperar a la ejecución para verlos.
La ventaja del tipado dinámico es su flexibilidad.
Lenguaje de especificación
También llamado lenguaje de descripción.
Esun lenguaje formal encargado de construir modelos de los
sistemas que se desea elaborar.
Noson interpretados o compilados pero especifican, modelan,
coceptualizan y validan procesos.
Se clasifican en:
Formales
No formales
Estructura Indica la forma que debe tener una solucion.
problema nombre(parametros) = nombreRes : tipoRes
Encabezado nombre: nombre que le damos al problema
sera resuelto por una funcion con ese mismo nombre
nombreRes: nombre que le damos al resultado
tipoRes: tipo de datos del resultado
parametros: lista que da el tipo y el nombre de cada uno
Ejemplo: Resta de 2 números
problema resta(minuendo; sustraendo : Int) = res : Int
la funcion se llama resta da un resultado que vamos a llamar res
y es de tipo Int (los enteros) depende de dos parametros: minuendo y sustraen
.tambien son de tipo Int
condicion sobre los argumentos I el programador da por ciertaI lo que requiere la funcion para
Precondición hacer su tarea
I por ejemplo: \el valor de entrada es un real no negativo"
condicion sobre el resultado
I debe ser cumplida por el programador, siempre y cuando el usuario haya cumplido la
Poscondición precondicion
I lo que la funcion asegura que se va a cumplir despues de llamarla (si se cumpla la
Lenguaje de especificación – Ejemplo 2
