Índice
Docentes
Horas de
Consulta
Horario
de Clases
Cronograma
de Actividades
Evaluación
Enunciado
de los exámenes
Enunciado
de Proyectos y normas para el informe y documentación
ÚLTIMA HORA:
- Mejor código (en cuanto a
legibilidad) del proyecto 1: Proyecto
1 Grupo 7
- El día de la
entrega de los proyectos cada grupo tendrá que hacer una exposición de
los resultados de su proyecto en máximo 15 minutos.
- LOS GRUPOS PARA EL PROYECTO SON:
| 0436721 |
Barrera Garcia |
Andres
Emiliano |
1 |
| 0437189 |
Lopez Scutaro |
Carlo X |
1 |
| 0639485 |
Drago Colmenares |
Alejandro |
2 |
| 0640108 |
Ponte Betancourt |
Federico Ignacio |
2 |
| 0538538 |
Mendoza Blanco |
José |
3 |
| 0639439 |
De Sousa De Andrade |
Alexander J |
3 |
| 0639609 |
Gomez Cermeño |
David E |
4 |
| 0639903 |
Mendonca |
Ismael |
4 |
| 0336097 |
Leger |
McArthur |
5 |
| 0538928 |
Santana |
Ricardo |
5 |
| 0639559 |
Fundaro Garcia |
Lorenzo |
6 |
| 0639749 |
Jaber De Lima |
German Eduardo |
6 |
| 0134014 |
Lacruz Lopez |
Aquiles Alberto |
7 |
| 0538990 |
Torre Mora |
Fernando |
7 |
- Deben agruparse en grupos de 2 personas.
- Hasta el domingo 10/01 recibo los e-mails donde especificarán los
grupos de 2 personas para los proyectos.. En la noche del domingo los
que no estén en grupo, yo los agrupo.
- Código de ética para
responder los exámenes:
- Los exámenes son para la casa con una
duración de una semana.
- Lo ideal
es que cada estudiante resuelva y redacte el examen por si solo. Como el examen es para la casa,
no se les puede impedir que se reúnan
con sus compañeros para discutir los problemas,
que consulten internet o cualquier otro
medio de información. Lo que si pido al estudiante es que
sea lo suficientemente honesto y
al momento de redactar el examen lo haga COMPLETAMENTE SOLO.
Lo ético es que una vez tenga claras las
respuestas a cada uno de los problemas, se siente
completamente solo y redacte el examen, como
si estuviera en un examen presencial.
Preguntas redactadas iguales entre
compañeros serán anuladas; y dependiendo del caso
podría acarrear
hasta el aplazamiento del curso.
Redactar solo le
permitirá tener un grado mayor de conocimiento de los temas tratados y
poner en práctica
uno de los problemas mas importantes con el que
nos confrontamos durante la carrera y el resto de la vida,
que es poder poner "en blanco y negro"
las ideas de manera clara, sencilla y concisa.
- Las respuestas a los exámenes y los informes de los proyectos,
deberán ser redactadas con un
procesador de palabras o
formateador de texto (word, latex, etc.) y ser entregadas,
el día estipulado, tanto en papel como enviadas por correo
electrónico en formato PDF a la dirección: meza@ldc.usb.ve. ESTO ES
OBLIGATORIO.
- Los proyectos serán programados en C puro y simple, en ambiente UNIX
- Lecturas recomendadas sobre el
curso:
Semana
1: Capítulos 1 al 4 de Brassard (hojear), primeras
páginas de los capítulos sobre Complejidad de Brassard y Cormen.
Semana 2, 3 y 4:
Brassard
capítulo 6 y sección 5.9, Cormen(segunda edicion, 2001) capítulos 16 y
21.
Semanas 4 y 5:
DFS del libro Grafos y Algoritmos (Oscar Meza y Maruja Ortega),
secciones 9.4 a 9.7 de Brassard
Semanas 7 : cap.
12 Brassard. Sección 3.1 de Garey&Johnson. Capítulo 34 de Cormen
Semanas 8 y 9: Brassard
secciones 4.7, 7.1, 7.2, 7.4, 7.5. Cormen(segunda edicion, 2001)
capítulo 7, cap. 9, secc. 33.4, 14.1,
Semanas 10 y 11:
Brassard cap. 8. Cormen secciones 15.2 y 15.3
Docentes: Oscar Meza
Horas de Consulta: después de
clases.
Horario de clases: lunes y miércoles
1:30-3:30
aula: MYS-111-A
Cronograma de Actividades:
Enero-Abril 2010
|
Lunes
|
Miércoles
|
(1)
11-15
enero
|
Presentación
del curso.
Análisis y síntesis de algoritmos. Complejidad en
tiempo
de algoritmos: Complejidad exacta. Análisis PeorCaso. Notación O grande,
Omega, etc.
|
Análisis Caso
promedio. Ej:
ordenamiento por inserción. Análisis
amortizado. Ej: contador binario.
Algoritmos
eficientes. Problemas
eficientes, problemas difíciles (SAT, coloración). Clases P, NP
|
(2)
18-22 enero
|
Estrategia
Greedy. Como heurística: cambio
moneda, coloración. Como
algoritmo exacto: Kruskal. Verificar correctitud de Kruskal.
entrega enunciado
proyecto 1 (15%)
|
Discusión
del primer proyecto: algoritmo Greedy de Brélaz para
coloración de grafos. Sobre solución del problema de
coloración de grafos por enumeración implícita.
|
(3)
25-29 enero
|
Algoritmos
Greedy. Estructura de
datos para representar particiones de conjuntos. Uso en Kruskal.
Problema
de la Mochila fraccionario (knapsack).
|
Secuenciación.
Verificacion del
algoritmo greedy para secuenciación.
|
(4)
1-5 feb
|
Formalización de
algoritmos Greedy: Matroides.
|
Recorridos
en grafos. Modelo general de etiquetamiento. DFS
propiedades, BFS propiedades. Aplicaciones: enumeración de conjuntos.
Backtracking. EjemplosBacktracking,
estrategias de poda más eficientes. |
(5)
8-12 feb
|
Backtracking. ej:
n-reinas, el problema de la suma. |
Branch&Bound.
Ejemplo: asignación. Knapsack |
(6)
15-19 feb
|
carnaval
|
entrega solución
proyecto 1. Discusión de resultados por los equipos.
entrega enunciado
proyecto
2 (20%).
entrega enunciado
1er. examen (30%)
|
(7)
22-26 feb
|
Discusión proyecto 2
retomar definición de
Problemas
NP, problemas
NP-completos, NP-hard. Reducción
de problemas.
Ejemplos: Cálculo de caminos mínimos en grafos sin circuitos a caminos
máximos. Caminos mínimos hasta cada vértice alcanzable desde uno dado
en caminos mínimos desde cada vértice que alcanza uno dado.
|
entrega solución 1er. examen.
Ejemplos: SAT, 3-SAT,
Coloración, etc. Ejemplos de reducción para mostrar que son
NP-completos (clique máxima). Reducción de sat a
3-sat a "vertex cover" a "ciclo hamiltoniano" a "agente viajero" a
"coloración"
|
(8)
1-5 mar
|
b-uniformidad.
Solúción de recurrencias útiles en
algoritmos recursivos. Teorema maestro. Ejemplos
de análisis
en tiempo de algoritmos recursivos. Corrección
de algoritmos recursivos. Ejemplo: merge-sort. |
Divide-and-Conquer:
esquema general.
Quicksort (análisis promedio) Multiplicación de enteros grandes.
|
(9)
8-12 mar
|
Divide&Conquer:
Estadísticos
de Orden. Aumento de estructuras de datos
para hallar estadísticos de orden. Algoritmo de SELECCION (est.
de orden, Brassard) |
Divide-and-Conquer:
Cálculo de la
mediana en tiempo linealAplicación
en geometría computacional: dos puntos más cercanos
|
(10)
15-19
mar
|
Prog.
Dinámica: En qué
consiste: Coeficiente binomial. Bellman. |
Prog.
Dinámica: Prog. Dinamica: Devolver
cambio. Knapsack |
(11)
22-26 mar
|
Prog. Din. ejemplos: evaluación de
expresiones, multiplicación de n
matrices. Funciones con
memoria. Inicialización
Virtual
|
Discusión
proyecto 2, por equipo.
entrega enunciado
2do. examen (35%)
|
(12)
29mar -
02 abr
|
semana santa
|
semana santa
entrega
solución 2do. examen.
entrega
solucion proyecto 2.
|
(12)
05 abr -
09 abr
|
entrega de
calificaciones. revisión exámenes y
proyectos
|
|
(*) B: Brassard, C:
Cormen, S: Sipser
|
Evaluación :
| Evaluación |
Semana |
Valor |
primer
examen
|
el
profesor entrega el enunciado el 17 de febrero
y el estudiante entrega la solución el 24 de febrero
|
30%
|
segundo
examen
|
el profesor entrega el
enunciado el 24 marzo
y el estudiante entrega la solución el 31 de marzo
|
35%
|
primera entrega proyecto
|
el profesor entrega el
enunciado el 18 enero
y el estudiante entrega la solución el 17 feb
|
15%
|
segunda entrega proyecto
|
el profesor entrega el
enunciado el 17 febrero
y el estudiante entrega la solución el 31 marzo
|
20%
|
Exámenes:
Los exámenes deben ser elaborados con
un procesador de palabras (ej: word) o con un formateador de
documentos (ej: latex) y enviados por e-mail en formato PDF al profesor
y entregar en papel el día de la entrega
- Primer examen, para entregar solución el 24 de
febrero: pdf
solucion:
pdf
- Segundo examen, para entregar solucion el 31 de marzo: pdf
solucion:
pdf
Proyectos:
- Material para los Proyectos:
- ARTÍCULOS PARA LOS PROYECTOS.
-
Estructura del Informe
La entrega de cada proyecto debe venir acompañado de un informe
con la siguiente estructura:
- Introducción:
- Motivación del proyecto.
- Breve descripción del problema.
- Descripción del contenido del informe.
- Diseño:
- Descripción y justificación del modelo utilizado
para representar
el problema.
- Estructuras de datos y algoritmos involucrados en
la aplicación. Justificación
de cada uno de ellos.
- Detalles de Implementación:
- Reseña de los elementos implementados.
- Indicación de los problemas encontrados y la
manera en que se resolvieron.
- Instrucciones de operación:
- Cógido fuente de la aplicación CORRECTAMENTE
DOCUMENTADO.
- Descripción DETALLADA de como compilar y correr
su aplicación.
- Estado Actual:
- Indicación del estado final de la aplicación
(totalmente
operativo, parcialmente operativo, etc.).
- Indicar errores en caso de existir.
- Presentación de los resultados.
- Conclusiones y Recomendaciones
- Referencias bibliográficas
|