Puntos extra

Hola profesora y compañeros de clase, aqui les muestro algunos de los problemas del ordinario.Sinceramente fueron de los problemas donde mejor me fue asi que decidi volverlos a contestar.

Arboles Binarios
Los árboles binarios constituyen un tipo particular de árboles de gran aplicación. Estos árboles se caracterizan porque no existen nodos con grado mayor que dos, es decir, un nodo tendrá como
máximo dos subárboles.
Definición: Un árbol binario es un conjunto finito de nodos que puede estar vacío o consistir
en un nodo raíz y dos árboles binarios disjuntos, llamados subárbol izquierdo y
subárbol derecho.

El problema era el siguiente:
Supongamos que los elementos siguientes están correctamente almacenados en un árbol binario
externo (llaves únicamente en las hojas) correctamente con vértices de ruteo adecuados en balance
perfecto: 45, 23, 38, 79.

a) Dibuje un posible árbol inicial (2 puntos).
b) Inserte el elemento 13 sin balancear el árbol (1 punto).
c) Elimine el elemento 38 sin balancear el árbol (1 punto).
d) Busque en el árbol por un elemento 55 y detalla cada paso de la búsqueda hasta obtener el
resultado (1 punto).
En los últimos tres incisos, identifique la complejidad computacional de la operación.

a) Lo primero que hize fue dibujar el arbol, en una rama dibuje el 23 y el 38 mientras que en la otra rama dibuje el 45 y 79.

Asi quedó el arbol

b) Despues lo que hize fue insertar el elemento 13, lo inserté debajo del elemento 23 ya que de todos los elementos, era el menor y se elimino el 23.

Insertar elementos en un árbol binario de búsqueda tiene una complejidad:


O(log n).

c) Se eliminó el elemento 38 del arbol sin balancearlo y se muestra asi:

Complejidad computacional: O(log n)

d) Se buscó un elemento 55 en el arbol, empezé desde la raiz nos vamos hacia la rama derecha, pasando por el elemento 79, por esa parte no se halló asi que nos devuelve un valor FALSE ya que ese elemento no se encontro. Aqui presento como fue la busqueda:

Recorrer los elementos del árbol en inorden tiene complejidad:

O(log n).

-------------------------------------------------------------------------------------------------Grafos

Demuestre que el grafo simple no dirigido definido por las siguientes aristas en formato (inicio,
final) es plano: (1, 2), (1, 3), (1, 4), (2, 4), (2, 6), (3, 5), (3, 6), (4, 5), (5, 6).

Calcule su diámetro y grado promedio. Luego, ejecuta paso por paso una búsqueda en profundidad (DFS) que imprime los vértices en postorden, iniciando el recorrido en el vértice con etiqueta 3 y visitando siempre primero aquel vecino no visitado que tiene la menor etiqueta.

Aqui les muestro como quedo mi grafo, como podran ver, las aristas no se intersecan, esto quiere decir que el grafo es plano.El grado es 3 porque es el numero mayor de aristas que tiene un vertice.

Aqui les muestro lo que es la busqueda, se inicia en la etiqueta 3 y va visitando el menor vertice posible para que se logre visitar todos los vertices sin pasar por el mismo.

Los vertices en postorden serian :6,5,4,2,1,3.

El diametro seria 2, porque es la mayor distancia entre dos vertices.

-------------------------------------------------------------------------------------------------
Listas enlazadas
Exprese en pseudocódigo las operaciones siguientes para listas doblemente enlazadas y analize la complejidad computacional asintótica de cada operación:
-Creación de una lista nueva
- Inserción entre dos elementos existentes
- Eliminación entre dos elementos existentes
- Inserción al inicio
- Eliminación del final


-Creacion de una lista nueva:
struct nodo {
int dato;
struct nodo *siguiente;
struct nodo *anterior;
};

Complejidad computacional: O(l) se refiere a que es lineal.

