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

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


[New]Novedades

[22-03-19, 10:05]
  • 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, (grios(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).

  • Horarios de consultas: en revisión ...

  • 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 desde el centro: micros 2 o 9. En el micro 2 verificar que entre a la Ciudad Universitaria (CU): es una condición suficiente de que "sirve" ese micro. Con el 9: basta que vaya al Pozo. En cualquier caso, bajarse en la parada siguiente a la CU, después que da toda la vuelta dentro de la misma. 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 un 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 12 de marzo): 1.1, 1.2.
  • Semana 2 (del 19 de marzo): 1.3, 1.4, 1.5.
  • Semana 3 (del 26 de marzo): 1.6, 1.7.
  • Semana 4 (del 02 de abril): 1.8, 3.3.
  • Semana 5 (del 09 de abril): 3.4, 7.1, 7.3.
  • Semana 6 (del 16 de abril): 7.5, 7.6, 2.4.
  • Semana 7 (del 23 de abril): 4.1, 4.2, Parcial 1 (todos los temas dados): Viernes 27 de Abril de 13 a 16 hs en el Aula 9.
  • Semana 8 (del 30 de abril): 4.3, 4.4.
  • Semana 9 (del 07 de mayo): 4.5, 6.1, 6.2.
  • Semana 10 (del 14 de mayo): 8.2, 8.3.
  • Semana 11 (del 21 de mayo): 8.4, 8.5, 8.6.
  • Semana 12 (del 28 de mayo): 8.7, 8.8, 9.1.
  • Semana 13 (del 04 de junio): 9.3, 9.4, 9.5.
  • Semana 14 (del 11 de junio): 11.2, 11.3.
  • Semana 15 (del 18 de junio): 11.1, 11.5, Parcial 2 (todos los temas dados): Viernes 22 de Junio de 13 a 16 hs en el Aula 9. Finalización del primer cuatrimestre: Sábado 23/06/18.
  • Semama 16 (del 25 de junio): Recuperatorio y CFI (1er grupo): Jueves 28 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.
  

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

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: r527 - 22 Mar 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