25,161
edits
Changes
Quote Templates added
==Intellectual Foundations==
{{Quote from ''Biography AS Kronrod'' by Alexander Yershov <ref>[http://vikont.50webs.com/art_kronrod.html Биография А.С. Кронрода], [http://translate.google.com/translate?sl=ru&tl=en&js=n&prev=_t&hl=en&ie=UTF-8&u=http%3A%2F%2Fvikont.50webs.com%2Fart_kronrod.html Biography AS Kronrod] by [http://www.linkedin.com/in/unixander Alexander Yershov] (translated by [https://en.wikipedia.org/wiki/Google_Translate Google Translate])</ref> In 1958, [[Alexander Kronrod|Kronrod]], Adelson-Velsky, and [[Mathematician#Landis|Landis]] selected "[https://en.wikipedia.org/wiki/Slapjack Snap]" ("подкидного дурака") as the intellectual foundations for the development of the game heuristic programming. The program itself was a fiasco - but the basic principles (board games, [[Search|search techniques]] and [[Depth|limited depth]]) were formulated. Further research laboratories in the field of game theory culminated in the first ever chess duel between the [[ITEP Chess Program|program]] of the [[Institute of Theoretical and Experimental Physics|Institute]] of Soviet and American [[Kotok-McCarthy-Program|best program]] developed at [[Stanford University]] under the direction of [[John McCarthy|J. McCarthy]]. By [[Stanford-ITEP Match|telegraph match]] was played in four games ended 3-1 in favor of our institute. At the time, chess became a [https://en.wikipedia.org/wiki/Guinea_pig_%28disambiguation%29|guinea pig]] for all programmers interested in [[Artificial Intelligence|artificial intelligence]].}}
==Hashing==
{{Quote from [[Mikhail Donskoy|Mikhail Donskoy's]] ''life cycle of a programmer'' <ref>[http://www.polit.ru/article/2008/08/20/programmist/ Михаил Донской: Жизненный цикл программиста - ПОЛИТ.РУ] (Russian) [[Mikhail Donskoy]] - [http://translate.google.com/translate?sl=ru&tl=en&js=n&prev=_t&hl=en&ie=UTF-8&u=http%3A%2F%2Fwww.polit.ru%2Farticle%2F2008%2F08%2F20%2Fprogrammist%2F The life cycle of a programmer] translated by [https://en.wikipedia.org/wiki/Google_Translate Google Translate], [https://www.facebook.com/politru polit.ru] August 20, 2008</ref>: When I was in high school I learned to program on the [[M-20]] ... In the group of programmers at [[Institute of Theoretical and Experimental Physics]], where computing work was done on [https://en.wikipedia.org/wiki/Nuclear_physics nuclear physics] on the M-20, they came up with [[Array|arrays]], [[Linked List|lists]], the need for [https://en.wikipedia.org/wiki/Subroutine subroutines] and more. One of my teachers, Georgy Adelson-Velsky came up with a [[Hash Table|hash memory]]. Details can be found in another of my teachers - [[Alexander Kronrod]] "Conversations about programming". Even before [[Mathematician#EWDijkstra|Dijkstra's]] basic principles of [https://en.wikipedia.org/wiki/Structured_programming structured programming] was known, [[Alexander Brudno]] published the book "Programming in meaningful notation." There was also created the first chess program ... The [[ITEP Chess Program|chess program ITEP]], the predecessor of [[Kaissa]] fit in memory of M-20, namely in 4096 cells, each of which has a 48-bit ... Hashing}}
==<span id="AVLTrees"></span>AVL Trees==
===Ershov and Shura-Bura===
{{Quote from ''The Early Development of Programming in the USSR'' by [[Mathematician#Ershov|Andrey Ershov]] and [[Mikhail R. Shura-Bura]] <ref>[[Mathematician#Ershov|Andrey Ershov]], [[Mikhail R. Shura-Bura]] ('''1980'''). ''[http://ershov.iis.nsk.su/archive/eaindex.asp?lang=2&gid=910 The Early Development of Programming in the USSR]''. in [https://en.wikipedia.org/wiki/Nicholas_C._Metropolis Nicholas C. Metropolis] (ed.) ''[http://dl.acm.org/citation.cfm?id=578384 A History of Computing in the Twentieth Century]''. [https://en.wikipedia.org/wiki/Academic_Press Academic Press], [http://ershov.iis.nsk.su/archive/eaimage.asp?did=28792&fileid=173671 preprint pp. 44]</ref> At the end of the 1950's a group of Moscow mathematicians began a study of computerized chess. Sixteen years later, the studies would lead to victory in the [[WCCC 1974|first world chess tournament for computer programs]] held in Stockholm during the 1974 [[IFIP]] Congress. An important component of this success was a deep study of the problems of information organization in [[Memory|computer memory]] and of various [[Search|search heuristics]]. G. M. Adelson-Velsky and [[Mathematician#Landis|E. M. Landis]] invented the [https://en.wikipedia.org/wiki/AVL_tree binary search tree] ("dichotomic inquiry") and [[Alexander Brudno|A. L. Brudno]], independent of [[John McCarthy|J. McCarthy]], discovered the [[Alpha-Beta|(α,β)-heuristic]] for reducing search times on a game tree.}}
===Donskoy===
{{Quote by [[Mikhail Donskoy]] from a [https://en.wikipedia.org/wiki/Radio_Free_Europe/Radio_Liberty Radio Liberty] interview on an anecdote concerning Georgy Adelson-Velsky and [https://en.wikipedia.org/wiki/AVL_tree AVL trees] <ref>[http://archive.svoboda.org/programs/sc/2002/sc.123102.asp Радио Свобода: Программы: Интернет] - [http://translate.google.com/translate?sl=ru&tl=en&js=n&prev=_t&hl=en&ie=UTF-8&u=http%3A%2F%2Farchive.svoboda.org%2Fprograms%2Fsc%2F2002%2Fsc.123102.asp Not very serious about digital], [https://en.wikipedia.org/wiki/Radio_Free_Europe/Radio_Liberty Radio Liberty] interview with Michael Schwartzman and [[Mikhail Donskoy]], December 31, 2002, translated by [https://en.wikipedia.org/wiki/Google_Translate Google Translate]</ref> <ref>[https://ece.uwaterloo.ca/~dwharder/aads/LectureMaterials/ Lecture Materials | Algorithms and Data Structures | University of Waterloo]</ref>: One of [[Mikhail Donskoy|my]] teachers, Georgy Adelson-Velsky, wrote an excellent report, "How did chess programs influence the development of programming". He lectured it in a strange way - at a congress in geophysics. In particular, the famous [https://en.wikipedia.org/wiki/AVL_tree AVL trees] were invented for chess programs at [[Institute of Theoretical and Experimental Physics|ITEP]]. I happened to be in Canada with Adelson-Velsky, at the [[University of Waterloo]], where we were invited. There are three Faculties of Computational Mathematics, one way or another related to computer science and programming. One of them is, more or less, department of AVL trees. Can you imagine the scene when Adelson-Velsky himself (AVL stands for Adelson-Velsky and [[Mathematician#Landis|Evgenii Landis]] - two authors) comes to a department bearing his name, with a head of the department, three full professors, and six assistant professors, a myriad of graduate students and all who study his works. We were seated at a place of honor. Adelson-Velsky did not speak English and I translated. They asked the fundamental question: "How do you feel about the AVL-tree today?". This was 20, maybe 30 years after the invention. Then Adelson-Velsky, a typical scientist, small and hunchbacked with glasses, said with his high voice: "Yes, AVL-trees - this was a mistake of my youth". I replied to him "Georgy Maximovich, should I translate that directly?". His honesty has always distinguished the crystal. He said yes, and I translated. Soon the department head said "You know, our guests are tired from the journey and need to rest". God forbid again Adelson-Velsky says that AVL-trees are nonsense again - their monthly salary exceeds two or three years' of Adelson's income ...}}
==The chronology of the events==
