Monografias.com > Computación
Descargar Imprimir Comentar Ver trabajos relacionados

Introducción a los Algoritmos y Estructuras de Datos




Enviado por Pablo Turmero



Partes: 1, 2


    Monografias.com

    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

    Monografias.com

    Corrector ortográfico
    A, ala, algoritmos, barco, cosa, curso, datos, estructuras, evaluación… prácticas…
    palabro

    No
    Correcta
    Error

    Monografias.com

    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!!

    Monografias.com

    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!

    Monografias.com

    Planificador de rutas
    ¿Cómo representar la información (lugares y carreteras)?

    ¿Cómo calcular el camino más corto entre dos lugares?

    Monografias.com

    Planificador de rutas
    Representación mediante un grafo:
    Lugares = nodos.
    Carreteras = arcos entre nodos.

    Monografias.com

    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!!

    Monografias.com

    Otro problema con grafos
    Problema del viajante: encontrar una ruta que pase por todas las ciudades con el mínimo coste.

    Monografias.com

    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.

    Monografias.com

    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).

    Monografias.com

    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.

    Monografias.com

    Evolución e historia de la programación
    Lenguajes
    de bajo nivel

    (Basic, Fortran, Ensamblador, …)

    Monografias.com

    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

    Monografias.com

    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

    Monografias.com

    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
    ¿?

    Monografias.com

    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

    Monografias.com

    Evolución e historia de la programación
    Lenguajes
    de bajo nivel

    (Basic, Fortran, Ensamblador, …)
    Lenguajes
    estructurados

    (Pascal, C,Modula, ADA, …)

    Partes: 1, 2

    Página siguiente 

    Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

    Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

    Categorias
    Newsletter