You are here: TWiki> Cimec Web>TeoriaDeLaComputacion (2017-03-16, JorgeDElia)

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


[New]Novedades

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 (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)intec(dot)unl(dot)edu(dot)ar)
    • Gustavo RIOS RODRIGUEZ, (grios(at)ceride(dot)gov(dot)ar)
    • Juan José GOMEZ BARROSO, (jgomezb)(at)intec(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)=.

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.

Modalidad de dictado

Se dictarán clases:

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

Días y horarios

  • Teoría (única comisión): Miércoles y Viernes de 14 a 16 hs en el Aula 9. Nota: tiene que asistir ambos días .
  • Prácticas. Los Martes y Jueves en las 3 comisiones ( Nota: la primera clase será teórico-práctica por lo que deberá asistir ):
    • Comisión 1 (Gustavo RIOS RODRIGUEZ y Juan José GOMEZ BARROSO): de 8 a 10 hs, los Martes en el Aula 2, y los Jueves en el Aula 1;
    • Comisión 2 (Juan José GOMEZ BARROSO): de 10 a 12 hs, los Martes en el Aula 2, y los Jueves en el Aula 1.
    • Comisión 3 (Juan Marcelo GIMENEZ y Sergio YAPUR): de 15 a 17 hs, los Martes en el Aula Magna, y los Jueves en el Aula 7.
  • Consultas:
    • Martes en la mañana: de 12 a 13 hs en Aula 2 (Juan Jose Gomez Barroso). Martes en la tarde: desde las 17hs (Juan Marcelo Gimenez, y Sergio Yapur) en aula a confirmar;
    • Jueves en la mañana: de 10 a 11 hs en Aula 5 (Gustavo Rios Rodriguez). Jueves en la tarde: desde las 17hs (Sergio Yapur, Juan Marcelo Gimenez) en aula a confirmar.

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 la teoría y de 80% (ochenta por ciento) a la 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 la teoría como a la práctica;
    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.

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. Dos ejemplos simples: (i) se emplea la base octal, vista en el tema 3, cuando se modifican los permisos de los archivos en los sistemas Linux/UNIX mediante el comando chmod (en caso de usarlo con argumentos numéricos); (ii) 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."

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

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]: 5, 7, 12, 13, 15, 16, 20, 21, 25, 30, 33.
  • Sec. 1.2 [proposiciones condicionales y equivalencias lógicas, pág. 24]: 1, 5, 13, 22, 24, 26, 27, 29, 35.
  • Sec. 1.3 [predicados y cuantificadores, pág. 36]: 1, 3, 5, 9, 11, 16, 17, 19, 23, 29, 33, 41, 43, 45.
  • Sec. 1.4 [cuantificadores anidados, pág. 47]: 1, 5, 9, 16 (a-d), 19, 21, 23, 25, 27, 29, 31.
  • Sec. 1.5 [métodos de demostración, pág. 67]: 11, 13, 15, 17, 18, 20, 21, 23, 29, 33, 36, 40, 43, 45, 53, 55, 74.
  • Sec. 1.6 [conjuntos, pág. 78]: 1-3, 5, 7, 11, 13, 18, 22, 24, 25, 27, 31.
  • Sec. 1.7 [operaciones con conjuntos, pág. 87]: 3, 10, 12, 15, 17, 21, 26, 27, 29, 31, 40.
  • Sec. 1.8 [funciones, pág. 99]: 1, 3, 12, 13, 15, 17, 19, 23, 25, 31.
  • Sec. 2.4 [enteros y división, pág. 152]: 1, 2, 5, 9, 11, 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, 2, 7, 13, 21, 25, 28, 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, 15, 19, 27, 31, 38.
  • Sec. 4.4 [coeficientes binomiales, pág. 309]: 1, 7, 19, 21, 23, 25, 31, 32, 33.
  • 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 la teoría.
  • 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.

Documentos (en formato electrónico PDF):

Programas demo

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(s) 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. El sistema mostrará las notas de los parciales únicamente a los alumnos registrados en dicha lista. La registración involucra tres pasos:

  1. En esa página hay que completar datos, por lo menos Nombre(s) y Apellido(s) tal como figura en Alumnado y una dirección de email que funcione normalmente, esto es, que no esté no-bloqueado por buzón lleno u otros motivos;
  2. Después de solicitar la registración, en forma automática les llegará un email a la casilla que pusieron cuando llenaron la solicitud en donde se pide confirmar la solicitud (para descartar robos de identidad), por lo que deberán responder en forma positiva al pedido.
  3. Recién cuando el sistema reciba esa confirmación, el sistema enviará un email a los administradores para autorizar la registración.

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

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: r475 - 2017-03-16 - 12:36:21 - JorgeDElia
 

TWIKI.NET
This site is powered by the TWiki collaboration platformCopyright � by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback