Universidad Nacional del Litoral
Facultad de Ingeniería y Ciencias Hídricas
Teoría de la Computación

Novedades

[19-05-12, 15:50]. Algoritmos de la página que entran en el parcial: esprimo, suma de Gauss (suma_i, suma_r), máximo de una lista (maximo_i, maximo_r), relaciones de recurrencia (e.g. an_21, an_24), factorial (factorial_i, factorial_r), potencia (potencia_i, potencia_r), mcd (mcd_i, mcd_r). Algoritmos para relaciones: es_reflexiva, es_simetrica, es_antisimetrica, es_transitiva, es_relacion_de_equivalencia, y es_relacion_de_orden.

[18-05-12, 13:15]. Se actualizaron los siguientes algoritmos en la página: (i) test para determinar si un entero positivo es primo; (ii) algunos demos usando recursión; y (iii) algunos tests para relaciones.

[17-05-12, 12:34]. Postergación de la fecha del Segundo Parcial (a pedido de los alumnos): pasa al MIERCOLES 23 de MAYO a las 14 hs en el Aula 9. Instrucciones:

• Presentarse 20' antes (13:40hs).
• Llevar calculadora.

[15-05-09, 11:10]. Para la Comisión 1: se corrigió el día de la práctica recuperatoria. Las demás comisiones sin cambios.

[14-05-09, 14:05]. Temario de la teoría para el Parcial 2 siguiendo el texto ROSEN: ver hasta la Sec. 7.3 mientras que las Sec. 7.4-7.6 pasan al siguiente parcial.

[14-05-09, 12:40]. Prácticas por el asueto del Martes 15 de Mayo (llegar con puntualidad):

• Comisión 1: la clase se dictará el Miércoles 16 de Mayo en la FICH en el Aula 8 de 13 a 15 hs.
• Comisión 2: la clase se dictará el Martes 15 de Mayo en el edificio INTEC-1 en el Aula 40 en el horario habitual de 10 a 12 hs.
• Comisión 3: la clase se dictará el Martes 15 de Mayo en el edificio INTEC-1 en el Aula 40 en el horario habitual de 15 a 17 hs.

[13-05-09, 17:45]. Temario tentativo de la teoría para el parcial 2 siguiendo el texto ROSEN: se completó el faltante con respecto a las Sec. 3.4 y 3.5 del Cap. 3.

[09-05-09, 8:08]. Temario tentativo de la teoría para el parcial 2 siguiendo el texto ROSEN ("Matemática discretas y sus aplicaciones", 5ta edición, 2004):

