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

Novedades

[02-12-12, 11:45]. Torneo de Programación. Las Cátedras de las asignaturas "Teoría de la Computación" y "Algoritmos y Estructuras de Datos" están organizando un torneo de programación, orientado a hacer algoritmos eficientes sobre todo por el lado de usar los contenedores más apropiados y los tipos de algoritmos más eficientes, y conocer las complejidades algorítmicas de las diferentes operaciones. Tener en cuenta:

• La fecha a realizarse sería durante el comienzo del primer cuatrimestre (marzo aproximadamente). La idea es que sea en el momento en que los estudiantes tengan la mayor cantidad de tiempo posible.
• Pueden anotarse alumnos de II de la FICH o cualquier particular en general.
• El objetivo del concurso es desarrollar capacidades de programación en C++ con los contenedores de STL y obtener códigos eficientes, por el conocimiento de la complejidad algorítmica de las diferentes operaciones involucradas.
• La consigna se emite a través de la página web del curso. Se provee un código (en forma de una clase de C++) que permite al concursante autoevaluarse y verificar la performance de su propuesta.
• La submisión de las propuestas se hace en forma eléctronica. Tienen un cierto tiempo T (e.g. 1 o 2 días, a definir) para enviar la propuesta, a una cuenta de correo a especificar.
• La propuesta que gana es la que pasa todos los tests y de ellas la que da el menor tiempo.
• El test se compondría de unos primeros tests iniciales con contenedores pequeños, una vez pasados estos tests, se prueba con estructuras grandes, o muchas estructuras pequeñas. Los participantes tendrán acceso al código que genera las estructuras, de manera que pueden diseñar algoritmos apropiados para aprovechar alguna debilidad de los datos generados (si la existe).
• Tendremos categorías para un sólo proc (categoría Peso Liviano) y varios procs (con OPENMP, libpthread o similar) (categoría Peso Pesado). Los tests para Peso Pesado se correrán en servidores con 12 procs. (Interesados en programación con OPENMP pueden visitar nuestra página del curso de posgrado HPCMC, en especial estos slides de Ruud van der Pas. http://www.nic.uoregon.edu/iwomp2005/iwomp2005_tutorial_openmp_rvdp.pdf)
• Otros detalles, visitar http://www.cimec.org.ar/twiki/bin/view/AED/ChuckNorris

[10-08-11, 11:45]

• Están las notas del examen final del quinto turno, http://venus.ceride.gov.ar/~mstorti/notas4.cgi
• Los exámenes se mostrarán el próximo Viernes en el CIMEC a las 15 hs.

[25-07-11, 6:45] Consultas y muestra del examen final del 07-07-11: será mañana Martes 26-Julio en el CIMEC a las 15 hs.

[04-07-11, 07:05] Se subieron a la página los enunciados de los temas 1 y 2 en el parcial 3 y el del globalizador de este año.

[30-06-11, 16:10]

• Están las notas del globalizador y la situación final de cursado, http://venus.ceride.gov.ar/~mstorti/notas4.cgi
• Los globalizadores se mostrarán mañana Viernes en el CIMEC a las 14 hs. Se ruega puntualidad pues a las 15 hs hay recuperatorio de otra asignatura.
• ATENCIÓN: los alumnos que promocionaron deberán anotarse en alguna fecha de examen para que se les pase la nota. Por favor avisar por email antes.

[20-06-11, 21:20] Parcial3: será (mañana) Martes 21-Junio en el Aula Magna de 13 a 16 hs.

[15-06-11, 09:30] Temario de la teoría, siguiendo el texto ROSEN ("Matemática discretas y sus aplicaciones", 5ta edición, 2004):

• En el parcial3:
  • Sec. 8.1 [Intro a grafos, pp. 503]:
    • Tipos de grafos (pp. 503): def. 1-5;
    • Modelos con grafos (pp. 506): cultural;
  • Sec. 8.2 (Terminología en teoría de grafos (pp. 511):
    • Terminología básica (pp. 511): def. 1-4; teor. 1-3: enunciados y demostraciones. Errata de tipeo en el teor. 3: en lugar de la suma de las 2 sumatorias es la igualdad de ambas e iguales al número de aristas de un digrafo, ejemplos 1-3.
    • Familias distinguidas de grafos simples (pp. 513): ejemplos 4-7.
    • Grafos bipartitos (pp. 514): def. 5, ejemplo 8-11.
    • Algunas aplicaciones de tipos especiales de grafos (pp. 516): cultural.
    • Grafos definidos a partir de otros (pp. 518): def. 6-7, ejemplos 14-15.
  • Sec. 8.3 (Representaciones de grafos e isomorfismo de grafos, pp. 521]:
    • Representación de grafos (pp. 521): listas de adyacencia, ejemplos 1-2.
    • Matrices de adyacencia (pp. 521): def., propiedades, matriz rala (o poco densa), ejemplos 3-5,
    • Matrices de incidencia (pp. 523): def., ejemplos 6-7.
    • Isomorfismo de grafos (pp. 524): def. 1, observ., invariantes bajo isomorfismo de grafos simples, ejemplos 8-11.
  • Sec. 8.4 (Conexiones en grafos, pp. 531):
    • Caminos (pp. 531): def. 1-2, ejemplo1 1 . Ejemplos 2-4: cultural.
    • Conexión en grafos (o conexión en grafos no-dirigidos, pp. 532): def. 3; teor. 1: enunciado y demostración; def. y ejemplos de: componentes conexas, vértice de corte (o vértice de articulación), arista puente (o arista de corte); ejemplos 5-6 y 8; ejemplo 7: cultural.
    • Conexión en grafo dirigidos: def. 4-5, ejemplos 9-10. Ejemplos 11: cultural.
    • Caminos e isomorfismo (pp. 536): ejemplos 12-13.
    • Número de caminos entre 2 vértices: teor. 2: enunciado y demostración; ejemplo 14.
  • Sec. 8.5 (Caminos eulerianos y hamiltonianos, pp. 540):
    • Caminos y circuitos eulerianos (pp. 540): def. 1; teor. 1 (existencia de circuitos y caminos eulerianos): enunciado y demostración (que empieza en la pág. anterior 542); teor. 2; ejemplos 1-4; omitir algoritmo 1.
    • Caminos y circuitos hamiltonianos (pp. 545): def. 2; códigos de Gray; ejemplos 5-8; omitir teor. 3 y 4.
  • Sec. 8.6 (Caminos de longitud mínima (o algoritmo de Dijsktra), pp. 554):
    • Intro: def. grafo ponderado, longitud de un camino en un grafo ponderado; camino de longitud mínima en un grafo ponderado; ¿hay unicidad?
    • Algoritmo de Dijkstra: ampliado tanto para que al finalizar pueda reconstruir el camino hallado como para que sea apto en un grafo no-conexo (ayuda ¿cuándo el algoritmo puede detectar que se tiene un vértice de peso mínimo que este en otra componente conexa?), teor. 1-2 (sólo enunciados), ejemplo 1.
    • El Problema del Agente Viajero (PAV, pp. 560): descripción; ¿por qué es tan "duro" de resolver?
  • Sec. 8.7 (Grafos planos, pp. 564):
    • Intro (pp. 564): def. 1, ejemplos 1-3.
    • Fórmula de Euler (pp. 566): teor. 1, corolarios 1-3 (enunciados y demostración), ejemplos 4-6.
    • Teorema de Kuratowski (pp. 569): división elemental, grafos homeomorfos, enunciado, ejemplos 7-8.
  • Sec. 8.8 (Coloreado de grafos, pp. 573):
    • Intro: def. 1-2, teor. 1 (teor. de los 4 colores), ejemplos 1-4.
    • Aplicaciones del coloreado de grafos (pp. 577): ejmeplo 5. Cultural: ejemplos 6-7.
  • Sec. 9.1 (Intro a árboles):
    • Intro: def. 1-3, teor. 1, ejemplos 1-4.
    • Arboles como modelos (pp. 593): cultural.
    • Propiedades de los árboles (pp. 595): def. 2, teor. 3-5, corolario 1, ejemplos 9-11.
  • Sec. 9.2 (Aplicaciones de los árboles, pp. 601): cultural.
  • Sec. 9.3 (Recorridos de los árboles, pp. 615):
    • Sistema de etiquetado universal (pp. 615): receta, ejemplo 1.
    • Algoritmos de recorrido (pp. 616): def. 1-3, ejemplos 2-4.
    • Notación infija, prefija y posfija: ejemplos 5-10.
• Desde el Globalizador en adelante:
  • Sec. 9.4 (Arboles generadores, pp. 628):
    • Intro (pp. 628): def. 1, ejemplo 1, teor. 1: enunciado y demostración.
    • Búsqueda en profundidad (o de la vuelta atrás, retroceso, o backtracking, pp. 630): ejemplos 3 y 4.
    • Búsqueda a la Ancho (pp. 633): ejemplo 5.
    • Aplicaciones de la vuleta atrás (pp. 634): pág. 634.
    • Búsqueda en profundidad en digrafos (pp. 636): omitir.
  • Sec. 9.5 (Arboles generadores mínimos, pp. 641): def. 1, algoritmos de Prim y de Kruskal, ejemplos 1-3.

[09-06-11, 11:35] Muestra del Parcial 2: será mañana Viernes 10-Junio en el CIMEC. Tema 1: a las 14 hs. Tema 2: a ls 14:30 hs.

[08-06-11, 13:35] Están las notas del Parcial 2 http://venus.ceride.gov.ar/~mstorti/notas4.cgi

[04-06-11, 9:25] Algunas cuestiones de actualidad en LINUX en una nota a Linus TORVALDS por los 20 años http://www.pagina12.com.ar/diario/dialogos/21-169096-2011-05-30.html

[03-06-11, 13:50] Se subieron a la página los enunciados de los temas 1 y 2 en el parcial 3 del año pasado y en el parcial 2 de este año.

[03-06-11, 10:00] En la Sec. "Programas demos" de esta página (ver al final) se ha incluido el demo "relaciones" con los algoritmos: cierre_reflexivo, cierre_simetrico, cierre_transitivo, roywarshall, es_reflexiva, es_simetrica, es_antisimetrica, es_transitiva, es_relacion_de_equivalencia, y es_relacion_de_orden.

[26-05-11, 12:30]. Tres comentarios.

• Sobre el Doctorado en Ingeniería (DI). Se comenta que en la página de la radio LT10: http://www.lt10digital.com.ar/noticia/idnot/111763/maxima-acreditacion-para-seis-carreras-de-posgrado-de-unl.html, se informa que el DI de la UNL que se dicta en la FICH y en FIQ sigue siendo "A". También aparece lo mismo en la página de la UNL: http://www.unl.edu.ar/noticias/leer/8226/Maxima_acreditacion_para_seis_carreras_de_posgrado.html
• Sobre el área del círculo. En contraste con lo anterior, en la semana pasada se produjo un hecho curioso durante un parcial de la asignatura "Cálculo Numérico" (CNUM, obligatoria de 3er año). Resultó que algunos alumnos "insistieron" al JTP que se les facilitara la fórmula de cálculo del área de un círculo dado su radio, con argumentos tales como: "que no-lo vieron en la primaria/secundaria", "que no-era un tema que estaba siendo evaluado", etc.. Obviamente no-se facilitó semejante fórmula, entre otros motivos, porque era una de la matemática elemental y, en primer lugar, porque eran alumnos de ingeniería.
• Sobre el área de un triángulo. Además, en la asignatura "Mecánica del Continuo" (MC, obligatoria de 4to año, cursado 2010, se produjo otro hecho curioso: un alumno que pasó al pizarrón ignoraba fórmula alguna para el área de un triángulo.

[20-05-11, 13:06] En la Sec. "Programas demos" de esta página (ver al final) se ha incluido el demo "recursividad" con algunos algoritmos recursivos simples.

[09-05-11, 11:50]

• Fecha del Parcial-2:
  
  • Fecha: Lunes 23 de Mayo a las 18:00 hs en el Aula Magna (único horario para todas las comisiones de práctica);
  • Concurrir con libreta universitaria o documento (con foto) para acreditar identidad;
  • Presentarse 5' antes (17:55 hs).
• Muestra del Parcial 1: será el Viernes 13-Mayo en el CIMEC. Tema 1: a las 15 hs. Tema 2: a las 15:30 hs.
• Temario de la Teoría siguiendo el texto ROSEN ("Matemática discretas y sus aplicaciones", 5ta edición, 2004):
  • Sec. 3.3 [Inducción matemática, pág. 222]:
    • Inducción: enunciado, ejemplos 1-10, excluir ejemplos 11 y 12.
    • Inducción fuerte: enunciado, ejemplos 14-15, excluir ejemplo 13.
    • La propiedad del buen orden: excluir.
  • Sec. 3.4 [Definiciones recursivas e inducción estructural, pág. 239]:
    • Funciones definidas recursivamente: definición, ejemplos 1-4.
    • Números de Fibonacci: def. 1, ejemplos 5 y 6, excluir teor. 1 (teor. de Lamé).
    • Conjuntos y estructuras definidas recursivamente: def. 2-6, ejemplos 7-9, excluir ejemplos 10, 11.
    • Inducción estructural: enunciado; definición 7, teoema 2; excluir: ejemplos 13, 14 y "ejemplos de demostraciones que utilizan la inducción estructural".
    • Inducción generalizada: excluir.
  • Sec. 3.5 [Algortimos recursivos, pág. 255]: lo visto en la práctica.
  • Sec. 3.6 [Verificación de programas, pág. 264]: excluir.
  • Sec. 4.1 [Fundamentos de combinatoria, pág.279]:
    • Principios básicos de recuento: las reglas del producto y de la suma, ejemplos 1-6, 8-12, excluir ejemplo 7.
    • Problemas de recuento más complicados: omitir.
    • El principio de inclusión-exclusión: ejemplo 16.
    • Diagramas árbol: ejemplo 17-19.
  • Sec. 4.2 [Principios del palomar, pág. 290]:
    • Introducción: teor. 1, ejemplos 1-4.
    • El Principio del Palomar (PP) generalizado: teor. 2, ejemplos 5-9.
    • Algunas aplicaciones elegantes del PP: ejemplo 10, excluir ejemplos 11-12 y teor. 3.
  • Sec. 4.3 [Permutaciones y combinaciones, pág. 297]:
    • Permutaciones: teor. 1, ejemplos 1-5.
    • Combinaciones: teor. 2, coroloario 1, definición 1, ejemplos 6-11.
  • Sec. 4.4 [Coeficientes binomiales, pág. 303]:
    • El teorema del binomio: teor. 1, corolarios 1-3, ejemplos 1-4.
    • El triángulo y la identidad de Pascal: teor. 2-4, corolario 4.
  • Sec. 4.5 [Permutaciones y combinaciones generalizadas, pág. 311]:
    • Permutaciones con repetición: teor. 1, ejemplo 1.
    • Combinaciones con repetición: teor. 2, ejemplos 2-7, Tabla 1.
    • Permutaciones con objetos indistinguibles: teor. 3, ejemplo 8.
    • Distribuciones de objetos en cajas: teor. 4, ejemplo 9.
  • Sec. 4.6 [Generación de permutaciones y combinaciones, pág. 320]: excluir.
  • Cap. 5 [Probabilidad discreta]: excluir todo este capítulo.
  • Sec. 6.1 [Relaciones de Recurrencia (RR), pág. 373]:
    • Relaciones de recurrencia: def. 1, ejemplos 1-2.
    • Modelos con RR: ejemplos 3-8.
  • Sec. 6.2 [Resolución de las RR, pág. 384]:
    • Intro: def. 1, ejemplos 1-2.
    • Resolución de RR Lineales, Homogéneas y de Coeficientes Constantes (RRLHCC): teor. 1-4, ejemplos 3-8.
    • RRLNHCC: teor. 5, 6, ejemplos 9, 13.
  • Sec. 6.3 [Algoritmos de divide y vencerás, y RR, pág. 396]:excluir.
  • Sec. 6.4 [Funciones generatrices, pág. 405]: excluir.
  • Sec. 6.5 [Principio de Inclusión-Exclusión (PIE), pág. 420]. Ejemplos 1-5, teor. 1: sólo enunciado.
  • Sec. 6.6 [Aplicaciones del PIE, pág. 426].
    • Una forma alternativa del PIE: sólo el ejemplo 1.
    • Número de aplicaciones sobreyectivas: excluir hasta el final de esta Sección.
  • Sec. 7.1 [Relaciones, pág. 439]:
    • Relaciones y sus propiedades: def. 1, ejemplos 1-3.
    • Funciones como relaciones.
    • Relaciones en unconjunto: def. 2, ejemplos 4-6.
    • Propiedades de las relaciones: def. 3-6, ejemplos 7-16.
    • Combinaciones de relaciones: def. 6-7, teor. 1, ejemplos 17-22.
  • Sec. 7.2 [Relaciones n-arias y sus aplicaciones, pág. 449]:
    • Relaciones n-arias: def. 1, ejemplos 1-2.
    • Bases de datos y relaciones: excluir hasta el final de esta Sección.
  • Sec. 7.3 [Representación de relaciones, pág. 456]:
    • Representación de relaciones usando matrices: ejemplos 1-6.
    • Representación de relaciones usando digrafos (o grafos dirigidos): def. 1, ejemplos 7-10.
  • Sec. 7.4 [Cierre de relaciones, pág. 463]:
    • Cierres: ejemplos 1-2.
    • Caminos en grafos dirigidos: def. 1, teor. 1, ejemplo 3.
    • Cierres transitivos: def. 2, teor. 2-3, lema 1, ejemplos 4-7.
    • Algoritmo de Roy-Warshall: lema 2, ejemplo 8, algoritmo 2.
  • Sec. 7.5 [Relaciones de equivalencia, pág. 473]:
    • Relaciones de equivalencia: def. 1, ejemplos 1-4.
    • Clases de Equivalencia (CE): def. 2, ejemplos 5-6.
    • CE y particiones: teor. 1-2, ejemplos 7-9.
  • Sec. 7.6 [Ordenes parciales, pág. 481]: ordenes parciales: def. 1-3, ejemplos 1-6. Excluir desde la def. 4 hasta el final del capítulo.

[07-05-11, 11:10]

• Se subieron a la página los enunciados de los temas 1 y 2 del Parcial 1.
• Se corrigió una entrada errónea (>100%) en el nota del E4c de un alumno.

[06-05-11, 14:30] Están las notas del Parcial 1 http://venus.ceride.gov.ar/~mstorti/notas4.cgi

[29-04-11, 12:15] En la Sec. "Programas demos" de esta página (ver al final) se ha incluido un demo para el tema de algoritmos recursivos.

[14-04-11, 11:05] En la Sec. "Programas demos" de esta página (ver al final) se ha incluido un demo para el tema de cuantificadores simples y anidados en una implementación más básica.

[14-04-11, 07:35] El temario para el Parcial-1 es el ya indicado el [31-03-11, 09:40] excepto que la Sec. 3.3 (Inducción matemática, pág. 222) se reducirá a lo dado en la teoría mientras que la ejercitación se postergará al parcial 2.

[31-03-11, 09:40]

• Parcial-1:
  
  • Fecha: Lunes 18 de Abril a las 18:00 hs en el Aula Magna (único horario para todas las comisiones de práctica);
  • Concurrir con libreta universitaria o documento (con foto) para acreditar identidad;
  • Presentarse 5' antes (17:55 hs).
• Temario de la teoría siguiendo el texto ROSEN ("Matemática discretas y sus aplicaciones", 5ta edición, 2004):
  • Sec. 1.1 (Lógica, pág. 1):
    • Proposiciones: def. 1-4, tabla de verdad, conectivos lógicos;
    • Implicaciones: definiciones 5-6, ejemplos adicionales;
    • Recíproca, contrarecíproca e inversa;
    • Precedencia de operadores lógicos;
    • Traducción de frases del lenguaje natural;
    • Lógica y operaciones de bits;
    • Omitir: "juegos de lógica", "especificaciones del sistema" 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;
    • 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):
    • Formalización de sentencias con cuantificadores anidados: ejemplos 1-9.
    • Negaciones de cuantificadores anidados: ejemplos 11-12;
    • El orden de los cuantificadores anidados: ejemplos 14-16, tabla 1;
    • Pensando en los cuantificadores como bucles.
  • 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;
    • Teoremas y cuantificadores: demostraciones de existencia y de unicidad. Contraejemplos, ejemplos 28, 29, 30;
    • Errores en las demostraciones: ejemplos 31-35;
    • Omitir: ejemplos 26-27.
  • Sec. 1.6 (Conjuntos, pág. 71):
    • Intro: def. 1-6, teor. 1, ejemplos 1-10;
    • El conjunto de las partes de un conjunto (o conjunto potencia): 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: def. 9-10, ejemplos 14-18;
    • Gráfica de una función: def. 11;
    • Algunas funciones importantes: parte entera (piso) y parte entera por exceso (techo), ejemplos 21-25, tabla 1.
  • Sec. 2.2 (Crecimiento de funciones, pág. 120):
    • La notación O mayúscula: def. 1, ejemplos 1-3;
    • Algunos resultados importantes sobre la notación O: teor. 1, ejemplos 4-6;
    • Crecimiento de combinaciones de funciones: teor. 2-3, corolario 1, ejemplos 7-8;
    • Las notaciones omega y zeta: def. 2 y 3, teor. 4, ejemplos 9-12.
  • Sec. 2.4 (Enteros y división, pág. 140):
    • División: def. 1, teor. 1, corolario 1, ejemplos 1, 2;
    • Números primos: def. 2, teor. 2-4, ejemplos 3-6;
    • Infinitud del conjunto de números primos: teor. 4 (sólo enunciado);
    • Omitir: "La distribución de los números primos", ejemplo 7, teor. 5.
    • El algoritmo de la división: teor. 6, def. 3 (errata en el enunciado del teor. 6: es "d" en lugar de "b"), ejemplos 8, 9;
    • Máximo común divisor y mínimo común múltiplo: def. 4-7, ejemplos 10-15, teor. 7;
  • Sec. 2.5 (Enteros y división, pág. 155):
    • Representaciones de números enteros: teor. 1; conversiones de base, ejemplos 1-6, algoritmo 1. Algoritmo de Euclides. Omitir el resto.
    • Algoritmo de Euclides: intro, lema 1, ejemplo 12, algoritmo 6.
  • Sec. 3.2 (Sucesiones y sumatorias, pág. 210).
    • Sucesiones: def. 1-3, ejemplos 1-4.
    • Sucesiones especiales de enteros: ejemplos 5-8.
    • Sumatorias: teor. 1, ejemplos 9-15, tabla 2;
    • Omitir: "Cardinal".
  • Sec. 3.3 (Inducción matemática, pág. 222):
    • Inducción: enunciado, notación simbólica, paso base y paso de inducción;
    • Inducción fuerte: enunciado, notación simbólica, paso base y paso de inducción;
    • Ejemplos de demostraciones por inducción: ejemplos 1-10, 15;
    • Omitir: "La propiedad del buen orden" y los ejemplos 11-14.

• 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
• Ejemplo: mención del tema "árbol de expansión" en un manual de switch

Teoría de la Computación

• Carreras: Ingeniería Informática, Analista en Informática Aplicada
• Extension: Cuatrimestral
• Carga horaria: 105 hs de clases (45 hs teoría / 60 hs práctica)
• Página : http://www.cimec.org.ar/tcomp
• Docentes:
  • Jorge D'ELIA, (jdelia(at)intec(dot)unl(dot)edu(dot)ar)
  • Lisandro DALCIN, (dalcinl(at)intec(dot)unl(dot)edu(dot)ar)
  • Pablo KLER, (pkler(at)intec(dot)unl(dot)edu(dot)ar)
  • Martín PUCHETA, (mpucheta(at)intec(dot)unl(dot)edu(dot)ar)
  • Gustavo RIOS, (grios(at)ceride(dot)gov(dot)ar)
  • Juan José GOMEZ BARROSO (jgomezb)(at)intec(dot)unl(dot)edu(dot)ar)
  • Alejandro COSIMO (acosimo)(at)intec(dot)unl(dot)edu(dot)ar)
    donde (at)=@, (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, sucesiones, sumatorias.
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 de consulta o complementarios:
  • JOHNSONBAUGH R., "Matemáticas Discretas", 6ta edición, ISBN 9789702606376, editorial Prentice Hall, 2005.
  • GRIMALDI R.P., "Matemáticas Discreta y Combinatoria", 3ra edición, ISBN 9789684443242, editorial: Pearson, 1997.
  • ALBERTSON M.O., HUTCHINSON J.P., "Discrete Mathematics with Algorithms", ISBN-10: 0471612782, ISBN-13: 978-0471612780, editorial: John Wiley and Sons, 1988.
  • TRUSS J.K., "Discrete Mathematics for Computer Scientists", 2nd edition, ISBN-10: 0201360616, ISBN-13: 978-0201360615, Adison-Wesley, 1991.
  • 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.
  • ANDREESCU T., FENG Z., "A Path to Combinatorics for Undergraduates, counting strategies", editorial Birkhäuser, 2004
  • NIVEN, "Matemática de las opciones, o cómo contar sin contar", editorial Red Olímpica, Argentina, 1995.
  • BECKER M.E., PIETROCOLA N., SANCHEZ C., "Notas de combinatoria", editorial Red Olímpica, Argentina, 1996. ROSEN K.,H., "Elementary Number Theory and its Applications", 4th edition, editorial Addison-Wesley, 2000.

Modalidad de dictado

Se dictarán clases:

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

Días y horarios

• Teoría: Miércoles y Viernes de 17 a 19 hs en el Aula 9.
  
• Prácticas. Los Martes y Jueves:
  • Comisión 1: de 8 a 10 hs, Aula 1 (los Martes) y Aula Magna (los Jueves).
  • Comisión 2: de 9 a 11 hs, Aula 2 (los Martes) y Aula 9 (los Jueves).
  • Comisión 3: de 17:30 a 19:30 hs, Martes en Laboratorio 3, Jueves en el Aula de Dibujo.
• Consultas: serán los viernes a las 15 hs en el CIMEC (para llegar ver plano en http://venus.ceride.gov.ar/twiki/bin/view/Cimec/CimecLocation). Recordar que se cancelará la consulta si no hay alumnos después de 15 min. de iniciado el horario.

Regímenes de regularidad y de promoción

La evaluación se realiza mediante 3 (tres) Parciales. Se calcula la Nota Final en función del promedio aritmético de los Parciales. La Regularidad se logra con una Nota Final mínima de 50/100 (cincuenta) puntos, con no-menos de 30/100 (treinta) puntos en cada uno de los Parciales. Lograrán Promoción Directa aquellos alumnos regulares que obtengan un Promedio Final mínimo de 75/100 (setenta y cinco) puntos, con no-menos de 50/100 (cincuenta) en cada uno de ellos. Se puede recuperar solamente un parcial pero el recuperatorio es Globalizador, que sirve tanto para alcanzar la promoción, la condición de alumno regular así como para levantar nota en caso de algún interesado. La nota del globalizador reemplazará la peor nota de los parciales sólo si fuera mayor. No puede usarse el globalizador para aquellos que tienen al menos un parcial con menos de 30/100 (treinta). Aquellos alumnos que no logren promoción directa, deberán rendir un examen final.

Ejemplo: mención del tema "árbol de expansión" en un manual de switch

Párrafo extraído de la Guía de Inicio Rápido del switch marca "Cisco Small Business" de la 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 interfaces afectadas o las redes LAN pueden tardar entre 30 y 60 segundos en comenzar a funcionar."

Cronograma

Se indican las secciones correspondientes al libro de texto base, y las fechas de los parciales previstos:

• Semana 1 (del 14 de marzo): 1.1, 1.2.
• Semana 2 (del 21 de marzo): 1.3, 1.4.
• Semana 3 (del 28 de marzo): 1.5, 1.6, 1.7, 1.8.
• Semana 4 (del 4 de abril): 2.2, 2.4, 2.5, 3.2.
• Semana 5 (del 11 de abril). 3.3, 3.4, 3.5.
• Semana 6 (del 18 de abril): 4.1. Parcial-1 (cap. 1, 2, 3): Lunes 18 de abril.
• Semana 7 (del 25 de abril): 4.2, 4.3, 4.4, 4.5.
• Semana 8 (del 2 de mayo): 6.1, 6.2, 6.5, 6.6.
• Semana 9 (del 9 de mayo): 7.1, 7.3, 7.4. 7.5.
• Semana 10 (del 16 de mayo): 7.6, 8.1, 8.2.
• Semana 11 (del 23 de mayo): 8.3, 8.4. Parcial-2 (cap. 4, 5, 6, 7): Lunes 23 de mayo.
• Semana 12 (del 30 de mayo): 8.5, 8.6, 8.7, 8.9.
• Semana 13 (del 6 de junio): 9.3, 9.4, 9.5, 11.1.
• Semana 14 (del 13 de junio): 11.2, 11.3, 11.4, 11.5.
• Semana 15 (del 20 de junio): Parcial-3 (cap. 8, 9 y 11): Martes 21 de junio, Globalizador (cap. 1-9 y 11): Viernes 24 de junio.

Ejercicios para las Prácticas

• Sec. 1.1 [lógica proposicional, pág. 14]: 1, 3, 5, 7, 9, 12, 13, 15, 16, 20, 21, 22, 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, 27, 29, 35.
• Sec. 1.3 [predicados y cuantificadores, pág. 36]: 1, 3, 5, 7, 10, 11-17, 19, 23, 27, 29, 31, 33, 34, 41, 43, 45, 46, 47.
• Sec. 1.4 [cuantificadores anidados, pág. 47]: 1, 3, 5, 7, 9, 12, 15, 16 (a-d), 17, 19, 21, 23, 25, 27, 28, 29, 31, 33, 37-43.
• Sec. 1.5 [métodos de demostración, pág. 67]: 11, 13, 15, 17, 18, 20, 21, 23, 25, 27, 29, 31, 33, 36, 39, 40, 41, 43, 45, 53, 55, 57, 73, 74.
• Sec. 1.6 [conjuntos, pág. 78]: 1-3, 5, 7-11, 13-19, 22-28, 31.
• Sec. 1.7 [operaciones con conjuntos, pág. 87]: 3, 5-13, 15, 17, 20, 21, 23, 24, 26, 27, 29, 31, 37, 40, 43, 44.
• Sec. 1.8 [funciones, pág. 99]: 1-3, 10-13, 15-17, 19, 21, 23, 25, 26-33, 61, 64.
• Sec. 2.2 [crecimiento de funciones, pág. 130]: 2, 3, 5, 9, 15, 19, 23, 25, 30, 31, 45, 47.
• Sec. 2.4 [enteros y división, pág. 152]: 1-9, 11, 13, 19, 29, 31.
• Sec. 2.5 [enteros y algoritmos, pág. 165]: 1, 3, 5, 21.
• Sec. 3.2 [sucesiones y sumatorias, pág. 219]: 1, 3, 9, 13, 15, 17, 27-30.
• Sec. 3.3 [inducción matemática, pág. 236]: 1-4, 7-16, 19, 21, 25, 28, 29, 42, 43, 45, 47, 48.
• Sec. 3.4 [definiciones recursivas e inducción estructural, pág. 251]: 1, 3, 7, 9, 13, 20.
• Sec. 3.5 [algoritmos recursivos, pág. 263]: 1-5, 9, 21, 24.
• Sec. 4.1 [fundamentos de combinatoria, pág. 287]: 1, 3-5, 7-12, 15, 21, 25, 27, 29-33, 39, 40, 48, 50, 57.
• Sec. 4.2 [principios del palomar, pág. 295]: 1, 2, 3, 5, 7, 9, 10, 11, 13, 15, 17, 18, 19, 24, 32, 33, 35, 37.
• Sec. 4.3 [permutaciones y combinaciones, pág. 301]: 1, 3-5, 7, 9, 10, 11, 13, 15, 16, 19, 21, 23, 27, 30, 31, 33, 38, 39.
• Sec. 4.4 [coeficientes binomiales, pág. 309]: 1, 5, 7, 13, 15, 19, 21, 23, 25, 27, 29, 31, 32-37.
• Sec. 4.5 [permutaciones y combinaciones generalizadas, pág. 317]: 1-3, 5, 7, 9, 11, 13-15, 20, 21, 23, 31, 33, 39, 45, 47, 53-56.
• Sec. 6.1 [relaciones de recurrencia, pág. 380]: 1, 3, 5, 7, 9, 10, 13, 17, 23, 25, 37, 46.
• Sec. 6.2 [resolución de relaciones de recurrencia, pág. 393]: 1, 3, 11, 21, 23, 25, 27, 28, 29, 30, 33, 35.
• Sec. 6.5 [principio de inclusión-exclusión (PIE), pág. 424]: 1, 3, 5, 7, 17, 19.
• Sec. 6.6 [aplicaciones del PIE, pág. 432]: 1, 3, 4.
• Sec. 7.1 [relaciones y sus propiedades, pág. 447]: 1-8, 23-25, 28, 30, 40, 41, 42 (a,c,d,f), 43, 45 (a,b,e), 47, 48 (a,b,e), 49, 51. Nota: en relaciones sólo interesa las siguientes propiedades: reflexiva, simétrica, antisimétrica y transitiva, omitir las demás.
• Sec. 7.3 [representación de relaciones, pág. 461]: 1, 3, 5, 7, 11, 13, 14, 18, 22, 23, 25, 27, 31, 33.
• Sec. 7.4 [cierre de relaciones, pág. 472]: 1, 3, 5, 7, 12, 13, 25.
• Sec. 7.5 [relaciones de equivalencia, pág. 478]: 1, 2, 5, 7, 10, 15, 17-21, 29, 35, 42 (a-b), 43, 47.
• Sec. 7.6 [órdenes parciales, pág. 492]: 2-5.
• Sec. 8.1 [introducción a grafos, pág. 509]: 3-10.
• Sec. 8.2 [terminología en teoría de grafos, pág. 519]: 1-5, 18, 19, 21, 24, 25, 27, 29, 30, 32, 33, 35, 36, 37, 39, 41.
• Sec. 8.3 [representaciones de grafos e isomorfismo de grafos, pág. 527]: 1, 2, 5, 6, 9, 11, 13, 15, 17, 23, 25, 35, 37, 39, 47-49, 54, 55, 57.
• Sec. 8.4 [conexión (en grafos), pág. 538]: 1, 3-6, 15, 18, 20, 37-39, 43.
• Sec. 8.5 [caminos eulerianos y hamiltonianos, pág. 550]: 1-6, 10, 26, 30-33, 34-36, 45.
• Sec. 8.6 [caminos de longitud mínima (algoritmo de Dijkstra), pág. 562]: 2, 3, 6, 15, 16, 18.
• Sec. 8.7 [grafos planos, pág. 571]: 1-8, 13, 15, 17, 21, 23, 25.
• Sec. 9.1 [introducción a árboles, pág. 598]: 1-3, 5, 7, 9, 11, 13, 15, 17, 19, 25, 27, 39, 41, 45.
• Sec. 9.3 [recorridos en árboles, pág. 626]: 7-19, 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-4, 7-10, 13, 14, 16-18, 23-25.
• Sec. 9.5 [árbol generador mínimo (algoritmos de Prim y de Kruskal, pág. 645]: 1-3, 6, 7, 9.
• Sec. 11.1 [lenguajes y gramáticas, pág. 697]: 1, 3, 5, 9, 17, 21.
• Sec. 11.2 [máquinas de estado finito (MEF) con salida, pág. 705]: 1, 2, 3, 5, 9, 11.
• Sec. 11.3 [MEF sin salida, pág. 712]: 1, 13, 15, 17, 19, 23, 25, 27.
• Sec. 11.4 [reconocimiento de lenguajes, pág. 721]: 1, 3, 7, 9.
• Sec. 11.5 [máquinas de Turing, pág. 721]: 1, 3, 5, 7, 9, 11.

Enunciados de parciales o exámenes finales tomados recientemente

(en formato PDF)

• tc-110627-p4.pdf.
• tc-110623-p3-t2.pdf.
• tc-110623-p3-t1.pdf.
• tc-110523-p2-t2.pdf.
• tc-110523-p2-t1.pdf.
• tc-110418-p1-t2.pdf.
• tc-110418-p1-t1.pdf.
• tc-110217-ef.pdf.
• tc-100625-p3-t2.pdf.
• tc-100625-p3-t1.pdf.
• tc-100304-ef.pdf.
• tc-100218-ef.pdf.
• tc-091210-ef.pdf.
• tc-091217-ef.pdf.
• tc-091201-p3-t2.pdf.
• tc-091201-p3-t1.pdf.
• tc-091029-p2-t2.pdf.
• tc-091029-p2-t1.pdf.
• tc-090917-p1-t2.pdf.
• tc-090917-p1-t1.pdf.

Programas demo

• relaciones.tgz: algunos tests para relaciones.
• recursividad.tgz: algunos demos usando recursión.
• cuantificadores.tgz: algunos tests usando cuantificadores.

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

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

Lista de discusión

http://groups.google.com/group/tcomp-fich-unl

Utilidades para navegar este sitio