My Avatar

Shilong ZHAO

Algorithmics for Hard Problems Notes

2015-07-03 00:00:00 +0200

In case you have any questions or suggestions, you can leave comments HERE . Thanks!

This post is an excerpt from the theory part (chapter 2) of book Algorithmics for Hard Problems. Honestly, It is practically not quite useful but provides a mathematical view into algorithms, which is very interesting.

Basic Concepts

alphabet, symbol

An alphabet is a non-empty, finite set. A symbol is an element in an alphabet .

word

An finite sequence of elements of an alphabet, the empty word consists zero element.

Of an alphabet , the set of all the words is . is the set of all words over whose length is n.

Alphabet can be used to code graphs (# can be any symbol), since it can program an adjacency matrix ,

.

language

Every set is a language over . It is a subset of all the possible words.

Algorithmic Problems

decision problem

To decide if a given input has a prescribed property.

A decision problem is a triple where . An algorithm solves the decision problem if, for every word ,

  1. if ,

  2. if .

optimization problem

An optimization problem is a 7-tuple,

  1. is the input alphabet, it is used to encode/represent the problem,

  2. is the output alphabet, it is used to encode/represent the output,

  3. is the language of feasible problem instances, it is all the possible problem instances.

  4. is the language of the (actual) problem instances of ,

  5. is a function , for every , is called the set of feasible solutions for ,

  6. is the cost function, for every pair , where , assigns a positive real number ,

  7. , if , the problem is a minimization problem and a maximum problem otherwise.

For every , a feasible solution is called optimal for and if

For example, can be a word encoding a specific graph by representing the adjacency matrix. Suppose the shortest path from node to is wanted. The set of feasible solutions will be all the connected paths from to . And the goal will be minimization. The optimal solution is the path with shortest distance.