Algoritmos y estructuras de datos

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

Resolver problemas
¿Qué clase de problemas? ¿Cómo es el proceso para resolverun 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.

Ejemplos de problemas

Ejemplos de problemas

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, …

Buscador de Internet

Buscador de Internet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 dereloj.

• ¡¡El recorrido de todas las páginas tardaría 4,5 segundos!!

Buscador de Internet
• Solución: Darle la vuelta al problema…
agua ayudante cosa las ...

Planificador de rutas

Calcular ruta

Planificador de rutas

Planificador de rutas

Planificador de rutas
• ¿Cómo representar la información (lugares y carreteras)? • ¿Cómo calcular el camino más corto entre doslugares?

Planificador de rutas
• Representación mediante un grafo:
– Lugares = nodos. – Carreteras = arcos entre nodos.
Coruña
171

Oviedo
45 5 356

304
28 0

Bilbao
32

395

Vigo

Zaragoza
296

0 10

Gerona

4

Valladolid
3 40

32

5
34 9

Barcelona

Jaén Sevilla
12 5

2 24 256

278

Cádiz

Granada

241

Badajoz

335

19 3
99

Madrid
25 1191

Valencia

0 15

Murcia

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.

Jugador deAjedrez

• ¿Cómo representar el problema? • ¿Cómo decidir el siguiente movimiento de forma “inteligente”? ¿?

Jugador de Ajedrez
Situación Inicial

Movimientos de A Movimientos de B Movimientos de A

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

El Sudoku
8 2 1 9 4 1 4 1 5 6 3 4 5 7 6 7 9 9 8 9 2 7 3 4 7 4 1 2 4 5 2 4
http://websudoku.com

8

5

ElSudoku
5 2 7 9 4 6 3 1 8 8 3 6 2 1 5 4 7 9 1 4 9 7 8 3 5 6 2 9 7 1 8 5 2 6 3 4 2 6 3 4 9 1 7 8 5 4 8 5 6 3 7 9 2 1 3 9 2 5 6 8 1 4 7 7 1 4 3 2 9 8 5 6 6 8 1 7 4 2 9 3
http://websudoku.com

5

¡Atención porque llega...!

7 1 4

3 8 1 6 7 2 2 1 5 6 8 7 3

8

7

3 8 1 7 6 2 5 5 8 1 3 9

9

9 4

2

4 7 6 5 1

6

¡El Sudoku Samurai!

5 3

8

6

4

4 6 3 2 4 9 7 1...