| navegación | |
Universidad del Cauca |
Contenido de la asignatura
En esta página puede consultar el contenido de la asignatura y alguna bibliografía asociada
Las notas de la asiguatura se encuentran en el siguiente enlace (HTML).
[10-12-2009] Examen Final.
El enunciado del examen final se encuentra en el siguiente enlace (PDF).
Fecha de entrega: Jueves 14 de enero de 2010, 4:00 P.M.
Grupos de máximo 2 personas.
[26-11-2009] Laboratorio 8. Grafos no dirigidos con peso - Arbol de expansion de costo minimo
Elaborar un programa que implemente las funcionalidades basicas de un grafo no dirigido con peso (conexo), que almacena números enteros en sus nodos. La entrada del programa se dará por entrada estándar, y consistirá en una serie de comandos:
nodo 1 arco 1 3 7 arco 1 4 3 arco 1 5 5 imprimir kruskal costo 1 end
El comando nodo # deberá insertar el nodo con el dato # en el grafo, si no existe.
El comando arco i j w deberá insertar un arco entre el nodo i y el nodo j, con un peso de w. Si los nodos no existen, se deberán crear automáticamente.
El comando costo # deberá calcular e imprimir el árbol de expansión de costo mínimo de ir desde el nodo # hasta los demás nodos del grafo.
El comando kruskal deberá calcular e imprimir el árbol de expansión mínima por medio del algoritmo del mismo nombre.
[12-11-2009] Laboratorio 7. Grafos no dirigidos sin peso.
Desarrollar un programa para crear y manipular grafos no dirigidos sin peso. La entrada de este programa se dará por entrada estándar, y consistirá en uno o varios comandos:
NODO n
ARCO n m
BUSCAR n
IMPRIMIR
SALIR
La implementación del grafo se hará con una lista de nodos. Igualmente, la implementación se deberá realizar de tal forma que los nodos puedan almacenar cualquier tipo de datos. Para el programa de prueba, los datos a almacenar y buscar son números enteros.
El comando ARCO n m deberá crear un arco entre los nodos con dato n y m. Si alguno de esos nodos no existe, se deberá crear automáticamente.
El comando IMPRIMIR deberá imprimir (en formato de lista de adyacencia) el grafo.
[05-11-2009] Segundo examen parcial.
El enunciado del segundo examen parcial se encuentra en el siguiente enlace (PDF).
Fecha de entrega: Jueves 12 de noviembre de 2009, 4:00 P.M.
Grupos de máximo 2 personas.
[29-10-2009] Implementación de lista genérica
En el siguiente enlace encontrarán la implementación de una lista genérica (.h)
[29-10-2009] Laboratorio 6. Á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
NIVELES
END
Para cada recorrido (preorden, inorden, postorden y niveles) el programa deberá imprimir la secuencia de números del recorrido en una sola línea.
[22-10-2009] Laboratorio 5. Árboles Binarios de Búsqueda
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
END
Para cada recorrido (preorden, inorden, postorden) el programa deberá imprimir la secuencia de números del recorrido en una sola línea.
[01-09-2009] Primer examen parcial.
El enunciado del primer examen parcial se encuentra en el siguiente enlace (PDF).
Fecha de entrega: Jueves 8 de octubre de 2009, 2:00 P.M.
Grupos de máximo 2 personas.
[24-09-2009] Laboratorio 4. Distancia entre cadenas.
Desarrollar un algoritmo que dadas dos cadenas de caracteres X e Y, determine el mínimo número de operaciones requeridas para transformar X en Y. Las operaciones válidas sobre las cadenas son:
- Eliminar un caracter
- Insertar un caracter
- Cambiar un caracter
La entrada del programa se dará por entrada estándar, y consistirá en una serie de líneas.
Cada línea contendrá dos cadenas separadas por un espacio, que representan a X y Y.
Para cada X e Y, el algoritmo deberá calcular e imprimir el mínimo número de pasos requeridos para transformar X en Y.
[17-09-2009] Laboratorio 3.
Desarrollar un algoritmo que dada una secuencia de números enteros mayores o iguales a cero, ecuentre todas las ocurrencias en las cuales el número es igual a su posición en la secuencia.
La entrada del programa se dará por entrada estándar, y consiste en una serie de secuencias de números a probar.
Ejemplo:
5 2 -3 7 1 -1 5 -2 3 -7 1 1 1 2 3 4 5 -5 -8 -2 -1 -3
[10-09-2009] Laboratorio 2.
Diseñar e implementar un algoritmo que resuelva el siguiente problema:
Se tiene una grúa encargada de recoger los troncos que flotan en un río. Para realizar esta tarea, la grúa solo se puede desplazar de una orilla hacia la otra, y río abajo (Si se considera la orilla inicial como "izquerda" y la otra orilla del rícomo "derecha", entonces la grúa sólo puede desplazarse de izquierda a derecha y de arriba hacia abajo).
Por las restricciones en el movimiento de la grúa, esta deberá realizar varios recorridos para recoger todos los troncos.
Desarrollar un algoritmo voraz que encuentre el mínimo número de recorridos que debe realizar la grúa para recoger todos los troncos.
La entrada del programa se dará por entrada estándar, y consistirá en una serie de casos de prueba. Cada caso de prueba consiste en una línea que contiene el orden de la matriz, e inmediatamente despué de esta línea se encuentra la matriz con la distribución de troncos en el río.
Ejemplo:
8 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
[03-09-2009] Laboratorio 1.
Diseñar e implementar un algoritmo que dadas dos secuencias de números binarios X e Y con longitud menor a 40, determine si la secuencia binaria Y se encuentra dentro de la secuencia binaria X.
Los datos de entrada se darán por entrada estándar, y consistirá en una serie de líneas.
Cada línea contendrá dos secuencias binarias de caracteres (X e Y), separadas por un espacio.
Para cada línea el algoritmo deberá determinar si la segunda secuencia (Y) se encuentra dentro de la primera secuencia(X).
En el siguiente enlace: (ZIP) encontrarán ejemplos de la estrategia que se utilizará en la asignatura para la lectura de datos.