técnicas algorítmicas gonzalo sainz-trápaga (gomox) charlas pc++ 2008 26 de julio de 2008
TRANSCRIPT
![Page 1: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/1.jpg)
Técnicas Algorítmicas
Gonzalo Sainz-Trápaga (GomoX)
Charlas PC++ 2008www.pcmasmas.com26 de Julio de 2008
![Page 2: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/2.jpg)
Temas
1. Problemas2. Técnicas exactas3. Técnicas aproximadas
![Page 3: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/3.jpg)
Problemas
![Page 4: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/4.jpg)
De decisión
•¿183287 es primo?
•¿Cuál es el mínimo de la secuencia [7,8,32]?
![Page 5: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/5.jpg)
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]
![Page 6: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/6.jpg)
Técnicas Exactas
![Page 7: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/7.jpg)
Fuerza Bruta
Probar todaslas opciones.
![Page 8: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/8.jpg)
Fuerza Bruta
Se recorre todo el universode soluciones posibles.
for cand in generarCandidatos(): if esSolucion(cand): return cand
![Page 9: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/9.jpg)
Fuerza Bruta
for p in permutaciones(secuencia): if estaOrdenado(p): return p
Ordenar por fuerza bruta:
![Page 10: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/10.jpg)
Fuerza Bruta
• Limitaciones
• Usos reales
![Page 11: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/11.jpg)
Backtracking
Probar todaslas opciones,
de forma más inteligente.
![Page 12: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/12.jpg)
Backtracking
Orden!
![Page 13: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/13.jpg)
Backtracking
Ordenar la secuencia [3,1,2]:
![Page 14: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/14.jpg)
Backtracking
• Podas
• Recursión
![Page 15: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/15.jpg)
Backtracking
• Limitaciones
• Usos reales
![Page 16: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/16.jpg)
Divide & Conquer
“Vamos por partes”- Jack el destripador
![Page 17: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/17.jpg)
Divide & Conquer
• “Dividir”• “Conquistar”• “Combinar”
![Page 18: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/18.jpg)
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:
![Page 19: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/19.jpg)
Divide & Conquer
• Recursión
• Paralelismo
![Page 20: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/20.jpg)
Divide & Conquer
• Usos reales
• Limitaciones
![Page 21: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/21.jpg)
ProgramaciónDinámica
“Usar COBOL arruina el cerebro”
- Edsger Dijkstra
![Page 22: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/22.jpg)
Programación Dinámica
SubestructuraÓptima
Recursión
![Page 23: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/23.jpg)
def fibo(n): if n == 1 or n == 2: return 1 else: return fibo(n-1) + fibo(n-2)
Fibonacci:
Programación Dinámica
![Page 24: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/24.jpg)
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)
![Page 25: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/25.jpg)
Programación Dinámica
Solapamiento
A B
![Page 26: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/26.jpg)
• “Top-down”
• “Bottom-up”
Programación Dinámica
![Page 27: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/27.jpg)
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
![Page 28: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/28.jpg)
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
![Page 29: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/29.jpg)
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
![Page 30: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/30.jpg)
• Usos reales
• Limitaciones
Programación Dinámica
![Page 31: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/31.jpg)
ProgramaciónLineal
![Page 32: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/32.jpg)
• Ecuaciones lineales
• SIMPLEX
• Programación entera
Programación Lineal
![Page 33: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/33.jpg)
Técnicas Aproximadas
![Page 34: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/34.jpg)
"La mayor deficiencia de la raza humana es nuestra incapacidad para comprender la función exponencial."
- Albert Bartlett
![Page 35: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/35.jpg)
Heurísticas
![Page 36: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/36.jpg)
Metaheurísticas
![Page 37: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/37.jpg)
Algoritmos Golosos
![Page 38: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/38.jpg)
• Usos
• Limitaciones
Algoritmos golosos
![Page 39: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/39.jpg)
Taboo Search
![Page 40: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/40.jpg)
Algoritmos Genéticos
- Charles Darwin
![Page 41: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/41.jpg)
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
![Page 42: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/42.jpg)
• Usos
• Parametrización
Algoritmos Genéticos
![Page 43: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/43.jpg)
Otras metaheurísticas
GRASPColonias de hormigasRedes neuronales
![Page 44: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/44.jpg)
Problemas de lasMetaheurísticas
• Confiabilidad
• Parametrización
![Page 45: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/45.jpg)
Más opciones!
• Algoritmos aproximados
• Algoritmos híbridos
![Page 46: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/46.jpg)
Esta charla fue traídaa ustedes por cortesía
de Lotux Neon.
![Page 47: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/47.jpg)
¿Preguntas?
![Page 48: Técnicas Algorítmicas Gonzalo Sainz-Trápaga (GomoX) Charlas PC++ 2008 26 de Julio de 2008](https://reader036.vdocumento.com/reader036/viewer/2022062309/5665b4341a28abb57c8ff2c1/html5/thumbnails/48.jpg)
Fin.