कलन-विधियों की सूची

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

संचय-सम्बन्धी कलन-विधियाँ (Combinatorial algorithms)

सामान्य संचयविन्यास (combinatorial) से सम्बन्धित कलनविधियाँ

Brent's algorithm: finds cycles in iterations using only two iterators
Floyd's cycle-finding algorithm: finds cycles in iterations
Pseudorandom number generators (uniformly distributed):
Robinson-Schensted algorithm: generates permutations from pairs of Young tableaux

आरेख-सम्बन्धी कलन-विधियाँ (Graph algorithms)

Bellman-Ford algorithm: computes shortest paths in a weighted graph (where some of the edge weights may be negative)
Dijkstra's algorithm: computes shortest paths in a graph with non-negative edge weights
Perturbation methods: an algorithm that computes a locally shortest paths in a graph
Floyd-Warshall algorithm: solves the all pairs shortest path problem in a weighted, directed graph
Johnson algorithm: All pairs shortest path algorithm in sparse weighted directed graph
Kruskal's algorithm: finds a minimum spanning tree for a graph
Prim's algorithm: finds a minimum spanning tree for a graph
Boruvka's algorithm: finds a minimum spanning tree for a graph
Ford-Fulkerson algorithm: computes the maximum flow in a graph
Edmonds-Karp algorithm: implementation of Ford-Fulkerson
Nonblocking Minimal Spanning Switch say, for a telephone exchange
Spring based algorithm: algorithm for graph drawing
Topological sort: finds linear order of nodes(e.g. jobs) based on their dependencies.
Hungarian algorithm: algorithm for finding a perfect matching
Coloring algorithm: Graph coloring algorithm.
Nearest neighbour algorithm.

खोज सम्बन्धी कलन-विधियाँ (Search algorithms)

Linear search: finds an item in an unsorted list
Selection algorithm: finds the kth largest item in a list
Binary search algorithm: locates an item in a sorted list
Binary search tree: uses binary tree to maintain elements.
Breadth-first search: traverses a graph level by level
Depth-first search: traverses a graph branch by branch
Best-first search: traverses a graph in the order of likely importance using a priority queue
A* tree search: special case of best-first search that uses heuristics to improve speed
Uniform-cost search: a tree search that finds the lowest cost route where costs vary
Predictive search: binary like search which factors in magnitude of search term versus the high and low values in the search. Sometimes called dictionary search or interpolated search.
Hash table: finds an item in an unsorted collection in O(1) time.
Crazy Turtle Puzzle algorithm

अक्षर-समूह सम्ब्नधी अल्गोरिद्म (String algorithms)

Searching

Aho-Corasick algorithm: trie based algorithm for finding all matches in dictionary.
Bitap algorithm: fuzzy algorithm that determines strings are approximately equal.
Boyer-Moore string search algorithm: amortised linear (sublinear in most times) algorithm
Knuth-Morris-Pratt algorithm: bypasses reexamination of matched characters
Rabin-Karp string search algorithm: searches multiple patterns efficiently
Longest common subsequence problem: Haskell's dynamic programming algorithm
Longest increasing subsequence problem
Shortest common supersequence problem
longest common substring problem
Kadane's algorithm: finds maximum sub-array of any size
Boyer-Moore-Horspool algorithm

Approximate matching

Hirschberg's algorithm: space efficient algorithm for computing edit distance
Levenshtein edit distance
Metaphone: an algorithm for indexing words by their sound, when pronounced in English
Needleman-Wunsch algorithm
NYSIIS: phonetic algorithm
Smith-Waterman algorithm
Soundex

Sorting algorithms

Binary tree sort
Bitonic sorter
Bogosort
Bubble sort: for each pair of indices, swap the items if out of order
Bucket sort
Burstsort
Cocktail sort
Comb sort
Counting sort
Gnome sort
Flashsort
Heapsort: convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list
Insertion sort: determine where the current item belongs in the list of sorted ones, and insert it there
Library sort
Merge sort: sort the first and second half of the list separately, then merge the sorted lists
Odd-even sort
Pancake sorting
Patience sorting
Pigeonhole sort
Quicksort: divide list into two, with all items on the first list coming before all items on the second list.; then sort the two lists. Often the method of choice
Radix sort: sorts strings letter by letter
Selection sort: pick the smallest of the remaining elements, add it to the end of the sorted list
Shell sort: an attempt to improve insertion sort
Smoothsort
Stooge sort
Strand sort
Topological sort
Tree sort
Walia sort

Merge algorithms

Simple Merge algorithm
k-way Merge algorithm

डेटा घनन की कलन-विधियाँ (Data Compression algorithms)

Lossless compression algorithms

