कलन-विधियों की सूची
imported>InternetArchiveBot द्वारा परिवर्तित ०४:५५, १६ जून २०२० का अवतरण (Rescuing 2 sources and tagging 0 as dead.) #IABot (v2.0.1)
यह सम्पूर्ण पृष्ठ या इसके कुछ अनुभाग हिन्दी के अतिरिक्त अन्य भाषा(ओं) में भी लिखे गए हैं। आप इनका साँचा:edit करके विकिपीडिया की सहायता कर सकते हैं। |
संचय-सम्बन्धी कलन-विधियाँ (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
- Huffman coding: simple lossless compression taking advantage of relative character frequencies
- 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
- 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
- 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:
- 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
आंकिक संकेत प्रसंस्करण (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
- 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)
चिकित्सा सम्बन्धी अल्गोरिद्म
न्यूरल नेटवर्क (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(n3) algorithm for parsing any context-free grammar
- Earley parser: Another O(n3) 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(n3) in worst case.
- Inside-outside algorithm: An O(n3) 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 (अंग्रेजी मे)