You are here: Foswiki>Main/Cimec Web>TeoriaDeLaComputacion (13 Sep 2019, JorgeDElia)Edit Attach

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


[New]Novedades

[11-09-19, 13:02]. Próxima consulta/muestra de exámenes antes del EF: será mañana Jueves 12/11/2019:
  • A las 12 hs en el CIMEC, con Jorge D'Elia;
  • A las 19 hs después de la clase de AED de Juan Gimenez.

[09-09-19, 18:28]. Sobre el próximo Examen Final (EF) y toma del Coloquio Final Integrador (CFI):
  • Debido a superposición de clases y exámenes, el EF y el CFI se postergan al día siguiente, i.e. próximo Viernes 13/09/2019 desde las 14 hs en la FICH en aula a determinar por Bedelía.
  • Esperar frente a Bedelía de FICH.
  • Próximas consultas o muestra de exámenes pasados: consultar para concertar.

[31-07-19, 11:55, actualizado 12:20].
  • Sobre el horario del próximo Examen Final (EF): será el Jueves 8 de Agosto pero desde las 14 hs en la FICH. Esperar frente a Bedelía.
  • Sobre la toma del CFI: se indicó antes en clases que, por omisión, los CFI se tomarán en las fechas y horarios de los exámenes finales. Entonces, por ejemplo, el próximo CFI se tomará durante el EF del Jueves 8 de Agosto desde las 14 hs en la FICH. Esperar frente a Bedelía.

