• inicio
• docencia
• investigación
• enlaces

Contenido de la asignatura

En esta página puede consultar el contenido de la asignatura y alguna bibliografía asociada.

[18-02-2009] En el siguiente enlace encontrarán las notas del tercer corte (HTML).

[2009-01-29] Parcial Final

Diseñar e implementar un algoritmo que permita encontrar la mejor asignacion de carreras universitarias para una serie de aspirantes. Cada aspirante tiene sus preferencias por determinada carrera, y cada carrera tiene su orden de preferencia con respecto a cada estudiante.
La entrada al programa se dará por entrada estándar, y consistirá en una serie de comandos:

elementos 5
estudiantes archivo_estudiantes.txt
carreras archivo_carreras.txt
seleccionar

El comando elementos especifica el numero de carreras y de aspirantes que se tienen.

El comando estudiantes especifica el archivo en el cual se encuentra el listado de estudiantes, con su respectivas preferencias. El comando carreras especifica el archivo en el cual se encuentra el listado de carreras.
El comando seleccionar deberá ejecutar el algoritmo para la seleccion de aspirantes, e imprimirá un listado con los estudiantes seleccionados para cada carrera.

Un ejemplo del archivo de carreras es el siguiente:

sistemas 101 102 103 104 105
electronica 103 102 101 104 105
automatica 105 101 102 103 104
telematica 102 105 104 103 101
telecomunicaciones 105 104 103 102 101

Este archivo especifica el numero de carreras, y para cada carrera especifica el orden de preferencia de los estudiantes con su codigo.

De otro lado, el archivo de estudiantes contiene la siguiente informacion:

101 sistemas automatica electronica telematica telecomunicaciones
102 sistemas telematica telecomunicaciones electronica automatica
103 electronica sistemas telematica telecomunicaciones automatica
104 automatica telecomunicaciones telematica electronica sistemas
105 telematica sistemas automatica telecomunicaciones electronica

En el siguiente enlace:

http://decsai.ugr.es/~mgs/ta/lista.html

Encontrarán material acerca de como usar la libreria STL de C++ (nota: se deben usar archivos .CPP para que Dev-C reconozca la libreria).

[22-01-2009] Laboratorio 11. Grafos dirigidos con peso - Flujo de redes

Elaborar un programa que implemente las funcionalidades basicas de una red, implementada como un grafo dirigido con peso con una sola fuente y un solo sumidero. Los nodos de la red almacenarán caracteres, y los arcos representan las uniones entre los nodos. El peso en cada arco representa su capacidad. La entrada del programa se dará por entrada estándar, y consistirá en una serie de comandos:

fuente a
sumidero f
nodo b

arco a b 8
arco b c 5
arco c f 12
arco a d 6
arco b d 4
arco d e 5
arco e f 8
imprimir
flujo
end

El comando flujo deberá calcular e imprimir el flujo máximo que se puede obtener de la red.

Suponga también que solo existirá una fuente y un sumidero, y que la red dada es válida (es decir, existe al menos un camino entre la fuente y el sumidero que incrementa el flujo obtenido).

[15-01-2009] Laboratorio 10. Grafos no dirigidos con peso - Arbol de expansion minima

Elaborar un programa que implemente las funcionalidades basicas de un grafo no dirigido con peso, que almacena caracteres en sus nodos. La entrada del programa se dará por entrada estándar, y consistirá en una serie de comandos:

arco a c 7
arco a d 3
arco a f 5
imprimir
kruskal
end

El comando kruskal deberá calcular e imprimir el árbol de expansión mínima por medio del algoritmo del mismo nombre.

[08-01-2009] Laboratorio 9. Grafos no dirigidos con peso - Costos mínimos

Elaborar un programa que implemente las funcionalidades basicas de un grafo no dirigido con peso, que almacena caracteres en sus nodos. La entrada del programa se dará por entrada estándar, y consistirá en una serie de comandos:

nodo a
nodo b
nodo c
arco a c 7
arco a d 3
arco a f 5
imprimir
costo a
end

El comando costo deberá calcular imprimir el costo (peso) mínimo de ir desde el nodo con el dato dado como parámetro hasta los demás nodos del grafo. Por ejemplo, el comando

costo a

Deberá calcular e imprimir el costo mínimo de ir desde a hasta todos los demás nodos del grafo.

Importante: Suponga que en el momento de agregar un arco si alguno de los nodos a que hace referencia el comando no existen, se deberán crear automáticamente.

[18-12-2008] Laboratorio 8. Grafos no dirigidos.

Elaborar un programa que implemente las funcionalidades basicas de un grafo no dirigido sin peso, que almacena caracteres. La entrada del programa se dará por entrada estándar, y consistirá en una serie de comandos:

nodo a
nodo b
nodo c
arco a c
arco a d
arco a f
imprimir
dfs a
bfs a
end