-Inserción entre dos elementos existentes:
1.Hacemos que nodo->siguiente apunte a lista->siguiente.
2.Hacemos que Lista->siguiente apunte a nodo.
3.Hacemos que nodo->anterior apunte a lista.
4.Hacemos que nodo->siguiente->anterior apunte a nodo

Complejidad computacional: O(l) se refiere a que es lineal.


-Eliminacion entre dos elementos existentes:
1.Si nodo apunta a Lista, hacemos que Lista apunte a Lista->anterior (o Lista->siguiente).
2.Hacemos que nodo->anterior->siguiente apunte a nodo->siguiente.
3.Hacemos que nodo->siguiente->anterior apunte a nodo->anterior.
4.Borramos el nodo apuntado por nodo.

Complejidad computacional: O(n) n numero de pasos


-Inserción al inicio:
Nos basamos en una lista no vacia, consideramos que lista apunta al primer elemento de la lista doblemente enlazada:
1.nodo->siguiente debe apuntar a Lista.
2.nodo->anterior apuntará a Lista->anterior.
3.Lista->anterior debe apuntar a nodo

Complejidad computacional: O(l) se refiere a que es lineal

-Eliminacion al final: 1.Si nodo apunta a Lista, hacemos que Lista apunte a Lista->anterior.
2.Hacemos que nodo->anterior->siguiente apunte a NULL
3.Borramos el nodo apuntado por nodo

Complejidad computacional: O(n) n numero de pasos.





Bibliografia: http://ldcastillo.wordpress.com/tema-2-listas-doblemente-enlazadas/

Cualquier duda u observacion favor de comentar en el blog.
Gracias.

Proyecto #5

Hola compañeros y profesora, aquí les muestro mi proyecto #5. El tema que elegí fue el de "detección de planaridad".
Este tema es bastante interesante y entretenido ya que ayuda a desarrollar la creatividad a la hora de encontrar alguna solución óptima en cuanto a los grafos, detectar si un grafo es plano o no.

-Definicion del problema
Cuando un grafo o multígrafo se puede dibujar en un plano sin que dos segmentos se corten, se dice que es plano.
Un grafo no es plano si no puede ser dibujado sobre un plano sin que sus aristas se intersequen.

Este problema es de "optimización".
La complejidad asintotica es φ(n)
Aquí les muestro un ejemplo de una pequeña actividad que una vez la profesora nos habia puesto en clases:





El dibujo nos muestra un grafo (figura del cubo) donde podemos apreciar que algunas de sus aristas se intersecan, esto quiere decir que aquel grafo no es plano.
En cambio si el grafo lo modificamos y lo analizamos desde otra perpectiva podemos ver que hay una manera de juntar todas sus aristas sin que estas se intersecan, entonces esto quiere decir que el grafo ahora si es plano.

Ahora les dejare el link de un juego para que se entretengan y comprendan un poco mejor este problema ya que esta basado en este principio.
Juego de las casas y los servicios.
Explicación del juego:


La presentación del juego es la que aparece en la imagen. El objetivo del mismo es conectar cada una de las casas de la fila superior con los tres círculos de la fila inferior si que ninguna de las líneas de conexión corte a otra.
Si representamos cada uno de los iconos (tanto las casas como los círculos) mediante puntos (vértices) y tomamos también las líneas de conexión (aristas) lo que obtenemos seria el siguiente grafo:
---------> K3,3

Llamando u1,u2,u3 a los vértices superiores y v1,v2,v3 a los inferiores y representando como ui, vj a la arista que une el vértice ui con el vértice vj obtenemos el grafo conocido como: K3,3


Partiendo de que dos aristas de un grafo sólo pueden contarse en un vértice (es decir, que si tenemos dibujados los vértices de antemano dos aristas no pueden cortarse en ningún punto nada más que en ellos).

Para intentar resolver este problema se usa el Teorema de Kuratowski:

