Concepto de Teoría de la Computación

Serie de conocimientos científicos y sistematizados que han sido formulados con el objeto de estudiar la abstracción de situaciones que ocurren en la realidad para representarlos con el apoyo de métodos de aplicación formal, conformados por un conjunto de códigos o caracteres y directrices lógicas, comprensibles por el ser humano. Además, son adaptados de acuerdo a la capacidad de los dispositivos que procesan la información.

Teoría de la Computación

La teoría de la computación precede a los ordenadores electrónicos. Uno de sus precursores fue Alan Turing, quien determinó anticipadamente la funcionabilidad de las computadoras mediante una serie de teorías en el año 1936. Otras ramas científicas como la matemática, la filosofía, la lingüística, la biología y la ingeniería eláctrica, forman parte del contexto como un complemento. Las teorías básicas son: la Teoría de los Autómatas y la Teoría de los Lenguajes Formales. De forma general, la teoría de la computación permite interpretar muchos de los programas que se utilizan en computación como por ejemplo: el administrador de base de datos, asimismo:

  • Se emplea en el diseño y codificación de las aplicaciones esenciales de software y hardware.
  • Ayuda a entender el funcionamiento del software.
  • Permite descubrir si la resolución de un problema es factible.

Esta teoría se origina a partir de algunas situaciones que se presentaron en el área de la matemática, la cual cayó en una profunda crisis a finales del siglo XIX y principios del siglo XX. No obstante, la lógica y las matemáticas se unieron para darle el maíz formal a la ciencia de la computación.

La Teoría de la Computación puede ser asimilada como una pauta o un tipo de perspectiva que sirve para solucionar problemas. Esta pauta contiene una serie de nociones bases sobre las que se establecen las definiciones de alfabeto, palabra o cadena, lenguaje y problema. Ahora bien, para comprender mejor estos conceptos, debe entenderse la definición de conjunto como el sistema que las soporta.

Conjunto: es un grupo (sin importar el orden) de objetos o elementos de un mismo modelo sin repetición. En computación, los conjuntos se representan a partir de dos modelos:

  • Por expansión: se enumeran todos sus objetos, por ejemplo: {0, 1, 2, 3}.
  • Por interpretación: se describen de manera formal las características de sus objetos, por ejemplo: {i | Para todo k entero i = 2k}
    Un conjunto vacío se representa con el símbolo ∅. La pertenencia de un elemento u objeto de un conjunto: A = {0, 1, 2, 3} donde 1 ∈ A o también se denota 1 en A.
  • El subconjunto: B ⊆ C significa que todo objeto de B está en C. Si B ⊆ C y B ≠ C entonces se representa así: B ⊊ C (subconjunto propio).
  • La teoría de los autómatas: es una disciplina en computación que se encarga de estudiar a las máquinas de funcionamiento abstracto y los problemas que éstas son capaces de solucionar. Ésta teoría está estrechamente vinculada con la teoría de los lenguajes formales, ya que los autómatas o androides son clasificados a partir del tipo de lenguajes formales que son capaces de interpretar.
    Un modelo teórico autómata, es un prototipo matemático para una máquina de estado finito (FSM). Una máquina FSM es un ordenador que, dada una entrada de símbolos, "salta" a través de una serie de codificaciones en base a una función de transición, que puede ser representada como una tabla.
  • Teoría de los lenguajes formales: son lenguajes cuyos símbolos primarios y métodos para unir esos símbolos, se dice que están formalmente definidos. Al cúmulo de símbolos primarios se les conoce como el alfabeto o vocabulario del lenguaje, y al grupo de normas se les llama gramática formal o sintaxis. A una cadena de símbolos constituida de acuerdo a la gramática se la llama fórmula bien formada o vocablo del lenguaje. A diferencia del alfabeto que, debe constituirse como un conjunto finito y con cada fórmula bien formada que debe poseer una extensión también finita, un lenguaje formal puede conformarse en base a un número infinito de fórmulas bien formadas.
  • Árboles de derivación: son aquellos por medio de los cuales, se puede representar gráficamente la forma en que descienden las cadenas presentes en un lenguaje mediante el símbolo específico de la gramática que lo reproduce. Este tipo de árboles, son imágenes o gráficos con orientación acíclica, en los cuales cada vértice se enlaza con otro vértice o nodo distinguido, llamado vértice raíz. En tal sentido tenemos que: un vértice o nodo V1 se dice que se deriva de otro vértice o nodo V2, si se puede llegar al segundo a través del primero. El vértice raíz no se deriva de ningún otro vértice, a los vértices que no tienen derivaciones se les llama hojas y al resto de los vértices o nodos se les denomina vértices interiores.