Importante: Suponga que en el momento de agregar un arco si alguno de los nodos a que hace referencia el comando no existen, se deberán crear automáticamente.

Fecha de entrega: Jueves 8 de enero de 2009.

[11-12-2008] Segundo examen parcial.

El enunciado del segundo examen parcial se encuentra en el siguiente enlace (PDF). Fecha de entrega: Jueves 18 de Diciembre de 2008.

[04:12:2008] Laboratorio 7. Árboles B+

Desarrollar un programa para crear y manipular árboles B+. La entrada de este programa se dará por entrada estándar, y consistirá en uno o varios comandos:

INSERTAR n

BUSCAR n

SALIR

El comando buscar deberá imprimir el numero de comparaciones que realizaron para encontrar el dato. Si el dato no se encuentra en el árbol, el comando buscar tamtién deberá imprimir el número de comparaciones realizadas.

[27:11:2008] Laboratorio 6. Árboles 2-3

Desarrollar un programa para crear y manipular árboles 2-3. La entrada de este programa se dará por entrada estándar, y consistirá en uno o varios comandos:

INSERTAR n

BUSCAR n

SALIR

Para el comando buscar, el programa deberá imprimir el número de comparaciones que se realizaron para encontrar el dato. Si el dato no se encuentra en el árbol, el comando buscar también deberá imprimir el número de comparaciones realizadas.

[20:11:2008] Laboratorio 5. Árboles AVL

Desarrollar un programa para crear y manipular árboles AVL. La entrada de este programa se dará por entrada estándar, y consistirá en uno o varios comandos:

INSERTAR n

BUSCAR n

ELIMINAR n

PREORDEN

INORDEN

POSTORDEN

SALIR

Para cada recorrido (preorden, inorden y postorden) el programa deberá imprimir la secuencia de números del recorrido en una sola línea.

[13:11:2008] Laboratorio 4. Árboles Binarios

Desarrollar un programa para crear y manipular árboles binarios. La entrada de este programa se dará por entrada estándar, y consistirá en uno o varios comandos:

INSERTAR n

BUSCAR n

ELIMINAR n

PREORDEN

INORDEN

POSTORDEN

SALIR

Para cada recorrido (preorden, inorden y postorden) el programa deberá imprimir la secuencia de números del recorrido en una sola línea.

[06-11-2008] Primer parcial.

Primer punto (50 puntos): Cualquier estrategia

El conductor y las estaciones de servicio

Un conductor decide viajar de una ciudad A a una ciudad B, situada al otro lado del país. El conductor dispone de un mapa de rutas, en el cual se muestra la distancia en kilómetros que existe entre cada estación de servicio en el recorrido entre A y B. Dado que el tanque de gasolina de su automóvil tiene una determinada capacidad, el conductor puede recorrer n kilómetros sin necesidad de parar a llenar el tanque.

Desarrollar un algoritmo que dado el número de kilómetros que puede recorrer el automóvil con el tanque lleno y el mapa de rutas, determine en cuales estaciones de servicio debe tanquear el conductor de modo que el número de paradas que tenga que realizar sea mínimo. Suponga que el conductor arranca de la ciudad A con el tanque lleno.

Segundo punto (50 puntos): Vuelta atrás

Subconjuntos de igual suma

[16:10:2008] Laboratorio 3. (Programacion Dinamica) Problema de la secuencia de suma maxima.

Desarrollar un programa que dado un conjunto no ordenado de numeros diferentes de cero, encuentre la secuencia de numeros cuya suma es maxima.
Los datos de entrada del programa consistiran en una serie de lineas, y cada linea es un conjunto de numeros a procesar. Para cada conjunto el programa debera calcular e imprimir la secuencia de numeros cuya suma es maxima.
El programa debera terminar cuando se encuentre la palabra end en una linea.

Ejemplos de datos de entrada:

1 2 3 -4 5 1 -2
-1 -2 3 2 6 7
end

[09:10:2008] Laboratorio 2. (Voraces) Problema de la secuencia de trabajos..

Desarrollar un programa que dada una serie de trabajos de duracion unitaria, la ganancia y el tiempo limite para cada trabajo, determine la combinación de trabajos que maximizan la ganancia total.
Los datos de entrada de este programa consistirán en conjuntos de prueba que se ingresarán por medio de la entrada estándar, con el siguiente formato:

n
g1 g2 g3 ... gn
l1 l2 l3 ... ln
n
g1 g2 g3 ... gn
l1 l2 l3 ... ln
end

[02:10:2008] Laboratorio 1. (Fuerza Bruta) Problema del laberinto.

Desarrollar un programa que dado un laberinto, la posicion inicial y la posicion final, determine si existe camino desde la posicion inicial hasta la posicion final. Los datos deberan ser leidos por entrada estándar

Para el proceso de leer los datos, se pueden basar en el siguiente programa: laberinto.c (Click derecho -> Guardar como..) y el archivo de prueba prueba.txt