• Sec. 1.8 [Funciones]. Funciones inversas y composición de funciones (pp. 94), def. 9-10, ejemplos 14-18. Gráfica de una función: def. 11, ejemplos 19-20. Algunas funciones importantes: funciones piso y techo (def. 12), tabla 1, ejemplos 21-25.
• Sec. 2.4 [Enteros y división]. División: def. 1, teor. 1, corolario 1, ejemplos 1-2. Números primos: def. 2, teor. 2-3, enunciados de los teor. 4-5, omitir ejemplo 7. El algoritmo de la división: teor. 6, def. 3, ejemplos 8-9. Máximo común divisor y mínimo común múltiplo: def. 4-7, teor. 7, ejemplos 10-15. Aritmética modular: omitir. Aplicaciones de las congruencias: omitir. Criptología: omitir.
• Sec. 2.5 [Enteros y algoritmos]. Representaión de números enteros: teor. 1, ejemplos 1-6, algoritmo 1. Algoritmos para operaciones con enteros: omitir. Exponenciación modular: omitir. El algoritmo de Euclides: lema 1, ejemplo 12, algoritmo 6 (tanto iterativo como recursivo).
• Sec. 2.6 [Aplicaciones de la teoría de números]: omitir.
• Sec. 2.7 [Matrices]: omitir.
• Sec. 3.4 [Definiciones recursivas e inducción estructural]: funciones definidas recursivamente: def. 1, ejemplos 1-5, reemplazar el ejemplo 6 por el visto en la teoría, omitir teor. 1. Conjuntos y estructuras definidas recursivamente: omitir. Inducción estructural: omitir. Inducción generalizada: omitir.
• Sec. 3.5 [Algoritmos rrecursivos]: def. 1, ejemplos 1 (alg. 1) y 4 (alg. 3), omitir ejemplos 2, 5, 6. Recursión e iteración: ejemplo 7 (alg. 6-9). Ordenación por mezcla: omitir. Omitir el resto del cap.
• Sec. 4.1 [Fundamentos de combinatoria]. Principios básicos de recuento: las reglas del producto y de la sumaejemplos 1-6, 9-12. Problemas de recuento más complicados: omitir. El principio de inclusión-exclusión: ejemplo 16. Diagramas árbol: ejemplos 17-18.
• Sec. 4.2 [Principios del palomar]. Introducción: teor. 1, ejemplos 1-3. El Principio del Palomar (PP) generalizado: teor. 2, ejemplos 9. Algunas aplicaciones elegantes del PP: sólo el ejemplo 10.
• Sec. 4.3 [Permutaciones y combinaciones]. Permutaciones: teor. 1, ejemplos 1-5. Combinaciones: teor. 2, coroloario 1, def. 1, ejemplos 6-11.
• Sec. 4.4 [Coeficientes binomiales]. El teorema del binomio: teor. 1, corolarios 1-3, ejemplos 1-4. El triángulo y la identidad de Pascal: teor. 2. Algunas identidades entre coeficientes binomiales: teor. 3, corolario 4, omitir teor. 4.
• Sec. 4.5 [Permutaciones y combinaciones generalizadas]. Permutaciones con repetición: teor. 1, ejemplo 1. Combinaciones con repetición: teor. 2, ejemplos 2-7. Permutaciones con objetos indistiguibles: teor. 3, ejemplo 8, tabla 1. Distribuciones de objetos en cajas: teor. 4 y ejemplo 9. Teor. Multinomial en el caso m=3 (ejercicio 53 de la página 319).
• Sec. 4.6 [Generación de permutaciones]: omitir.
• Sec. 6.1 [Relaciones de recurrencia (RR)]. Def. 1, ejemplos 1-6, omitir ejemplos 7-8.
• Sec. 6.2 [Resolución de las RR]. Def. 1, ejemplos 1-2. Resolución de las RRLHCC: teor. 1-3, enunciados de los teor. 3-4, ejemplos 3-8. Relaciones de recurrencia lineales y no-homogéneas de CC: enunciados de los teor. 5-6, ejemplos 9-13.
• Sec. 6.3 [Algoritmos de divide y vencerás y RR]: omitir.
• Sec. 6.4 [Funciones generatrices]: omitir.
• Sec. 6.5 [Principio de inclusión-exclusión (PIE)]. Ejemplos 1, 3, 4, omitir ejemplo 2, enunciado del teor. 1.
• Sec. 6.6 [Aplicaciones del PIE]. Forma alternativa del PIE: sólo el ejemplo 1 y omitir el resto de la sección.
• Sec. 7.1 [Relaciones y sus propiedades]. def. 1, ejemplos 1-3. Funciones como relaciones. Relaciones en un conjunto: def. 2, ejemplos 4-6. Propiedades de las relaciones: def. 3-5, ejemplos 7-16. Combinaciones de relaciones: def. 6-7, teor. 1, ejemplos 17-22.
• Sec. 7.2 [Relaciones n-arias y sus aplicaciones]: omitir.
• Sec. 7.3 [Representaciones de relaciones]. Representación usando matrices: ejemplos 1-6. Representación usando digrafos: def. 1, ejemplos 7-10.

Temas que se postergan al Parcial 3:

• Sec. 7.4 [Cierre de relaciones]. Cierres: ejemplos 1-2. Caminos en grafos dirigidos: def. 1, teor. 1 (sólo enunciado), ejemplo 3. Cierre transitivo: def. 2, ejemplos 4-7, teor. 2-3 (sólo enunciado), algoritmo 7. El algoritmo de Roy-Warshall: ejemplo 8 y algoritmo 2.
• Sec. 7.5 [Relaciones de equivalencia]. Def. 1, ejemplos 1-4. Clases de equivalencia: def. 2, ejemplos 5-6. Clases de Equivalencia y particiones: teor. 1, ejemplos 7-9.
• Sec. 7.6 [Ordenes parciales]. Def. 1, , ejemplos 1-3. Def. 2-3, ejemplos 4-6. Omitir el resto del cap.

