Computational Problems
homomorphism is a special kind of function that preserves the structure of the input. An algorithm can be seen as a homomorphism from one set of all words in an alphabet to another set of all words in an alphabet. an algorithm solves a descision problem if it can decide for any input word if it is in the language or not i.e the output is 1 or 0. We then say that the algorithm a recognizes the language L for the problem. If a language is recognized by an algorithm we say that the language is recursive. Not the same as recursive function in programming???
Algorithms and Programs
what are they? a homomorphism from one set of all words in an alphabet to another set of all words in an alphabet.
Äquivalent Algorithms
if they have the same input alphabet and all outputs are the same.
Enumeration Algorithms
for all intergers n it outputs the sequence of the alphabet from 1 to n.
Decision Problems
Is a word in a language. For example, is a number prime?
if the word is in the language, the answer is yes, otherwise no.
If there is such an algorithm we call it recursive???
lots of examples such as primtest, hamiltonian cycle, etc.
Function Problems
In german relationsproblem?
Optimization Problems
takes 6 parameters, minimize or maximize
like TSP, max-sat, max-clique, ILP etc.