Probabilistic algorithms Flashcards
heuristics
t
approximation algorithm
t
randomized algorithm
t
stochastic
describes something that was randomly determined
randomly determined; having a random probability distribution or pattern that may be analyzed statistically but may not be predicted precisely.
Probability density function
a probability density function (PDF), or density of a continuous random variable, is a function, whose value at any given point in the sample space (the set of possible values taken by the random variable) can be interpreted as providing a relative likelihood that the value of the random variable would equal that sample
pivot
t
Probabilistic Algorithm paradigm
for each input make a random choice and hope that it is good.
Non-Deterministic execution of algorithm
for the same input different sequences of
operations are possible
vs. for the same input the same sequence of
operations is executed
Probabilistic Algorithm
A Probabilistic (or Randomized) Algorithm is an algorithm which employs a degree of randomness as part of its logic
- > During execution, it takes random choices depending on those random numbers
- > The behavior (output) can vary if the algorithm is run multiple times on the same input
=> probabilistic algorithms are often simpler and faster than their deterministic counterparts
=> however, in the worst execution case, the algorithm may be very slow
positive vs negative probability
??
probabilistic algorithm
+ gain execution time
- loose correctness of answer
Las Vegas algorithms
a randomized algorithm that
- always gives correct/optimal results
- the execution time is variable
- example: RandQSORT
Monte Carlo algorithms
a randomized algorithm that
- the running time is deterministic
- the output may be incorrect with a certain probability
- example: Check matrices equality
- for Decision problem (Yes/No): one- or two-sided error
one-sided error
Monte Carlo algorithm: Yes or No always correct
two-sided error
Monte Carlo algorithm: a non-zero probability to err for both outputs
E[X]
Expected value of discrete X: E[X]
The expected value of random variable X is often written as E(X)
sl. 15 lecture_01
Random number generation
- the kernel of Monte Carlo simulation
- the heart of many standard statistical methods (bootstrap, Bayesian analysis)
- cryptography
bisection method
d
sucessive quadratic estimation method
d
Powell’s algorithm
d
inflection point
An inflection point is a point on a curve at which the sign of the curvature (i.e., the concavity) changes. Inflection points may be stationary points, but are not local maxima or local minima.
http://mathworld.wolfram.com/InflectionPoint.html
first order condition
The first order condition means that the local maximum or local minimum of some continuous function within some range (not including the end points) must occur where the derivative of that function is equal to 0.
- > At the highest and lowest points of a curve, the tangent to the curve at such points is horizontal.
- > The slope of the curve is zero.
http://users.etown.edu/p/pauls/ec309/lectures/lec04_unconst.html
second order condition
SOC for a local max is that f’‘(x) < 0
SOC for a local min is that f’‘(x) > 0
loss function
a function that maps an event or values of one or more variables onto a real number intuitively representing some “cost” associated with the event.
An optimization problem seeks to minimize a loss function
Hessian matrix?
useful in characterizing the shape of L and to
distinguish, among the zeros of gradient g(d), the minimum points, the maximum points and the inflexion points
why an inverse matrix?
we can multiply by an Inverse, which achieves the same thing as “dividing by a number”
remember: with Matrices the order of multiplication matters. AB is almost never equal to BA.
https: //www.mathsisfun.com/algebra/matrix-inverse.html
Jacobian matrix
is the matrix of all first-order partial derivatives of a vector-valued function. When the matrix is a square matrix, both the matrix and its determinant are referred to as the Jacobian in literature
The Jacobian matrix is important because if the function f is differentiable at a point x (this is a slightly stronger condition than merely requiring that all partial derivatives exist there), then the Jacobian matrix defines a linear map ℝ^n → ℝ^m, which is the best (pointwise) linear approximation of the function f near the point x. This linear map is thus the generalization of the usual notion of derivative, and is called the derivative or the differential of f at x.
Differenzierbarkeit / differentiable
Als Differenzierbarkeit bezeichnet man in der Mathematik die Eigenschaft einer Funktion, sich lokal um einen Punkt in eindeutiger Weise linear approximieren zu lassen.
TSP
find a Hamiltonian cycle with minimal path length in G
TSP extension
- Asymmetric TSP
- optimum configuration for the ATSP
- time dependent TSP
- Vehicle Routing Problem
- ## probabilistic VRP
Branch & Bound
an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.
Branch & Bound TSP
in B & B we try to reduce the search space:
linear programming
LP, also called linear optimization
best outcome of a mathematical model (provided constraints)
convex set
a convex set is a subset of an affine space that is closed under convex combinations.
in a Euclidean space, a convex region is a region where, for every pair of points within the region, every point on the straight line segment that joins the pair of points is also within the region
Convex polytope
a special case of a polytope, having the additional property that it is also a convex set of points in the n-dimensional space R^n
Steepest Descent algorithm
tbd
Newton-Raphson
tbd
Branch & Bound
tbd
Localized Random Search
tbd
Direct Random Search
tbd
