Difference between revisions of "Algorithms"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
| Line 113: | Line 113: | ||
* [[Donald Knuth]] ('''2010'''). ''[http://www-cs-faculty.stanford.edu/~uno/da.html Selected Papers on Design of Algorithms]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 191, [https://en.wikipedia.org/wiki/Cambridge_University_Press Cambridge University Press] | * [[Donald Knuth]] ('''2010'''). ''[http://www-cs-faculty.stanford.edu/~uno/da.html Selected Papers on Design of Algorithms]''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN.shtml CSLI lecture notes series] 191, [https://en.wikipedia.org/wiki/Cambridge_University_Press Cambridge University Press] | ||
* [[Mathematician#BVoecking|Berthold Vöcking]] et al. (eds.) ('''2011'''). ''[http://www.springer.com/gp/book/9783642153273 Algorithms Unplugged]''. [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer] | * [[Mathematician#BVoecking|Berthold Vöcking]] et al. (eds.) ('''2011'''). ''[http://www.springer.com/gp/book/9783642153273 Algorithms Unplugged]''. [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer] | ||
| + | * [[Matteo Frigo]], [[Charles Leiserson]], [[Harald Prokop]], [https://dblp.uni-trier.de/pers/hd/r/Ramachandran:Sridhar Sridhar Ramachandran] ('''2012'''). ''Cache-Oblivious Algorithms''. [[ACM#TALG|ACM Transactions on Algorithms]], Vol. 8, No. 1, [http://supertech.csail.mit.edu/papers/FrigoLePr12.pdf pdf] | ||
* [[Katja Grace]] ('''2013'''). ''Algorithmic Progress in Six Domains''. Technical report 2013-3, [https://en.wikipedia.org/wiki/Machine_Intelligence_Research_Institute Machine Intelligence Research Institute], [https://en.wikipedia.org/wiki/Berkeley,_California Berkeley, CA], [http://intelligence.org/files/AlgorithmicProgress.pdf pdf], 5 [[Games|Game Playing]], 5.1 [[Chess]], 5.2 [[Go]], 9 [[Learning|Machine Learning]] | * [[Katja Grace]] ('''2013'''). ''Algorithmic Progress in Six Domains''. Technical report 2013-3, [https://en.wikipedia.org/wiki/Machine_Intelligence_Research_Institute Machine Intelligence Research Institute], [https://en.wikipedia.org/wiki/Berkeley,_California Berkeley, CA], [http://intelligence.org/files/AlgorithmicProgress.pdf pdf], 5 [[Games|Game Playing]], 5.1 [[Chess]], 5.2 [[Go]], 9 [[Learning|Machine Learning]] | ||
Revision as of 17:52, 13 November 2018
Home * Programming * Algorithms
.png)
Algorithms,
in mathematics and computer science, methods for solving a problem expressed as a finite sequence of instructions. The term “algorithm” is derived from the name of Muḥammad ibn Mūsā al-Khwārizmī (born approximately 780 in Khwarezm, died between 835 and 850), the Persian mathematician, astronomer, geographer, and scholar in the House of Wisdom in Baghdad, from the Khorasan province of present-day Uzbekistan [2] .
Contents
General Concepts
Sorting and Searching
- ABDADA
- All shortest Paths
- Alpha-Beta
- B*
- Best-First
- Brute-Force
- Depth-First
- Flood Fill Algorithm
- Iterative Search
- Jamboree
- Monte-Carlo Tree Search
- Move Ordering
- MTD(f)
- NegaC*
- NegaScout
- Parallel Alpha-Beta in Cilk
- Parallel Search
- Principal Variation Search
- Proof-Number Search
- Retrograde Analysis
- Search
- SEE - The Swap Algorithm
- SEX Algorithm
- SOMA Algorithm
- SSS* and Dual*
- UCT
- Young Brothers Wait Concept
Enumeration and Backtracking
Mathematical Optimization
Combinatorial
- Bit-Twiddling
- BitScan
- Flipping Mirroring and Rotating
- Kogge-Stone Algorithm
- Parallel Prefix Algorithms
- Population Count
See also
- BCH Hashing
- Data
- Fill Algorithms
- Hash Table
- Learning
- Mathematician
- SIMD and SWAR Techniques
- Space-Time Tradeoff
- Zobrist Hashing
Publications
1960 ...
- Volume 1 - Fundamental Algorithms (1968)
- Volume 2 - Seminumerical Algorithms (1969)
- Volume 3 - Sorting and Searching (1973)
- Volume 4 - Combinatorial Algorithms in preparation (five fascicles have been published as of April 2009)
- Volume 4A - Enumeration and Backtracking
- Volume 4B - Graph and Network Algorithms
- Volume 4C and possibly 4D - Optimization and Recursion
- Volume 5 - Syntactic Algorithms, planned (as of August 2006, estimated in 2015).
1970 ...
- Niklaus Wirth (1976). Algorithms + Data Structures = Programs.
- Georgy Adelson-Velsky, Vladimir Arlazarov, Mikhail Donskoy (1979). Algorithms of adaptive search. Machine Intelligence 9 (eds. Jean Hayes Michie, Donald Michie and L.I. Mikulich), pp. 373-384. Ellis Horwood, Chichester
1980 ...
- Andrei P. Ershov, Donald Knuth (Eds.) (1981). Algorithms in Modern Mathematics and Computer Science. Proceedings, Urgench, Uzbek SSR, September 16-22, 1979. Lecture Notes in Computer Science, Vol. 122, Springer » Ershov Archive
- Michel Gondran, [Mathematician#MMinoux|Michel Minoux]], Steven Vajda (1984). Graphs and Algorithms. John Wiley & Sons, google, amazon
- Georgy Adelson-Velsky, Vladimir Arlazarov, Mikhail Donskoy (1988). Algorithms for Games. Springer, amazon.com
1990 ...
- John Tromp (1993). Aspects of Algorithms and Complexity. Ph.D. thesis, University of Amsterdam, advisor Paul Vitányi
- Warren D. Smith, Kevin J. Lang (1994). Values of the merging function and algorithm design as a game. NEC Research Institute, ps
- Leen Ammeraal (1996). Algorithms and Data Structures in C++. Chichester: John Wiley
- Steven Skiena (1998). The Algorithm Design Manual. 2nd Edition 2008
- Harald Prokop (1999). Cache-Oblivious Algorithms. Masters thesis, Department of Electrical Engineering and Computer Science, MIT, pdf
2000 ...
- Donald Knuth (2000). Selected Papers on Analysis of Algorithms. CSLI lecture notes series 102
- R. C. T. Lee, S. S. Tseng, R. C. Chang, Y. T. Tsai (2005). Introduction to the Design and Analysis of Algorithms, a Strategic Approach. McGraw-Hill, amazon
- Jill Cirasella (2006). Classical and Quantum Algorithms for Finding Cycles. slides as pdf
- Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani (2006). Algorithms. McGraw-Hill, amazon
- Jacques Bahi, Sylvain Contassot-Vivier, Raphaël Couturier (2007). Parallel Iterative Algorithms: From Sequential to Grid Computing. Chapman & Hall/CRC Numerical Analysis and Scientific Computing Series
- David J. Stracuzzi (2007). Randomized Feature Selection. in Huan Liu, Hiroshi Motoda (eds.) Computational Methods of Feature Selection. CRC Press, pdf
- Steven Skiena (2008). The Algorithm Design Manual. Springer, 2nd Edition
- Kurt Mehlhorn, Peter Sanders (2008). Data Structures and Algorithms: The Basic Toolbox. Springer
- Michel Gondran, Michel Minoux (2008, 2010). Graphs, dioids and semirings - New Models and Algorithms. Springer, from google, amazon.com, 2nd edition from alibris.com [4]
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2009). Introduction to Algorithms, 3rd Edition.
2010 ...
- Donald Knuth (2010). Selected Papers on Design of Algorithms. CSLI lecture notes series 191, Cambridge University Press
- Berthold Vöcking et al. (eds.) (2011). Algorithms Unplugged. Springer
- Matteo Frigo, Charles Leiserson, Harald Prokop, Sridhar Ramachandran (2012). Cache-Oblivious Algorithms. ACM Transactions on Algorithms, Vol. 8, No. 1, pdf
- Katja Grace (2013). Algorithmic Progress in Six Domains. Technical report 2013-3, Machine Intelligence Research Institute, Berkeley, CA, pdf, 5 Game Playing, 5.1 Chess, 5.2 Go, 9 Machine Learning
External Links
- Algorithm from Wikipedia
- Muḥammad ibn Mūsā al-Khwārizmī
- Banū Mūsā from Wikipedia
- Algorithm characterizations from Wikipedia
- Analysis of algorithms from Wikipedia
- Big O notation from Wikipedia
- Algorithms - Wikibooks
- Dictionary of Algorithms and Data Structures by Paul E. Black, National Institute of Standards and Technology
- Dictionary of Algorithms and Data Structures from Wikipedia
- The Aggregate Magic Algorithms by Hank Dietz » Bit-Twiddling
- Algorithmic Art by Maarten van Emden
- The Art of Computer Programming from Wikipedia
- Java implementation of algorithms from Norvig and Russell's Artificial Intelligence: A Modern Approach. 3rd edition
Algorithms
- Algorithms for calculating variance
- Approximation algorithm from Wikipedia
- Cryptographic hash algorithms
- Divide and conquer algorithm
- Deterministic algorithm
- Distributed algorithms
- Nondeterministic algorithm
- Metaheuristic
- Parallel algorithm
- Quantum algorithm
Algebra and Calculus
- Algorism from Wikipedia
- Berlekamp's algorithm from Wikipedia » Elwyn Berlekamp
- Berlekamp–Massey algorithm from Wikipedia
- Buchberger's algorithm from Wikipedia
- Cantor–Zassenhaus algorithm from Wikipedia
- Computus from Wikipedia
- Divisibility rule from Wikipedia
- Division (digital) from Wikipedia
- Euclidean algorithm from Wikipedia
- Gaussian elimination from Wikipedia
- Gauss–Newton algorithm from Wikipedia
- Householder's method from Wikipedia
- Kuwaiti algorithm from Wikipedia
- Levenberg–Marquardt algorithm from Wikipedia
- Multiplication algorithm from Wikipedia
- Karatsuba algorithm from Wikipedia
- Algorithms: Design and Analysis, Part 1 by Tim Roughgarden, Stanford University, Coursera, YouTube Video
- Numerical analysis from Wikipedia
- Numerical linear algebra from Wikipedia
- Pollard's kangaroo algorithm from Wikipedia
- Quine–McCluskey algorithm from Wikipedia
- Rod calculus from Wikipedia
- Root-finding algorithm from Wikipedia
Graphics
- Digital Differential Analyzer (graphics algorithm)
- Bresenham's line algorithm
- Xiaolin Wu's line algorithm
Linear Programming
- Criss-cross algorithm from Wikipedia
- Karmarkar's algorithm from Wikipedia
- Simplex algorithm from Wikipedia
Sorting and Searching
- A* from Wikipedia
- Bellman–Ford algorithm
- Dijkstra's algorithm
- Flooding algorithm
- Floyd–Warshall algorithm
- Greedy algorithm
- Hill climbing
- Kruskal's algorithm
- Nearest neighbour algorithm
- String searching algorithm
Complexity
- Category: Computational complexity theory from Wikipedia
- Combinatorial explosion from Wikipedia
- Complexity from Wikipedia
- Complexity class from Wikipedia
- Computational Complexity of Games and Puzzles by David Eppstein
- Computational complexity theory from Wikipedia
- Game complexity from Wikipedia » Games
- Go and mathematics from Wikipedia » Go
- List of complexity classes from Wikipedia
- Problem solving from Wikipedia » Artificial Intelligence
- Reduction (complexity) from Wikipedia
- Shannon number from Wikipedia » Claude Shannon
- Time complexity from Wikipedia
- Wheat and chessboard problem from Wikipedia » Chessboard
Misc
- Correctness (disambiguation) from Wikipedia
- Correctness (computer science) from Wikipedia
- Halting problem from Wikipedia
- Kraan - Gut und Richtig (1973), YouTube Video
References
- ↑ A stamp issued September 6, 1983 in the Soviet Union], commemorating Al-Khwārizmī's (approximate) 1200th birthday
- ↑ Kurt Mehlhorn, Peter Sanders (2008). Data Structures and Algorithms: The Basic Toolbox. Springer, Appetizer: Integer Arithmetics (pdf)
- ↑ The Art of Computer Programming from Wikipedia
- ↑ Ordinal optimization from Wikipedia
