Ciencias de la Computación FAMAF

Herramientas de usuario

Herramientas del sitio

Traza: • 2016
algo2:main:2016

Tabla de Contenidos

Algoritmos y Estructuras de Datos II

Novedades

  • el segundo parcial está en la wiki.

Generalidades

Docentes

  • Teóricos: Daniel Fridlender.
  • Prácticos: Alejandro Gadea, Emmanuel Gunther y Demetrio Vilela.
  • Laboratorio: Diego Dubois, Gonzalo Peralta, Jorge Rafael y Leonardo Rodríguez.
    • Ayudantes: Verónica Días, Franco Margaria y Pablo Ventura.

Horarios

  • Teóricos: lunes y miércoles de 14 a 16hs, en el aula 17.
  • Prácticos: lunes y miércoles de 16 a 18hs, en el aula 17.
  • Laboratorio: martes y jueves de 14 a 18hs, en el aula 28 (lab). Los martes se dicta clase, se enuncian y evalúan los proyectos, y se atienden consultas. Los jueves se atienden consultas.

Objetivos

Se pretende que el alumno adquiera:

  • capacidad para comprender y describir el problema que resuelve un algoritmo (el “qué”) y diferenciarlo de la manera en que lo resuelve (el “cómo”),
  • capacidad para analizar algoritmos, compararlos según su eficiencia en tiempo y en espacio,
  • capacidad y hábito de identificar abstracciones relevantes al abordar un problema computacional,
  • familiaridad con técnicas de diseño de algoritmos de uso frecuente,
  • familiaridad con la programación (en el lenguaje c, entre otros) de algoritmos y estructuras de datos,
  • familiaridad con la utilización de diversos niveles de abstracción y lenguajes de programación.

Programa

  • Los contenidos se dividen en tres partes:
    • Análisis de algoritmos: algoritmos de ordenación, orden de un algoritmo, recurrencias.
    • Tipos abstractos de datos: tipos concretos versus tipos abstractos, contador, pila, cola, árboles.
    • Técnicas de programación: algoritmos voraces, divide y vencerás, programación dinámica, backtracking.
  • En Programa de la materia se encuentra una descripción detallada de los contenidos, como así también de los objetivos de la materia, modalidad de evaluación, etc.

Régimen de aprobación, promoción y regularidad

  • Parciales: 2.
  • Fechas: 27/04/2016, 15/06/2016.
  • Recuperatorio: 22/06/2016. El recuperatorio no cuenta para la promoción.
  • Proyectos del laboratorio: entre 4 y 6.
  • Fechas preliminares de evaluación de proyectos: 29/03, 3/5, 24/5
  • Regularidad: aprobando dos parciales (eventualmente recuperando uno de ellos) + aprobando al menos el 60 por ciento de los proyectos del laboratorio.
  • Promoción: aprobando cada parcial con 6 o más, con promedio total de 7 o más + aprobando cada proyecto del laboratorio con 6 o más.
  • Examen final: evaluación por escrito de teórico-práctico + resolución de problemas frente a la computadora (1 ó 2 días, normalmente 2 días).
  • Alumnos libres: ambas partes del examen (teórico y laboratorio) contienen ejercicios adicionales.
  • Los alumnos regulares que promocionan sólo los parciales o sólo los proyectos del laboratorio serán exceptuados de rendir la parte promocionada en las mesas de julio-agosto de 2016, únicamente.

