Bueno como lo prometi, aqui estan algunas cosas y curiosidades que me plantearon despues de exponer la clase el día del jueves. Aqui pongo, el tema de kruskal en la deteccion de celulas cancerosas (aclaracion) y el video de la clase. __________________________________________________________
Prueba "Kruskal - Wallis" Bueno para empezar, en el proyecto 5 explique el algoritmo de Joseph Kruskal (MST). En la informacion que saque venia que tambien se puede usar en la deteccion de celulas cancerosas, me puse a investigar y encontre la prueba "Kruskal-Wallis". Al principio se puede pensar que es lo mismo, pero la verdad es que no. Esta prueba fue hecha por William H Kruskal. Segun creo, hubo un error de informacion debido a los apellidos, porque Joseph es hermano del matemático y estadista William Kruskal (autor de la Prueba de Kruskal-Wallis), y del matemático y físico Martin Kruskal (autor de las coordenadas de Kruskal-Szekeres), entonces, en la informacion que saque se pudo confundir los proyectos de los hermanos.
La prueba de Kruskal-Wallis es un método no paramétrico para probar si un grupo de datos proviene de la misma población. Intuitivamente, es idéntico al ANOVA con los datos reemplazados por categorías. Si quieren informacion del metodo click AQUI
Ejemplo: Relación entre las reservas de hierro maternas y del recién nacido
Material y métodos. Diseño transversal en el que se incluyó a 163 mujeres embarazadas y sus neonatos de término, derechohabientes del Hospital de Ginecología y Obstetricia número 15 del Instituto Mexicano del Seguro Social (IMSS) en Chihuahua, Chih., México. Se analizaron antecedentes maternos. Se determinaron niveles de hemoglobina, hematocrito y ferritina sérica en muestras maternas y de cordón umbilical. Se definieron reservas de hierro maternas de acuerdo a ferritina (µg /l): bajas £11.9, moderadas de 12 a 20 y normales ³20.1. Se utilizó la prueba de Kruskal Wallis para establecer diferencias entre grupos, ji cuadrada para diferencia de proporciones y r de Pearson para establecer la relación entre reservas de hierro maternas y del recién nacido.
Tengo que recalcar que no es un ejemplo de celulas cancerosas, pero se da a entender con esto que este metodo se utiliza para pruebas medicasy muy posiblemente se utilice para reconocer las celulas cancerosas __________________________________________________________
El video del proyecto 5
aqui el video de la clase, perdonen la calidad de video, mi celular no es tan potente, pero espero que el audio se oiga bien. __________________________________________________________
en la prueba kruskal - wallis la verdad es que no encontre mucha informacion, si alguien tiene mas informacion o piensa que la informacion aqui subida esta mal, hagamelo saber por medio de un comentario en esta entrada.
Hola raza, bueno para pedirles un favor yo subi los puntos extra el miercoles en la madrugada por unos problemillas de conexion que tuve el lunes y martes
Les agradeceria si pudieran checar la entrada de Puntos Extra y luego ir a esta direccion de las lista de correos:
y comentaran a su parecer, cuantos puntos extra me dan :D __________________________________________________________
en otro tema, mas al rato subire algunas cosillas, engtre ellas tratare de buscar lo de la ultilizacion del algoritmo de Kruskal en el reconocimiento de celulas cancerosas, que la verdad me quede intrigado de como se utilizaria este algoritmo.
Saludos raza, comenten! yo ahorita me paso a los blogs, porque tengo algunas dudas con algunos temas para que respondan!
Árbol: Es un grafo en el que existe un único nodo desde el que se puede acceder a todos los demás y cada nodo tiene un único predecesor, excepto el primero, que no tiene ninguno. También podemos definir un árbol como: o Un grafo conexo y sin ciclos. o Un grafo sin ciclos y con n-1 aristas, siendo n el número de vértices.
Grado de un nodo: en un árbol es el número de subárboles de aquel nodo (en el ejemplo, el grado de v1 es 2 y de v2 1). Denominamos hojas en un árbol a los nodos finales (v3, v5 y v6). Un árbol de máximo alcance : es aquel que obtenemos en un grafo conexo y sin ciclos. Árbol de mínima expansión: Árbol de máximo alcance cuyo valor es mínimo, es decir, la suma de sus aristas es mínima. ______________________________________________________
Joseph B. Kruskal investigador del Math Center (Bell-Labs), que en 1956 descubrió su algoritmo para la resolución del problema del Árbol de coste total mínimo (minimum spanning tree - MST) también llamado árbol recubridor euclídeo mínimo. Este problema es un problema típico de optimización combinatoria, que fue considerado originalmente por Otakar Boruvka (1926) mientras estudiaba la necesidad de electrificación rural en el sur de Moravia en Checoslovaquia.
El objetivo del algoritmo de Kruskal es construir un árbol (subgrafo sin ciclos) formado por arcos sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.
Algoritmo de Kruskal:
El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor total de todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido mínimo para cada componente conexa). El algoritmo de Kruskal es un ejemplo de algoritmo voraz.
El algoritmo de Kruskal permite hallar el árbol minimal de cualquier grafo valorado (con capacidades). Hay que seguir los siguientes pasos:
1. Se marca la arista con menor valor. Si hay más de una, se elige cualquiera de ellas. 2. De las aristas restantes, se marca la que tenga menor valor, si hay más de una, se elige cualquiera de ellas. 3. Repetir el paso 2 siempre que la arista elegida no forme un ciclo con las ya marcadas. 4. El proceso termina cuando tenemos todos los nodos del grafo en alguna de las aristas marcadas, es decir, cuando tenemos marcados n-1 arcos, siendo n el número de nodos del grafo.
Complejidad del algoritmo
m el número de aristas del grafo y n el número de vértices, el algoritmo de Kruskal muestra una complejidad O(m log m) o, equivalentemente, O(m log n), cuando se ejecuta sobre estructuras de datos simples. Los tiempos de ejecución son equivalentes porque:
-m es a lo sumo n2 y log n2 = 2logn es O(log n). -ignorando los vértices aislados, los cuales forman su propia componente del árbol de expansión mínimo, n ≤ 2m, así que log n es O(log m).
Aplicaciones:
La aplicación típica de este problema es el diseño de redes telefónicas. Una empresa con diferentes oficinas, trata de trazar líneas de teléfono para conectarlas unas con otras. La compañía telefónica le ofrece esta interconexión, pero ofrece tarifas diferentes o costes por conectar cada par de oficinas. Cómo conectar entonces las oficinas al mínimo coste total.
Otra aplicación menos obvia es que el árbol de coste total mínimo puede ser usado como solución aproximada al problema del viajante de comercio (traveling salesman problem), recuerde que encontrar la solución óptima a este problema es NP-completo. La manera formal de definir este problema es encontrar la trayectoria más corta para visitar cada punto al menos una vez. Nótese que si se visitan todos los puntos exactamente una vez, lo que se tiene es un tipo especial de árbol. Pseudocodigo:
Entrada: Un grafo ponderado conexo con todos sus pesos diferentes.
i : = 1;
N := tamaño del grafo de Entrada en número de vértices;
mientras (i < style="font-weight: bold;">Ejemplo:
Este es el grafo original. Los números de las aristas indican su peso. Ninguna de las aristas está resaltada.
AD y CE son las aristas más cortas, con peso 5, y AD se ha elegido arbitrariamente, por tanto se resalta.
Sin embargo, ahora es CE la arista más pequeña que no forma ciclos, con peso 5, por lo que se resalta como segunda arista.
La siguiente arista, DF con peso 6, ha sido resaltada utilizando el mismo método.
La siguientes aristas más pequeñas son AB y BE, ambas con peso 7. AB se elige arbitrariamente, y se resalta. La arista BD se resalta en rojo, porque formaría un ciclo ABD si se hubiera elegido.
El proceso continúa marcando las aristas, BE con peso 7. Muchas otras aristas se marcan en rojo en este paso: BC (formaría el ciclo BCE), DE (formaría el ciclo DEBA), y FE (formaría el ciclo FEBAD).
Finalmente, el proceso termina con la arista EG de peso 9, y se ha encontrado el árbol expandido mínimo.
Como se puede apreciar, este algoritmo es de optimizacion, ya que saca un coste minimo vistando a todos los nodos. Puede usarse para el problema del viajante.
Algoritmo de Kruskal
ejemplo del algoritmo en la web para probarlo click AQUI
Para descargar la diapositiva de la clase click AQUI
_____________________________________________________ Autoevaluacion: Pues este tema me gusto desde el principio, puesto que en proyecto 2 habia hecho el problema del transbordo con costos, y se parece. De este algoritmo hay mucha informacion en la web, pero creo que pude redactarla en un modo mas entendible. Creo que si me esforce en cumplir el cometido del blog, ya seran ustedes los que juzguen... ______________________________________________________ Bibliografia: http://es.wikipedia.org/wiki/Joseph_Kruskal http://es.wikipedia.org/wiki/Algoritmo_de_Kruskal http://lear.inforg.uniovi.es/ioperativa/TutorialGrafos/minimaexp/kruskal/appletKruskal.htm (programa del algoritmo de kruskal en la web) 'http://www.dma.fi.upm.es/gregorio/grafos/primkruskal/kruskal/kruskal.html http://www.monkers.net/examenes/EDA/practica2.pdf ______________________________________________________ bueno espero que les haya gustado el tema, si tienen algunas preguntas o simplemente comentar algo, no duden en hacerlo.
Represente este pseudocodigo en un diagrama de flujo
Bueno aqui yo lo trate de hacer en raptor para que el programa corriera y me quedo como resultado este diagrama de flujo. Que hace exactamente? Pues la funcion del pseudocodigo y que esta representado en el diagrama, es saber si un numero es primo o no. Para esto tiene diferentes funciones el diagrama, tratare de explicar una por una:
Cuando se inicia el programa, se pide un valor "n"cualquiera. Este sera evaluado por la primera condicion: ((n%2)==0) esto quiere decir, se saca ((n modulo 2)==0), si el resultado del numero n introducido es 0 entra por la parte verdadera donde la condicion sera que si el residuo de la condicion anterior es 2 entonces el numero no es primo, si no es 2, es primo.
Cuando el ((n modulo 2)==0) sea falso, entrara a otras instrucciones. Al principio de las instrucciones se añade un valor i y este sera igual a 3. Luego se evalua un while con la condicion i<=raiz(n) (en raptor se escribiria: i>=sqrt(n) ). Si esta condicion es verdadera se evaluara la condicion ((n%i)==0) que evaluaria ((n modulo 3)==0). Si esta condicion se cumple imprime un "no"y si no se cumple va le va sumando a i (3) 2 numeros hasta que se deje de cumplir la expresion i>=sqrt(n). Si al final se deja de cumplir esta condicion se imprimira un "si". Ejecucion paso a paso.
Tratare de explicar 2 ejecuciones: evaluando 4 y 17
Evaluando numero 4
InicioSe introduce el numero 4 Se cumple la primera condicion del if,quedaria ((4%2)==0) Entra por la parte verdadera Se evalua ùn if con la siguiente condicion (4==2) Como el 4 no es igual a 2 el resultado es Falso Entra por la parte falsa Imprime un "no"Fin
Evaluando el numero 17
Inicio Se introduce el numero 17 No se cumple la primer if con la condicion ((17%2)==0) Entra por la parte falsaSe añade el valor "i" que es igual a 3 Se evalua un while con la condicion 3<=raiz(17), la afirmacion es verdadera ya que raiz(17)=4.1 y 3 es menor Entra por la parte verdadera Evalua un if con la siguiente condicion ((17%3)==0), esta afirmacion es falsa Se suma 3+2=5 Se evalua la condicion 5<=raiz(17), la afirmacion es falsa ya que 5 es mayor a 4.1 Sale del while Imrpime si Fin tambien aqui dejo un video del diagrama de flujo en raptor, donde se evaluan tres numero que son el 3, 4 y 17. Si quieren descargar el programa click aqui
Problema No. 3 Ejecuta paso por paso la máquina Turing definida por la siguiente función de transición, con la entrada siendo la representación binaria del número decimal 43 Primero que nada, avaluaremos el numero binario para 43, para eso vamos dividiendo el numero de 2 en 2 43/2= 26 residuo 1 26/2= 13 residuo 0 13/2= 6 residuo 1 6/2= 3 residuo 0 3/2=1 residuo 1 1/2= 0 residuo 1
y quedaria el numero binario 101011 Conforme a las instrucciones evaluamos
iniciamos s, inicio s, inicio - nos movemos hacia la derecha leemos s,1 - imprimimos 1 y avanzamos hacia la derecha (no hay modificaciones) leemos s,0 - imprimimos 0 y avanzamos hacia la derecha (no hay modificaciones) leemos s,1 - imprimimos 1 y avanzamos hacia la derecha (no hay modificaciones) leemos s,0 - imprimimos 0 y avanzamos hacia la derecha (no hay modificaciones) leemos s,1 - imprimimos 1 y avanzamos hacia la derecha (no hay modificaciones) leemos s,1 - imprimimos 1 y avanzamos hacia la derecha (no hay modificaciones) leemos s, espacio - cambiamos estado "s" a "t", imprimimos 1 y avanzamos hacia la izquierda (si hay modificaciones) leemos t,1 - imprimimos 1 y avanzamos hacia la izquierda (no hay modificaciones) leemos t,1 - imprimimos 1 y avanzamos hacia la izquierda (no hay modificaciones) leemos t,1 - imprimimos 1 y avanzamos hacia la izquierda (no hay modificaciones) leemos t,0 - imprimimos si y hacemos alto.
(perdonen la tabla mal hecha)
el numero de salida seria 1011111 que seria igual a 95
Lo que hace la maquina es multiplicarse por 2 a agrega un 1 de suma y un 1 en el lugar del 8 (se suma 8, dando (43x2)+8+1=95 )
La complejidad asintotica es lineal O(n). ________________________________________________________
