알고리즘 행성 여행자들을 위한 안내서

원제 Planet der Algorithmen (2015년)

11/14/2018 ~ 1/7/2019

• 독일원전이라서 몇군데 번역이 의문스러운 부분이 있기는 하지만, 컴퓨터 알고리즘에 대해서 살펴보기에는 재미있는 책이다.  쉽게 알수 있는 내용들도 있고, 어떤 부분들은 실제 학술적인 논문의 내용을 살펴봐야 깊게 이해할 수 있는 부분들도 있다.  어떤 부분들에서는 컴퓨터와 관계가 없어 보이는 부분의 문제들을 해결하는 것도 알고리즘을 이용하고 있다는 것이다. 알고리즘에 대한 일반적인 이해가 컴퓨터를 이용해서 문제를 해결하는 것이라고 하는 것은 실제 알고리즘의 아주 일부분에 국한된 문제라는 것이다. 알고리즘은 어떤 문제해결을 위한 연속된 사고의 과정을 논리적으로 설명하는 방법이라고 하면, 일상 생활에서 우리가 무의식적으로 사용하는 많은 의사결정의 부분들이 이미 연구된 알고르즘에 따르고 있고, 우리가 그 알고리즘을 모르고 있어도 논리적으로 타당한 의사선택을 하는 것이 바로 알고리즘이라는 것이다.

 

pp.19 "Programming of Interdependent Activities, II: Mathematical Mode"

http://www1.cmc.edu/pages/faculty/MONeill/math188/papers/dantzig4.pdf

https://projecteuclid.org/download/pdf_1/euclid.pjm/1103044531

https://apps.dtic.mil/dtic/tr/fulltext/u2/263628.pdf

https://sites.math.washington.edu/~burke/crs/407/notes/section2.pdf

https://mat.gsia.cmu.edu/classes/QUANT/NOTES/chap7.pdf

 

pp. 23 알고리즘은 게으름의 예술이다. ... 알고리즘이 빛나는 것은, 알고리즘이 주어진 과제를 완벽한 게으름으로 흠 없이 이행해내기 때문이다.

 

pp. 29 알고리즘은 현실과의 연계고리를 필요로 한다. 즉, 입력 데이터와 모델, 적어도 현실에 대한 이해가 있어야 한다. 알고리즘의 품질은 이런 연계고리의 품질에 따라 달라진다. 

 

pp. 59 Algorithmen und Datenstrukturen by Thomas OttmannPeter Widmayer

Q. 알고리즘이란 무엇인가?

... 이는 철학적인 문제로서, 이 책에서는 답할 수가 없다. 그리고, 다행히 그런 대답이 필요하지도 않다.

 

pp.61 Computational Complexity by Christos H. Papadimitriou

... 알고리즘은 문제를 풀기 위한 세부적이고도 단계적인 방법이다. 그런데, 문제란 무엇일까? 이번 장에서는 세 가지 중요한 사례를 설명해보겠다. 

 

pp. 64 Computers and Intractability. A Guide to the Theory of NP-Completeness by Michael R. Garey, David S. Johnson

... 알고리즘은 문제를 풀기 위한 일반적이고도 단계적인 방법이다.

 

pp. 69 지연 결정의 원리(Principle of deferred decision) - .... 이 원리가 적용되면 우리가 이미 충분히 상상할 수 있는 상황, 즉 모든 지점을 한 번은 반드시 방문해야 하는 상황이 발생한다.

 

pp. 78 게으름의 예술은 다양성을 생성시키는 생성 규칙을 추구한다. 모든 것을 동일한 것으로 취급해버리는 식의 게으름은 예술도 아니고, 알고리즘은 더더욱 아니다.

 

pp. 81 알고리즘의 본질은 확정된 규칙이 아니라, 거기에서 도출되는 다양성에 있다. ... 알고리즘은 인풋에 따라 예측 불가능한 다양성을 만들어낸다.

 

pp. 93 Dijkstra's algorithm

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

http://garfield.library.upenn.edu/classics1983/A1983QA19900001.pdf

http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf

 

pp. 100 알고리즘은 기호의 변형에 관한 일종의 규정집이다. 알고리즘은 우리가 임의로 기호를 입력하면 작동하기 시작해서 언젠가는 '끝난다' 혹은 '끝나지 않았다'라고 우리에게 알려줄 것으로 기대되는 기계와 비슷하다.

 

pp. 101 Church–Turing thesis / Church–Turing thesis

https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis

https://plato.stanford.edu/entries/church-turing/

http://www.alanturing.net/turing_archive/pages/reference%20articles/The%20Turing-Church%20Thesis.html

http://mathworld.wolfram.com/Church-TuringThesis.html

https://www.andrew.cmu.edu/user/kk3n/recursionclass/chap6.pdf

https://pdfs.semanticscholar.org/cbce/6ea4f2cb209b07dd61639e424a278b73f11f.pdf

https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

 

pp. 173 The Market for "Lemons": Quality Uncertainty and the Market Mechanism by George A. Akerlof (1970)

https://en.wikipedia.org/wiki/The_Market_for_Lemons

https://www2.bc.edu/thomas-chemmanur/phdfincorp/MF891%20papers/Ackerlof%201970.pdf

https://policonomics.com/the-market-for-lemons/

 