[31-07-19, 11:55]. Próximas consultas antes del EF del Jueves 8 de Agosto:
  • Viernes 2 de Agosto: de 14 a 15 hs en el CIMEC (Gustavo Rios, Jorge D'Elia);
  • Lunes 5 de Agosto: de 15 a 16 hs en el CIMEC (Sergio Yapur).
[26-06-19, 11:55] Toma del Coloquio Final Integrador (CFI): cambio de lugar. El CFI para finalizar la promoción se tomará en el CIMEC desde las 15 hs. Por otra parte, los recuperatorios se tomarán sin cambios de aula, hora, o temario.

[25-06-19, 16:55] Recuperatorios del P1 y/o P2, toma del Coloquio Final Integrador (CFI), o alumnos de FIQ que deban el P2:
  • Fecha: Jueves 27 Junio;
  • Lugar: Aula Magna Puerta Este en planta baja detrás de la cantina del edificio FICH (donde antes fueron las clases de práctica de la Comisión 3);
  • Temario: el temario de cada recuperatorio es SIN cambios;
  • Toma de los recuperatorios del P1 y/o del P2: a las 12 hs. Todo alumno que cursó puede presentarse a rendir, ya sea que recupere el P1, o el P2, o ambos P1 y P2;
  • Toma del CFI: a las 15 hs (tienen que presentarse para finalizar la promoción);
  • Alumnos de FIQ que no-pudieron rendir por superposición de parciales: también presentarse a rendir a las 12 hs.

[24-06-19, 17:55] Notas, muestra, y consultas:
  • Están las notas del Parcial 2 junto con un detalle de los incisos, y la situación actual de cursado. Ver en https://cimec.org.ar/~mstorti/notas4.cgi
  • Consultas y/o muestra del Parcial 2: Martes 25 de Junio en el CIMEC a las 15 hs.

[21-06-19, 09:20] Sobre la toma del Parcial 2: será hoy Viernes 21 de Junio de 14 a 17 hs en el Aula 7 del Aulario. Instrucciones:
  • Concurrir con Libreta Universitaria o algún documento (con foto) para acreditar identidad.
  • Quienes puedan presentarse 15' antes (13:45 hs).
  • Tener presente las recomendaciones de cómo presentar un parcial/examen escrito dadas en un documento en formato PDF disponible en esta página (como-presentar-un-examen.pdf).
  • Temarios de la práctica y de la teoría: todo lo indicado en clases y lo ya indicado en la página de TCOMP.

[19-06-19, 10:20] Temario práctica parcial 2 corregido: el siguiente listado hace referencia a los temas que no serán evaluados como parte de la práctica en el parcial 2.
  • Sec. 2.1 [Algoritmos, pág. 109]: Completa.
  • Sec. 2.2 [Crecimiento de funciones, pág. 120]: Completa.
  • Sec. 2.3 [Complejidad de algoritmos, pág. 132]: Completa.
  • Sec. 2.4 [Enteros y división, pág.140]:
    • Aplicaciones de las congruencias: funciones de dispersión, números pseudoaleatorios.
    • Criptología: cifrado de César.
  • Sec. 2.5 [Enteros y algoritmos, pág. 155]:
    • Representación de números enteros.
    • Algoritmos para operaciones con enteros.
    • Exponenciación modular.
  • Sec. 2.6 [Aplicaciones de la teoría de números, pág. 167]: Completa.
  • Sec. 2.7 [Matrices, pág. 181]: Completa.
  • Sec. 4.1 [Introducción a conteo]: Diagramas en árbol.
  • Sec. 6.1 [Introducción a Relaciones de Recurrencia (RR)].
  • Sec. 6.2 [Solución de RRHLCC de 2do orden].
  • Sec. 7.4 [Cierre de relaciones]: Cierre transitivo.
  • Sec. 8.7 [Nociones de grafos planos]: Completa.
  • Sec. 8.8 [Nociones de coloreado de grafos]: Completa.

[31-05-19, 07:32]
  • Sobre el temario de las teóricas en el Parcial 2:
    • Sec. 2.1 [Algoritmos, pág. 109]: omitir toda la sección.
    • Sec. 2.2 [Crecimiento de funciones, pág. 120]: omitir toda la sección.
    • Sec. 2.3 [Complejidad de algoritmos, pág. 132]: omitir toda la sección.
    • Sec. 2.4 [Enteros y división, pág.140]:
      • División: def. 1, teor. 1, y corolario 1 (enunciados y demostraciones), ejemplos 1-2.
      • Números primos y compuestos: def. 2, enunciados de los teor. 2-5.
      • El algoritmo de la división: enunciado del teor. 6, def. 3, ejemplos 8-9.
      • Máximo común divisor y del mínimo común múltiplo: def. 4-7, demostración del teor. 7 (verla en el texto de Johnsonbaugh).
      • Aritmética modular: def. 8, enunciados de los teor. 8-10,
      • Aplicaciones de las congruencias: funciones de dispersión, números pseudoaleatorios.
      • Criptología: cifrado de César.
    • Sec. 2.5 [Enteros y algoritmos, pág. 155]:
      • Representación de números enteros: teor. 1, ejemplos 1-6.
      • Algoritmos para operaciones con enteros: omitir.
      • Exponenciación modular: omitir.
      • El algoritmo de Euclides: enunciado y demostración, ejemplo 12, y algoritmo 6.
    • Sec. 2.6 [Aplicaciones de la teoría de números, pág. 167]:
      • Algunos resultados útiles: enunciado del teorema 1. Lema 1 (hay un error de tipeo en la demostración: en la oración "Como a|c y a|tbc", cambiar por "Como a|sac y a|tbc"]. Lema 2. Teorema 2: enunciado y demsotración. Congruencias lineales: teorema 3, enunciado y demostración. Ejemplos 3 y 4.
      • Teorema chino del resto: omitir.
      • Aritmética computacional con números grandes: omitir.
      • Pseudoprimos: omitir.
      • Criptografía de clave pública, cifrado y descifrado RSA: incluir.
      • RSA como sistema de clave pública: lectura.
    • Sec. 2.7 [Matrices, pág. 181]: omitir toda la sección.
    • Sec. 4.1 [introducción a conteo]: la regla del producto (o principio de la multiplicación), y regla de la suma (o principio de la suma), uso del Principio de Inclusión-Exclusión (PIE) en conteo, diagramas en árbol.
    • Sec. 4.2 [Principios del Palomar (PP)]: teoremas 1-2, y ejemplos.
    • Sec. 4.3 [permutaciones y combinaciones]: definiciones, propiedades, teoremas, y ejemplos.
    • Sec. 4.4 [coeficientes binomiales]: teorema del binomio, corolarios 1-3 (enunciados y demostración). Triángulo y la identidad de Pascal: incluir teoremas 2-3 y coroloario 4, pero omitir teorema 4.
    • Sec. 4.5 [permutaciones y combinaciones generalizadas]: definiciones, propiedades, teoremas, y ejemplos.
    • Sec. 6.1 [intro a Relaciones de Recurrencia (RR)]: definiciones, clasificación exhaustiva.;
    • Sec. 6.2 [solución de las RRHLCC de 2do orden]: enunciados de los 2 teoremas, y ejemplos.
    • Sec. 7.3 [representaciones de las relaciones].
    • Sec. 7.5 [relaciones de equivalencia]: definiciones, propiedades, teoremas.
    • Sec. 7.5 [relaciones de orden parcial y total]: definiciones, propiedades.
    • Sec. 8.1 [intro a grafos]: definiciones;
    • Sec. 8.2 [terminología en grafos]: definiciones, ejemplos;
    • Sec. 8.3 [representaciones de grafos, y nociones de isomorfismo en grafos];
    • Sec. 8.4 [conexión en grafos]: definiciones, propiedades, teoremas, ejemplos;
    • Sec. 8.5 [circuitos y caminos eulerianos y hamiltonianos]: toda la sección;
    • Sec. 8.6 [algoritmo de Dijkstra]: incluir modificación para grafos con más de una componente conexa;
    • Sec. 8.7 [nociones de grafos planos]: definición, ejemplos;
    • Sec. 8.8 [nociones de coloreado de grafos]: definición, ejemplos;
    • Sec. 9.1 [intro a arboles]: terminología en árboles, ejemplos;
    • Sec. 9.3 [recorridos en árboles]: recorridos pre-orden, post-orden, y entre-orden;
    • Sec. 9.4 [árbol de expansión]: definición, propiedades, búsqueda a lo ancho y en profundidad;
    • Sec. 9.5 [árbol de expansión mínimo]: definición, propiedades, algoritmos de Prim y de Kruskal.
  • Muestra del parcial 1: hoy viernes desde las 13 hs en el aula 7 del Aulario.

[20-05-19, 16:09] Están las notas del Parcial 1 junto con un detalle de los incisos en https://cimec.org.ar/~mstorti/notas4.cgi La muestra del parcial 1 será anunciada en un ulterior mensaje.

[19-04-19, 09:37] Sobre la toma del Parcial 1:
  • Fecha: Viernes 26 de Abril de 14 a 17 hs en el Aula 7 del Aulario. Instrucciones:
    • Concurrir con Libreta Universitaria o algún documento (con foto) para acreditar identidad.
    • Quienes puedan presentarse 15' antes (13:45 hs).
    • Tener presente las recomendaciones de cómo presentar un parcial/examen escrito dadas en un documento en formato PDF disponible en esta página (como-presentar-un-examen.pdf).
    • Temario de la práctica: desde la Sec. 1.1 (Lógica) hasta la Sec. 3.3 (Principio de Inducción Matemática) excepto: Sec. 1.8 (funciones), y el Capítulo 2, que se postergan al Parcial 2.
    • Temario de la teoría: todo lo indicado en clases aunque a continuación se lista un temario detallado:
      • Sec. 1.1 [Lógica, pág. 1]. Proposiciones: def. 1-4, tabla de verdad, conectivos lógicos (not, and, or, xor). 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. Negación de cuantificadores (o Leyes de De Morgan generalizadas). 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.
      • 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. Leer la introducción a los apartados: teoremas y cuantificadores (demostraciones de existencia y de unicidad), y Errores en las demostraciones. Incluir los ejemplos 31-32 pero omitir los ejemplos 26-30.
      • 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. Funciones inversas y composición de funciones (pp. 94), def. 9-10, ejemplos 14-18. Algunas funciones importantes: funciones piso y techo (def. 12), tabla 1, ejemplos 21-25.
      • Cap. 2: se posterga al parcial 2.
      • Sec. 3.1 [Estrategias de demostración, pág. 199]: lectura.
      • Sec. 3.2 [Sucesiones y sumatorias, pág. 210]: lectura.
      • Sec. 3.3 [Principio de Inducción Matemática (PIM), 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.
      • Sec. 3.4 [Definiciones recursivas e inducción estructural, pág. 239]: funciones definidas recursivamente: def. 1, ejemplos 1-5, omitir el ejemplo 6 y el teor. 1. Omitir: "conjuntos y estructuras definidas recursivamente", "inducción estructural", e "inducción generalizada".
      • Sec. 7.1 [Relaciones y sus propiedades, pág. 439]: definición de relación binaria. Funciones como relaciones. Relaciones en un conjunto. Definiciones de relación reflexiva, relación simétrica, y relación antisimétrica.

[09-04-19, 11:50] Debido a algunas consultas recibidas: se confirma que en la presente semana (del 08 al 13 de Abril) no se dictarán clases en la FICH en todas las asignaturas desde 2do año en adelante tanto teóricas como prácticas. En consecuencia, en toda la presente semana NO habrá clases de ningún tipo en la asignatura TCOMP.

[22-03-19, 10:05] Varios:
  • Las clases teóricas de los Viernes migran al Aula 7 del 3er piso del Edificio CUBO en el horario de 14-16 hs.
  • Se actualizó la página electrónica de tcomp con el listado de ejercicios de la GTP a la fecha.
  • Idem para las listas de correo: (i) e-fich para los alumnos de FICH, y (ii) noti-tc (para los alumnos de FIQ).

Vejedades (novedades que ya no son)

Contenidos...

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

Teoría de la Computación

  • Carreras: Ingeniería Informática (II), Analista en Informática Aplicada (AIA)
  • Extension: Cuatrimestral
  • Carga horaria: 105 hs de clases (45 hs teoría / 60 hs práctica)
  • Página electrónica: http://www.cimec.org.ar/tcomp
  • Docentes:
    • Jorge D'ELIA, (jdelia(at)cimec(dot)unl(dot)edu(dot)ar)
    • Gustavo RIOS RODRIGUEZ, (gusadrr(at)santafe-conicet(dot)gob(dot)ar)
    • Juan José GOMEZ BARROSO, (jgomezb)(at)cimec(dot)unl(dot)edu(dot)ar)
    • Juan Marcelo GIMENEZ, (jmarcelogimenez)(at)gmail(dot)com)
    • Sergio YAPUR, (sergio(dot)yapur(at)gmail(dot)com)

