Information Technology Reference
In-Depth Information
for which no reasonable algorithms exist: the traveling salesman problem is
just one of a number of problems for which we know of no polynomial time
algorithm. In the next chapter we shall see that there are not only tractable and
intractable problems, but also those that are noncomputable by any algorithm or
computer!
Key concepts
Algorithms as recipes
M
Euclid's algorithm
l
Numerical methods
M
Discrete approximation to continuous variables
l
Monte Carlo method and pseudorandom numbers
l
Sorting algorithms
M
Bubble sort
l
Merge sort
l
Graph problems
M
Minimal spanning tree
l
Dijkstra's shortest path algorithm
l
Traveling salesman problem
l
Complexity theory
M
Big-O notation
l
Polynomial time, tractable problems
l
Exponential time, intractable problems
l
NP-complete problems
l
Search WWH ::




Custom Search