Operating Systems
Programming Languages
Microsoft Technologies
Computer Science
Formal Methods
MM & Game Dev.
Theory Computing
DS & Algorithms
Software Engineering
Web Programming
Web Technologies

Contact Us | What's New | Missing Link | Feedback

Data Structures and Algorithms

Book Title : Complexity of Algorithms
eBook download format(s) : ps
Author(s) : Péter Gács
Section : Data Structures and Algorithms
Book Review:

Book Description
The need to be able to measure the complexity of a problem, algorithm or structure, and to obtain bounds and quantitive relations for complexity arises in more and more sciences: besides computer science, the traditional branches of mathematics, statistical physics, biology, medicine, social sciences and engineering are also confronted more and more frequently with this problem. In the approach taken by computer science, complexity is measured by the quantity of computational resources (time, storage, program, communication) used up by a particular task. These notes deal with the foundations of this theory.

Computation theory can basically he divided into three parts of different character. First, the exact notions of algorithm, time, storage capacity, etc. must be introduced. For this, different mathematical machine models must be defined, and the time and storage needs of the computations performed on these need to be clarified (this is generally measured as a function of the size of input). By limiting the available resources, the range of solvable problems gets narrower; this is how we arrive at different complexity classes.

Second, one must determine the resource need of the most important algorithms in various areas of mathematics, and give efficient algorithms to prove that certain important problems belong to certain complexity classes. In these notes, we do not strive for completeness in the investigation of concrete algorithms and problems; this is the task of the corresponding fields of mathematics (combinatorics, operations research, numerical analysis, number theory). Nevertheless, a large number of concrete algorithms will be described and analyzed to illustrate certain notions and methods, and to establish the complexity of certain problems.

Third, one must find methods to prove "negative results", i.e. for the proof that some problems are actually unsolvable under certain resource restrictions. Often, these questions can be formulated by asking whether certain complexity classes are different or empty. This problem area includes the question whether a problem is algorithmically solvable at all; this question can today be considered classical, and there are many important results concerning it; in particular, the decidability or undecidability of most concrete problems of interest is known.

It is, finally, worth noting that if a problem turns out to be "difficult" to solve, this is not necessarily a negative result. More and more areas (random number generation, communication protocols, cryptography, data protection) need problems and structures that are guaranteed to be complex. These are important areas for the application of complexity theory, from among them, we will deal with random number generation and cryptography, the theory of secret communication.

add to                 Digg!

You may use anyone of the download options

eBook VersionLook @ Amazon
Front Cover

Missing Link?, Report It and you may wish to find Similar Books from amazon.

Tell a Friend!

Similar Book titles in Data Structures and Algorithms section:
Handbook of Algorithms and Data Structures
Problems on Algorithms, 2nd Edition
Algorithms and Complexity
Introduction to Algorithms
Design and Analysis of Computer Algorithms
Computer Animation: Algorithms and Techniques
Dictionary of Algorithms and Data Structures
Sorting and Searching Algorithms: A Cookbook
Planning Algorithms
Algorithms in the Real World - Lecture Notes
Algorithms and Data Structures in VLSI Design: OBDD - Foundations and Applications
How to Think About Algorithms - Loop Invariants and Recursion
Algorithms for Communications Systems and their Applications
Algorithms for Programmers
Average Case Analysis of Algorithms on Sequences
Efficient Algorithms for Sorting and Synchronization
Combinatorial Algorithms
Jeff Erickson's Algorithms Course Materials

Similar Book titles in Other sections:

Section: Bio-Chemistry
Algorithms for Molecular Biology
Complexity in Biological Information Processing

Section: CS -> Theory
Cellular Automata and Complexity
Information Theory, Inference and Learning Algorithms
Parallel Complexity Theory
Lecture Notes on Algorithm Analysis and Computational Complexity (4th Edition)
Introduction to Computational Complexity
Show all..

Section: Logic Design and Architecture
The Complexity of Boolean Functions

Section: Mathematics
Algorithms For Computing With Modular Forms
Graph-Theoretic Algorithms
Algorithms for Modular Elliptic Curves, Second Edition
Combinatorial Algorithms for Computers and Calculators, Second Edition
Discrete Mathematics with Algorithms
Show all..

Section: Miscellaneous
Applied Cryptography: Protocols, Algorithms, and Source Code in C, 2nd Edition
Computational Complexity: A Modern Approach
Computational Complexity: A Conceptual Perspective
Digraphs Theory, Algorithms and Applications

Section: Microsoft C Sharp (C#)
Data Structures and Algorithms with Object-Oriented Design Patterns in C#

Section: C++ Language
Algorithms And Data Structures in C++
Data Structures and Algorithms with Object-Oriented Design Patterns in C++
C++ Network Programming, Vol. 1: Mastering Complexity with ACE and Patterns

Similar Books from Amazon :

Tell a Friend!

©2008 - Home - Privacy Policy - Program Policy, Terms and Conditions