donde (at)=@, y (dot)=.

Modalidad de dictado

Se dictarán clases:
  • Teóricas-prácticas (4 hs semanales)
  • Prácticas (4 hs semanales)
  • De consulta (1 h semanal)

Días y horarios

  • Teórico-prácticas (única comisión): Miércoles y Viernes de 14 a 16 hs. Los Miércoles en el Aula 9 (3er piso, edificio FICH). Los Viernes en el Aula 7 (edificio Cubo) (Nota: se debe asistir desde la primera clase).
  • Prácticas. Los Martes y Jueves en las 3 comisiones (Nota: se debe asistir desde la primera clase) :
  • Horarios de consultas: a continuación de cada clase.
  • Instrucciones para llegar al CIMEC:
    • El CIMEC es un instituto de doble dependencia (UNL-CONICET) cuyo edificio está ubicado dentro del Predio CONICET Santa Fe.
    • Para llegar a pie desde la Ciudad Universitaria: caminar hacia la Facultad de Medicina y continuar por una vereda de hormigón (al norte de ese edificio) unos 50 metros para llegar a un alambrado con un portal de ingreso de color blanco. Al atravesar la puerta de hoja doble tendrán a la vista el Instituto INCAPE. Entonces, continuar hacia la izquierda siempre sobre la calle hormigonada (i.e. caminando hacia el Oeste, ver plano en https://cimec.org.ar/foswiki/Main/Cimec/CimecLocation) hasta llegar al CIMEC. Tocar timbre.
    • Para llegar en micro desde el centro: líneas 2 o 9. En el micro 2 verificar que entre a la Ciudad Universitaria (CU). Con el micro 9 basta que vaya al Pozo. En cualquier caso, bajarse en la parada siguiente a la CU, después que dé toda la vuelta dentro de la CU. Dicha parada coincide con una dársena de giro e ingreso al Predio. Entonces: cuidado al cruzar la calle. Una vez en la entrada del Predio: dirigirse al personal de vigilancia, indicar que vienen a vernos en el edificio CIMEC y, en todo caso, que le expliquen cómo llegar. Ver plano en https://cimec.org.ar/foswiki/Main/Cimec/CimecLocation

Regímenes de regularidad y de promoción

  • Para Regularizar deberá cumplir con 2 (dos) condiciones:
    1. Lograr una asistencia mínima de 50% (cincuenta por ciento) a las clases teórico-prácticas y de 80% (ochenta por ciento) a las clases de práctica;
    2. Obtener al menos 40% (cuarenta por ciento) de nota en cada uno de los 2 (dos) parciales teóricos-prácticos, y que incluirá una componente de concepto de participación en clase a evaluarse en clases de práctica;
  • Para Promocionar deberá cumplir con 3 (tres) condiciones:
    1. Lograr una asistencia mínima del 80% (ochenta por ciento) tanto a las clases teórico-prácticas como a las clases prácticas;
    2. Obtener un promedio de 70% (setenta por ciento) con al menos 60% (sesenta por ciento) en cada uno de 2 (dos) parciales teórico-prácticos, y que incluirá una componente de concepto de participación en clase a evaluarse en clases de práctica;
    3. Obtener un promedio de 70% (setenta por ciento) entre las 2 (dos) evaluaciones y el Coloquio Final Integrador (CFI), con al menos 60% (sesenta por ciento) en cada uno.
  • Recuperatorio: habrá 1 (un) único recuperatorio del parcial teórico-práctico con menor nota para intentar, o bien regularizar, o bien promocionar, y la reemplazará sólo si resultara una nota mayor.
  • Coloquio Final Integrador (CFI):
    1. El CFI se tomará en forma oral o por escrito según la cantidad de alumnos, y será posible rendirlo HASTA el segundo turno de examen posterior a la finalización del cursado de la asignatura en coincidencia con los llamados a examen final;
    2. La inscripción al CFI en el SIU GUARANI será exclusivamente en la modalidad "PP" (Promoción Pendiente);
    3. En caso de no aprobar el CFI podrá presentarse nuevamente sólo una vez más y dentro del plazo indicado en el punto (1). En caso contrario quedará como alumno regular.

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.
  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.

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 11 de marzo): 1.1, 1.2.
  • Semana 2 (del 18 de marzo): 1.3, 1.4, 1.5.
  • Semana 3 (del 25 de marzo): 1.6, 1.7.
  • Semana 4 (del 01 de abril): 1.8, 3.3.
  • Semana 5 (del 08 de abril): 3.4, 7.1, 7.3.
  • Semana 6 (del 15 de abril): 7.5, 7.6, 2.4.
  • Semana 7 (del 22 de abril): 4.1, 4.2, Parcial 1 (todos los temas dados): Viernes 26 de Abril de 13 a 16 hs en el Aula 9.
  • Semana 8 (del 29 de abril): 4.3, 4.4.
  • Semana 9 (del 06 de mayo): 4.5, 6.1, 6.2.
  • Semana 10 (del 13 de mayo): 8.2, 8.3.
  • Semana 11 (del 20 de mayo): 8.4, 8.5, 8.6.
  • Semana 12 (del 27 de mayo): 8.7, 8.8, 9.1.
  • Semana 13 (del 03 de junio): 9.3, 9.4, 9.5.
  • Semana 14 (del 10 de junio): 11.2, 11.3.
  • Semana 15 (del 17 de junio): 11.1, 11.5, Parcial 2 (todos los temas dados): Viernes 21 de Junio de 13 a 16 hs en el Aula 9. Finalización del primer cuatrimestre: Sábado 22/06/2019.
  • Semama 16 (del 24 de junio): Recuperatorio y CFI (1er grupo): Jueves 27 de Junio.

Ejercicios para las Prácticas

A continuación se listan 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-29, 35, 51.
  • Sec. 1.3 [predicados y cuantificadores, pág. 36]: 1, 3, 5, 7, 9, 10, 11-17, 19, 23, 27, 29, 31, 33, 34, 41-43, 45, 47.
  • Sec. 1.4 [cuantificadores anidados, pág. 47]: 1, 5, 9, 12, 15, 16 (a-d), 19, 21, 23, 25, 27-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, 40, 41, 43, 45, 53, 55, 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-31, 33, 61.
  • Sec. 2.4 [enteros y división, pág. 152]: 1, 2, 5, 9, 11, 19, 29, 31, 53, 54.
  • 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-10, 12-17, 20, 21, 25, 28, 29, 42, 43, 45-47.
  • Sec. 3.4 [definiciones recursivas e inducción estructural, pág. 251]: 3, 7, 9, 13, 20.
  • Sec. 4.1 [fundamentos de combinatoria, pág. 287]: 1, 3, 8, 11, 12, 15, 27, 29, 33, 39, 40, 48.
  • Sec. 4.2 [principios del palomar, pág. 295]: 2, 3, 5, 7, 9, 10, 11, 13, 19, 24, 32, 35.
  • Sec. 4.3 [permutaciones y combinaciones, pág. 301]: 1, 3, 4, 5a, 7a, 9, 10, 11, 13, 15, 16, 19, 21, 27, 30, 31, 38.
  • Sec. 4.4 [coeficientes binomiales, pág. 309]: 1, 7, 19, 21, 23, 25, 31, 32, 33, 39 (foto de boda).
  • Sec. 4.5 [permutaciones y combinaciones generalizadas, pág. 317]: 1, 7, 9, 11, 15, 20, 31, 33, 45, 47. Los ejercicios 53-56 se ven en las clases teórica-práctica de los miércoles y viernes.
  • Sec. 6.1 [relaciones de recurrencia, pág. 380]: 3, 5, 9, 17, 23, 25, 37.
  • Sec. 6.2 [resolución de relaciones de recurrencia, pág. 393]: 1, 3, 7, 11, 21, 23, 25, 27, 35.
  • Sec. 6.5 [principio de inclusión-exclusión (PIE), pág. 424]: 3, 5, 7, 17.
  • Sec. 6.6 [aplicaciones del PIE, pág. 432]: 3, 4.
  • Sec. 7.1 [relaciones y sus propiedades, pág. 447]: 1, 6, 8, 23, 24, 28, 41, 42 (a,c,d,f), 45 (a,b,e), 48 (a,b,e), 49, 51. Nota 1: en relaciones sólo interesa las siguientes propiedades: reflexiva, simétrica, antisimétrica y transitiva, omitir las demás. Nota 2: el ejercicio 45 se dará en la teoría.
  • Sec. 7.3 [representación de relaciones, pág. 461]: 1, 7, 11, 12, 18, 22, 27, 31.
  • Sec. 7.4 [cierre de relaciones, pág. 472]: 1, 3, 5, 12, 13.
  • Sec. 7.5 [relaciones de equivalencia, pág. 478]: 1, 5, 10, 18, 20, 29, 35, 42 (a-b), 43.
  • Sec. 7.6 [órdenes parciales, pág. 492]: 2-5.
  • Sec. 8.1 [introducción a grafos, pág. 509]: 4, 5, 7, 8.
  • Sec. 8.2 [terminología en teoría de grafos, pág. 519]: 2, 5, 18, 21, 24, 25, 32, 33, 41.
  • Sec. 8.3 [representaciones de grafos e isomorfismo de grafos, pág. 527]: 2, 6, 9, 11, 15, 25, 39, 47, 48, 49.
  • Sec. 8.4 [conexión (en grafos), pág. 538]: 2, 4, 6, 15, 20, 38, 39, 42, 45.
  • Sec. 8.5 [caminos eulerianos y hamiltonianos, pág. 550]: 4, 5, 26, 31, 32, 38, 39, 45.
  • Sec. 8.6 [caminos de longitud mínima (algoritmo de Dijkstra), pág. 562]: 2, 3, 5, 6, 16, 18.
  • Sec. 8.7 [grafos planos, pág. 571]: 3, 5, 8, 13, 21, 23, 25.
  • Sec. 9.1 [introducción a árboles, pág. 598]: 1, 3, 5, 7, 9, 11, 15, 17, 19.
  • Sec. 9.3 [recorridos en árboles, pág. 626]: 9, 12, 15, 17, 23, 25.
  • Sec. 9.4 [árbol generador, o de expansión, (algoritmos de búsqueda a lo ancho y en profundidad, pág. 638]: 1, 3, 7, 13, 16, 23, 25.
  • Sec. 9.5 [árbol generador mínimo (algoritmos de Prim y de Kruskal, pág. 645]: 1, 3, 7, 9.
  • Sec. 11.1 [lenguajes y gramáticas]: ejemplos 1, 3, 5, 9, 17, 21.
  • Sec. 11.2 [Máquinas de Estado Finito (MEF) con salida]: ejemplos 1, 2, 3, 5, 9, 11.
  • Sec. 11.3 [MEF sin salida]: ejemplos 1, 13, 15, 17, 19, 23, 25, 27.
  • Sec. 11.4 [Reconocimiento de lenguajes]: 1, 3, 7, 9.
  • Sec. 11.5 [Máquinas de Turing]: 1, 3, 5, 7, 9, 11.

Utilidad de la asignatura

La asignatura es una base para otros temas y, en el caso de la Ingeniería Informática, por ejemplo, en algoritmos y estructuras de datos, teoría de autómatas, lenguajes formales, compiladores, criptografía, sistemas operativos, etc. Tres ejemplos simples: (i) el sistema criptográfico de clave pública RSA de amplio uso, tanto para cifrar como para firmar digitalmente, y cuya seguridad se basa en el problema de la factorización de números enteros; (ii) el uso de la base octal para modificar los permisos de los archivos en los sistemas GNU/Linux mediante el comando chmod en la variante de ingreso con argumentos numéricos; y (iii) el concepto de árbol de expansión visto en el tema 9 aparece aplicado en el siguiente párrafo extraído de la "Guía de Inicio Rápido" de un switch de internet (concretamente, un "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."

Documentos (en formato electrónico PDF):

Programas demo

Listas de correo e-fich y noti-tc

Las listas de correro e-fich (http://e-fich.unl.edu.ar/) y noti-tc (https://cimec.org.ar/mailman/listinfo/noti-tc) son dos listas electrónicas para enviar avisos a los alumnos de cuando las notas de los parciales o exámenes estén disponibles, o para notificar modificaciones de días u horarios de las clases, o en el material de la página. Tener en cuenta que NO se publicarán ni se enviarán por email notas de evaluaciones a los alumnos que no-estén suscriptos. Las notas publicadas incluirán un desglose de las mismas. Los alumnos de FICH deberán suscribirse a la lista de correo e-fich, mientras que los alumnos de FIQ lo harán en la lista noti-tc. En cualquier caso, incluir Nombre(s) y Apellido(s) tal como figura en Alumnado para así poder mapearlos con los listados de Alumnado. Los alumnos deberán estar suscriptos hasta que aprueben la asignatura. 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.
  1. Registración en efich: seguir la usual del Entorno Virtual de los alumnos de FICH;
  2. Registración en noti-tc: seguir el enlace que los llevará a una página en donde tienen que completar algunos datos, por lo menos: Nombre(s) y Apellido(s) tal como figura en Alumnado, y una dirección de email que funcione (e.g. que no esté no-bloqueado por buzón lleno u otros motivos). Después de solicitar la registración en forma automática llegará un email a la casilla informada indicando si confirman la solicitud de registración.) Una vez que hayan respondido tendrán que esperar hasta que los administradores de esa lista autoricen la registración. Para desuscribirse, seguir el instructivo dado en la parte inferior de la página de registración.

Utilidades para navegar este sitio

  • WebSearch: Servicio de Busqueda para el TC-Wiki
  • (Mas opciones en WebSearch)
  • WebChanges: Cambios efectuados recientemente al TC-Wiki
  • WebIndex: Mostrar todos los topicos del TC-Wiki en orden alfabetico
  • WebNotify: Suscribirse para ser notificado en forma automática de cambios recientes en el TC-Wiki
  • WebStatistics: Estadisticas del TC-Wiki

Topic revision: r553 - 13 Sep 2019, JorgeDElia
This site is powered by FoswikiCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding Foswiki? Send feedback