Automata, Computability, and Complexity

Automata, Computability, and Complexity

1. Complexity Theory

   • What makes some problems computationally hard and others easy?
   • Options to confront a problem that seems to be hard
     • We're able to settle for less than a perfect solution to the problem
     • Some problems are hard only on the worst case situation, but easy most of the time
     • Undertanding which aspect of the problem is at the root of diffucluty, we are able to alter it, so that the problem is more easily solvable

2. Computability Theory

   • Mehtematicians such as Kurt Godel, Alan Turing and Alonzo Church discovered that certain basic problems cannot be solved by computers
   • Thanks to this profound result, was the development od ideas concerning theoretical models of computers that eventually lead to the constructions of actual computers
   • The objective is to classify problems as easy ones and hard ones.

3. Automata Theory

   • Deals with the definitions and properties of mathematical models of computation
   • Some exmaples of models that play a role in several applied area of computer science are "Fiite Automaton" & "Context-Free Grammar"
   • Allows practice with formal defiinitions of computation as it introduces concepts relevant to other nontheorical areas of computer science