Problemas, programas, algoritmos y estructuras de datos
Problema: Conjunto de hechos o circunstancias que dificultan la consecución de algún fin.
Algoritmo: Conjunto de reglas finito e inambiguo.
Estructura de datos: Disposición en memoria de la información.
Programa: Algoritmos + Estructuras de datos.
PROBLEMA
PROGRAMA
Algoritmos+
Estructuras de datos
Corrector ortográfico
A, ala, algoritmos, barco, cosa, curso, datos, estructuras, evaluación… prácticas…
palabro
Sí
No
Correcta
Error
Corrector ortográfico
Supongamos un ordenador a 2 GHz.
Supongamos que el diccionario tiene 5 millones de palabras, y el acceso y comparación de cada palabra tarda 100 ciclos de reloj.
Cada palabra tarda 0,25 segundos.
¡¡La corrección de un párrafo de 100 palabras tardaría 25 segundos!!
Corrector ortográfico
1000 palabras en 2 segundos = 1 palabra en 2 milisegundos.
¡125 veces más rápido que la búsqueda básica!
Planificador de rutas
¿Cómo representar la información (lugares y carreteras)?
¿Cómo calcular el camino más corto entre dos lugares?
Planificador de rutas
Representación mediante un grafo:
Lugares = nodos.
Carreteras = arcos entre nodos.
Planificador de rutas
¿Cómo calcular los caminos mínimos en el mapa?
Fuerza bruta: empezar por Cádiz y probar todos los caminos hasta llegar.
Supongamos que limitamos a 20 ciudades, existiendo 6 caminos por ciudad.
¡¡Existen 95 billones de caminos!!
Otro problema con grafos
Problema del viajante: encontrar una ruta que pase por todas las ciudades con el mínimo coste.
El Reto del Viajante
RETO. Encontrar un ciclo para el grafo anterior, superando la mejor solución existente.
Seguir el formato de entrada/salida dado (http://dis.um.es/~ginesgm/aed1.html).
RECOMPENSA.
Un 10 en el tema de grafos para el ganador del reto.
Un comodín para el que baje de 22.000.
Otro reto
EL JUEGO DE LAS CIFRAS.
Dado un conjunto de 6 enteros, encontrar la forma de conseguir otro entero, utilizando las operaciones de suma, resta, producto y división entera (y sin usar cada número más de una vez).
El Reto de las Cifras
RETO. Implementar un programa para resolver el problema, más rápido que la versión del profesor, y que no pierda ninguna solución.
RECOMPENSA.
Un comodín para quien lo supere.
Más +1 punto de notas adicionales.
Evolución e historia de la programación
Lenguajes
de bajo nivel
(Basic, Fortran, Ensamblador, …)
Ejemplo de programa BASIC
10 PAPER 7: BORDER 7: INK 0: BRIGHT 0: FLASH 0
20 DIM a$(22,20): DIM f(22): DIM c(22): DIM g$(11,2): DIM z$(22,18): DIM x$(22)
30 FOR n= 1 TO 22
40 READ f,c: LET b$=CHR$ 19+CHR$ 1: LET f(n)=f: LET c(n)=c
50 FOR m=0 TO 2: READ r$
60 LET b$=b$+CHR$ 22+CHR$ (f+m)+CHR$ c+ r$
70 NEXT m: LET a$(n)=b$: NEXT n: GO SUB 470
80 CLS : FOR N=1 TO 22: PRINT A$(N): NEXT N: IF x$(1)<>" " THEN LET
g$=x$
90 PRINT AT 0,2;"__";AT 1,2;"¦ EBEO";AT 2,2;"¯¦";AT 3,2;"¦¦ OBLE";AT
4,2;"_¯ "; INK 3; AT 19,16;"Adaptacion para"; INK 1;AT
20,19;"MICRO";" HOBBY"
100 PLOT 128,0: DRAW 0,170: DRAW 10,4: DRAW 24,1: DRAW 82,0
110 PLOT 128,0: DRAW 10,4: DRAW 24,1: DRAW 88,0
120 DRAW 0,164: DRAW -2,2: DRAW 0,-164: DRAW -2,2: DRAW 0,164: DRAW –
2,2: DRAW 0,-165
130 PLOT 128,0: DRAW -10,4: DRAW -24,1: DRAW -88,0
140 DRAW 0,164: DRAW 2,2: DRAW 0,-164: DRAW 2,2: DRAW 0,164: DRAW 2,2:
DRAW 0,-164
150 PLOT 128,170: DRAW -10,4: DRAW -24,1: DRAW -82,0
160 DATA 1,12," ¦ "," _ "," ¯‚",1,17," ¦ "," ¦ "," ¦ ",1,22," _ "," _
"," ¯ ",1,27,"¦¦ ","¯¦ "," ¯ "
170 PLOT 128,2: DRAW -10,4: DRAW -24,1: DRAW -85,0
180 PLOT 128,2: DRAW 10,4: DRAW 24,1: DRAW 85,0
Ejemplo de programa BASIC
290 DIM b$(22,2): FOR n=1 TO 11: FOR m=1 TO 2
300 LET s=INT (RND*22)+1
310 IF b$(s,1)=" " THEN LET b$(s,1)=g$(n,1): LET b$(s,2)=g$(n,2): NEXT m: NEXT n: GO TO 330
320 GO TO 300
330 DIM r(22): LET di=0: LET itn=0: LET u=.001
340 PRINT AT 20,2;di: IF di=275000 THEN LET di=350000: PRINT AT 20,2; FLASH 1;di'"CONSEGUIDO EL PLENO EN ";itn;" veces": PRINT #0;"Pulsa una tecla para empezar": GO SUB 440: GO SUB 440: GO SUB 440: PAUSE 0: GO TO 80
350 INPUT n: IF n>22 OR n<1 THEN GO TO 350
360 IF r(n)=1 THEN GO TO 350
370 LET k=n: GO SUB 700
380 INPUT m: IF m>22 OR m<1 OR m=n THEN GO TO 380
390 IF r(m)=1 THEN GO TO 380
400 LET k=m: GO SUB 700
410 LET itn=itn+1: IF b$(n)=b$(m) THEN LET di=di+25000: PAPER 3: LET k=n: GO SUB 720: PAPER 3: LET k=m: GO SUB 720: LET r(n)=1: LET r(m)=1: GO SUB 440: GO SUB 450: GO TO 340
420 BRIGHT 1: PAUSE 45: PAUSE 45: LET f=f(n): LET c=c(n): PRINT AT f,c;a$(n,8);AT f+1,c;a$(n,14);AT f+2,c;a$(n,20): PRINT AT f,c;a$(n,7 TO 8);AT f+1,c;a$(n,13 TO 14);AT f+2,c;a$(n,19 TO 20): BEEP .01,-10: PRINT a$(n): BEEP .02,0
430 LET f=f(m): LET c=c(m): PRINT AT f,c;a$(m,8);AT f+1,c;a$(m,14);AT f+2,c;a$(m,20): PRINT AT f,c;a$(m,7 TO 8);AT f+1,c;a$(m,13 TO 14);AT f+2,c;a$(m,19 TO 20): BEEP .01,-10: PRINT a$(m): BEEP .02,0: BRIGHT 0: GO TO 350
Ejemplo de programa BASIC
430 LET f=f(m): LET c=c(m): PRINT AT f,c;a$(m,8);AT f+1,c;a$(m,14);AT f+2,c;a$(m,20): PRINT AT f,c;a$(m,7 TO 8);AT f+1,c;a$(m,13 TO 14);AT f+2,c;a$(m,19 TO 20): BEEP .01,-10: PRINT a$(m): BEEP .02,0: BRIGHT 0: GO TO 350
440 BEEP .07,15: BEEP .06,25: BEEP .07,35: BEEP .07,35: BEEP .09,40: RETURN
450 INK 8: LET xx=c(n)*8-2: LET yy=177-(f(n)*8): PLOT xx,yy: DRAW 27,0: DRAW 0,-27: DRAW -27,0: DRAW 0,27
460 LET xx=c(m)*8-2: LET yy=177-(f(m)*8): PLOT xx,yy: DRAW 27,0: DRAW 0,-27: DRAW -27,0: DRAW 0,27: INK 0: RETURN
470 RESTORE 260: FOR n=1 TO 22
475 IF n=17 THEN LET g$(6,2)=".": GO TO 540
480 READ p$
490 FOR m=0 TO 7: READ f: POKE USR p$+m,f: NEXT m
520 IF n<12 THEN LET g$(n,1)=p$
530 IF n>11 THEN LET g$(n-11,2)=p$
540 NEXT n: RETURN
700 PAPER 5: LET y$=b$(k,1): LET t$=b$(k,2): LET f=f(k): LET c=c(k): BEEP u,25: PRINT AT f,c+2;t$;AT f+1,c+2;" ";AT f+2,c+2;" ": BEEP u,49: BEEP u,25
710 PRINT AT f,c+1;t$;" ";AT f+1,c+1;" ";y$;AT f+2,c+1;" v": BEEP u,49: BEEP u,25
720 PRINT AT f(k),c(k);b$(k,2);" ";b$(k,2);AT f(k)+1,c(k);" ";b$(k,1);" ";AT f(k)+2,c(k);" v ": BEEP u,49: PAPER 7: RETURN
¿?
Lenguajes de bajo nivel
No existen procedimientos ni funciones
No existen registros ni tipos definidos por el usuario
No existen bloques estructurados (while, repeat, etc.)
En definitiva: no hay abstracciones
Y sin embargo… funciona:
http://dis.um.es/~ginesgm/museo.html
Evolución e historia de la programación
Lenguajes
de bajo nivel
(Basic, Fortran, Ensamblador, …)
Lenguajes
estructurados
(Pascal, C,Modula, ADA, …)
Página siguiente |