SLIDES - Tecnología Digital V Diseño de Algoritmos (1)

Vista previa del material en texto

COMPLEJIDAD COMPUTACIONAL (REPASO)
Tecnología Digital V: Diseño de Algoritmos
Universidad Torcuato Di Tella
Bienvenidos!
# Objetivos. Conocer técnicas de diseño de algoritmos que nos permitan
resolver problemas más difíciles que los que pudimos resolver hasta
ahora.
1. Técnicas algorítmicas: recursión, divide and conquer, backtracking,
programación dinámica, heurísticas y metaheurísticas, algoritmos
aproximados, etc.
2. Introducción a la teoría de grafos.
3. Introducción a la teoría de NP-completitud.
4. Aplicaciones. Cómo usar estas técnicas para modelar y resolver problemas
prácticos de gran relevancia.
5. Implementación y estructuras de datos. Benchmarking: cómo evaluar la
performance? Buenas prácticas más allá del testing unitario.
TD5: Diseño de Algoritmos - UTDT 2
Sobre la cursada
# Clases.
◦ Dos módulos de clases teóricas y dos módulos de clases prácticas por
semana.
◦ Las disposición de clases prácticas / teóricas podría cambiar debido al
calendario.
# Evaluación
◦ Dos parciales escritos e individuales. Se aprueban con 60/100.
◦ Dos trabajos prácticos grupales. Se aprueban con 60/100.
◦ Cuatro mini-ejercicios individuales, periódicos, distribuídos a lo largo del
cuatrimestre. Aprobado / No Aprobado.
# Comunicación. Todo el material de las clases y las consultas se canalizan
a través del Campus Virtual.
TD5: Diseño de Algoritmos - UTDT 3
Complejidad computacional: Las reglas del juego
# En el contexto de la teoría de complejidad computacional, llamamos
problema a la descripción de los datos de entrada y la respuesta a
proporcionar para cada dato de entrada.
# Una instancia de un problema es un juego válido de datos de entrada.
# Ejemplo:
1. Entrada: Un número = entero no negativo.
2. Salida: ¿El número = es primo?
# En este ejemplo, una instancia está dada por un número entero no
negativo.
TD5: Diseño de Algoritmos - UTDT 4
Complejidad computacional: Las reglas del juego
# Suponemos una Máquina RAM (random access memory).
1. La memoria está dada por una sucesión de celdas numeradas. Cada celda
puede almacenar un valor de 1 bits.
2. Supondremos habitualmente que el tamaño 1 en bits de cada celda está fijo,
y suponemos que todos los datos individuales que maneja el algoritmo se
pueden almacenar con 1 bits.
3. Se tiene un programa imperativo no almacenado en memoria, compuesto
por asignaciones y las estructuras de control habituales.
4. Las asignaciones pueden acceder a celdas de memoria y realizar las
operaciones estándar sobre los tipos de datos primitivos habituales.
TD5: Diseño de Algoritmos - UTDT 5
Complejidad computacional: Las reglas del juego
# Cada instrucción tiene un tiempo de ejecución asociado.
1. El acceso a cualquier celda de memoria, tanto para lectura como para
escritura, es constante.
2. Las asignaciones y el manejo de las estructuras de control se realiza en
constante.
3. Las operaciones entre valores lógicos son constante.
# Las operaciones entre enteros/reales dependen de 1:
1. Las sumas y restas trabajan bit a bit.
2. Las multiplicaciones y divisiones también pero requieren algoritmos más
complejos.
TD5: Diseño de Algoritmos - UTDT 6
Repaso: Notación $
Dadas dos funciones 5 , 6 : ℕ→ ℝ, decimos que:
# 5 (=) = $(6(=)) si existen 2 ∈ ℝ+ y =0 ∈ ℕ tales que 5 (=) ≤ 2 6(=) para
todo = ≥ =0.
# 5 (=) = Ω(6(=)) si existen 2 ∈ ℝ+ y =0 ∈ ℕ tales que 5 (=) ≥ 2 6(=) para
todo = ≥ =0.
# 5 (=) = Θ(6(=)) si 5 = $(6(=)) y 5 = Ω(6(=)).
TD5: Diseño de Algoritmos - UTDT 7
Complejidad computacional: Las reglas del juego
# Tiempo de ejecución de un algoritmo �:
)�(�) = suma de los tiempos de ejecución de las instrucciones realizadas
por el algoritmo con la instancia �.
# Dada una instancia �, definimos |� | como la cantidad de bits necesarios
para almacenar los datos de entrada de �.
1. Si 1 está fijo y la entrada ocupa = celdas de memoria, entonces
|� | = 1= = $(=).
# Complejidad de un algoritmo �:
5�(=) = max�:|� |== )�(�).
TD5: Diseño de Algoritmos - UTDT 8
Repaso: Notación $
# Cada instrucción tiene un tiempo de ejecución asociado.
1. El acceso a cualquier celda de memoria, tanto para lectura como para
escritura, es $(1).
2. Las asignaciones y el manejo de las estructuras de control se realiza en $(1).
3. Las operaciones entre valores lógicos son $(1).
# Las operaciones entre enteros/reales dependen de 1:
1. Las sumas y restas son $(1).
2. Las multiplicaciones y divisiones son $(1 log 1).
⇒ Si 1 está fijo, estas operaciones son $(1). En cambio, si no se puede
suponer esto, entonces hay que contemplar que el costo de estas
operaciones depende de 1.
TD5: Diseño de Algoritmos - UTDT 9
Repaso: Notación $
# Si un algoritmo es $(=), se dice lineal.
# Si un algoritmo es $(=2), se dice cuadrático.
# Si un algoritmo es $(=3), se dice cúbico.
# Si un algoritmo es $(=:), : ∈ ℕ, se dice polinomial.
# Si un algoritmo es $(log =), se dice logarítmico.
# Si un algoritmo es $(3=), 3 ∈ ℝ+, se dice exponencial.
# Cualquier función exponencial es peor que cualquier función polinomial:
Si :, 3 ∈ ℕ entonces := no es $(=3).
# La función logarítmica es mejor que la función lineal (no importa la base),
es decir log = es $(=) pero no a la inversa.
TD5: Diseño de Algoritmos - UTDT 10
Repaso: Trabajando con la notación $
# Suma de funciones.
$( 5 (=)) + $(6(=)) −→ $( 5 (=) + 6(=))
# Multiplicación de funciones. Sea 2 ∈ ℝ,
2 ∗ $( 5 (=)) −→ $( 5 (=))
$( 5 (=)) × $(6(=)) −→ $( 5 (=) × 6(=))
Ejercicio 1
Dados dos algoritmos
# � ∈ $(=)
# � ∈ $(=2)
Cuál es la complejidad ejecutar �
inmediatamente después de �?
Ejercicio 2
Demostrar que las relaciones $ son
transitivas. Si
# 5 (=) = $(6(=)), y
# 6(=) = $(ℎ(=)),
entonces 5 (=) = $(ℎ(=)).
TD5: Diseño de Algoritmos - UTDT 11
Problemas bien resueltos
Definición: Decimos que un problema está bien resuelto si existe un
algoritmo de complejidad polinomial para el problema.
= = 10 = = 20 = = 30 = = 40 = = 50
$(=) 0.01 ms 0.02 ms 0.03 ms 0.04 ms 0.05 ms
$(= log =) 0.01 ms 0.03 ms 0.04 ms 0.06 ms 0.08 ms
$(=2) 0.10 ms 0.40 ms 0.90 ms 1.60 ms 2.50 ms
$(=3) 1.00 ms 8.00 ms 27.00 ms 64.00 ms 0.12 sg
$(2=) 1.02 ms 1.04 sg 17.90 min 12 días 35 años
$(3=) 0.59 sg 58 min 6 años 3855 siglos 2 × 108 siglos!
TD5: Diseño de Algoritmos - UTDT 12
Problemas bien resueltos
Instancia más grande que se puede resolver en 1 minuto en función de la
velocidad de la computadora disponible:
92 kIPS 2.66 MIPS 9.7 MIPS 177 MIPS
IBM 4004 Intel 286 Pentium IV Intel Core i7
(1971) (1982) (2000) (2011)
$(=) 5520 1.5 105 5.8 105 1.06 107 (1923x)
$(= log =) 4141 1.0 105 2.7 105 6.19 106 (1495x)
$(=2) 74 399 762 3258 (43x)
$(=3) 17 54 83 219 (12x)
$(2=) 12 17 19 23 (1.88x)
$(3=) 7 10 12 14 (1.88x)
TD5: Diseño de Algoritmos - UTDT 13
Problemas bien resueltos
Convención. Los algoritmos polinomiales se consideran satisfactorios
(cuanto menor sea el grado, mejor), y los algoritmos supra-polinomiales se
consideran no satisfactorios.
No obstante ...
# Si los tamaños de instancia son pequeños, ¿es tan malo un algoritmo
exponencial?
# ¿Cómo se comparan $(=85) con $(1.001=)?
# ¿Puede pasar que un algoritmo de peor caso exponencial sea eficiente en
la práctica?
# ¿Puede pasar que en la práctica sea el mejor?
# ¿Qué pasa si no encuentro un algoritmo polinomial?
TD5: Diseño de Algoritmos - UTDT 14