pp. 178 Computational Complexity and Information Asymmetry in Financial Products

https://scholar.princeton.edu/markus/publications/computational-complexity-and-information-asymmetry-financial-products

https://www.boazbarak.org/Papers/derivative.pdf

https://users.cs.duke.edu/~rongge/derivativelatest.pdf

http://fed-aerated.blogspot.com/2011/05/lemons-problem.html

 

pp. 180 Shor's algorithm

https://en.wikipedia.org/wiki/Shor%27s_algorithm

https://qudev.phys.ethz.ch/content/QSIT15/Shors%20Algorithm.pdf

https://arxiv.org/pdf/quant-ph/9508027.pdf

https://courses.cs.washington.edu/courses/cse599d/06wi/lecturenotes11.pdf

https://www.quantiki.org/wiki/shors-factoring-algorithm

https://pdfs.semanticscholar.org/3b96/1bf56e29349415502d74a59d437307ead352.pdf

https://quantumexperience.ng.bluemix.net/proxy/tutorial/full-user-guide/004-Quantum_Algorithms/110-Shor's_algorithm.html

 

pp. 189 Einstein–Podolsky–Rosen paradox (EPR paradox)

https://en.wikipedia.org/wiki/EPR_paradox

https://plato.stanford.edu/entries/qt-epr/

https://www.aps.org/publications/apsnews/200511/history.cfm

https://cds.cern.ch/record/111654/files/vol1p195-200_001.pdf

 

pp. 220  Authoritative Sources in a Hyperlinked Environment by Jon Kleinberg

https://www.cs.cornell.edu/home/kleinber/auth.pdf

https://en.wikipedia.org/wiki/HITS_algorithm

https://nlp.stanford.edu/IR-book/html/htmledition/hubs-and-authorities-1.html

http://pi.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture4/lecture4.html

http://pages.cs.wisc.edu/~jerryzhu/cs769/link.pdf

https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0100338

 

pp. 250 RENTAL HARMONY: SPERNER’S LEMMA IN FAIR DIVISION by Francis Edward Su

https://en.wikipedia.org/wiki/Simmons%E2%80%93Su_protocols

https://www.math.hmc.edu/~su/papers.html

https://www.math.hmc.edu/~su/papers.dir/rent.pdf RENTAL HARMONY: SPERNER’S LEMMA IN FAIR DIVISION by Francis Edward Su

https://www.math.hmc.edu/~su/papers.dir/bfe.pdf Bidding for envy-freeness: A procedural approach to n-player fair-division problems

 

pp. 261  Counterspeculation, Auctions, and Competitive Sealed Tenders

https://en.wikipedia.org/wiki/Vickrey_auction

https://web.stanford.edu/~milgrom/publishedarticles/Lovely%20but%20Lonely%20Vickrey%20Auction-072404a.pdf

https://homepages.cwi.nl/~apt/stra/ch7.pdf

https://kylewoodward.com/blog-data/pdfs/references/vickrey-the-journal-of-finance-1961A.pdf

 

pp. 264 Vickrey–Clarke–Groves mechanism

https://en.wikipedia.org/wiki/Vickrey%E2%80%93Clarke%E2%80%93Groves_mechanism

https://en.wikipedia.org/wiki/Vickrey%E2%80%93Clarke%E2%80%93Groves_auction

https://web.stanford.edu/~jdlevin/Econ%20285/Vickrey%20Auction.pdf

https://cheeptalk.files.wordpress.com/2009/07/vcg.pdf

https://www.cs.ubc.ca/~cs532l/gt2/slides/10-2.pdf

http://www.cs.upc.edu/~mjserna/docencia/agt-miri/slides/AGT10-VCR-mechanism.pdf

 

pp. 271 COLLEGE ADMISSIONS AND THE STABILITY OF MARRIAGE by D. Gale and L. S. Shapley

https://apps.dtic.mil/dtic/tr/fulltext/u2/251958.pdf

https://en.wikipedia.org/wiki/Stable_marriage_problem

https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/01StableMatching.pdf

https://cse.buffalo.edu/~hartloff/CSE331-Summer2015/GaleShapley.pdf

 

pp. 275 Kidney Exchange

https://www.nber.org/papers/w10002

https://www.nber.org/papers/w10002.pdf

https://web.stanford.edu/~niederle/Stanford.kidney%20exchange.Market%20design%20Oct%202012.pdf

 

pp. 276 중요한 건 게임이 아니라 행위다. 어떤 원칙으로 행위를 결정할 것인지 밝혀진다면, 이 원칙이 어떻게 하면 최대 효과를 낼 수 있는지 심각하게 고려해보야 하는 상황이 많이 발생할 것이다. 

 

pp. 282 그가 추구한 원칙은 '현상을 이해하려면 모든 것을 가능한 한 단순화해야 한다'는 것이다.

 

pp. 291 A mixability theory for the role of sex in evolution. by Adi Livnat, Christos Papadimitriou, Jonathan Dushoff, Marcus W. Feldman

https://www.semanticscholar.org/paper/A-mixability-theory-for-the-role-of-sex-in-Livnat-Papadimitriou/7be7d4c57d8b7ff865ff53217e30cc82655de9fd

https://www.pnas.org/content/105/50/19803

https://www.pnas.org/content/pnas/105/50/19803.full.pdf