Un grafo es plano si no contiene como subgrafo a K5(el grafo completo de 5 vértices) ni a K3,3.
Es decir, ni K5 ni K3,3 son grafos planos (ya que cada uno de ellos se contiene a sí mismo como subgrafo). O lo que es lo mismo, no pueden dibujarse en un papel con la condición de que ninguna arista corte a otra en un punto que no sea desde el principio un vértice.
En conclusión este juego por mas que intentemos encontrar una solución no se podra ya que no es un grafo plano (K3,3) .

Teorema (Formula de Euler):
"Si a y n son enteros primos relativos, entonces aφ(n) ≡ 1 (mod n)".
Sea M un mapa conexo con R regiones que represente al grafo G=(V, E), entonces:
V-E+R=2, es decir, R+V=E+2.
Sea G=(V, E) un grafo plano conexo, con V>2, entonces E3<=V-6
K5


Una subdivisión elemental de un grafo G es otro grafo, donde se sustituye una arista por
un nuevo vértice unido a los extremos de la arista suprimida por dos nuevas aristas.
En un mapa se trata de añadir un vértice sobre el interior de una arista existente.
Una subdivisión de un grafo G es el grafo obtenido efectuando un número finito (puede
ser 0) de subdivisiones elementales sucesivas.

Para K3,3
Si G es un grafo plano, conexo, con n vértices, q aristas y que
descompone al plano en r regiones (o caras), entonces

Demostración:
Por inducción sobre q
Si q=0, entonces n =1, r =1 y se cumple que n−q+r = 2
Supongamos que el resultado es cierto para todos los grafos planos
y conexos con q-1 aristas, donde q≥1.
Sea G un grafo plano y conexo con q aristas.

Si G no es árbol, entonces existe alguna arista a de un ciclo de G
G−{a} es plano, conexo con n vértices, q−1 aristas y r −1 regiones.
La hipótesis de inducción asegura entonces que:
n − (q−1)+ (r−1)= 2 , es decir, n−q+r = 2

Consecuencias
Si G es un grafo simple y planar con n vértices y q aristas
2.- Si n≥3 y G no tiene ciclos de longitud 3, entonces
q ≤ 2n−4
Ahora el borde de cada región tiene, al menos, 4 aristas y cada
arista pertenece al borde de dos regiones.
Así contando el nº de aristas, resulta que 4r ≤ 2q
Sustituyendo en la fórmula de Euler 2n−2q+2r = 4,
q ≤ 2n−4
3.- G tiene, al menos, un vértice v con grado d(v) ≤ 5
Si para cada vértice x, se tiene que d(x)≥6 entonces
2q=Σd(x) ≥ 6n, luego q≥3n

Aplicaciones:
El saber si un grafo es o no es plano puede ser de gran importancia en el diseño de circuitos integrados, de carreteras, de ferrocarriles y en general en todos los casos en que el cruce de dos aristas represente una situación incómoda (o incluso cara).


Conclusiones:
Este tema me gustó mucho en lo personal, ya que pude identificar como detectar si un grafo es plano o no. A base del juego y algunos grafos pude entender mejor este principio.
Sinceramente no fue fácil encontrar la información ya que es muy extenso este tema pero con dedicación y leyendo varias fuentes pude comprender la idea principal del tema.
Creo que me falto investigar mas ya que hay algunos aspectos cuales no logré comprender muy bien. Sobre la presentación quise poner la idea principal para que fuera concreta e invitarlos a que entraran a mi blog para que se familiarizaran mas con el problema.

Algoritmo Euclidiano (Puntos extra)

Hola profesora y compañeros, aqui les muestro un tema que me llamo la atencion para puntos extra se trata sobre el algoritmo euclidiano.

Algoritmo Euclidiano

Este algoritmo es un método para encontrar el máximo factor común de dos enteros. Primero se divide el número mayor entre el número menor.
Se repite la división, utilizando el residuo como divisor, hasta que el residuo se convierte en cero. El último residuo diferente a cero es el máximo factor común de los dos enteros.

