Embed Size (px)
Citation preview
11
Introducción a la Computación
para Biólogos, Bioquímicos, Médicos, etc.
22
El problema...
33
La solución...
44
¿Es una solución?
55
La computación...
66
¿Qué es la ciencia de la computación?
Es la disciplina que estudia como resolver problemas con
computadoras.
77 Toda solución computacional involucra...
Posibilidad real de resolver el problema.
88 Toda solución computacional involucra...
Posibilidad. Algoritmo como Solución a un
conjunto de problemas.
99 Toda solución computacional involucra...
Posibilidad. Solución. Espacio Físico de Información.
1010 Toda solución computacional involucra...
Posibilidad. Solución. Espacio. Tiempo de la Respuesta.
1111
Lo que nos interesa como usuarios
Entrada
Salida
Proceso
Problema
Resulta
do
Algoritmo
1212
Un ejemplo típico
Teniendo un conjunto de números S ¿Existe alguna suma de esos números
que de n?
1313
Visualmente...
S, n
{Si, No}
Proceso
Problema
Resulta
do
Algoritmo
1414
Ejemplo sencillo
S = { 3, 5, 7, 8 }, n = 12 sumas posibles:
0, 3, 5, 7, 83 + 5 = 8 3 + 7 = 10 3 + 8 = 11
5 + 7 = 12 5 + 8 = 13 7 + 8 = 153 + 5 + 7 = 15 3 + 5 +8 = 16
3 + 7 + 8 = 18 5 + 7 + 8 = 203 + 5 + 7 + 8 = 22
1515
Visualmente...
{ 3, 5, 7, 8 }, 12
Si
Proceso
Problema
Resulta
do
Algoritmo
1616
¿Es Posible?
No tiene ningún impedimento teórico ó lógico.
1717
¿Existe un Algoritmo?
Si... Y es el siguiente:Para todo subconjunto P de S:
Si la suma de los elementos de P es igual a n entonces la respuesta es SISI.
1818
¿Cuánto Espacio necesita?
Necesitamos recordar S, P y n. ... que ocupan como máximo la
cantidad de 9 números: 4 + 4 + 1 = 9. ¡También se necesita recordar el
algoritmo!
1919
¿Cuánto Tiempo necesita?
Verificar cada subconjunto de S tarda de 0.001 segundo.
El algoritmo usa 0.001 seg. x 16 = 0.016 seg.
2020
Resumiendo...
{ 3, 5, 7, 8 }, 12
Si
Proceso
Problema
Resulta
do
Algoritmo
0.016 seg.9 números
2121
Generalicemos
Cant(S) = cantidad de elementos de S. Cant(P) = cantidad de elementos de P. Cantidad de subconjuntos de S: 2Cant(S)
El algoritmo necesita recordar:Cant(S) + Cant(P) + 1
El algoritmo tarda:0.001 x 2Cant(S)
2222 ¿Pero, para qué usar la computadora para 4 elementos?
¿Cuántos recursos necesitamos para 10 elementos?Espacio: 21Tiempo: 0.001 x 1024 = 1.024 seg
¿y para 20 elementos?Espacio: 41Tiempo: 0.001 x 220 = 1048.576 seg = 17
min
2323
...
¿y para 30 elementos?Espacio: 61Tiempo: 0.001 x 230 = 1x109seg =
17895.7 min. = 298 horas = 12 días. ¿y para 40 elementos?
Espacio: 81Tiempo: 0.001 x 240 = 35 años.
2424
Visualmente...Subconjuntos
0
2E+14
4E+14
6E+14
8E+14
1E+15
1,2E+15
1 2 3 4 5 6 7 8 9 10 11
Subconjuntos
Años
0
5000
10000
15000
20000
25000
30000
35000
40000
1 2 3 4 5 6 7 8 9 10 11
Años
Siglos
0
50
100
150
200
250
300
350
400
1 2 3 4 5 6 7 8 9 10 11
Siglos
2525
¿Opciones?
Tener computadoras más rápidas...¿Qué tanto más rápidas?
Usar muchas computadoras...¿Cuántas?
2626
Esto se lo conoce como complejidad de un problema.
2727
¿Y para qué me sirve saber esto?
Muchos de los problemas de la bioinformática tienen una
complejidad difícil de manejar.
2828
¿Cuáles? (I)
Problemas no posibles:Ensamblado de genomas con repeticionesrepeticiones.Estructuras 3D de proteínas.
Problemas de espacio:Base de datos.
2929
¿Cuáles? (II)
Problemas de tiempo:EnsambladoAlineamiento múltiple.
Filogénia.
3030
Entonces...¿Porque uso computadoras?
Usar computadoras es más barato, son más rápidas y dan buenos
resultados.
3131
3232
Aproximaciones y Heurísticas
Si modificamos el problema de tal manera que la respuesta nos
ayude, entonces es útil.
3333
¿Qué es una heurística?
Heurística, del griego “heuriskein” significa encontrar o descubrir. La heurística trata de métodos o algoritmos exploratorios durante la resolución de problemas en los cuales las soluciones se descubren por la evaluación del progreso logrado en la búsqueda de un
resultado final. Técnicas heurísticas, las cuales son empleadas en
una gran cantidad de disciplinas y áreas del conocimiento y su finalidad es la de entregar soluciones que satisfagan al máximo el problema al cual se pretenden encontrar salidas.
3434
Algoritmo Heurístico
Un algoritmo heurístico es un procedimiento de búsqueda de soluciones casi optímales a un coste computacional razonable, sin ser capaz de garantizar la factibilidad de las soluciones empleadas ni determinar a que distancia de la solución optima nos encontramos.
3535
Características...
No aseguran dar el resultado optimo. No se puede asegurar que tan bueno
es el resultado. El tiempo de los resultados es
aceptable. Se pueden hacer estudios estadísticos
sobre los resultados.
Correcto
3636
Cualquier análisis clínico es una heurística.
Ninguno tiene un 100% de exactitud en sus resultados.
3737
Algunas Heurísticas
Vecino más cercano. Redes neuronales. Algoritmos genéticos. Hidden Markov Model. Funciones Heurísticas. Etc...
¡¡¡Ojo co
n los n
ombres!!!
3838
Aprendizaje automático
Es la disciplina de la ciencia de la computación que estudia un subconjunto de metaheurísticas que tienen la propiedad de
“aprender” heurísticas.
3939
Recordando...
Entrada
Salida
Proceso
Problema
Resulta
do
Algoritmo
4040
Salida
Lo que busca...
Proceso
Proceso
Salida
Lo que se aprendeEntrada
4141
Cosas que hay que tener en cuenta cuando se enseña...
Entrenamiento: Supervisados ó no supervisados.
Muestras de entrenamiento y prueba. Sesgo. Interpretación de los resultados.
4242
Conclusión
4343
Fin de la Presentación
