Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008

Técnicas Algorítmicas

Gonzalo Sainz-Trápaga (GomoX)

Charlas PC++ 2008www.pcmasmas.com26 de Julio de 2008

Temas

1. Problemas2. Técnicas exactas3. Técnicas aproximadas

Problemas

De decisión

•¿183287 es primo?

•¿Cuál es el mínimo de la secuencia [7,8,32]?

Elegir o proponer una solución.

De optimización

• Hallar el camino más corto entre Buenos Aires y Beijing

• Ordenar la secuencia: [1,9,34,-2,6,28]

Técnicas Exactas

Fuerza Bruta

Probar todaslas opciones.

Fuerza Bruta

Se recorre todo el universode soluciones posibles.

for cand in generarCandidatos(): if esSolucion(cand): return cand

Fuerza Bruta

for p in permutaciones(secuencia): if estaOrdenado(p): return p

Ordenar por fuerza bruta:

Fuerza Bruta

• Limitaciones

• Usos reales

Backtracking

Probar todaslas opciones,

de forma más inteligente.

Backtracking

Orden!

Backtracking

Ordenar la secuencia [3,1,2]:

Backtracking

• Podas

• Recursión

Backtracking

• Limitaciones

• Usos reales

Divide & Conquer

“Vamos por partes”- Jack el destripador

Divide & Conquer

• “Dividir”• “Conquistar”• “Combinar”

Divide & Conquer

def mergesort(l): m1 = l[0:len(l)/2] m2 = l[len(l)/2:len(l)] return combinar(mergesort(m1), mergesort(m2))

Merge sort:

Divide & Conquer

• Recursión

• Paralelismo

Divide & Conquer

• Usos reales

• Limitaciones

ProgramaciónDinámica

“Usar COBOL arruina el cerebro”

- Edsger Dijkstra

Programación Dinámica

SubestructuraÓptima

Recursión

def fibo(n): if n == 1 or n == 2: return 1 else: return fibo(n-1) + fibo(n-2)

Fibonacci:

Programación Dinámica

Programación Dinámica

fibo(n) = fibo(n-1) + fibo(n-2)

fibo(n-2) + fibo(n-3) fibo(n-3) + fibo(n-4)

fibo(n-4) + fibo(n-5)

Programación Dinámica

Solapamiento

A B

• “Top-down”

• “Bottom-up”

Programación Dinámica

tabla = {}def fibo(n): if n == 1 or n == 2: return 1 else: if n in tabla: return tabla[n] else: res = fibo(n-1) + fibo(n-2) tabla[n] = res return res

Fibonacci (top down):

Programación Dinámica

tabla = {}def fibo(n): if n == 1 or n == 2:

return 1 else: tabla[1] = fibo(1) tabla[2] = fibo(2) for i in 3…n-1: tabla[i] = tabla[i-1] + tabla[i-2] return tabla[n-1] + tabla[n-2]

Fibonacci (bottom up):

Programación Dinámica

def fibo(n): if n == 1 or n == 2:

return 1 else: t1 = fibo(1) t2 = fibo(2) for i in 3…n-1: tmp = t2 t2 = t1 + t2 t1 = tmp return t1 + t2

Fibonacci (bottom up 2.0):

Programación Dinámica

• Usos reales

• Limitaciones

Programación Dinámica

ProgramaciónLineal

• Ecuaciones lineales

• SIMPLEX

• Programación entera

Programación Lineal

Técnicas Aproximadas

"La mayor deficiencia de la raza humana es nuestra incapacidad para comprender la función exponencial."

- Albert Bartlett

Heurísticas

Metaheurísticas

Algoritmos Golosos

• Usos

• Limitaciones

Algoritmos golosos

Taboo Search

Algoritmos Genéticos

- Charles Darwin

generacion = 0poblacion = generarIndividuosAleatorios()while(generacion < 5000): padres = poblacion.tomarAlgunos() poblacion.agregar(padres.procrear()) poblacion.mutarAlgunos() poblacion.matarAlgunos() generacion++

poblacion.sort(aptitud)machoAlfa = poblacion[0]return machoAlfa

Algoritmo genético:

Algoritmos Genéticos

• Usos

• Parametrización

Algoritmos Genéticos

Otras metaheurísticas

GRASPColonias de hormigasRedes neuronales

Problemas de lasMetaheurísticas

• Confiabilidad

• Parametrización

Más opciones!

• Algoritmos aproximados

• Algoritmos híbridos

Esta charla fue traídaa ustedes por cortesía

de Lotux Neon.

¿Preguntas?

Fin.