Burrows-Wheeler transform: preprocessing useful for improving lossless compression
DEFLATE: lossless data compression
Delta encoding: aid to compression of data in which sequential data occurs frequently
Dynamic Markov Compression: Compression using predictive arithmetic coding
Incremental encoding: delta encoding applied to sequences of strings
LZW: lossless data compression (Lempel-Ziv-Welch)
LZ77 (algorithm): LZ77 and LZ78 are the names for the two lossless data compression algorithms
LZMA: short for Lempel-Ziv-Markov chain-Algorithm
LZO: data compression algorithm that is focused on speed
PPM compression algorithm
Shannon-Fano coding
Truncated binary encoding
Run-length encoding: lossless data compression taking advantage of strings of repeated characters
SEQUITUR algorithm: lossless compression by incremental grammar inference on a string
EZW (Embedded Zerotree Wavelet)
Entropy encoding: coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols
- Huffman coding: simple lossless compression taking advantage of relative character frequencies
  - Adaptive Huffman coding: adaptive coding technique based on Huffman coding
  - Package-Merge: Optimizes Huffman coding subject to a length restriction on code strings
- Arithmetic coding: advanced entropy coding
  - Range encoding: same as arithmetic coding, but looked at in a slightly different way
Entropy coding with known entropy characteristics
- Unary coding: code that represents a number n with n ones followed by a zero
- Elias delta|gamma|omega coding: universal code encoding the positive integers
- Fibonacci coding: universal code which encodes positive integers into binary code words
- Golomb coding: form of entropy coding that is optimal for alphabets following geometric distributions
- Rice coding: form of entropy coding that is optimal for alphabets following geometric distributions

Lossy compression algorithms

Linear predictive coding: lossy compression by representing the spectral envelope of a digital signal of speech in compressed form
A-law algorithm: standard companding algorithm
Mu-law algorithm: standard analog signal compression or companding algorithm
Fractal compression: method used to compress images using fractals
Transform coding: type of data compression for "natural" data like audio signals or photographic images
Vector quantization: technique often used in lossy data compression
Wavelet compression: form of data compression well suited for image compression (sometimes also video compression and audio compression)

गणनात्मक ज्यामिति (Computational geometry)

Euclidean Distance Transform - Computes the distance between every point in a grid and a discrete collection of points.
Fortune's Algorithm: a well-known and simple-to-understand algorithm for computing Voronoi diagrams from a set of sites
Collision detection algorithms: check for the collision or intersection of two given solids
Convex hull algorithms: determining the convex hull of a set of points
- Chan's algorithm
- Gift wrapping algorithm or Jarvis march
- Graham scan
- Kirkpatrick–Seidel algorithm
Gilbert-Johnson-Keerthi distance algorithm: determining the smallest distance between two convex shapes.
Line segment intersection: finding whether lines intersect, usually with a sweep line algorithm
- Bentley-Ottmann algorithm
- Shamos-Hoey algorithm
Point in polygon algorithms: tests whether a given point lies within a given polygon
Polygon triangulation algorithms: decompose a polygon into a set of triangles

कम्प्यूटर ग्राफिक्स (Computer graphics)

Bresenham's line algorithm: plots points of a 2-dimensional array to form a straight line between 2 specified points (uses decision variables)
Line drawing algorithm: graphical algorithm for approximating a line segment on discrete graphical media.
DDA line algorithm: plots points of a 2-dimensional array to form a straight line between 2 specified points (uses floating-point math)
Flood fill: fills a connected region of a multi-dimensional array with a specified symbol
Xiaolin Wu's line algorithm: algorithm for line antialiasing.
Painter's algorithm: detects visible parts of a 3-dimensional scenery
Ray tracing (graphics): realistic image rendering
Phong shading: an illumination model and an interpolation method in 3D computer graphics
Gouraud shading: an algorithm to simulate the differing effects of light and colour across the surface of an object in 3D computer graphics
Scanline rendering: constructs an image by moving an imaginary line over the image
Global illumination algorithms: Considers direct illumination and reflection from other objects.
Interpolation: Constructing new data points such as in digital zoom.
- Ramer-Douglas-Peucker algorithm: Given a 'curve' composed of line segments to find a curve not too dissimilar but that has fewer points
Spline interpolation: Reduces error with Runge's phenomenon.

कम्प्यूटर दृष्टि (Computer vision)

In image processing, epitomic analysis can be used to represent an image or video by a smaller image or video which preserves its statistical properties.

Counting objects in an image: Counts the number of objects in a binary image. Uses the connected-component labeling algorithm to first label each object. Then returns the number of labeled objects.

SIFT (Scale-invariant feature transform): is an algorithm to detect and describe local features in images.

बीज-लेखन के अल्गोरिद्म (Cryptographic algorithms)

