1 Introducción a la Computación para Biólogos, Bioquímicos, Médicos, etc

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