Por ejemplo, para encontrar los máximos factores comunes de 99 y 44, dividimos 44 entre 99. Esto da 2 con un residuo de 11. A continuación, se divide 11 entre 99, que da 9 con un residuo de 0. Ya que 11 es el último residuo diferente a cero, es el máximo factor común de 99 y 44.

Otro ejemplo seria el siguiente
Por ejemplo, para encontrar el máximo común divisor de 93164 y 5826 el algoritmo genera la siguiente secuencia de divisiones:

Paso Operación Significado
1 93164 dividido entre 5826 es 15 y sobran 5774
2 5826 dividido entre 5774 es 1 y sobran 5
3 5774 dividido entre 52 es 111 y sobran 2
4 52 dividido entre 2 es 26 y sobra 0

Su complejidad computacional seria O(log n) divisiones para que se calcule el maximo comun divisor de n y m donde

n>m

Su implementacion en pseudocodigo seria:

Algoritmo en forma recurrente

Funcion

mcd (a,b)

Si b=0 entonces:

El resultado es a

En otro caso:

El resultado es mcd (b, a mod b)

Algoritmo en forma iterativa

Funcion

mcd(a,b):

mientras haga lo siguiente:

El resultado es a

Cualquier duda o sugerencia favor de dejar un comentario.

Gracias

Proyecto # 4

Hola profesora y compañeros de clase, aquí les muestro el proyecto #4 donde a mi equipo nos toco hablar sobre el tema de pilas.

Lo que hice yo fue buscar información e investigar a fondo sobre las pilas para poder comprender el tema. Busque lo que fue animaciones para comprender mas fácil y ver la aplicacion de lo que son las pilas, algunos ejemplos y pseudodigos.
También hice parte del inicio de la presentación.

Lo que hice me salio bien aunque siento que me pudieron faltar algunas cosas.

Estoy bien en el aspecto de haber comprendido el tema de pilas y sus aplicaciones, las animaciones realmente me ayudaron.
Siento que me falta investigar un poco mas sobre las aplicaciones y entender mejor los pseudocodigos y la implementación en problemas reales.

Yo creo que ayudo a los demás en lo que puedo y en lo que tengan alguna duda, pero también me apoyo en ellos para tener una retroalimentación y comprender mejor. Es muy importante saber trabajar en equipo para así aprender a organizarse mejor y tomar decisiones para llegar a un fin común.

Todos nos encargamos de coordinar el trabajo desde el principio para que todos participemos, en este proyecto mi compañero Gustavo Chavanna y yo fuimos los que mostramos iniciativa con el inicio del proyecto.

El papel que tomo es como alguien que puede proponer ideas y estar participativo en todo momento, me gusta mostrar iniciativa y disposicion, ayudar a organizarse para llevar todos un liderazgo común y saber escuchar. Comprender y respetar lo que mis compañeros opinan, proponen y hacen.

Este es el link de nuestra presentación:
Proyecto #4

Estos son mis compañeros de equipo:
Claudia
Rocio Cecilia
Gustavo Chavanna

Proyecto #3

Hola profesora y compañeros de clase, aqui les muestro el proyecto # 3 donde a mi equipo nos toco el tema de la serie de fibonacci

Primero les explicare lo que significa
-Recursión
Una función es recursiva cuando se llama a sí misma,la llamada a sí mismo se conoce como llamada recursiva o recurrente.
Aunque por otra parte, la recursividad también puede ser indirecta, si tenemos un procedimiento P que llama a otro Q y éste a su vez llama a P.
La recursión nos sirve para experimentar con facilidad, resolver muchos problemas de manera sencilla y demostrar propiedades acerca de los algoritmos y un montón de cosas más.