[06-05-12, 19:30]. Clase optativa de práctica en la Comisión 3 (i.e. no es obligatoria): este próximo Martes 08-Mayo exactamente a las 14:45 hs se verá una explicación más detallada del E37 de la GTP sobre el Principio del Palomar.

[27-04-12, 14:00].

• Están las notas del Parcial 1 en http://venus.ceride.gov.ar/~mstorti/notas4.cgi
• Muestra del Parcial 1: será el Viernes 4-Mayo en el CIMEC. Tema 1: a las 14 hs. Tema 2: a las 14:30 hs.
• Se subieron a la página los enunciados de los temas 1 y 2 del Parcial 1.

[14-04-12, 15:10].

• Para los que estuvieron ayer en el Aula 9: alguien dejó olvidada una calculadora (al fondo hacia el ventanal). Solicitarla en la teoría del próximo Miércoles.
• La Sec. 3.2 se agregará en el Globalizador, por lo cual se la incluyó en el Temario de la teoría del parcial 1.

[10-04-12, 14:40]. Ante consultas varias:

• La próxima clase de teoría se confirma sin cambios e incluirá un repaso para el parcial.
• A la finalización de la clase habrá otra clase opcional (de asistencia libre) de repaso o consultas pero en otra aula (a determinar).

[06-04-12, 16:00] Fecha del Primer Parcial: VIERNES 13 de ABRIL a las 15:00 hs en el Aula 9. Instrucciones:

• Concurrir con Libreta Universitaria o documento (con foto) para acreditar identidad.
• Presentarse 20' antes (14:40 hs).
• Temario de la teoría siguiendo el texto ROSEN ("Matemática discretas y sus aplicaciones", 5ta edición, 2004):
  • Sec. 1.1 (Lógica, pág. 1). Proposiciones: def. 1-4, tabla de verdad, conectivos lógicos. Implicaciones: definiciones 5-6, ejemplos adicionales. Recíproca, contrarecíproca e inversa. Precedencia de operadores lógicos. Lógica y operaciones de bits. Omitir: especificaciones del sistema, juegos de lógica y búsquedas booleanas.
  • Sec. 1.2 (Equivalencias Proposicionales, pág. 19). Def. 1-2, tablas 5-7, ejemplos 1-6.
  • Sec. 1.3 (Predicados y Cuantificadores, pág. 26). Intro: dominio de discurso, función proposicional y predicado, ejemplos 1-4. Cuantificadores universal y existencial: def. 1-2, tabla 1, ejemplos 5-13. Variables ligadas: ejemplo 14. Negaciones: tabla 2, ejemplos adicionales, ejemplos 15-16. Omitir: "traducción de oraciones en lenguaje natural al lenguaje formal", "ejemplos de Lewis Carroll" y "programación lógica".
  • Sec. 1.4 (Cuantificadores Anidados, pág. 40). Ejemplos 1-9. Negaciones de cuantificadores anidados: ejemplos 11-12. El orden de los cuantificadores anidados: ejemplos 14-16, tabla 1 y algoritmos vistos en la teoría.
  • Sec. 1.5 (Métodos de Demostración, pág. 52), Reglas de inferencia: tabla 1, ejemplos 1-5. Argumentos válidos: ejemplos 5-7. Resolución: ejemplos 8-9. Falacias: ejemplos 10-11. Reglas de inferencia para sentencias cuantificadas: ejemplos 12-13. Métodos para demostrar teoremas: demostraciones directas, indirectas, por reducción al absurdo, por casos y por equivalencia, ejemplos 14-25. Teoremas y cuantificadores: demostraciones de existencia y de unicidad. Contraejemplos, ejemplos 28, 29, 30. Errores en las demostraciones: ejemplos 31-35. Omitir ejemplos 26-27.
  • Sec. 1.6 (Conjuntos, pág. 71), Intro: def. 1-6, teor. 1, ejemplos 1-10. El conjunto de las partes de un conjunto: def. 7, ejemplos 11-12. Producto cartesiano: def. 8-10, ejemplos 13-16.
  • Sec. 1.7 (Operaciones con Conjuntos, pág. 79). Def. 1-5, tabla 1, ejemplos 1-9. Identidades de conjuntos: ejemplos 10-12, 14. Uniones e intersecciones generalizadas: def. 6-7, ejemplos 15-16. Omitir: "representación de conjuntos en un ordenador".
  • Sec. 1.8 (Funciones, pág. 90). Intro: def. 1-4, ejemplos 1-5. Funciones inyectivas y sobreyectivas: def. 5-8, ejemplos 6-13.
  • Sec. 3.2 (Sucesiones y Sumatorias, pág. 210). Sucesiones: def. 1-3, ejemplos 1-4. Sucesiones especiales de enteros: ejemplos 5-7. Sumatorias: teorema 1, ejemplos 9-15. Omitir el resto de la sección.
  • Sec. 3.3 (Inducción Matemática, pág. 222). Enunciado, notación simbólica, paso base y paso de inducción. Inducción fuerte. Ejemplos 1-10, 15. Omitir: "la propiedad del buen orden" y los ejemplos 11-14.