Symmetric (secret key) encryption:
- Advanced Encryption Standard (AES), winner of NIST competition, also known as Rijndael
- Blowfish
- Data Encryption Standard (DES), sometimes DE Algorithm, winner of NBS selection competition, replaced by AES for most purposes
- IDEA
- RC4 (cipher)
- Tiny Encryption Algorithm
Asymmetric (public key) encryption:
- DSA
- ElGamal
- RSA
- NTRUEncrypt
Cryptographic Message digest functions (hashing functions):
- MD5 – Note that there is now a method of generating collisions for MD5
- RIPEMD-160
- SHA-1
- HMAC: keyed-hash message authentication
- Tiger (TTH), usually used in Tiger tree hashes
Cryptographically secure pseudo-random number generators
- Blum Blum Shub - based on the hardness of factorization
- Yarrow algorithm
- Fortuna, intended as an improvement on Yarrow algorithm
- Linear feedback shift register
Secret sharing, Secret Splitting, Key Splitting, M of N algorithms
- Shamir's Scheme
- Blakey's Scheme
Key exchange
- Diffie-Hellman key exchange

आंकिक संकेत प्रसंस्करण (Digital signal processing)

CORDIC: Fast trigonometric function computation technique.
Rainflow-counting algorithm: Reduces a complex stress history to a count of elementary stress-reversals for use in fatigue analysis
Osem: algorithm for processing of medical images
Goertzel algorithm Can be used for DTMF digit decoding.
Discrete Fourier transform: determines the frequencies contained in a (segment of a) signal
Richardson-Lucy deconvolution: image de-blurring algorithm
Elser Difference-Map Algorithm: X-Ray diffraction microscopy

सॉफ्टवेयर प्रौद्योगिकी (Software engineering)

Algorithms for Recovery and Isolation Exploiting Semantics: recovery
Unicode Collation Algorithm
CHS conversion: converting between disk addressing systems
Cyclic redundancy check: calculation of a check word
Parity: simple/fast error detection technique
Rayrole's algorithm: resource calendar management

वितरित प्रणालियों के लिये कलन-विधियाँ (Distributed systems algorithms)

Lamport ordering: a partial ordering of events based on the happened-before relation
Snapshot algorithm: a snapshot is the process of recording the global state of a system
Vector clocks: a total ordering of events
Marzullo's algorithm: distributed clock synchronization
intersection algorithm: another clock agreement algorithm.
Byzantine fault tolerance: good fault tolerance.

Memory Allocation and deallocation algorithms

Boehm garbage collector: Conservative garbage collector
Buddy memory allocation: Algorithm to allocate memory such that fragmentation is less.
Cheney's algorithm An improvement on the Semi-space collector
Generational garbage collector: Fast garbage collectors that segregate memory by age
Mark and sweep
Reference counting
Semi-space collector An early copying collector

Operating systems algorithms

Banker's algorithm: Algorithm used for deadlock avoidance.
Page replacement algorithms: Selecting the victim page under low memory conditions.
Bully algorithm: Selecting new leader among many computers.

Disk scheduling algorithms:

Elevator algorithm: Disk scheduling algorithm that works like an elevator.
Shortest seek first: Disk scheduling algorithm to reduce seek time.

Process synchronisation algorithms:

Scheduling algorithms

एलेक्ट्रानिकी एवं हार्डवेयर सम्बन्धी अल्गोरिद्म

Quine-McCluskey algorithm: Also called as Q-M algorithm, programmable method for simplyfying the boolean equations.
Petrick's method: Another algorithm for boolean simplification.
Espresso heuristic logic minimization: Fast algorithm for boolean function minimization.

मशीन शिक्षा के अल्गोरिद्म (Machine learning algorithms)

Support Vector Mac ting

चिकित्सा सम्बन्धी अल्गोरिद्म

न्यूरल नेटवर्क (Neural networks)

जेनेटिक अल्गोरिद्मँ

Fitness proportionate selection - also known as roulette-wheel selection
Truncation selection
Tournament selection
Stochastic universal sampling

संख्यात्म बीजगणित (Numerical algebra)

Buchberger's algorithm: finds a Gröbner basis
Eigenvalue algorithm
Exponentiating by squaring: quickly computes powers of numbers and matrices
Gram-Schmidt process: orthogonalizes a set of vectors
Knuth-Bendix completion algorithm: for rewriting rule systems
Multivariate division algorithm: for polynomials in several indeterminates

संख्या सिद्धान्त सम्बन्धी कलन-विधियाँ

Discrete logarithm:
Euclidean algorithm: computes the greatest common divisor
Extended Euclidean algorithm: Also solves the equation ax+by = c.
Binary gcd algorithm: Efficient way of calculating gcd.
Integer factorization: breaking an integer into its prime factors
Multiplication algorithms: fast multiplication of two numbers
Booth's multiplication algorithm
Primality tests: determining whether a given number is prime
Odlyzko-Schönhage algorithm: calculates nontrivial zeroes of the Riemann zeta function

