Universidad Nacional de Santiago del Estero
Facultad de Ciencias Exactas y Tecnologías
 
ga
Novedades X
Descarga de Cuadernillo de Actividades Prácticas .
Descarga de Diapositivas de Clase. Unidad N 1.

Clases de Teoría: Miércoles Hora: 09:00 a 11:00 hs
Clases de Práctica: Jueves Hora: 17:00 a 19:00 hs
Clases de Consultas: Lunes Hora: 18:00 a 20:00 hs
INICIO
CÁTEDRA
TEORÍA

Programa Analítico

Descarga la planifiación de la asignatura en formato PDF (Acrobat Reader) haciendo clic aquí. Si no tienes Acrobat Reader, haz clic aquí para ir a la pagina de Adobe y descargar el Software
  1. TEORÍA DE LA COMPUTABILIDAD
    (i) PROBLEMA. Concepto. Formalización y Solución. Procedimientos y algoritmos.
    (ii) CONCEPTOS FUNDAMENTALES DE LA TEORÍA: Función computable. Gödelización.
    (iii) COMPLEJIDAD Y EFICIENCIA DE ALGORITMOS: Teoría de la Complejidad Computacional. Análisis de algoritmos. Determinación del orden de un algoritmo.
    Dominación asintótica. Orden de un algoritmo O(p(n)) y O(cn). Principios y consideraciones para la determinación del orden. Análisis de algoritmos no recursivos y
    recursivos.
    (iv) CLASIFICACIÓN DE PROBLEMAS: Problemas demostrablemente insolubles, demostrablemente difíciles. Clase P, Clase NP, NP completa y CO-NP.


  2. TEORÍA DE LENGUAJES FORMALES
    ( i ) CONCEPTOS BÁSICOS: Símbolo, alfabeto, palabra, subhilera. Operaciones con lenguajes: unión, intersección, concatenación. Propiedades de las operaciones.
    ( ii ) GRAMÁTICAS FORMALES: definición , tipos de gramáticas. Jerarquía de Chomsky.
    Gramáticas no restringidas, contextuales, incontextuales y regulares (tipo 3). Lenguajes
    generados por cada tipo de gramáticas.
    ( iii ) CARACTERÍSTICAS DE LAS GRAMÁTICAS: Recursividad en las gramáticas conextuales. Gramáticas libres de contexto: árbol de derivación. Derivaciones a izquierda y a derecha. La ambigüedad. Gramáticas propias.
    ( iv ) GRAMÁTICAS REGULARES. Expresiones regulares. Propiedades y equivalencias.
    Obtención de una gramática regular a partir de una expresión regular.


  3. TEORÍA DE AUTÓMATAS
    ( i ) AUTÓMATAS FINITOS: Definición y representación gráfica. El autómata finito como
    reconocedor de lenguajes. Autómata finito determinista y no determinista. Equivalencia. Minimización de autómatas finitos deterministas.
    ( ii ) AUTÓMATAS FINITOS Y EXPRESIONES REGULARES. Método de ecuaciones para la
    obtención de un autómata finito. Autómatas finitos con movimientos lambda.
    Equivalencia entre los autómatas finitos y las expresiones regulares. Método para
    construir autómata finito a partir de una expresión regular.
    ( iii ) AUTÓMATA DE PILA: Definición formal. Autómata de pila como reconocedor de un
    lenguaje. Autómata a pila determinístico y no determinístico.
    ( iv ) MÁQUINAS DE TURING: Definición formal. Representación. Interpretaciones de las
    computaciones. Configuración de una máquina de Turing. Máquina de Turing multicinta.
    Máquina universal de Turing. Codificación de una máquina de Turing. La insolubilidad
    del problema de la parada.


  4. DISEÑO DE COMPILADORES
    ( i) TIPO DE TRADUCTORES: Ensambladores, compiladores e intérpretes. Características de cada uno. Comparación. Análisis y síntesis de la compilación Herramientas para la
    construcción de compiladores.
    ( ii ) ANÁLISIS LÉXICO: Componentes léxico, patrones y lexemas. Especificación y
    reconocimiento de tokens. Definiciones regulares. Diagrama de transición.
    (iii)ANÁLISIS SINTÁCTICO: Métodos descendentes y ascendentes. Manejo de errores
    sintácticos. Estrategia. Analizador sintáctico descendente: gramáticas LL(k), por
    descenso recursivo, analizador sintáctico predictivo y analizador sintáctico predictivo no recursivo. Gramáticas LR(k). Implantación de un analizador sintáctico ascendente
    mediante poda. Analizador sintáctico por precedencia de operadores. Analizadores
    Sintácticos LR. Métodos para analizador sintáctico LR.
    ( iv ) ANÁLISIS SEMÁNTICO: Traducción dirigida por la sintaxis. Definición dirigida por la
    sintaxis. Reglas semánticas. Árbol sintáctico para expresiones. Grafos dirigidos acíclicos
    para expresiones (GDA). Esquema de traducción. Acciones semánticas. Notación
    postfija. Comprobación de tipos.
    ( v ) GENERACIÓN DE CÓDIGO: generación de código Intermedio distinto tipo de
    representaciones. Optimización de Código Intermedio. Generación de Código Objeto.