[02-12-12, 11:45]. TorneoProgramacion.

• Vejedades (novedades que ya no son)

Contenidos...

• Programa
• Bibliografía
• Modalidad de dictado
• Días y horarios
• Cronograma tentativo
• Ejercicios para las prácticas
• Regímenes de regularidad y de promoción
• Utilidad de la asignatura

Teoría de la Computación

• Carreras: Ingeniería Informática, Analista en Informática Aplicada
• Extension: Cuatrimestral
• Carga horaria: 105 hs de clases (45 hs teoría / 60 hs práctica)
• Página : http://www.cimec.org.ar/tcomp
• Docentes:
  • Jorge D'ELIA, (jdelia(at)intec(dot)unl(dot)edu(dot)ar)
  • Lisandro DALCIN, (dalcinl(at)intec(dot)unl(dot)edu(dot)ar)
  • Martín PUCHETA, (mpucheta(at)intec(dot)unl(dot)edu(dot)ar)
  • Gustavo RIOS, (grios(at)ceride(dot)gov(dot)ar)
  • Juan José GOMEZ BARROSO (jgomezb)(at)intec(dot)unl(dot)edu(dot)ar)
  • Alejandro COSIMO (acosimo)(at)intec(dot)unl(dot)edu(dot)ar)
  • Pablo Sebastián ROJAS FREDINI (srojasfredini(at)santafe-conicet(dot)gov(dot)ar)
    donde (at)=@, (dot)=.

Programa

• Objetivos: proporcionar las bases teóricas de la ciencia de la computación y de la matemática discreta, a través de una introducción a la lógica proposicional, teoría de conjuntos, relaciones y funciones, algoritmos,métodos de conteo, grafos y árboles, máquinas de estado finito, gramáticas y lenguajes.
• Contenidos:

1. Lógica y razonamiento matemático: proposiciones, proposiciones condicionales y equivalencia lógica, predicados y cuantificadores, cuantificadores anidados, métodos de demostración.
2. Conjuntos y funciones: conjuntos, principio de inclusión-exclusión, funciones.
3. Enteros y sucesiones: enteros, mínimo común múltiplo y máximo común divisor, algoritmo de Euclides, sucesiones, sumatorias.
4. Inducción y recursividad: inducción matemática, algoritmos recursivos.
5. Métodos de conteo: principios básicos, permutaciones y combinaciones, permutaciones y combinaciones generalizadas, coeficientes binomiales e identidades combinatorias, principio del palomar.
6. Relaciones de recurrencia (RR): introducción, solución, ejemplos de RR en algoritmos.
7. Relaciones: relaciones y sus propiedades, representación de relaciones con matrices y digrafos, relaciones de equivalencia y órdenes parciales.
8. Grafos: caminos y ciclos, ciclos eulerianos y hamiltonianos, ruta más corta mediante el algoritmo de Dijkstra, representaciones de grafos, isomorfismos de grafos, grafos planos.
9. Árboles: terminología y caracterización de árboles, árboles de expansión (o generadores), mediante los algoritmos e búsqueda a lo ancho y en profundidad, árboles de expansión mínimos mediante los algoritmos de Prim y de Kruskal, árboles binarios, recorridos de árboles.
10. Modelos de computación: Máquinas de Estado Finito (MEF) con y sin salida, lenguajes y gramáticas, relaciones entre lenguajes y MEF, máquinas de Turing.

