You are here: Foswiki>Main/Cimec Web>TeoriaDeLaComputacion (26 Jul 2022, JorgeDElia)Edit Attach

Universidad Nacional del Litoral (UNL)

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

[New]Novedades

Vejedades (novedades que ya no son)

Contenidos...

  • Intro
  • Días, horarios, y fechas de las evaluaciones en 2022
  • Regímenes de regularidad y de promoción
  • Programa
  • Bibliografía
  • Ejercicios para las prácticas
  • Material de estudio
  • Programas demo
  • Listas de correo e-fich y noti-tc
  • Utilidad de la asignatura

Intro

  • Carreras en FICH: Ingeniería Informática (IINF), Analista en Informática Aplicada (AIA)
  • 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, (jpvido(at)gmail(dot)com)
    • Ignacio SANCHEZ [a designar]
donde (at)=@, y (dot)=.

Días, horarios, y fechas de las evaluaciones en 2022:

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

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.

Material de estudio (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.

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

Edit  | Attach | Print version | History: r647 < r646 < r645 < r644 | Backlinks | View wiki text | Edit wiki text | More topic actions
Topic revision: r647 - 26 Jul 2022, 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