SOLUCIÓN DE PROBLEMASSOLUCIÓN DE PROBLEMAS

Problema Solución

MUNDO REAL

Espacio del Problema

Espacio de la Solución

MODELO

Estructurasde

Datos Abstractas

Operaciones Abstractas

ALGORITMOABSTRACTO

ABSTRACCIÓN

CONCRECCIÓN

Datos dePrueba

Programa Resultados

MUNDO ABSTRACTO

PROBLEMAS

•Imposibles de formular en términos que permitan solución por computador

•Expresables en términos de un modelo formal

Investigar si existe un programa para solucionarlo

Si no existe, se pueden estudiar las propiedades del modelo que ayuda a construir una buena solución

MODELO SOLUCIÓN EN TÉRMINOS DE UN ALGORITMO

ALGORITMOALGORITMO

SECUENCIA FINITA DE PASOS LÓGICOS, CADA UNO DE LOS CUALES

TIENE UN SIGNIFICADO CLARO, PARA

SOLUCIONAR UN PROBLEMA CON UNA CANTIDAD FINITA DE

ESFUERZO, EN UN TIEMPO FINITO

SECUENCIA FINITA DE PASOS LÓGICOS, CADA UNO DE LOS CUALES

TIENE UN SIGNIFICADO CLARO, PARA

SOLUCIONAR UN PROBLEMA CON UNA CANTIDAD FINITA DE

ESFUERZO, EN UN TIEMPO FINITO

LA CONSTRUCCIÓN DE

ALGORITMOS

Para construir un algoritmo, es necesario:

• Tener un problema a resolver• Haberle encontrado solución

Frase del día:

“LA MITAD DE LA BATALLA ES SABER

QUE PROBLEMA SOLUCIONAR”

LA CONSTRUCCIÓN DE

ALGORITMOS cont...

Una vez que se tiene la solución, se puede proceder al diseño del algoritmo.

Pasos:

•Identificar los tipos de objetos que el algoritmo va a usar.

•Seleccionar las variables que representen instancias de cada tipo, para uso del programa.

•Seleccionar estructuras de control y operadores abstractos primitivos que reflejen las manipulaciones de datos.

•Abstraer estas estructuras de control y datos en procedimientos.(Estos procedimientos son “encarnaciones” abstractas del algoritmo.

IMPORTANTE: En este punto, se está muy por encima de

cualquier lenguaje de programación

PROBLEMA

E

A

D

C

B

Diseñar un semàforo para una intersección complicada de calles

SOLUCIÓN

MODELO MATEMÁTICO

GRAFO

VÉRTICES : GIROS PERMISIBLESÁRCOS : GIROS NO PERMISIBLES

DETERMINACIÓN DE GIROS

( AB, AC, AD, BA, BC,...)

GIROS NO SIMULTÁNEOS

ABEA

COLOREAR

ABEA

SOLUCIÓN cont..

AB AC

EA

DCDBDA

BA BC BD

AD

EDECEB

SOLUCIÓN cont..

AB AC

EA

DCDBDA

BA BC BD

AD

EDECEB

BA, DC, EB: Libres.

MACROALGORITMO

1. Seleccionar algún vértice no coloreado y asignarle un nuevo color.

2. Revisar la lista de vértices no coloreados. Para cada vértice no coloreado, determinar si tiene un ARCO a algún vértice ya coloreado con el nuevo color.

Si no lo hay, coloree el vértice con el nuevo color.

SEUDOCÓDIGO

PRIMER REFINAMIENTO

Procedimiento COLOREAR(G:grafo;NUEVOCOLOR:set);

NUEVOCOLOR = [ ] para cada vértice no coloreado V en G

si V no es adyacente a algún vértice en NUEVOCOLOR entonces marque a V como coloreado lleve V a NUEVOCOLOR finsi

finCOLOREAR

SEUDOCÓDIGO cont...

SEGUNDO REFINAMIENTO

Procedimiento COLOREAR(G:grafo;NUEVOCOLOR:set);

NUEVOCOLOR = [ ] para cada vértice no coloreado V en G encontró = falso para cada vértice W en NUEVOCOLOR si hay un arco entre V y W en G entonces encontró = verdadero finsi si (no encontró) marque a V como coloreado lleve V a NUEVOCOLOR finsi

finCOLOREAR

ALGUNAS DEFINICIONES IMPORTANTES

TIPO DE DATOSConjunto de valores que puede tener una variable Ej: BOOLEAN: true, false

ADT (Abstract Data Type)

Modelo matemático con una colección de operaciones definidas sobre el modeloEj: Conjunto :

ESTRUCTURA DE DATOS

Permite representar el modeloEj: arreglo, lista, map, stack

TIPOS DE DATOS ABSTRACTOSBÁSICOS

LISTA

ESTRUCTURA DE DATOS FLEXIBLE QUE PUEDE CRECER O DISMINUIR BAJO DEMANDA, Y LOS ELEMENTOS SE PUEDE

•ACCEDER•INSERTAR•ELIMINAR

EN CUALQUIER POSICIÓN DENTRO DE LA LISTA

ESTRUCTURA DE DATOS FLEXIBLE QUE PUEDE CRECER O DISMINUIR BAJO DEMANDA, Y LOS ELEMENTOS SE PUEDE

•ACCEDER•INSERTAR•ELIMINAR

EN CUALQUIER POSICIÓN DENTRO DE LA LISTA

DEFINICIÓN

LISTAS

OPERACIONES ABSTRACTAS

1. INSERTAR(x, p, L)

Inserta x, en la posición p de L

2. ELIMINAR(p, L)

Borra elemento de la posición p de L

3. LOCALIZAR(x, L)

Retorna a través de LOCALIZAR, la posición de x en L

4. RECUPERAR(p, L)

Retorna a través de RECUPERA, el contenido de la posición p en L

LISTAS cont...

OPERACIONES ABSTRACTAS

5. HACERLISTANULA(L)

Crea o hace una lista vacía

6. PRIMERO(L)

Retorna en PRIMERO, la primera posición de la lista L. Si está vacía, retorna el final de la lista

7. FINAL(L)

Retorna la posición siguiente al “último elemento” de la lista

LISTAS cont...

OPERACIONES ABSTRACTAS

8. PROXIMO(p, L)

Entrega en PROXIMO, la dirección del elemento siguiente a p

9. PREVIO(p, L)

Entrega en PREVIO, la dirección del elemento anterior a p

10. IMPRIMIRLISTA(L)

Imprime los elementos de la lista L