PDF de programación - Tema 0. Introducción - Algoritmos y Estructuras de Datos

Imágen de pdf Tema 0. Introducción - Algoritmos y Estructuras de Datos

Tema 0. Introducción - Algoritmos y Estructuras de Datosgráfica de visualizaciones

Publicado el 30 de Agosto del 2017
1.161 visualizaciones desde el 30 de Agosto del 2017
1,2 MB
25 paginas
Creado hace 19a (06/10/2004)
Algoritmos y

Estructuras de Datos

Tema 0. Introducción

Objetivo de la asignatura

Objetivo central

SER CAPAZ DE ANALIZAR, COMPRENDER Y

RESOLVER UNA AMPLIA VARIEDAD DE

PROBLEMAS COMPUTACIONALES, DISEÑANDO E
IMPLEMENTANDO SOLUCIONES EFICIENTES Y DE
CALIDAD, COMO RESULTADO DE LA APLICACIÓN

DE UN PROCESO METÓDICO

1

Resolver problemas

¿Qué clase de problemas?

¿Cómo es el proceso para resolver

un problema?

¿Cuándo se dice que la solución es

eficiente y de calidad?

Problemas, programas, algoritmos

y estructuras de datos

PROBLEMA

Algoritmos

+

Estructuras

de datos

PROGRAMA

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

2

Ejemplos de problemas

Ejemplos de problemas

3

Ejemplos de problemas

Buscador de Internet

algoritmos, ayudante, curso,
datos, estructuras, garcía,
ginés, mateos, …

algoritmos, cosa, curso,
datos, estructuras,
evaluación, prácticas, …

agua, botavara, barco,
confeccionar, las, velas, …

4

Buscador de Internet

Buscador de Internet

5

Buscador de Internet

• ¡¡¡Cuatro mil millones de páginas en un

cuarto de segundo!!!

• Problema: ¿cómo estructurar la

información necesaria para realizar las
consultas rápidamente? ¿Qué algoritmos
de búsqueda utilizar?

Buscador de Internet

• Supongamos una red de 1024

ordenadores a 3 GHz.

• Supongamos que cada página tiene 200
palabras, de 8 letras cada una y en cada
letra se tarda 2 ciclos de reloj.

• ¡¡El recorrido de todas las páginas

tardaría 4,5 segundos!!

6

Buscador de Internet

• Solución: Darle la vuelta al problema…

agua

ayudante

cosa

las
. . .

Planificador de rutas

Calcular
ruta

7

Planificador de rutas

Planificador de rutas

8

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.
Coruña
1
7
1

Oviedo

Bilbao

304

Vigo

455

356

Valladolid

1

9

3

3 2 5

Murcia

9

9

8

7

2

Granada

9

280

5
9
3

3

2

4

Zaragoza
296

Gerona

100
Barcelona

Madrid

2

5

1

1

5

0

349

Valencia

1

9

1

1
4
2

3

0

4

5
3
3

Jaén
2 4 2

256

Badajoz

Sevilla
125

Cádiz

Planificador de rutas

• ¿Cómo calcular los caminos mínimos

en el mapa?

• Fuerza bruta: empezar por Cagitán y
probar todos los caminos hasta llegar.

• Supongamos que limitamos a 20

ciudades, existiendo 6 caminos por
ciudad.

• ¡¡Existen 95 billones de caminos!!

Jugador de Ajedrez

• En mayo de 1997 Deep Blue (de IBM)

gana a Kasparov.

10

Jugador de Ajedrez

• ¿Cómo representar el problema?

• ¿Cómo decidir el siguiente movimiento de

forma “inteligente”? ¿?

Jugador de Ajedrez

Situación

Inicial

Movimien-
tos de A

Movimien-
tos de B

Movimien-
tos de A

11

Jugador de Ajedrez

• El árbol de juego del ajedrez representa

todas las posibles partidas del juego.

• Solución: encontrar un camino en el árbol

que llegue hasta la victoria.

• ¿Qué tamaño tiene el árbol de juego del

ajedrez?

Jugador de Ajedrez

• Suponiendo que cada jugador hace unos
50 movimientos, el factor de ramificación
medio es de 35 posibles movimientos.

• Tamaño del árbol: 35100 = 2,5·10154

• ¡¡Sólo existen 1087 partículas subatómicas

en el universo!!

12

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