Bibliografía

• Libro de texto base: ROSEN K.H., "Matemática Discreta y sus Aplicaciones", 5ta edición, ISBN 9788448140731, editorial Mc Graw Hill, 2004.
• Libros de texto complementarios (en español):
  • JOHNSONBAUGH R., "Matemáticas Discretas", 6ta edición, ISBN 9789702606376, editorial Prentice Hall, 2005 (advertencia: esta edición en español contiene errores de tipeo y de traducción).
  • GRIMALDI R.P., "Matemáticas Discreta y Combinatoria", 3ra edición, ISBN 9789684443242, editorial: Pearson, 1997.
• Libros de consulta para temas puntuales y/o más avanzados (2 en español, los demás en inglés):
  • BECKER M.E., PIETROCOLA N., SANCHEZ C., "Notas de combinatoria", editorial Red Olímpica, Argentina, 1996.
  • NIVEN, "Matemática de las opciones, o cómo contar sin contar", editorial Red Olímpica, Argentina, 1995.
  • ALBERTSON M.O., HUTCHINSON J.P., "Discrete Mathematics with Algorithms", ISBN-10: 0471612782, ISBN-13: 978-0471612780, editorial: John Wiley and Sons, 1988.
  • ANDREESCU T., FENG Z., "A Path to Combinatorics for Undergraduates, counting strategies", editorial Birkhäuser, 2004.
  • DEAN N., "The Essence of Discrete Mathematics", ISBN-10: 0133459438, ISBN-13: 978-0133459432, editorial Prentice Hall, 1996.
  • LOVASZ L., PELIKAN J., VESZTERGOMBI K., "Discrete Mathematics. Elementary and Beyond", editorial Springer, 2003.
  • ROSEN K.,H., "Elementary Number Theory and its Applications", 4th edition, editorial Addison-Wesley, 2000.
  • TRUSS J.K., "Discrete Mathematics for Computer Scientists", 2nd edition, ISBN-10: 0201360616, ISBN-13: 978-0201360615, Adison-Wesley, 1991.

Modalidad de dictado

Se dictarán clases:

• Teóricas (4 hs semanales)
• Prácticas (4 hs semanales)
• De consulta (1 hs semanal)

Días y horarios

• Teoría (única comisión): Miércoles de 15 a 17 hs y Viernes de 16 a 18 hs, en el Aula 9.
• Prácticas. Los Martes y Jueves:
  • Comisión 1 (Gustavo RIOS y Lisandro DALCIN): de 8 a 10 hs en las aulas 2 (los Martes) y 1 (los Jueves).
  • Comisión 2 (Juan José GOMEZ BARROSO y Pablo Sebastián ROJAS FREDINI): de 10 a 12 hs en el Aula Magna.
  • Comisión 3 (Martín PUCHETA y Alejandro COSIMO): de 15 a 17 hs en el Aula Magna (los Martes) y a confirmar (los Jueves).
