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

यह सम्पूर्ण पृष्ठ या इसके कुछ विभाग हिन्दी के अतिरिक्त अन्य भाषा(ओं) में भी लिखे गए हैं। आप इनका अनुवाद करके विकिपीडिया की सहायता कर सकते हैं।

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

General combinatorial algorithms

• 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):
  • Blum Blum Shub
  • Mersenne twister
  • Linear congruential generator
  • Lagged Fibonacci generator
• 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
  • Fast Fourier transform
  • Cooley-Tukey FFT algorithm
  • Rader's FFT algorithm
  • Bluestein's FFT algorithm
  • Bruun's FFT algorithm
  • Prime-factor FFT algorithm
• 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:

• Peterson's algorithm
• Lamport's Bakery algorithm
• Dekker's algorithm

Scheduling algorithms

• Rate-monotonic scheduling
• Earliest deadline first scheduling
• Fair-share scheduling
• Round-robin scheduling
• Multi level feedback queue
• shortest job next
• shortest remaining time
• Least slack time scheduling
• List scheduling

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

• 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 Machines
• Boosting

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

• Medical algorithm
• Texas Medication Algorithm Project

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

• Hopfield net
• Backpropagation
• Self-organizing map

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

• 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:
  • Baby-step giant-step
  • Pollard's rho algorithm for logarithms
  • Pohlig-Hellman algorithm
  • Index calculus algorithm
• 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
  • prime factorization algorithm
  • Fermat's factorization method
  • Trial division
  • Lenstra elliptic curve factorization
  • Pollard's rho algorithm
  • Pollard's p − 1 algorithm
  • Congruence of squares
  • Quadratic sieve
  • Dixon's algorithm
  • Special number field sieve
  • General number field sieve
• Multiplication algorithms: fast multiplication of two numbers
• Booth's multiplication algorithm
• Primality tests: determining whether a given number is prime
  • AKS primality test
  • Miller-Rabin primality test
  • Sieve of Eratosthenes
  • Sieve of Atkin
• 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:
  • Operator-precedence parser
  • SLR (Simple LR) parser
  • LALR (Look-ahead LR) parser
  • Canonical LR parser
• 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 (अंग्रेजी मे)