Kozen Teoría de la computación

Dexter Kozen , profesor en el Departamento de Ciencias de la Computación en la Universidad de Cornell , es el autor de " Teoría de la computación " ( 2006 ) , que es un libro de texto de ciencias de la computación de pregrado. El libro está organizado como un conjunto de conferencias y termina con una serie de ejercicios de tarea y sus soluciones. Teoría de la computación

La teoría de la computación es una especialidad dentro de la informática que se enfoca en el desarrollo de modelos , tanto lógicos y matemáticos , haciendo abstracción de las preocupaciones sobre los límites del hardware y de memoria.

la teoría se derivaba de trabajo en las áreas fundamentales de las matemáticas del siglo 20 por figuras como Kurt Gödel y Alan Turing . Según Richard L. Epstein y Walter A. Carnielli en su libro, " computabilidad " (1989 ) , los trata a la teoría de las computadoras resultantes como "métodos para empujar símbolos alrededor. "
Primera Conferencia

Kozen comienza la primera conferencia en la " Teoría de la computación " por colocar las dos preocupaciones centrales del curso. Estos son el estudio de " varios modelos computacionales y construcciones de programación ", y la clasificación de los problemas "en términos de su complejidad inherente. "

Históricamente , un buen punto de partida para la discusión de estos puntos es un artículo de 1936 escrito por Turing llamó , "Sobre los números computables ". En este trabajo de Turing define lo que él llamó una máquina universal (ahora conocido como máquina de Turing en su honor ) .

Una máquina de Turing consiste en un conjunto finito de estados y una cinta semi - infinita. La máquina lee la entrada y ( basado en esa entrada ) imprime símbolos en las celdas separadas de la cinta . La cinta se llama "semi- infinita ", ya que está delimitado en el extremo izquierdo , pero sin límite a la derecha.

Kozen lo pone, la máquina de Turing ofrece un "modelo para la definición de tiempo básico y la complejidad del espacio" con definiciones que "reflejan con bastante precisión las expectativas de la computación en la vida real . " teorema
de Savitch

Kozen pasa a discutir el teorema de Savitch , el nombre de Walter Savitch , un profesor de mucho tiempo en la Universidad de California, San Diego. El teorema de Savitch demuestra que existe un algoritmo para determinar si existe un camino entre dos vértices en un grafo dirigido .

Kozen señala que ello tiene una incidencia sobre , aunque no es idéntico a " cielo abierto más importante pregunta en la ciencia de la computación teórica " (el problema P = NP ) .

Por ejemplo , si se define " P " como el conjunto de todos los problemas que se pueden resolver fácilmente, y " NP " como el conjunto de todos los problemas que son difíciles de resolver , pero pueden ser fácilmente reconocidas con la mayor precisión resuelto de una vez alguien lo ha hecho, entonces parece intuitivamente obvio que "P " y " NP " no son el mismo conjunto . Si fueran el mismo conjunto , sería un hecho preocupante para los informáticos , porque significaría que todo es (en principio) de piratear .

Sin embargo, ni Savitch de ni teoremas de Kozen resuelve el problema .

Otro libro

Kozen es también el autor de " el Diseño y Análisis de Algoritmos ", que es un libro que cubre un tema similar para estudiantes de posgrado ya " familiarizadas con el clásico el material que normalmente se enseña en los cursos de pregrado de nivel superior "en la zona.