Advertisement
Published in:
2014 | OriginalPaper | Chapter
4. Randomized Algorithms
Author : Cesare Alippi
Published in: Intelligence for Embedded Systems
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Every time we cannot solve a complex problem, either because it is too complex or computationally hard, we try to explore it on a number of instances and expect that, asymptotically with the number of samples, something can be said. This chapter introduces a key mechanism every engineer/computer scientist should be aware of, that of randomization. After having introduced the main results coming from the theory of randomization and those granting convergence of sampled quantities to the exact ones, we will present some general methods based on randomized algorithms for solving a large class of performance assessment problems. Results, independent of the dimension of the sampling space and the particular probability density function associated with sample drawing, hold in probability at arbitrary accuracy and confidence levels, function of the envisaged number of samples.