• Consultas: serán los viernes a las 14 hs en el CIMEC (para llegar ver plano en http://venus.ceride.gov.ar/twiki/bin/view/Cimec/CimecLocation). Recordar que se cancelará la consulta si no hay alumnos después de 15 min. de iniciado el horario. Opcional para los alumnos de FIQ: los viernes después de las 19 hs en el Dpto de Matemáticas de la FIQ.

Regímenes de regularidad y de promoción

La evaluación se realiza mediante 3 (tres) Parciales. Se calcula la Nota Final en función del promedio aritmético de los Parciales. La Regularidad se logra con una Nota Final mínima de 50/100 (cincuenta) puntos, con no-menos de 30/100 (treinta) puntos en cada uno de los Parciales. Lograrán Promoción Directa aquellos alumnos regulares que obtengan un Promedio Final mínimo de 75/100 (setenta y cinco) puntos, con no-menos de 50/100 (cincuenta) en cada uno de ellos. Se puede recuperar solamente un parcial pero el recuperatorio es Globalizador, que sirve tanto para alcanzar la promoción, la condición de alumno regular así como para levantar nota en caso de algún interesado. La nota del globalizador reemplazará la peor nota de los parciales sólo si fuera mayor. No puede usarse el globalizador para aquellos que tienen al menos un parcial con menos de 30/100 (treinta). Aquellos alumnos que no logren promoción directa, deberán rendir un examen final.

Utilidad de la asignatura

La asignatura es una base para otros temas y en el caso de la Ingeniería Informática, e.g. algoritmos y estructuras de datos, teoría de autómatas, lenguajes formales, compiladores, criptografía, sistemas operativos, etc. Por otra parte, como un ejemplo simple de la vida profesional del uso del concepto de árbol de expansión, a continuación transcribimos un párrafo extraído de la Guía de Inicio Rápido de un switch de internet ("Cisco Small Business'", serie SG 300-52 52-port Gigabit Managed Switch, modelo SMB- SRW2048-K9-AR):

"Tiempo de acceso excesivamente prolongado: debido a la lógica de detección del bucle del árbol de expansión estándar, al agregar nuevas conexiones, las interfases afectadas a las redes LAN pueden tardar entre 30 y 60 segundos en comenzar a funcionar."

Cronograma

A continuación se indican las secciones correspondientes al libro de texto base (Rosen K.H., "Matemática Discreta y sus Aplicaciones", 5ta edición, 2004), y las fechas de los parciales previstos:

• Semana 1 (del 12 de marzo): 1.1, 1.2.
• Semana 2 (del 19 de marzo): 1.3, 1.4, 1.5, 1.8.
• Semana 3 (del 26 de marzo): 1.6, 1.7, 3.2, 3.3.
• Semana 4 (del 2 de abril): 2.4, 2.5.
• Semana 5 (del 9 de abril). repaso, Parcial 1 (cap. 1, 2 y 3): Viernes 13 de Abril.
• Semana 6 (del 16 de abril): 3.4, 3.5, 4.1.
• Semana 7 (del 23 de abril): 4.2, 4.3, 4.4, 4.5.
• Semana 8 (del 30 de abril): 6.1, 6.2.
• Semana 9 (del 7 de mayo): 7.1, 7.3, 7.5, 7.6.
• Semana 10 (del 14 de mayo): repaso, Parcial 2 (cap. 3, 4, 6 y 7): Viernes 18 de Mayo.
• Semana 11 (del 21 de mayo): 8.1, 8.2, 8.3, 8.4.
• Semana 12 (del 28 de mayo): 8.5, 8.6.
• Semana 13 (del 4 de junio): 8.7, 8.8, 9.1, 9.3.
• Semana 14 (del 11 de junio): 9.4, 9.5.
• Semana 15 (del 18 de junio): Parcial 3 (cap. 8 y 9): Viernes 22 de junio; Globalizador (cap. 1-4, 5-9): Miércoles 27 de junio.

Ejercicios para las Prácticas

A continuación se indican las secciones y ejercicios correspondientes al libro de texto base (Rosen K.H., "Matemática Discreta y sus Aplicaciones", 5ta edición, 2004):

• Sec. 1.1 [lógica proposicional, pág. 14]: 1, 3, 5, 7, 9, 12, 13, 15, 16, 20, 21, 23, 25, 27, 29, 30, 33.

• Sec. 1.2 [proposiciones condicionales y equivalencias lógicas, pág. 24]: 1, 3-9, 11-17, 20, 22, 24, 26, 27, 29, 35.
• Sec. 1.3 [predicados y cuantificadores, pág. 36]: 1, 3, 5, 9, 11-16, 19, 23, 27, 29, 33, 34, 41, 43, 45, 47.
• Sec. 1.4 [cuantificadores anidados, pág. 47]: 1, 9, 15, 16 (a-d), 19, 21, 23, 25, 27, 28, 29, 31, 33, 37-43.
• Sec. 1.5 [métodos de demostración, pág. 67]: 11, 13, 15, 17, 18, 20, 21, 23, 27, 29, 31, 33, 36, 39, 40, 43, 55, 57, 73, 74.
• Sec. 1.6 [conjuntos, pág. 78]: 1, 3, 5, 7-11, 13-19, 22-25, 27, 28, 31.
• Sec. 1.7 [operaciones con conjuntos, pág. 87]: 3, 5-13, 15, 17, 20, 21, 23, 24, 26, 27, 29, 31, 40, 43.
• Sec. 1.8 [funciones, pág. 99]: 1, 3, 10-13, 15-17, 19, 23, 25, 26-31, 61.
• Sec. 2.4 [enteros y división, pág. 152]: 2-9, 11, 13, 19, 29, 31.
• Sec. 2.5 [enteros y algoritmos, pág. 165]: 1, 3, 5, 21.
• Sec. 3.3 [inducción matemática, pág. 236]: 1-4, 7-16, 19, 21, 25, 28, 42, 43, 45, 47.
• Sec. 3.4 [definiciones recursivas e inducción estructural, pág. 251]: 1, 3, 7, 9, 13, 20.
• Sec. 3.5 [algoritmos recursivos, pág. 263]: 1-5, 9, 21, 24.
• Sec. 4.1 [fundamentos de combinatoria, pág. 287]: 1, 3-5, 7-9, 11, 12, 15, 21, 25, 27, 29-33, 39, 40, 48, 50, 57.
• Sec. 4.2 [principios del palomar, pág. 295]: 1, 2, 3, 5, 7, 9, 10, 11, 13, 15, 18, 19, 24, 33, 35, 37.
• Sec. 4.3 [permutaciones y combinaciones, pág. 301]: 1, 3, 4, 5, 7, 9, 10, 11, 13, 15, 16, 19, 21, 23, 27, 30, 31, 33, 38, 39.
• Sec. 4.4 [coeficientes binomiales, pág. 309]: 1, 5, 9, 13, 15, 19, 21, 23, 25, 27, 29, 31, 32, 33-37.
• Sec. 4.5 [permutaciones y combinaciones generalizadas, pág. 317]: 1-3, 5, 7, 13-15, 20, 21, 23, 31, 33, 45, 47, 53-56.
• Sec. 6.1 [relaciones de recurrencia, pág. 380]: 1, 3, 5, 7, 9, 10, 13, 17, 23, 25, 37.
• Sec. 6.2 [resolución de relaciones de recurrencia, pág. 393]: 1, 3, 11, 21, 23, 25, 27, 29, 33, 35.
• Sec. 6.5 [principio de inclusión-exclusión (PIE), pág. 424]: 1, 3, 5, 7, 17, 19.
• Sec. 6.6 [aplicaciones del PIE, pág. 432]: 3, 4.
• Sec. 7.1 [relaciones y sus propiedades, pág. 447]: 1-8, 23-25, 28, 30, 40, 41, 42 (a,c,d,f), 43, 45 (a,b,e), 47, 48 (a,b,e), 49, 51. Nota: en relaciones sólo interesa las siguientes propiedades: reflexiva, simétrica, antisimétrica y transitiva, omitir las demás.
• Sec. 7.3 [representación de relaciones, pág. 461]: 1, 3, 5, 7, 11, 13, 14, 18, 22, 23, 25, 27, 31, 33 (hay 14).
• Sec. 7.4 [cierre de relaciones, pág. 472] 1, 3, 5, 7, 9, 12, 13.
• Sec. 7.5 [relaciones de equivalencia, pág. 478]: 1, 2, 5, 7, 10, 15, 17, 18, 20, 21, 29, 35, 42 (a-b), 43, 47.
• Sec. 7.6 [órdenes parciales, pág. 492]: 2, 3, 4, 5.
• Sec. 8.1 [introducción a grafos, pág. 509]: 3-10.
• Sec. 8.2 [terminología en teoría de grafos, pág. 519]: 1-5, 18, 19, 21, 24, 25, 27, 29, 30, 32, 33, 35, 36, 37, 39, 41.
• Sec. 8.3 [representaciones de grafos e isomorfismo de grafos, pág. 527]: 1, 2, 5, 6, 9, 11, 13, 15, 17, 23, 25, 35, 37, 39, 47-49, 57.
• Sec. 8.4 [conexión (en grafos), pág. 538]: 1, 3-6, 15, 18, 20, 37-39, 43.
• Sec. 8.5 [caminos eulerianos y hamiltonianos, pág. 550]: 1-6, 10, 26, 30-36, 45.
• Sec. 8.6 [caminos de longitud mínima (algoritmo de Dijkstra), pág. 562]: 2, 3, 6, 15, 16, 18.
• Sec. 8.7 [grafos planos, pág. 571]: 1-8, 13, 15, 17, 21, 23, 25.
• Sec. 9.1 [introducción a árboles, pág. 598]: 1-3, 5, 7, 9, 11, 13, 15, 17, 19, 25, 27, 39, 41, 45.
• Sec. 9.3 [recorridos en árboles, pág. 626]: 7-15.
• Sec. 9.4 [árbol generador, o de expansión, (algoritmos de búsqueda a lo ancho y en profundidad, pág. 638]: 1-4, 7-10, 13, 14, 16-18, 23-25.
• Sec. 9.5 [árbol generador mínimo (algoritmos de Prim y de Kruskal, pág. 645]: 1-3, 6, 7, 9.

Enunciados de parciales o exámenes finales tomados recientemente

(en formato PDF)

• tc-120413-p1-t1.pdf.
• tc-120413-p1-t2.pdf.
• tc-120301-ef.pdf.
• tc-111222-ef.pdf.
• tc-111212-ef.pdf.
• tc-110627-p4.pdf.
• tc-110623-p3-t2.pdf.
• tc-110623-p3-t1.pdf.
• tc-110523-p2-t2.pdf.
• tc-110523-p2-t1.pdf.
• tc-110418-p1-t2.pdf.
• tc-110418-p1-t1.pdf.
• tc-110217-ef.pdf.
• tc-100625-p3-t2.pdf.
• tc-100625-p3-t1.pdf.
• tc-100304-ef.pdf.
• tc-100218-ef.pdf.
• tc-091210-ef.pdf.
• tc-091217-ef.pdf.
• tc-091201-p3-t2.pdf.
• tc-091201-p3-t1.pdf.
• tc-091029-p2-t2.pdf.
• tc-091029-p2-t1.pdf.
• tc-090917-p1-t2.pdf.
• tc-090917-p1-t1.pdf.
• tc-120216-ef.pdf.

Programas demo

• esprimo.tgz: test para determinar si un entero positivo es primo.
• recursividad.tgz: algunos demos usando recursión.
• relaciones.tgz: algunos tests para relaciones.
• cuantificadores.tgz: algunos demos usando cuantificadores.

Lista de correo "Noti-TC"

Noti-TC es una lista de correo para enviar avisos a los alumnos sobre modificaciones en el material de la página y/o cuando las notas de una evaluación estén disponibles. Los alumnos deberán suscribirse a la lista de correo en http://venus.ceride.gov.ar/mailman/listinfo/noti-tc. Incluir Nombre(s) y Apellido tal como figura en Alumnado. Los alumnos deberán estar suscriptos durante el cursado de la materia. No se enviarán las notas de evaluaciones a los alumnos que no-estén suscriptos. También puede suscribirse cualquier persona que desee recibir notificaciones de los cambios en el material de la página. La lista NO es para enviar mensajes por parte de los suscriptores.

Para desuscribirse: en la parte inferior de la página de la lista están las instrucciones para desuscribirse.

Lista de discusión

http://groups.google.com/group/tcomp-fich-unl

Utilidades para navegar este sitio