-Cuando no usar la recursión:
La solución recursiva tiene un costo y memoria mayor que la iterativa, en otras palabras, los programas recursivos en ocaciones son menos eficientes.
Para ello podemos seguir los siguientes aspectos:
Los algoritmos que por naturaleza son recursivos y donde la solución iterativa es complicada deben manejarse explícitamente una pila para enumerar las llamadas recursivas; deben resolverse por métodos recursivos.
Cuando haya una solución obvia por iteración al problema, debe evitarse la recursividad.

Ejemplo del algoritmo de la serie de fibonacci en forma recursiva:


Ejemplo del algoritmo de la serie de fibonacci en forma iterativa:


como se daran cuenta en este problema es mas facil utilizar la forma iterativa porque requiere efectuar sólo n sumas para calcular fn, lo cual significa que este método es considerablemente más rápido, ya que en forma recursiva el algoritmo es mas lento y la sucecion crece mas rapido con un mayor margen de error.


El trabajo en equipo fue bueno ya que realmente pudimos ponernos de acuerdo para ver que podiamos contribuir cada quien con el proyecto, aunque al principio nos falto mas comunicacion para poder comenzar el proyecto con mayor anterioridad.
Lo que yo hize y mis compañeros tambien fue buscar informacion sobre la recursión, ver algunos ejemplos y recordar lo que la profesora nos habia explicado en el caso de la serie de fibonacci.
Lo que podriamos mejorar en un futuro seria juntarnos con aterioridad para analizar mas detalladamente los algoritmos y asi sacar mas conclusiones y detalles del proyecto.

Mi equipo :
Claudia Lozano
Rocio
Gustavo Chavanna


Este es el link donde se encuentra nuestra presentacion:
Fibonacci

Proyecto #2

Hola compañeros de clase y profesora aqui les dejo mi proyecto #2, el problema que escogi fue el de programacion de horario (sheduling) .

Es un problema muy amplio del cual se pueden derivar distintos subproblemas según sean las restricciones que se consideren en cada caso y según sean las del caso.

La mayoría de estos problemas son problemas NP Completos.

Considere un servidor (cajero de banco, una caja de supermercado ó procesador ) para atender a una secuencia de clientes ( tareas ). Además supongamos que conocemos por adelantado cuanto tiempo se necesita para atender a cada cliente. Si nuestro objetivo es minimizar el tiempo de espera de cada cliente, entonces una estrategia voraz consiste en atender a los clientes en orden no decreciente de tiempo de atención.

Este es un algoritmo voraz:

Supongamos que hay tres clientes etiquetados C1, C2, C3 que necesitan 8, 4
y 6 unidades de tiempo para ser atendidos, el tiempo total de atención para estos clientes 8 + 4 +6 = 18 unidades. En la siguiente tabla calculamos el tiempo medio que resulta para cada una de las seis secuencias de atención.




La solución óptima para este ejemplar del problema se obtiene atendiendo a C2 primero
luego a C3 y finalmente a C1 lo que arroja un tiempo medio de atención de 10.7 . Esta es la
secuencia que escoge la estrategia voraz

Fuente: http://chavez.gerenciadeproyectos.org/algoIII/sem10/UNMSM-AG3-PRD-10.pdf

Este es un ejemplo del problema en terminos matematicos:

Codificacion de problema de optimizacion
Dada una maquina y 5 trabajos que hay que realizar en ella, en cualquier orden, se dispone del tiempo de ejecucion de cada trabajo


y del tiempo de ajuste de la maquina para pasar de ejecutar el trabajo i(fila) a ejecutar el trabajo j (columna)


Resolver el problema para determinar cual es el menor tiempo posible para completar los 5 trabajos y como hacerlo. Se considera un ciclo de trabajo cerrado, que se repite y vuelve a comenzar.


*La segunda formulacion evita subciclos de parejas de trabajos
SETS
I trabajos que se van a ejecutar / TR1 * TR5 /
ALIAS (i,j)
TABLE C (i,j) tiempo de ajuste para pasar del trabajo i al trabajo j

