Difference between revisions of "Algorithms"

From Chessprogramming wiki
Jump to: navigation, search
m
(6 intermediate revisions by the same user not shown)
Line 32: Line 32:
 
* [[Parallel Search]]
 
* [[Parallel Search]]
 
* [[Principal Variation Search]]
 
* [[Principal Variation Search]]
* [[Proof-number Search]]
+
* [[Proof-Number Search]]
 
* [[Retrograde Analysis]]
 
* [[Retrograde Analysis]]
 
* [[Search]]
 
* [[Search]]
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]
 +
* <span id="ACM-Turing"></span>[[Mathematician#CHPapadimitriou|Christos H. Papadimitriou]], [[Mathematician#LAdleman|Leonard Adleman]], [[Richard Karp]], [[Donald Knuth]], [[Mathematician#RETarjan|Robert E. Tarjan]], [[Mathematician#LValiant|Leslie Valiant]] ('''2012'''). ''[https://dl.acm.org/citation.cfm?id=2322189 An Algorithmic View of the Universe]''. ACM-Turing 2012 » [[Alan Turing]]
 +
: {{#evu:https://www.youtube.com/watch?v=f6df3s3x3zo|alignment=left|valignment=top}}
 
* [[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]]
  
Line 121: Line 124:
 
* [https://en.wikipedia.org/wiki/Algorithm_characterizations Algorithm characterizations from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Algorithm_characterizations Algorithm characterizations from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Analysis_of_algorithms Analysis of algorithms from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Analysis_of_algorithms Analysis of algorithms from Wikipedia]
 +
* [https://en.wikipedia.org/wiki/Algorithmic_efficiency Algorithmic efficiency from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Big_O_notation Big O notation from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Big_O_notation Big O notation from Wikipedia]
 
* [https://en.wikibooks.org/wiki/Algorithms Algorithms - Wikibooks]
 
* [https://en.wikibooks.org/wiki/Algorithms Algorithms - Wikibooks]
Line 140: Line 144:
 
: [https://en.wikipedia.org/wiki/Nondeterministic_algorithm Nondeterministic algorithm]
 
: [https://en.wikipedia.org/wiki/Nondeterministic_algorithm Nondeterministic algorithm]
 
: [https://en.wikipedia.org/wiki/Metaheuristic Metaheuristic]
 
: [https://en.wikipedia.org/wiki/Metaheuristic Metaheuristic]
 +
: [https://en.wikipedia.org/wiki/Online_algorithm Online algorithm]
 
: [https://en.wikipedia.org/wiki/Parallel_algorithm Parallel algorithm]
 
: [https://en.wikipedia.org/wiki/Parallel_algorithm Parallel algorithm]
 
: [https://en.wikipedia.org/wiki/Quantum_algorithm Quantum algorithm]
 
: [https://en.wikipedia.org/wiki/Quantum_algorithm Quantum algorithm]
 +
: [https://en.wikipedia.org/wiki/Streaming_algorithm Streaming algorithm]
 
* [https://en.wikipedia.org/wiki/Randomized_algorithm Randomized algorithm from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Randomized_algorithm Randomized algorithm from Wikipedia]
 
: [https://en.wikipedia.org/wiki/Las_Vegas_algorithm Las Vegas algorithm]
 
: [https://en.wikipedia.org/wiki/Las_Vegas_algorithm Las Vegas algorithm]
Line 172: Line 178:
 
* [https://en.wikipedia.org/wiki/Root-finding_algorithm Root-finding algorithm from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Root-finding_algorithm Root-finding algorithm from Wikipedia]
 
===Graphics===  
 
===Graphics===  
* [https://en.wikipedia.org/wiki/Even-odd_rule Even-odd rule from Wikipedia]
+
{{Graphic Algorithms}}
* [https://en.wikipedia.org/wiki/Flood_fill Flood fill from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Line_drawing_algorithm Line drawing algorithm from Wikipedia]
 
: [https://en.wikipedia.org/wiki/Digital_Differential_Analyzer_%28graphics_algorithm%29 Digital Differential Analyzer (graphics algorithm)]
 
: [https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm Bresenham's line algorithm]
 
: [https://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm Xiaolin Wu's line algorithm]
 
* [https://en.wikipedia.org/wiki/Ray_tracing_%28graphics%29 Ray tracing (graphics) from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Spline_interpolation Spline interpolation from Wikipedia]
 
: [https://en.wikipedia.org/wiki/De_Boor%27s_algorithm De Boor's algorithm]
 
: [https://en.wikipedia.org/wiki/De_Casteljau%27s_algorithm De Casteljau's algorithm]
 
 
===[https://en.wikipedia.org/wiki/Linear_programming Linear Programming]===  
 
===[https://en.wikipedia.org/wiki/Linear_programming Linear Programming]===  
 
* [https://en.wikipedia.org/wiki/Criss-cross_algorithm Criss-cross algorithm from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Criss-cross_algorithm Criss-cross algorithm from Wikipedia]
Line 201: Line 198:
 
* [https://en.wikipedia.org/wiki/Sorting_algorithm Sorting algorithm from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Sorting_algorithm Sorting algorithm from Wikipedia]
 
==Complexity==  
 
==Complexity==  
 +
* [https://en.wikipedia.org/wiki/Complexity Complexity from Wikipedia]
 +
* [https://en.wikipedia.org/wiki/Combinatorial_explosion Combinatorial explosion from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Category:Computational_complexity_theory Category: Computational complexity theory from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Category:Computational_complexity_theory Category: Computational complexity theory from Wikipedia]
* [https://en.wikipedia.org/wiki/Combinatorial_explosion Combinatorial explosion from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Complexity Complexity from Wikipedia]
 
 
* [https://en.wikipedia.org/wiki/Complexity_class Complexity class from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Complexity_class Complexity class from Wikipedia]
 
* [http://www.ics.uci.edu/~eppstein/cgt/hard.html Computational Complexity of Games and Puzzles] by [[David Eppstein]]
 
* [http://www.ics.uci.edu/~eppstein/cgt/hard.html Computational Complexity of Games and Puzzles] by [[David Eppstein]]
Line 219: Line 216:
 
* [https://en.wikipedia.org/wiki/Correctness_%28computer_science%29 Correctness (computer science) from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Correctness_%28computer_science%29 Correctness (computer science) from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Halting_problem Halting problem from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Halting_problem Halting problem from Wikipedia]
* [[Videos#Kraan|Kraan]] - [https://www.flashlyrics.com/lyrics/kraan/gut-und-richtig-03 Gut und Richtig] (1973), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
+
* [[:Category:Kraan|Kraan]] - [https://www.flashlyrics.com/lyrics/kraan/gut-und-richtig-03 Gut und Richtig] (1973), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
 
: {{#evu:https://www.youtube.com/watch?v=HjR320Y4NTQ|alignment=left|valignment=top}}
 
: {{#evu:https://www.youtube.com/watch?v=HjR320Y4NTQ|alignment=left|valignment=top}}
  
Line 226: Line 223:
  
 
'''[[Programming|Up one Level]]'''
 
'''[[Programming|Up one Level]]'''
 +
[[Category:Kraan]]
 +
[[Category:Stamp]]

Revision as of 09:56, 1 May 2019

Home * Programming * Algorithms

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] .

General Concepts

Sorting and Searching

Enumeration and Backtracking

Mathematical Optimization

Combinatorial

See also

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 ...

1980 ...

1990 ...

2000 ...

2010 ...

External Links

Algorithms

Algorithms for calculating variance
Approximation algorithm from Wikipedia
Cryptographic hash algorithms
Divide and conquer algorithm
Deterministic algorithm
Distributed algorithms
Nondeterministic algorithm
Metaheuristic
Online algorithm
Parallel algorithm
Quantum algorithm
Streaming algorithm
Las Vegas algorithm
Monte Carlo algorithm
Pseudorandom number generator

Algebra and Calculus

Karatsuba algorithm from Wikipedia
Algorithms: Design and Analysis, Part 1 by Tim Roughgarden, Stanford University, Coursera, YouTube Video

Graphics

Digital Differential Analyzer (graphics algorithm)
Bresenham's line algorithm
Xiaolin Wu's line algorithm
De Boor's algorithm
De Casteljau's algorithm

Linear Programming

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

Misc

References

Up one Level