Theory of computation

What is the use of a regular expressions?

Shorthand way to describe sets

Whatever Theoretical operators of regular expressions are there?

“*” — 0 or more repetitions

“+” - 1 or more repetitions

“?” - character optional

“|” - or

() - group

What is a set?

A group of unordered, unique values

What types of sets are there?

• finite

• Non-finite

• Countably finite

• Non-countable - real numbers

• Subsets

What is meant by the cardinality of the set?

Number of items in a set

What is a subset?

only contains items from other sets

what condition subset has to meet in order to become a proper subset?

If there are items in one set that are not in another

What Big O notation does?

• Describes complexity of a function

• It is represented by a higher power

What is constant “O c)” in BIG O Notation?

Time independent of input

What time complexities are there?

• Linear O(n) —> linear search

• Logarithmic O(log2n) —> binary search

• Linear-Logarithmic O(nlog2n) —> merge sort

• Polynomial O(n²) —> loop inside a loop —> bubble sort

• Fibonacci numbers O(2^n) —> intractable

• TSP O(n!) —> intractable

What is meant by “intractable” problems?

Problems that are theoretically soluble but may take million years to solve. May use Heuristics which are only approximate solutions

What is meant by “tractable” problems?

Problems with polynomial time complexity or less. Can be solved in a useful period of time.

What is the Halting Problem?

Impossible to determine whether program will stop for given input.