Problema de las cifras

13

Problema de las cifras

Problema de las cifras

• Caso 2. 6 8 10 9 4 75

835

• Con un algoritmo sencillo, existen unos
100 millones de posibles combinaciones
de los números.

• Si en lugar de 6 números tuviéramos 7

habrían unos 15 mil millones.

• Con 10, algo menos de medio trillón.

14

Evolución e historia de la

programación

Lenguajes
de bajo nivel

(Basic, Fortran,
Ensamblador, …)

Ejemplo de programa BASIC

DIM x$(22)

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):
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
90 PRINT AT 0,2;"▄▄";AT 1,2;"▐ EBEO";AT 2,2;"▀▌";AT 3,2;"▌▐ OBLE";AT

g$=x$
4,2;"▄▀ "; INK 3; AT 19,16;"Adaptacion para"; INK 1;AT
20,19;"MICRO";" HOBBY"

2,2: DRAW 0,-165

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 –
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:
150 PLOT 128,170: DRAW -10,4: DRAW -24,1: DRAW -82,0
160 DATA 1,12," ▌ "," ▄ "," ▀‚",1,17," ▌ "," ▌ "," ▐ ",1,22," ▄ "," ▄
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

"," ▀ ",1,27,"▌▐ ","▀▌ "," ▀ "

DRAW 0,-164

15

Ejemplo de programa BASIC

NEXT m: NEXT n: GO TO 330

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

430 LET f=f(m): LET c=c(m): PRINT AT f,c;a$(m,8);AT

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
u,49: BEEP u,25
";b$(k,1);" ";AT f(k)+2,c(k);" v ": BEEP u,49: PAPER 7: RETURN

710 PRINT AT f,c+1;t$;" ";AT f+1,c+1;" ";y$;AT f+2,c+1;" v": BEEP
720 PRINT AT f(k),c(k);b$(k,2);" ";b$(k,2);AT f(k)+1,c(k);"

¿?

16

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:

TEBEODOBLE

http://dis.um.es/~ginesgm/museo.html

Evolución e historia de la

programación

Lenguajes
de bajo nivel

Lenguajes

estructurados

(Basic, Fortran,
Ensamblador, …)

(Pascal, C,

Modula, ADA, …)

17

Lenguajes estructurados
Concepto de
módulo/unidad

UNIT calculo;

INTERFACE

const
NMAX= 10;
MAX_GUARDA= 2000;

Separación de

interface/implementación

type
TDatosEnt= array [1..NMAX] of integer;
TDatosSal= record
NPasos: Shortint;
Paso: array [1..NMAX-1] of record

O1: byte;
O2: byte;
Fn: byte;

end;

end;

Tipos definidos
por el usuario

Procedimientos

y funciones

procedure Operar (var Arr: TDatosEnt; O1, O2, Func, Nivel: byte; var Vale: boolean); forward;
procedure CalculaCifras (var Entrada: TDatosEnt); forward;
procedure CalculaCifrasRec (var Entrada: TDatosEnt; PA, PB, Func, Nivel: byte); forward;

Lenguajes estructurados
Separación
interface/

implementación

IMPLEMENTATION

var
suma, num: integer;
CopiaOrden: TDatosEnt;

procedure OrdenaComb (var Entrada: TDatosEnt; Nivel: byte);
var
i, j, maxim, pmaxim, tmp: integer;
begin
CopiaOrden:= Entrada;
num:= Nivel;
for i:= 1 to Nivel-1 do begin
maxim:= CopiaOrden[i];
pmaxim:= i;
j:= i+1;
while j<=Nivel do begin
if CopiaOrden[j]>maxim then begin
maxim:= CopiaOrden[j];
....
end;
end;
end;

Procedimiento
con parámetros

Bloques de

control

estructurados

18

Lenguajes estructurados

• Procedimientos y funciones son abstracciones

de control

• Los tipos definidos por el usuario son

abstracciones de datos

• Las unidades, módulos o paquetes son

abstracciones de nivel superior: abstracciones
de funcionalidades

• CIFRAS

Reto del problema 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 10 en la tercera práctica de la
asignatura (diseño de algoritmos).

– Un 10 en el ejercicio correspondiente del

examen
  • Links de descarga
http://lwp-l.com/pdf6654

Comentarios de: Tema 0. Introducción - Algoritmos y Estructuras de Datos (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad