You are here: Foswiki>Main/Cimec Web>TeoriaDeLaComputacion (07 May 2021, JorgeDElia)Edit Attach

Universidad Nacional del Litoral (UNL)

Teoría de la Computación (TCOMP) [Facultad de Ingeniería y Ciencias Hídricas (FICH)]

Matemática Discreta (MAD) [Facultad de Ingeniería Química (FIQ)]


[New]Novedades

  • [06-05-2021, 09:37] Nueva actualización de:
    • Guía de Ejercicios (GE): en las Sec. 1.3 y 3.3. se mejoró la presentación de algunos ejercicios, en la Sec. 2.4 se completó el desarrollo de los ejercicios, y se corrigieron erratas de tipeo en la Sec. 1.7.
    • Notas teóricas: correciones de erratas en las Sec. 4.1, 4.2, y 4.3.
  • [04-05-2021, 08:30] La clase de práctica en la Comisión 1 (C1) [Rolando YERA MORENO y Gustavo Ríos Rodríguez] de hoy Martes a las 10 hs queda cancelada. Opcionalmente pueden sumarse a la clase de la C2 a la tarde de 16-18 hs.
  • [20-04-2021, 17:42] Nueva actualización de: * Guía de Ejercicios (GE): en la Sec. 1.7 tiene una nueva explicación de la demostración de E12b, en la Sec. 3.3. se re-escribieron los ejercicios 7 y 13, y se corrigieron erratas de tipeo en las Sec. 1.6, 1.7 y 1.8. * Notas teóricas: en la Sec. 3.3 (inducción) se uniformizó la presentación y notación con la dada en la GE.
  • [21-04-2021, 17:47] Nueva actualización de las notas teóricas: se corrigieron erratas de tipeo o se mejoró la presentación (e.g. Sec. 1.7: re-escritura de los métodos para probar la igualdad de dos conjuntos, Sec. 3.3: PIM segundo ejemplo, errata detectada en la clase de hoy, etc.).
  • [20-04-2021, 09:28] Nueva versión de la GE donde se corrigieron erratas de tipeo en Sec. 1.6, 1.7 y 1.8, y con una nueva explicación de la demostración de E12b de la Sec 1.7.
  • [14-04-2021, 17:15] En http://e-fich.unl.edu.ar y en http://www.cimec.org.ar/tcomp hay una nueva versión de la Guía de Ejercicios (GE), donde se expandió en detalle la demostración del ejercicio 43 de la Sec. 1.3 del libro de texto de ROSEN.
  • [13-04-2021, 15:02] En la GE había una errata en la respuesta del ejercicio 12g de la Sec. 1.3 ya que, por hacer copy-paste con el inciso de arriba, había quedado verdadero y en realidad es falso. La versión corregida tiene fecha 13 Abril 2021.
Vejedades (novedades que ya no son)

Contenidos...

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

Intro

  • Carreras en FICH: Ingeniería Informática (IINF), Analista en Informática Aplicada (AIA)
  • Carrera en FIQ: Ingeniería Industrial (IIND)
  • Extension: Cuatrimestral
  • Carga horaria: 105 hs (39 hs teóricas + 54 hs prácticas + 12 hs evaluaciones)
  • 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 Pablo VIDOCEVICH [a designar]
    • Rolando YERA MORENO [a designar]
    • XY [a designar]
donde (at)=@, y (dot)=.

Días y horarios 2021 (en construcción):

  • Inicio de cursado 2021. El inicio del 1er cuatrimestre para 2do año en adelante en la FICH será el 05/04/21, por lo que el cursado de TCOMP empezará el Martes 06 de abril de 2021.
  • Clases Teóricas-prácticas (4 hs semanales) [única comisión] (Nota: (i) asistir desde la primera clase; (ii) cursar ambos días) serán:
    • Miércoles de 14 a 16 hs, por plataforma virtual a definir, y
    • Jueves de 14 a 16 hs, por plataforma virtual a definir.
  • Clases Prácticas (4 hs semanales) [2 comisiones] (Nota: (i) asistir desde la primera clase; (ii) cursar ambos días) :
    • Comisión 1 (C1) [Rolando YERA MORENO y Johan SARACHE]:
      • Martes y Jueves de 10 a 12 hs, por plataforma virtual a definir.
    • Comisión 2 (C2) [Gustavo RIOS RODRIGUEZ y Juan Pablo VIDOCEVICH]:
      • Martes y Jueves de 16 a 18 hs, por plataforma virtual a definir.
    • De consulta (1 h semanal). Horarios de consultas: a continuación de cada clase.
  • Otra info:

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á un recuperatorio de cada parcial teórico-práctico 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, 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.
  • Examen final en tiempos de pandemia: será en modalidad virtual. La estructura del examen consiste en dos partes, una parte escrita y otra parte oral. La parte escrita es lo primero a desarrollar, y es de naturaleza teórico-práctico con más énfasis en la GTP. La parte oral es reminiscente al CFI con más énfasis en los temas teóricos.

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 2021

En construcción.

Ejercicios para las Prácticas (en construcción++)

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ácticas (y se toman).
  • 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 clase teórico-práctica (y se toma).
  • 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.

Documentos (en formato electrónico PDF):

  • Notas complementarias de las clases teóricas actualizado al 06-05-2021:
tcomp-notas-20210506.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.

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

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: r626 - 07 May 2021, 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