Preguntas frecuentes

  • La regularidad requiere regularidad en el teórico/práctico y en el laboratorio?
    • Sí: la regularidad de la materia es un AND de la regularidad del teórico/práctico con la regularidad del taller.
  • Si voy al laboratorio un jueves de 14 a 18hs, ¿tendré a quien consultar mis dudas?
    • Sí, habrá docentes o ayudantes a quienes podrás consultar.
  • Si apruebo los parciales pero no los proyectos del laboratorio, ¿deberé resolver ejercicios adicionales en el examen escrito?
    • Sí, porque vas a rendir como alumno libre.
  • Si apruebo los proyectos del laboratorio pero no alcanzo a aprobar los parciales, ¿deberé rendir un examen de laboratorio con ejercicios adicionales?
    • Sí, porque vas a rendir como alumno libre.
  • El año pasado aprobé los parciales pero no los proyectos del laboratorio, ¿debo rendir los parciales nuevamente durante este año?
    • Para poder regularizar, sí.
  • El año pasado aprobé los proyectos del laboratorio pero no alcancé a aprobar los parciales, ¿debo volver a hacer el laboratorio este año?
    • Para poder regularizar, sí.
  • ¿Puedo rendir el examen final sin haber hecho el laboratorio?
    • Sí. Como alumno libre. Pero deberás demostrar suficientes conocimientos de programación durante el examen.
  • El año pasado regularicé (es decir, estaba inscripto como regular, aprobé los parciales y los proyectos del laboratorio). Quiero volver a cursar este año. ¿Voy a perder la regularidad obtenida el año pasado?
    • Si te inscribís en la materia automáticamente perdés esa regularidad. Te conviene volver a cursarla sin inscribirte.
  • En ese caso, ¿qué pasa si este año promociono?
    • Te inscribís en la primera fecha de exámenes y te pasamos la nota de la promoción.
  • Tengo condición de regular y promocioné los parciales pero no los proyectos del laboratorio. ¿Debo rendir el escrito también?
    • En las mesas de julio-agosto 2016, no. Después de esas mesas, sí.
  • Tengo condición de regular y promocioné los proyectos del laboratorio pero no los parciales. ¿Debo rendir el laboratorio también?
    • En las mesas de julio-agosto 2016, no. Después de esas mesas, sí.

Evaluaciones

Parciales

Finales

Teórico

Horarios

Lunes y miércoles de 14 a 16hs, en el aula 17.

Bibliografía

  • Notas de Algoritmos y Estructuras de Datos II.
    • Buscar en la wiki de años anteriores.
  • Brassard and Bratley, Fundamentals of Algoritmics.
  • Manber, Introduction to Algorithmics: A Creative Approach.
  • Bibliografía Complementaria
    • Cormen, Leiserson, Rivest y Stein, Introduction to Algorithms.
    • Balcázar, Programación Metódica.
    • Biggs, Matemática Discreta.
    • Kaldewaij, Programming: the Derivation of Algorithms.
    • Blanco, Smith y Barsotti, Cálculo de Programas.