VARIABLES
X(i,j) paso del trabajo i al trabajo j
TT tiempo total en completar los trabajos

BINARY VARIABLE X
EQUATIONS
TIEMPO tiempo total de trabajo
ANTERIOR(i) de cada trabajo se parte una vez
POSTERIOR(j) a cada trabajo se llega una vez
PAREJAS(i,j) suma de los trabajos por parejas ;

TIEMPO ..TT=E= SUM[(i,j) $(NOT SAME AS (i,j)), C(i,j)*X(i,j)] ;
ANTERIOR(i) ..SUM[j $(NOT SAME AS (i,j)), X(i,j)] =E= 1 ;
POSTERIOR(j) ..SUM[i $(NOT SAME AS (i,j)), X(i,j)] =E= 1 ;
PAREJAS(i,j) $(ORD(i) < l="1" href="http://www.gams.com/docs/contributed/modelado_en_gams.pdf">http://www.gams.com/docs/contributed/modelado_en_gams.pdf

Aqui otro tipo del problema donde se puede apreciar en forma matematica con su grafica:

Dado un conjunto de productos J=[1....n] y un conjunto de secadores M=[1.....m] en paralelo, se debe programar y secuenciar cada producto en el conjunto de secadores M, respetando las restricciones del probleama.

1): Un secador i ∈M puede procesar solo un producto j∈J a la vez.

2):En una hora de programacion, la suma de los consumos de vapor en cada secador i en paralelo no debe exceder el recurso de vapor maximo Vmax. Esto debe cumplirse para cada hora de programacion en la totalidad de los secadores y en toda la programacion.

3):Debido a condiciones tecnologicas del proceso del secado, algunos productos, j'∈J' siendo J⊂J
no pueden ser programados en ciertos secadores i∈M

4): Se debe cumplir con las fechas de entrega estipuladas para cada producto j∈J

Se define el vector vapor para cada producto i en cada secador j como:

Esta es la grafica del problema


fuente: http://redalyc.uaemex.mx/redalyc/pdf/299/29916103.pdf

Hola amigos y profesora de algoritmos computacionales. Aquí les muestro el proyecto #1 que hize con mi compañera Claudia Lozano. Decidimos realizar el primer problema que se trata de "Buscar un número en una guía telefónica".


Lo primero que realizamos fue el algoritmo del problema:
1.-Inicio.
2.-Imprimir un letrero "Agenda Telefónica".
3.-Capturar Datos.
4.-Pedir Datos.
5.-Declaramos y Capturamos variables.
6.-Imprimir la información solicitada.
7.-Fin.

Después de haber hecho el algoritmo, utilizamos el programa raptor para realizar un diagrama de flujo. Empezamos usando un "output" para mostrar el nombre que es "Agenda Telefónica"




Después utilizamos otro "output" para mostrar la lista de nombres de los contactos, lo siguiente fue usar un "input" para que mostrara una sentencia (Seleccione un contacto) y una variable a la que llamamos "Contacto".

Al hacer esto, usamos un "selection" y en el rombo pusimos "Contacto"=1.
Si ingresábamos el 1, nos llevaba a la opción "yes" y nos desplegaba el numero telefónico del primer contacto. Si ingresábamos otro numero del 1 al 10 (ya que son 10 contactos), nos llevaba a la opción "no" en el primer "selection" hasta llegar al "selection" del numero ingresado y así desplegar la información del contacto asignado. Si ingresábamos un numero que no fuera del 1 al 10, un "output" nos mostraba la leyenda: "Ya no existen mas contactos".

Este es el diseño de nuestro diagrama, por lo mismo que es largo, solo pude poner la imagen de vista alejada:

Este es un ejemplo similar al del proyecto se trata sobre un menú de restaurante:

Este es un vídeo donde se muestra el proyecto usando el programa dev c++ en forma de pseudocodigo