Se ha producido un error en este gadget.

Libros publicados por Noam Chomsky

  • Como se reparte la tarta
  • Conocimiento y Libertad
  • El programa Minimalista
  • El triángulo fatal: Estados Unidos, Isrel y Palestina
  • Estados fallidos: abuso de poder y ataque a la democracia
  • Intervenciones
  • La (des)educación
  • Los guardianes de la libertad:propagnada, desinformación y consenso en los medios de comunicación de masas
  • Lucha de clases
  • Sobre el anarquismo
  • ¿Quienes son los terroristas?:Terrorismo ciego,terrorismo de estado,terrorismo global, kamikazes, al-qaeda

¡¡Bienvenidos!!

Estás en el blog de Noam Chomsky. Un lugar donde podrás encontrar toda la información relevante sobre él.

domingo, 6 de junio de 2010

Teoría de la computación

Esther Márquez

Teoría de la computación

Es una ciencia que estudia las limitaciones y capacidades fundamentales de las computadoras.Está entroncada con las matemáticas y la computación. Dentro de esta teoría existen varias subcategorías:

Teoría de los autómatas:

Esta teoría da las fórmulas matemáticas que sirven para simplificar y generalizar las capacidades de las computadoras y juegan un rol indispensable en aplicaciones de las ciencias de la computación que incluyen procesamiento de texto, compiladores, diseño de hardware, inteligencia artificial…

Los tres modelos más importantes son:

· Autómatas finitos: A este grupo pertenecen las computadoras que tienen una cantidad limitada de memoria.

· Autómatas con pilas: Están en el aquellas computadoras que tienen una gran cantidad de memoria pero que solo pueden manipular la información de forma que el último dato almacenado es el siguiente en ser leído.

· Máquinas de Turing: Pertenecen a este grupo, aquellas con una gran cantidad de memoria y que la almacenan en una cinta. En este grupo es en el que juega un papel imprescindible las teorías chomskyanas, ya que cada autómata es equivalente a una gramática formal , lo que hace que la jerarquía de Chomsky se use en términos de autómatas.

A continuación podemos ver una representación de una máquina de Turing.




Teoría de la computabilidad

Trata de resolver problemas computacionales son tener que recurrir a planteamientos algorítmicos ya que se han descubierto problemas imposibles de resolver de esta forma, por lo que esta teoría permite ahorrar tiempo y esfuerzo.

Los problemas se clasifican de la siguiente manera en relación a su grado de imposibilidad:

· Computables: Existen algoritmos capaces de resolverlos y se pueden distinguir aquellos casos en los que no existe solución.

· Semicomputables: Existen algoritmos capaces de encontrar una solución si existe pero no pueden distinguir aquellos que no la tienen ( ante un problema sin solución el algoritmo entraría en un bucle infinito)

Incomputables: No existen ningún algoritmo capaz de resolverlo.

Teoría de la complejidad computacional

Estudia las necesidades de memoria, tiempo y otro recursos para determinar si es rentable resolver un problema. Uno de sus mayores logros ha sido la clasificaciónn de los problemas, de una forma similar a la tabla periódica, según su dificultad a la hora de resolverse.

Las aplicaciones de esta teoría son innumerables. Una de las más importantes es la criptografía que es una de las bases del mundo digital.

No hay comentarios:

Publicar un comentario