Clases

  • Primera parte: Análisis de Algoritmos.
    • 7-3-16: 01.ordenacion_seleccion.pdf Introducción a la materia, análisis de algoritmos (motivación), problema del bibliotecario, ordenación por selección, número de comparaciones. Conteo de operaciones de un comando.
    • 9-3-16: 02.ordenacion_insercion.pdf Ordenación por inserción, análisis, mejor caso, peor caso y caso medio.
    • 14-3-16: 03.ordenacion_intercalacion.pdf y 04.ordenacion_rapida.pdf Ordenación por intercalación y ordenación rápida.
    • 16-3-16: Ejecución de algoritmos recursivos como ordenación por intercalación y ordenación rápida.
    • 21-3-16: 05.recurrencias_dyv.pdf Análisis de algoritmos recursivos. Análisis de la ordenación por intercalación: análisis para potencias de 2 y análisis para el caso general. Análisis de la ordenación rápida. Generalización: algoritmos divide y vencerás, recurrencias divide y vencerás. Resolución de recurrencias divide y vencerás.
    • 23-3-16: 06.jerarquia.pdf Jerarquía de funciones según su ritmo de crecimiento.
  • Segunda parte: Estructuras de Datos.
    • 28-3-16: 07.tipos.pdf Tipos concretos. Arreglos, listas, tuplas y punteros. Ejemplos de secuencia en arreglo, lista y lista enlazada.
    • 4-4-16: 08.tads.pdf Tipos abstractos. Paréntesis balanceados y el TAD Contador tadcontador.tgz. Delimitadores balanceados y el TAD Pila tadpila.tgz.
    • 6-4-16: 09.implementaciones_contador_pila.pdf Implementación de contadores. Implementación natural. Otras implementaciones. Implementación de pila con listas como tipo concreto. Implementación de pila con arreglos. Implementación de pila con listas enlazadas.
    • 11 y 13-4-16: 10.colas.pdf Buffer. TAD Cola. Especificación Implementaciones con listas como tipo concreto, con arreglos circulares y con listas enlazadas. Algoritmos de ordenación. TAD cola de prioridades, especificación y ordenación por cola de prioridades.
    • 18-4-16: 11.arboles_binarios.pdf Árboles binarios. Intuición. Terminología. Especificación. Implementación con punteros. Posiciones. Posiciones en un árbol. Subárboles de un árbol binario. Elementos de un árbol binario.
    • 20-4-16: 12.abb.pdf Árboles binarios de búsqueda. 13.heap.pdf Heaps. Implementación de cola de prioridades. Heapsort.
  • Tercera parte: Algoritmos Avanzados.
    • 9-5-16: 15.voraz.pdf Algoritmos voraces. Características. Forma general. Problema de la moneda. Problema de la mochila. Problema del árbol generador de costo mínimo.
    • 11-5-16: 16.voraz.pdf Árbol generador de costo mínimo. Algoritmo de Prim. Algoritmo de Kruskal. Problema Union-Find.
    • 16-5-16: 17.dijkstra.pdf Problema del camino de costo mínimo. Algoritmo de Dijkstra. Orden de los algoritmos voraces sobre grafos.
    • 18-5-16: 18.backtracking.pdf Backtracking. Solución general al problema de la moneda. Solución general al problema de la mochila. Problema de los caminos de costo mínimo.
    • 23-5-16: 19.grafo_implicito.pdf Grafo implícito en los algoritmos de backtracking. Ejemplo: problema de la moneda.
    • 25-5-16: feriado
    • 30-5-16: 20.programacion_dinamica.pdf Programación dinámica. Fibonacci, problema de la moneda, problema de la mochila.
    • 1-6-16: 21.programacion_dinamica.pdf Programación dinámica. Problema del camino de costo mínimo.
    • 6-6-16: 22.dfs.pdf Recorrida de árboles binarios. Pre-orden, in-orden y pos-orden. Recorrida de árboles finitarios. Recorrida de grafos. DFS iterativo. BFS.
    • 8-6-16: 23.8reinas.pdf Backtracking. Grafos implícitos. 8 reinas. n reinas.

Vínculos interesantes

Práctico

Horarios

Lunes de 11 a 13hs y miércoles de 16 a 18hs, en el aula 17.

Guías de ejercicios

Notas de parciales

Laboratorio

Los grupos serán de 2 (dos) personas. Mínimo 2, máximo 2. O sea, 2 :-).

Horarios

  • Martes 14 a 18 hs: Teóricos del taller, presentación de enunciados, entregas y evaluación de proyectos, consultas.
  • Jueves 14 a 18 hs: Uso del laboratorio y consultas.

Todas las clases son en el laboratorio de computación del 2do piso (aula 28).

Proyectos

Clases

Instrucciones para inscribirse en la lista de mails

Tenemos un googlegroup para los alumnos y los docentes en la siguiente dirección:

https://groups.google.com/forum/#!forum/ayed2-famaf

Para subscribirse, hacer click en “solicitar membresía” (o “subscribe to this group”).

Por favor elegir una dirección de mail que lean todos los días y que no tenga restricciones de tamaño. No es obligatorio que sea un email de gmail. Las direcciones de hotmail/outlook están particularmente no recomendadas ya que suelen llenarse rápido y no les llegan los correos.

IMPORTANTE 1: una vez que se subscribieron al grupo, ir a la casilla de mail que usaron y aceptar la invitación.

IMPORTANTE 2: si ya estaban logueados en gmail, les aparece un diálogo para la subscripción donde tienen que elegir, entre otras cosas, el tipo de envíos de los emails: elegir “todos los emails”, como se muestra acá:

Instrucciones para mandar un mail en la lista de mails

Para mandar un mail a la lista de la materia, escribir a:

ayed2-famaf@googlegroups.com

algo2/main/2016.txt · Última modificación: 2018/08/10 03:03 por 127.0.0.1