संख्यात्मक कलन-विधियाँ (Numerical algorithms)

Approximate counting algorithm: Allows counting large number of events in a small register
Biconjugate gradient method: solves systems of linear equations
Borwein's algorithm: an algorithm to calculate the value of 1/π
Dancing Links: finds all solutions to the exact cover problem
De Boor algorithm: computes splines
De Casteljau's algorithm: computes Bézier curves
False position method: approximates roots of a function
Gauss–Jordan elimination: solves systems of linear equations
Gauss–Seidel method: solves systems of linear equations iteratively
Gauss–Legendre algorithm: computes the digits of pi
Kahan summation algorithm: a more accurate method of summing floating-point numbers
Levinson recursion: solves equation involving a Toeplitz matrix
Metropolis–Hastings algorithm: used to generate a sequence of samples from the probability distribution of one or more variables
MISER algorithm: Monte Carlo simulation, numerical integration
Newton's method: finds zeros of functions with calculus
Risch algorithm: Translates indefinite integral to algebraic problem
Rounding functions: the classic ways to round numbers
Secant method: approximates roots of a function
Shifting nth-root algorithm: digit by digit root extraction
Square root: approximates the square root of a number
Strassen algorithm: faster matrix multiplication
Symbolic Cholesky decomposition: Efficient way of storing sparse matrix
Tridiagonal matrix algorithm (Thomas algorithm): solves systems of tridiagonal equations

अभीष्टप्राप्ति के अल्गोरिद्म (Optimization algorithms)

Ant colony optimization
BFGS method: A nonlinear optimization algorithm
Branch and bound
Chain matrix multiplication
Conjugate gradient
Differential evolution
Evolution strategy
Gauss–Newton algorithm: An algorithm for solving nonlinear least squares problems.
Genetic algorithms
Gradient descent
Interior point method
Karmarkar's algorithm: The first reasonably efficient algorithm that solves the linear programming problem in polynomial time.
Levenberg–Marquardt algorithm: An algorithm for solving nonlinear least squares problems.
Line search
Local search
Nelder-Mead method (downhill simplex method): A nonlinear optimization algorithm.
Newton's method in optimization
Particle swarm
Random-restart hill climbing
Simplex algorithm: An algorithm for solving the linear programming problem
Simulated annealing
Stochastic tunneling
Subset sum algorithm
Tabu search
Minimax used in game programming
Alpha-beta pruning: search to reduce number of nodes in minimax algorithm

पार्जिंग (Parsing)

Recursive descent parser: A top-down parser suitable for LL(k) grammars
LL parser: A relatively simple linear time parsing algorithm for a limited class of context-free grammars
LR parser: A more complex linear time parsing algorithm for a larger class of context-free grammars. Variants:
Packrat parser: A linear time parsing algorithm supporting some context-free grammars and parsing expression grammars
CYK algorithm: An O(n³) algorithm for parsing any context-free grammar
Earley parser: Another O(n³) algorithm for parsing any context-free grammar
GLR parser:An algorithm for parsing any context-free grammar by Masaru Tomita. It is tuned for deterministic grammars, on which it performs almost linear time and O(n³) in worst case.
Inside-outside algorithm: An O(n³) algorithm for re-estimating production probabilities in probabilistic context-free grammars

क्वांटम अल्गोरिद्म (Quantum algorithms)

Application of quantum computation to various categories of problems and algorithms

Grover's algorithm: provides quadratic speedup for many search problems
Shor's algorithm: provides exponential speedup for factoring a number
Deutsch-Jozsa algorithm: criterion of balance for Boolean function

गणना सिद्धान्त एवं आटोमेटा (Theory of computation and automata)

Powerset construction: Algorithm to convert nondeterministic automaton to deterministic automaton.
Todd-Coxeter algorithm: Procedure for generating cosets.

अन्य

Alpha max plus beta min algorithm: an approximation of the square-root of the sum of two squares.
Astronomical algorithms
Baum-Welch algorithm: hidden markov models
Bit manipulation algorithms: Create bit mask algorithm
Doomsday algorithm: day of the week
Schreier-Sims algorithm: computing a base and strong generating set (BSGS) of a permutation group
Viterbi algorithm: hidden markov models
Xor swap algorithm: swaps the values of two variables without using a buffer
Luhn algorithm: a method of validating identification numbers
Rutishauser's algorithm
Stemming algorithm: a method of reducing words to their stem, base, or root form
Hamming weight (population count): find the number of 1 bits in a binary word
Heisenman-Drogulous isomoglobic algorithm
Gerchberg–Saxton algorithm: Phase retrieval algorithm for optical planes
Shunting yard algorithm: convert an infix-notation math expression to postfix

बाहरी कड़ियाँ

Dictionary of Algorithms and Data Structures (अंग्रेजी मे)