Dejeme aclarar que algunas soluciones de los problemas resuleto aca, no son todas mias.
Problema2
Considere una ciudad cuyas calles están dadas por una red ortogonal X´Y (todas las manzanas son cuadrados del mismo tamaño y forman una matriz, hay X calles en una dirección y Y calles en la otra). Se desea caminar de la esquina superior izquierda a la esquina inferior derecha, pero hay intersecciones de calles por las que está prohibido pasar. Estas intersecciones prohibidas están dadas en una matriz P donde el valor P[i, j]=1 quiere decir que la intersección está prohibida y P[i,j]=0 quiere decir que se puede pasar por ella. Diseñe un algoritmo que encuentre el camino más corto (de la esquina superior izquierda a la inferior derecha) sin pasar por las intersecciones prohibidas.
La idea general de la estrategia de solución es la siguiente:
· Marca en el mapa todas las esquinas que un número que sea indicador de la longitud mínima de un camino que vaya desde el inicio hasta esa esquina.
· Se marcara con –(k + 1) todas aquellas esquinas para las cuales los caminos más cortos desde el inicio hasta ellas tienen longitud k.
· Se marcaran con 0 todas las esquinas que no tengan un camino desde el inicio hasta ellas.
· Si una casilla se marco con –m y tiene una vecina que está marcada con 0 se actualiza la marca para esa casilla con el valor –(m+1). Esto es debido a que hasta ese momento no se habían encontrado caminos desde el origen hasta ella pero en el momento en que corroboramos que era vecina de una marcada con –m podemos asegurar que existe un camino desde el inicio hasta ella con longitud m (camino hasta la marcada con –m tiene longitud m-1 y le añadimos el viaje hacia la nueva esquina).
· Para garantizar que cuando se marque una casilla es porque se encontró uno de los caminos más cortos desde el inicio hasta la casilla vamos explorando el mapa de forma tal que primero se marquen todas las casillas que se pueden alcanzar en m pasos y luego pasamos a marcar las que se alcanzan en (m+1).
Se han dejado claras las bases fundamentales del algoritmo. Solo nos queda mencionar que su implementación se hizo en el lenguaje CSharp. Para un mejor encapsulamiento de código se implementaron tres métodos auxiliares:
· Ady: Recibe un punto como parámetro y devuelve una lista con los puntos látices adyacentes a él.
· EndCorner: Recibe un punto, el mapa y retorna un valor booleano indicador de si el punto es la esquina inferior derecha del mapa.
· InsideMap: Recibe un punto, el mapa y retorna un valor booleano indicador de si el punto está dentro del mapa.
Metodos auxiliares
static List Ady(Point p)
{
List res = new List();
for (int i = -1; i <= 1; i++)
for (int j = -1; j <= 1; j++)
if (i != j && i*j == 0)
res.Add(new Point(p.X + i, p.Y + j));
return res;
}
static bool EndCorner(int[,] map, Point p)
{
return p.X == map.GetLength(0) - 1 && p.Y == map.GetLength(1) - 1;
}
static bool InsideMap(int[,] map, Point p)
{
return p.X >= 0 && p.Y >= 0 && p.X <>
p.Y <>
}
Algoritmo de solución
static List Lee(int[,] map)
{
Queue q = new Queue();
// Marcar el comienzo
map[0, 0] = -1;
q.Enqueue(new Point(0, 0));
while (q.Count > 0)
{
Point cur = q.Dequeue();
foreach (Point p in Ady(cur))
// Si el punto no esta marcado
if (InsideMap(map, p) && map[p.X, p.Y] == 0)
{
// no se habia podido llegar en menos pasos y
// marcar con los pasos para llegar al
// anterior mas uno
map[p.X, p.Y] = map[cur.X, cur.Y] - 1;
// Si llegue a la esquina inferior derecha
if (EndCorner(map, p))
{
// Suspender la busqueda para pasar a
// reconstruir el camino
q.Clear();
break;
}
}
}
// Construir el camino
List path = new List();
Point end = new Point(map.GetLength(0) - 1,
map.GetLength(1) - 1);
// Si se llego a marcar la esquina inferior derecha
if (map[end.X, end.Y] != 0)
{
// Mientras end no sea la ezquina superior izquierda
while(map[end.X, end.Y] != -1)
{
// Buscar en los vecinos de end un punto al que se
// pueda llegar en 1 paso menos
foreach (Point p in Ady(end))
if (InsideMap(map, p) &&
map[p.X, p.Y] == map[end.X, end.Y] + 1)
{
path.Add(end);
end = p;
break;
}
}
// Adicionar el punto inicial
path.Add(new Point(0, 0));
// Obtener el camino en el orden correcto
path.Reverse();
}
return path;
}
Orden del Algoritmo
Para analizar el orden del algoritmo podemos separar su estructura en dos partes fundamentales:
· Marcar las casillas del mapa
· Construir el camino a partir del mapa marcado
Marcar las casillas del mapa
Para analizar el costo de esta operación es necesario cerciorarse de que las operaciones realizadas en el interior del ciclo while son constantes. Dentro del ciclo se itera sobre una colección de 8 elementos y por cada uno de estos se realizan operaciones O (1) . Luego el costo de esta operación viene dado por la cantidad de elementos que puede contener la cola utilizada para almacenar los nuevos puntos en el algoritmo. Dicha cola solo puede almacenar puntos del mapa por lo que la cantidad de elementos que pueden pertenecer a ella son O(n*m) donde n y m son respectivamente la cantidad de filas y columnas del mapa.
Construir el camino a partir del mapa marcado
Para construir el camino se realizan por cada punto intermedio del camino operaciones O(1) por lo que el costo de esta operación depende explícitamente de la longitud del camino. La longitud del camino esta acotada superiormente por la cantidad de casillas del tablero, que es O(n*m) .
Luego el costo de dar solución al problema es O(n*m) debido a que las dos partes fundamentales del mismo se realizan en este orden.
Correctitud del Algoritmode longitud p+k-i+1 < k lo que sería una contradicción. El vértice
Para mostrar la correctitud del problema demostraremos que el camino encontrado por el algoritmo es mínimo. Para ello haremos uso del método de reducción al absurdo. Sea v1,v2,v3...vk un camino del inicio al fin cuya longitud es menor a la del camino encontrado por el algoritmo. Además como este camino es menor que el obtenido por el algoritmo podemos garantizar que la esquina inferior derecha fue marcada con un número menor que -k. Todo vértice vi del camino mínimo tiene que haber sido marcado con el numero –i. Si fue marcado con uno mayor entonces existe un camino v1,v2,v3...vp,vi
con p < i-1 que parte desde el inicio hasta i, luego, podemos formar un camino v1,v2,v3...vp,vi,v(i+1),...vk de longitud p+k-i+1 < k lo que sería una contradicción. El vértice vk fue marcado con el numero –k lo cual es una contradicción. Luego la suposición inicial de que el camino era más corto no ha lugar.
viernes, 22 de mayo de 2009
Problema1 de Diseño de Analisis y Algoritmos
Considere n cuerdas en un círculo y cada una definida por sus puntos extremos. Diseñe un algoritmo de tiempo O(n log n) que determine el número de pares de cuerdas que se intersecan dentro del círculo. Asuma que ningún par de cuerdas tienen un extremo común.
La idea general de la estrategia de solución es la siguiente:
• Ordenar los extremos de las cuerdas bajo algún criterio
• Etiquetar todos las cuerdas con un ID único que las identifique de todas las demás y que ese ID se le asigne según el orden de sus extremos. En otras palabras las cuerdas con extremos de menores recibirán IDs menores.
• Recorrer los extremos ordenados y utilizando una estructura de datos que almacene una lista ordenada eficientemente, mantener en ella todas las cuerdas que hasta el momento permanecen abiertas (se ha iterado por un solo extremo de la cuerda).
• Cuando se encuentre el segundo extremo de la cuerda se cuenta cuantas cuerdas se han abierto después de la inserción del primer extremo.
Criterio de orden para los extremos
El criterio para ordenar los extremos es sencillo. Primero cambiaremos las referencias de las cuerdas: En vez de tomar una cuerda como un par de puntos del plano tomaremos las referencias donde a es el ángulo formado por el eje positivo de las X y el vector u, análogamente b es el ángulo formado por el eje positivo de las X y el vector v. El ángulo se escoge siempre en sentido antihorario. Es fácil ver que en esta notación la cuerda también queda unívocamente determinada.
Luego una vez establecido que es lo que se va a entender por cuerda el criterio de ordenación a utilizar es el usual de los reales ya que los extremos de la cuerda no son pares ordenados sino son ángulos.
Algoritmo de Solución
En nuestro algoritmo de solución hacemos uso de las colecciones brindadas por CSharp tales como:
• SortedList: Estructura de datos que almacena pares de y se pueden recuperar tanto el índice de la llave en la lista de ordenada llaves como el valor asociado a una llave en . Esta estructura se puede implementar utilizando un ABB que tenga definida una estrategia para mantener sus alturas en O(log n). Tomamos como criterio de ordenación la llave, y dado el tipo de árbol utilizado aseguramos que las operaciones de de inserción, eliminación y búsqueda de un elemento dado su llave son O(log n). Las operaciones de indexado de una llave dentro de la lista ordenada de llaves también serían O(log n), para ello necesitamos en cada nodo un nuevo campo para almacenar la cantidad de nodos hijos que este posee. La actualización de este campo puede realizarse dentro de las operaciones de inserción y eliminación en O(1). Para conocer que índice ocupa una llave dentro de la lista ordenada de llaves bastaría descender por las ramas, teniendo en cuenta en cada paso que cada decisión de descender por un hijo derecho aumenta el índice del elemento buscado en la cantidad de nodos que posee el hijo izquierdo, cero si no existe este. Con esta estrategia, todas las operaciones requeridas se mantienen O(log n).
• List: Es una lista genérica que es utilizada para ordenar en los extremos (llamado al método Sort()).
Clases utilizadas en el algoritmo de solucion
class Chord
{
// Extremo 1 de la cuerda
public float A { get; set; }
// Extremo 2 de la cuerda
public float B { get; set; }
// Etiqueta de la cuerda
public int Tag { get; set; }
public Chord(float a, float b, int tag)
{
A = a;
B = b;
Tag = tag;
}
public Chord(float a, float b) : this(a, b, 0) { }
}
class Entry : IComparable
{
// Cuerda
public Chord Chord { get; set; }
// Extremo de la cuerda a tomar como llave en la ordenacion
public float Key { get; set; }
public Entry(float key, Chord cuerda)
{
Key = key;
Chord = cuerda;
}
public int CompareTo(Entry other)
{
return Key.CompareTo(other.Key);
}
}
Algoritmo de solución
static public int Solve(List col)
{
// Contador de intersecciones
int hit = 0;
// Colección ordenada según los extremos
List entries = new List();
for (int k = 0; k < col.Count; k++) { // Asignar etiquetas a las cuerdas col[k].Tag = -1; // Agregar extremos de la cuerda entries.Add(new Entry(col[k].A, col[k])); entries.Add(new Entry(col[k].B, col[k])); } // Ordenar los extremos entries.Sort(); // Contar interseccionnes SortedList open = new SortedList();
// Variable para asignar las etiquetas en orden
int tag = 0;
foreach (Entry e in entries)
{
if (e.Chord.Tag == -1)
{
// Primer extremo de la cuerda
open.Add(tag, e.Chord);
// Asignar una nueva etiqueta en orden
e.Chord.Tag = tag++;
}
else
{
// Extremo final de la cuerda
int index = open.IndexOfKey(e.Chord.Tag);
// Contar las intersecciones con esta cuerda
hit += open.Count - index - 1;
// Eliminarla de la lista de cuerdas abiertas
open.RemoveAt(index);
}
}
return hit;
}
Orden del Algoritmo
Debido a la concepción del algoritmo podemos separarlo en las siguientes operaciones.
• Ordenar los extremos de los segmentos.
• Recorrer la colección ordenada y contar las intersecciones con cada cuerda.
Ordenar los extremos de los segmentos: Son operaciones de comparación que se resuelven en O(1) ya que son entre números. El costo de la operación de ordenación es en su caso promedio O(2n log(2n))donde n es la cantidad de cuerdas pasadas al algoritmo (2n: es la cantidad de extremos).
Recorrer la colección ordenada y contar las intersecciones con cada cuerda: En cada iteración se realiza o bien una eliminación o bien una inserción sobre la colección que almacena las cuerdas abiertas. Estas operaciones son O(log n).Por tanto el costo del conteo es O(2n log n)
Resumiendo el costo de las partes del algoritmo podemos concluir que es O (n log n)
Correctitud del Algoritmo
Para demostrar la Correctitud del algoritmo demostramos en primer lugar que no cuenta intersecciones entre cuerdas que no existen y en una segunda demostración que ninguna intersección se queda sin contar. Esta estrategia de demostración nos garantiza que nuestro algoritmo no solo cuenta intersecciones que existen sino que también las cuenta todas. Para las demostraciones dividiremos las cuerdas en 3 tipos con respecto a una cuerda prefijada.
I. Son las cuerdas que terminan antes que el extremo final de la cuerda dada.
II. Son las cuerdas que comienzan antes que extremo inicial o después del extremo final y terminan después que el extremo final de la cuerda dada.
III. Son las cuerdas que comienzan después del extremo inicial de la cuerda dada y terminan después de su extremo final.
Cuenta solo las intersecciones existentes
Está claro que si tomamos como referencia la cuerda que vamos a contar las intersecciones solo realmente la intersecan las cuerdas de tipo III. Nuestro algoritmo no cuenta las cuerdas de tipo:
I. Debido a que cuando aparezca el extremo final de nuestra cuerda ya las cuerdas de este tipo han sido removidas de la colección de cuerdas abiertas.
II. Debido a que sus dos extremos son mayores que los extremos de la cuerda dada y cuando aparezca el extremo final de nuestra cuerda todavía las cuerdas de este tipo no han sido insertadas en la colección de cuerdas abiertas o porque la cuerda comenzó antes que la cuerda dada y tampoco se tendrá en cuenta.
Luego nuestro algoritmo solo cuenta cuerdas de tipo III que son las que producen intersecciones. Además podemos asegurar que no cuenta doble una intersección debido que la cuerda dada es una cuerda de tipo I si prefijamos cualquier cuerda de tipo III.
Todas las intersecciones son contadas
Toda intersección entre cuerdas se puede definir por las cuerdas que la generan. Luego para la cuerda que tiene el extremo menor la otra cuerda es de tipo III por lo que nuestro algoritmo siempre la va a contar.
La idea general de la estrategia de solución es la siguiente:
• Ordenar los extremos de las cuerdas bajo algún criterio
• Etiquetar todos las cuerdas con un ID único que las identifique de todas las demás y que ese ID se le asigne según el orden de sus extremos. En otras palabras las cuerdas con extremos de menores recibirán IDs menores.
• Recorrer los extremos ordenados y utilizando una estructura de datos que almacene una lista ordenada eficientemente, mantener en ella todas las cuerdas que hasta el momento permanecen abiertas (se ha iterado por un solo extremo de la cuerda).
• Cuando se encuentre el segundo extremo de la cuerda se cuenta cuantas cuerdas se han abierto después de la inserción del primer extremo.
Criterio de orden para los extremos
El criterio para ordenar los extremos es sencillo. Primero cambiaremos las referencias de las cuerdas: En vez de tomar una cuerda como un par de puntos del plano
Luego una vez establecido que es lo que se va a entender por cuerda el criterio de ordenación a utilizar es el usual de los reales ya que los extremos de la cuerda no son pares ordenados sino son ángulos.
Algoritmo de Solución
En nuestro algoritmo de solución hacemos uso de las colecciones brindadas por CSharp tales como:
• SortedList
• List
Clases utilizadas en el algoritmo de solucion
{
// Extremo 1 de la cuerda
public float A { get; set; }
// Extremo 2 de la cuerda
public float B { get; set; }
// Etiqueta de la cuerda
public int Tag { get; set; }
public Chord(float a, float b, int tag)
{
A = a;
B = b;
Tag = tag;
}
public Chord(float a, float b) : this(a, b, 0) { }
}
class Entry : IComparable
{
// Cuerda
public Chord Chord { get; set; }
// Extremo de la cuerda a tomar como llave en la ordenacion
public float Key { get; set; }
public Entry(float key, Chord cuerda)
{
Key = key;
Chord = cuerda;
}
public int CompareTo(Entry other)
{
return Key.CompareTo(other.Key);
}
}
Algoritmo de solución
static public int Solve(List col)
{
// Contador de intersecciones
int hit = 0;
// Colección ordenada según los extremos
List entries = new List();
for (int k = 0; k < col.Count; k++) { // Asignar etiquetas a las cuerdas col[k].Tag = -1; // Agregar extremos de la cuerda entries.Add(new Entry(col[k].A, col[k])); entries.Add(new Entry(col[k].B, col[k])); } // Ordenar los extremos entries.Sort(); // Contar interseccionnes SortedList open = new SortedList();
// Variable para asignar las etiquetas en orden
int tag = 0;
foreach (Entry e in entries)
{
if (e.Chord.Tag == -1)
{
// Primer extremo de la cuerda
open.Add(tag, e.Chord);
// Asignar una nueva etiqueta en orden
e.Chord.Tag = tag++;
}
else
{
// Extremo final de la cuerda
int index = open.IndexOfKey(e.Chord.Tag);
// Contar las intersecciones con esta cuerda
hit += open.Count - index - 1;
// Eliminarla de la lista de cuerdas abiertas
open.RemoveAt(index);
}
}
return hit;
}
Orden del Algoritmo
Debido a la concepción del algoritmo podemos separarlo en las siguientes operaciones.
• Ordenar los extremos de los segmentos.
• Recorrer la colección ordenada y contar las intersecciones con cada cuerda.
Ordenar los extremos de los segmentos: Son operaciones de comparación que se resuelven en O(1) ya que son entre números. El costo de la operación de ordenación es en su caso promedio O(2n log(2n))donde n es la cantidad de cuerdas pasadas al algoritmo (2n: es la cantidad de extremos).
Recorrer la colección ordenada y contar las intersecciones con cada cuerda: En cada iteración se realiza o bien una eliminación o bien una inserción sobre la colección que almacena las cuerdas abiertas. Estas operaciones son O(log n).Por tanto el costo del conteo es O(2n log n)
Resumiendo el costo de las partes del algoritmo podemos concluir que es O (n log n)
Correctitud del Algoritmo
Para demostrar la Correctitud del algoritmo demostramos en primer lugar que no cuenta intersecciones entre cuerdas que no existen y en una segunda demostración que ninguna intersección se queda sin contar. Esta estrategia de demostración nos garantiza que nuestro algoritmo no solo cuenta intersecciones que existen sino que también las cuenta todas. Para las demostraciones dividiremos las cuerdas en 3 tipos con respecto a una cuerda prefijada.
I. Son las cuerdas que terminan antes que el extremo final de la cuerda dada.
II. Son las cuerdas que comienzan antes que extremo inicial o después del extremo final y terminan después que el extremo final de la cuerda dada.
III. Son las cuerdas que comienzan después del extremo inicial de la cuerda dada y terminan después de su extremo final.
Cuenta solo las intersecciones existentes
Está claro que si tomamos como referencia la cuerda que vamos a contar las intersecciones solo realmente la intersecan las cuerdas de tipo III. Nuestro algoritmo no cuenta las cuerdas de tipo:
I. Debido a que cuando aparezca el extremo final de nuestra cuerda ya las cuerdas de este tipo han sido removidas de la colección de cuerdas abiertas.
II. Debido a que sus dos extremos son mayores que los extremos de la cuerda dada y cuando aparezca el extremo final de nuestra cuerda todavía las cuerdas de este tipo no han sido insertadas en la colección de cuerdas abiertas o porque la cuerda comenzó antes que la cuerda dada y tampoco se tendrá en cuenta.
Luego nuestro algoritmo solo cuenta cuerdas de tipo III que son las que producen intersecciones. Además podemos asegurar que no cuenta doble una intersección debido que la cuerda dada es una cuerda de tipo I si prefijamos cualquier cuerda de tipo III.
Todas las intersecciones son contadas
Toda intersección entre cuerdas se puede definir por las cuerdas que la generan. Luego para la cuerda que tiene el extremo menor la otra cuerda es de tipo III por lo que nuestro algoritmo siempre la va a contar.
Problemas de Diseño Analisis y Algoritmos
Voy a publicar unos problemas de diseño Analisis y algoritmo con sus Soluciones pero estas estan en C#. Estos son unos problemas que los dieron en la Universidad de la Habana en la facultad de Matematica Computacion.
Aqui tambien pienso publicar Mis Notas y como MiniTutoriales, y tutoriales completos, ya que estoy en pruebas finales y voy a publicar de cierta manera lo que di en La universidad. Los mejores cursos que he dado han sido los que el Profesor Somoza me ha impartido. Este es un excelente profesor.
La proxima entrada va ser un problema de Diseño Analisis y Algoritmos
Aqui tambien pienso publicar Mis Notas y como MiniTutoriales, y tutoriales completos, ya que estoy en pruebas finales y voy a publicar de cierta manera lo que di en La universidad. Los mejores cursos que he dado han sido los que el Profesor Somoza me ha impartido. Este es un excelente profesor.
La proxima entrada va ser un problema de Diseño Analisis y Algoritmos
miércoles, 13 de mayo de 2009
Hola Mundo!!!
Mi Primer articulo en este Blog, nunca habia hecho un blog en mi vida este es el primero y espero que lo haga bien.
Mi Tareas de Lenguaje de Programacion (LP)
Los resultados de esta tarea lo voy a poner despues ya que todavia estan evaluando la misma.
Esta tarea no contiene un alto nivel de complejidad pero si de conocimiento general, ya que son en Lenguajes diferentes.
Haskell
1. Implementación funcional de 8-Reinas
2. Implementación Lazy de un generador de números de Fibonnaci
3. Generar un árbol semi-completo a partir de una lista ordenada de números.
4. Implementación funcional de Torres de Hanói
5. Implementación Lazy del Triangulo de Pascal
6. Implementación funcional de la Criba de Erastoteles
Administración de memoria
1. Mostrar gráficamente la fragmentación de memoria: La memoria es un segmento (0, N) y cada objeto se representa como (A, B). A, B, N son Números Naturales. Implementar ID<-GET-BLOCK(SIZE) y FREE-BLOCK (ID)
2. Dado una secuencia de tokens que representa una expresión matemática (numero, +, -, *, /,^,resto,etc.).devolver el resultado utilizando únicamente una pila para almacenamiento en memoria.
3. Dado un grafo que representa la relación de los objetos en memoria, implementar los mecanismos de recolección de basura (Ver libro de Meyer).
Concurrencia (En el lenguaje que desses)
Implementar los siguientes problemas:
• Filósofos
• Barbero durmiente
• Vendedores – Clientes
Utilizando las siguientes técnicas:
• Sincronización (tareas, las citas, paso de mensajes)
• Señalización (Semáforos, Monitores)
• Comunicación (Memoria Compartida)
Spec#
Modele utilizando Spec# un TDA (Tipo de dato abstracto) para las siguientes estructuras de datos:
• Pila
• Cola
• Cola con prioridad
• Diccionario
NOTA: No se requiere la implementación de la estructura (use throw new Exception(“Not implemented”) como cuerpo de los miembros según sea necesario)
Python
Implemente un pequeño framework para el “Diseño por contrato” en Python y argumente su usabilidad. (NOTA: Este ejercicio puede complicarse tanto como se desee; se necesita solamente una implementación básica y simple, justificando el por qué de la utilización de la(s) característica(s) del lenguaje python que haya seleccionado. Tenga en cuenta que existen múltiples frameworks para el diseño por contrato en Python por lo que no tiene sentido desgastarse reinventado la rueda).
Delphi Prim
Como podrán ver en este lenguaje se tiene una gran variedad de recursos. Por lo que para este lenguaje los problemas serian más o menos los mismos que los planteados para los temas anteriores.
1. Modele utilizando Delphi Prim un TDA (Tipo de dato abstracto) para las siguientes estructuras de datos:
o Pila
o Cola
o Cola con prioridad
o Diccionario
Nota: Use las características de este lenguaje que permiten el Diseño por Contratos. De hacer esta pregunta compárela con la implementación de Spec#
2. Implementar los siguientes problemas:
• Filósofos
• Barbero durmiente
• Vendedores – Clientes
Utilizando las siguientes técnicas:
• Sincronización (tareas, las citas, paso de mensajes)
• Señalización (Semáforos, Monitores)
• Comunicación (Memoria Compartida)
Use las características del lenguaje que permiten el uso de programación paralela.
3. Cuál o cuales características de este lenguaje le gusto mas y porque. Considere otro lenguaje donde quisiera tener estas características .
Esta tarea no contiene un alto nivel de complejidad pero si de conocimiento general, ya que son en Lenguajes diferentes.
Haskell
1. Implementación funcional de 8-Reinas
2. Implementación Lazy de un generador de números de Fibonnaci
3. Generar un árbol semi-completo a partir de una lista ordenada de números.
4. Implementación funcional de Torres de Hanói
5. Implementación Lazy del Triangulo de Pascal
6. Implementación funcional de la Criba de Erastoteles
Administración de memoria
1. Mostrar gráficamente la fragmentación de memoria: La memoria es un segmento (0, N) y cada objeto se representa como (A, B). A, B, N son Números Naturales. Implementar ID<-GET-BLOCK(SIZE) y FREE-BLOCK (ID)
2. Dado una secuencia de tokens que representa una expresión matemática (numero, +, -, *, /,^,resto,etc.).devolver el resultado utilizando únicamente una pila para almacenamiento en memoria.
3. Dado un grafo que representa la relación de los objetos en memoria, implementar los mecanismos de recolección de basura (Ver libro de Meyer).
Concurrencia (En el lenguaje que desses)
Implementar los siguientes problemas:
• Filósofos
• Barbero durmiente
• Vendedores – Clientes
Utilizando las siguientes técnicas:
• Sincronización (tareas, las citas, paso de mensajes)
• Señalización (Semáforos, Monitores)
• Comunicación (Memoria Compartida)
Spec#
Modele utilizando Spec# un TDA (Tipo de dato abstracto) para las siguientes estructuras de datos:
• Pila
• Cola
• Cola con prioridad
• Diccionario
NOTA: No se requiere la implementación de la estructura (use throw new Exception(“Not implemented”) como cuerpo de los miembros según sea necesario)
Python
Implemente un pequeño framework para el “Diseño por contrato” en Python y argumente su usabilidad. (NOTA: Este ejercicio puede complicarse tanto como se desee; se necesita solamente una implementación básica y simple, justificando el por qué de la utilización de la(s) característica(s) del lenguaje python que haya seleccionado. Tenga en cuenta que existen múltiples frameworks para el diseño por contrato en Python por lo que no tiene sentido desgastarse reinventado la rueda).
Delphi Prim
Como podrán ver en este lenguaje se tiene una gran variedad de recursos. Por lo que para este lenguaje los problemas serian más o menos los mismos que los planteados para los temas anteriores.
1. Modele utilizando Delphi Prim un TDA (Tipo de dato abstracto) para las siguientes estructuras de datos:
o Pila
o Cola
o Cola con prioridad
o Diccionario
Nota: Use las características de este lenguaje que permiten el Diseño por Contratos. De hacer esta pregunta compárela con la implementación de Spec#
2. Implementar los siguientes problemas:
• Filósofos
• Barbero durmiente
• Vendedores – Clientes
Utilizando las siguientes técnicas:
• Sincronización (tareas, las citas, paso de mensajes)
• Señalización (Semáforos, Monitores)
• Comunicación (Memoria Compartida)
Use las características del lenguaje que permiten el uso de programación paralela.
3. Cuál o cuales características de este lenguaje le gusto mas y porque. Considere otro lenguaje donde quisiera tener estas características .
Suscribirse a:
Entradas (Atom)