Home

Өмірді алгоритммен басқару

Name: Өмірді алгоритммен басқару
Author: Brian Christian, Tom Griffiths

Brian Christian, Tom Griffiths

Оқылуы: 0%

Жазылымсыз режим: 20-беттен кейін жазылым беті ашылады, әрі қарай әр 10 бет сайын (ең көбі 5 рет).

Жазу өлшемі 20 px

Жол аралығы 1.85

Әріп аралығы 0.30 px

Абзац аралығы 0.95 em

Кіріспе

Өмір сүруге арналған алгоритмдер

Отыз жеті пайыз.

Ал алгоритм сол тепе-теңдіктің отыз жеті пайыз екенін айтады.

1 Оңтайлы тоқтау

Іздеуді қашан тоқтату керек

Көріп отырғанымыздай, бұл «Catch-22», бірінші курстық жан айқайы — математиктер «оңтайлы тоқтау» мәселесі деп атайтын нәрсе және оның нақты жауабы болуы мүмкін: 37%.

Әрине, бәрі сіздің махаббат туралы қандай болжамдар жасауға дайын екеніңізге байланысты.

Хатшы мәселесі

37% ережесі

Неліктен 37%?

Үміткерлер саны артқан сайын, қарау мен секіру арасындағы шекара 37%-ға тұрақтайды: алғашқы 37% үміткерді қарап, ешкімді таңдамаңыз, содан кейін осыған дейінгілердің бәрінен асып түсетін кез келген адамға «секіруге» дайын болыңыз.

Хатшыны қалай оңтайлы таңдау керек.

Ғашықтардың секірісі (Lover’s Leap)

Жақсы нәрсені көргенде тани білу: Толық ақпарат

Толық ақпараты бар хатшы туралы есептегі оңтайлы тоқтау табалдырықтары.

Қашан сату керек

Үй сату мәселесіндегі оңтайлы тоқтау табалдырықтары.

Қашан көлік қою керек

Тұрақты қалай оңтайлы табуға болады.

Қашан тоқтау керек

Әрқашан тоқтай білу

Бірақ бұл оңтайлы тоқтау мәселелерінің маңыздылығын төмендетпейді; керісінше, оларды маңыздырақ етеді, өйткені уақыт ағыны кез келген шешім қабылдауды оңтайлы тоқтауға айналдырады.

*Біз кітап бойында кездесетін алгоритмдерді жуан қаріппен белгілейміз.

*Ойын теориясының есептеу қиындықтары туралы толығырақ 11-тарауда.

2 Зерттеу/Пайдалану

Ең соңғысы ма, әлде ең жақсысы ма?

Зерттеу/Пайдалану

Оның үстіне, зерттеу (exploration) қарғысқа айналуы да мүмкін.

Уақыт аралығын ұстап қал

Ұтсаң — қал

Шешімге бағытталған алғашқы қадамдар соғыстан кейінгі жылдары жасалды, Колумбия университетінің математигі Герберт Роббинс кемелді болмаса да, жақсы кепілдіктер беретін қарапайым стратегияны көрсетті.

Gittins индексі

«Ұтылсаң — ауыс» стратегиясының кемшілігі

Gittins индексі

Пара беру және шешім қабылдау

Жеңістер мен ұтылыстарға байланысты Gittins индексінің мәндері (келесі жолғы табыс қазіргінің 90%-ына тең деп есептелген).

Жеңістер мен ұтылыстарға байланысты Gittins индексінің мәндері (келесі жолғы табыс қазіргінің 99%-ына тең деп есептелген).

Өкініш пен оптимизм

Өкінішті азайту шеңбері

Жоғарғы сенім шегі (UCB) алгоритмдері

Онлайн бандиттер

Ол батырмамен нақты не істеді?

Ол оны А/В тестілеуден (өнімнің екі немесе бірнеше нұсқасын салыстыру арқылы ең тиімдісін анықтау әдісі) өткізді.

Клиникалық сынақтардың сынағы

Мазасыз әлем

Зерттеу …

Біз балалардың қыңырлығы деп қабылдайтын нәрсе, біз білгеннен де ақылдырақ болуы мүмкін.

… Және пайдалану

Сонымен, өмір бойғы зерттеулердің жемісін татып, сол кешкі мейрамхананың тұрақты қонағы болуда асыға күтетін көп нәрсе бар.

3 Сұрыптау Тәртіп орнату

Дэнни Хиллис Thinking Machines корпорациясын құрмас бұрын, өзінің әйгілі Connection Machine параллельді суперкомпьютерін ойлап таппас бұрын, ол MIT студенті еді, жатақханада тұратын және көршісінің шұлықтарынан шошитын.

Бұл кез келген болашақ компьютер маманының бөлмесін ауыстыруды сұрауына жеткілікті себеп еді.

Сұрыптау ләззаты

Үлкен, сұрыпталған тізімнің қиылған жоғарғы бөлігі көп жағдайда әмбебап пайдаланушы интерфейсі болып табылады.

Сұрыптау азабы

Бірақ біз қалай сұрыптауымыз керек және қай әдістер ең жақсы деген сұраққа жауап бермес бұрын, алдымен басқа нәрсені анықтап алуымыз керек: нәтижені қалай есептейміз?

Big-O: Ең нашар жағдайдың өлшемі

Тұрақты уақыт, O(1) деп жазылады; сызықтық уақыт, O(n) деп жазылады; және квадраттық уақыт, O(n2) деп жазылады.

Квадраттықтар: Көпіршікті сұрыптау және Қондыру арқылы сұрыптау

Квадраттық кедергіні бұзу: Бөл де биле

Салыстырудан тыс: Логарифмнен айла асыру

Сұрыптау — іздеудің алдын алу шарасы

Бірақ егер сіз компьютерлік мамандан бұл процесті енгізуге көмек сұрасаңыз, олардың қоятын бірінші сұрағы — сұрыптаудың мүлдем қажеті бар-жоғы болады.

Ретсіздік жағына қарай бейімделіңіз.

Ешқашан іздемейтін нәрсені сұрыптау — бұл уақытты толықтай босқа кетіру; ал ешқашан сұрыпталмаған нәрсені іздеу — жай ғана тиімсіздік.

Сұрақ, әрине, болашақтағы пайдалану көлемін алдын ала қалай бағалауға болатынында.

Үкім анық: кітап сөреңізді ретке келтіру оны жай ғана көзбен шолып шыққаннан гөрі көбірек уақыт пен энергияны талап етеді.

Сұрыптау және спорт

Шағымдану құқығы: Шу және төзімділік

Спортқа алгоритмдік тұрғыдан қараудың тағы бір, бәлкім, одан да маңызды жолы — күміс медальға қаншалықты сенуіміз керек екенін емес, алтын медальға қаншалықты сенуіміз керек екенін сұрау.

Қанды сұрыптау: Шұқысу реті және доминанттылық иерархиясы

Осы уақытқа дейін біз қарастырған барлық мысалдарда сұрыптау процесі жоғарыдан төмен қарай жүзеге асырылды: кітапханашы кітаптарды сөреге қойды, NCAA командаларға кіммен және қашан ойнау керектігін айтты. Ал егер бетпе-бет салыстырулар тек ерікті түрде болса ше? Сұрыптау органикалық түрде, төменнен жоғары қарай пайда болғанда ол қалай көрінеді?

Ол онлайн покеге ұқсауы мүмкін.

Төбелес орнына жарыс

Біз кез келген топтың өзін-өзі сұрыптауға деген ұмтылысының екі негізгі кемшілігін көрдік. Кем дегенде логарифмдік мөлшердегі қақтығыстар болады, бұл топ үлкейген сайын өмірді қиындатады. Сондай-ақ, әрбір қатысушы басқалардың үнемі өзгеріп тұратын мәртебесін қадағалап отыруға мәжбүр, әйтпесе олар қажетсіз шайқастарға тап болады. Бұл тек денені ғана емес, ақыл-ойды да қажытады.

Күнделікті «тынымсыз тірлікті» (rat race) қанша балағаттасақ та, оның төбелес емес, жарыс екендігі бізді маймылдардан, тауықтардан және егеуқұйрықтардың өзінен ерекшелейтін басты нәрсе.

4. Кэштеу (Caching)

Бәрін ұмытыңыз

Бірақ, сақтау мәселесі туралы үздіксіз ойланатын тағы бір үлкен кәсіби индустрия бар — олардың өз идеялары бар.

Бұл процесс кэштеу (caching) (жиі қолданылатын деректерді жылдам қолжетімді жерде сақтау) деп аталады.

Жады иерархиясы

Тұтынушылар біле бермейтін нәрсе — дәл осы таңдау (tradeoff) машинаның ішінде бірнеше деңгейде жасалады және бұл есептеуіш техниканың іргелі принциптерінің бірі болып саналады.

Жад иерархиясының негізгі идеясы кез келген кітапхананы пайдаланған адамға түсінікті болуы керек. Мысалы, егер сіз белгілі бір тақырыпта мақала жазу үшін зерттеу жүргізіп жатсаңыз, кейбір кітаптарға бірнеше рет жүгінуіңіз мүмкін. Әр жолы кітапханаға бара бергенше, тиісті кітаптарды үйіңізге, жұмыс үстеліңізге алып келесіз, ол жерден оларды оқу әлдеқайда оңай.

Аластау және көріпкелдік

Әрине, бір нәрсенің сізге қайтадан қашан қажет болатынын нақты білу айтуға ғана оңай.

Кітапхананы іштен сыртқа айналдыру

Көшенің шетіндегі бұлт

Тұрмыстағы кэштеу

Бұл мәселелер арасындағы тікелей параллель компьютер ғылымындағы шешімдерді үй жағдайында саналы түрде қолдануға мүмкіндік бар екенін білдіреді.

Файлдарды реттеу және жинау

Бірақ компьютер ғылымы бізге тиімділік мамандары бере алмайтын нәрсені береді: кепілдіктер.

Ногучи файлдау жүйесін іс жүзіндегі LRU принципінің мысалы ретінде тану бізге оның тек тиімді ғана емес, шын мәнінде оңтайлы екенін айтады.

Сіз оны әлдеқашан ұйымдастырып қойғансыз.

Ұмыту қисығы

Оның нәтижелері жадтың уақыт өте келе қалай өшетінін көрсететін графикті сызып шықты, ол бүгінде психологтар арасында «ұмыту қисығы» (the forgetting curve) деп аталады.

Жақсы адам жадының кілті — жақсы компьютер кэшінің кілтімен бірдей: болашақта қай элементтердің қажет болу ықтималдығы жоғары екенін болжау.

Басқаша айтқанда, шындықтың өзі Эббингауз қисығын қайталайтын статистикалық құрылымға ие.

Тәжірибе озбырлығы

Амалсыз, жад неғұрлым үлкен болса, одан ақпаратты іздеуге және алуға соғұрлым көп уақыт кетеді.

Егер жадтың негізгі мәселесі сақтау емес, ұйымдастыру болса, онда бұл біздің қартаюдың ақыл-ой қабілеттеріне әсері туралы түсінігімізді өзгертуі тиіс.

*Белгісіз себептермен, «Менің жеке Айдахом» (My Own Private Idaho) фильмін Мэн штатында бәрінен де қатты жақсы көреді.

5 Жоспарлау (Scheduling)

Бірінші кезектегі маңызды істер

Әрбір гурудың өз жүйесі бар және кімді тыңдау керектігін білу қиын.

Уақытты жұмсау ғылымға айналуда

Мерзімдермен жұмыс істеу

Істерді ретке келтіру

Аяқталу уақыттарының қосындысын азайту өте қарапайым оңтайлы алгоритмге әкеледі, ол «Ең қысқа өңдеу уақыты» (Shortest Processing Time) деп аталады: әрқашан қолыңыздан келетін ең жылдам тапсырманы орындаңыз.

Мәселелерімізді таңдау

Мәселелерді таңдау

Прокрастинацияға жаңа көзқарас

Басымдық инверсиясы және сабақтастық шектеулері

Ал енді ол прокрастинациямен айналысып жатты.

Кедергі

Бәрін таста: Преемпция және белгісіздік

Болашақ бұлыңғыр болғанда, сізге күнтізбенің қажеті жоқ — тек істер тізімі (to-do list) жеткілікті.

Преемпция тегін емес: Контекстті ауыстыру

Трэшинг

Егер сіз әлі де өз басымдықтарыңызды сақтағыңыз келсе, өнімділікті қайтару үшін жасауға болатын басқа, тіпті одан да қызықты мәміле бар.

Үзілістерді біріктіру (Interrupt Coalescing)

Біз intractable (шешілуі қиын немесе есептеуге келмейтін) мәселелерді 8-тарауда егжей-тегжейлі талқылаймыз.

Жағдай бұл сан көрсеткендей нашар емес, өйткені бұған бірнеше машинаны қамтитын кестелеу мәселелері де кіреді — бұл өз күнтізбеңізді басқарудан қарағанда, қызметкерлер тобын басқаруға көбірек ұқсайды.

6. Бейес ережесі

Болашақты болжау

Оқиға он сегізінші ғасырдағы Англияда, сол кездегі ұлы математикалық ақыл-ой иелері, тіпті дінбасылар үшін де тартымды болған зерттеу саласы — құмар ойындардан басталады.

Преподобный Бейеспен бірге кері логика жүргізу

Осыдан 250 жылдан астам уақыт бұрын, шағын деректерден болжам жасау мәселесі Англияның көркем курорттық қалашығы Танбридж Уэллстегі пресвитериандық министр, преподобный Томас Бейесті қатты мазалады.

Бұл сұрақтың жауабы — барлық әртүрлі мүмкін гипотезаларды қалайша бір нақты күтуге айналдыру керек екенін — бірнеше жылдан кейін француз математигі Пьер-Симон Лаплас табады.

Лаплас заңы

Бейес ережесі және бастапқы сенімдер

Коперник принципі

Бейес Коперникпен кездеседі

Ақпаратсыз априорлы ықтималдық — бұл зерттелетін нысан туралы алдын ала ешқандай мәлімет немесе басымдық болмаған жағдайда қолданылатын бастапқы ықтималдық.

Байес ережесі осы ықтималдықтардың барлығын біріктіргенде — ықтималдығы жоғары қысқа мерзімдер орташа болжамды төмен түсіреді, ал ықтималдығы төмен болса да мүмкін болатын ұзақ мерзімдер оны жоғары көтереді — Коперник принципі пайда болады: егер біз бір нәрсенің қанша уақытқа созылатынын болжағымыз келсе және ол туралы басқа ешқандай біліміміз болмаса, біз жасай алатын ең жақсы болжам — ол осы уақытқа дейін қанша тұрса, тағы сонша уақыт тұрады деген тұжырым.

Соғыс кезіндегі статистикалық болжамдардың дәлдігі барлау мәліметтерінен асып түсіп, математикалық модельдердің шынайы күшін көрсетті.

Шынайы әлемдегі априорлы ықтималдықтар

Кең мағынада әлемде заттардың екі түрі бар: қандай да бір «табиғи» мәнге ұмтылатын (немесе соның айналасында топтасатын) заттар және олай істемейтін заттар.

... және олардың болжау ережелері

Әртүрлі априорлы үлестірімдер және олардың болжау ережелері.

Қандай үлестіріммен жұмыс істеп жатқаныңызды білу үлкен айырмашылық тудыруы мүмкін.

Кішігірім деректер және сана

Адамдардың түйсігі Байес статистикасымен таңқаларлықтай үйлеседі, бұл біздің күнделікті тәжірибеден жинақтаған бай априорлы біліміміздің арқасында.

Біздің болжамдарымыз өзіміз туралы не айтады?

Механикалық көбею дәуіріндегі априорлы білімдер

*Мұнда белгілі бір ирония бар: уақыт туралы сөз болғанда, біздің келуімізде ешқандай ерекшелік жоқ деп есептеу, ақыр соңында өзімізді дәл орталықта деп елестетуімізге әкеледі.

7 Оверфиттинг

Қашан азырақ ойлану керек

Франклин тіпті бұл туралы есептеу сияқты ойлап, былай деді: «Мен теңдеудің бұл түрінен "Моральдық немесе ақыл-парасат алгебрасы" деп атауға болатын үлкен артықшылық таптым».

Күрделілікке қарсы дәлелдер

Анықталғандай, бәрі соншалықты оңай емес.

Деректерге табыну

Нәтижесінде, көбірек факторларды ескеру және оларды модельдеуге көбірек күш жұмсау бізді қате нәрсені оңтайландыруға әкелуі мүмкін — бұл деректердің артындағы үлкен күшке емес, деректердің «қола жыланына» сиынумен тең.

Әр жерде кездесетін артық бейімделу

Артық бейімделу туралы білгеннен кейін, оны барлық жерден көретін боласыз.

Артық бейімделуді анықтау: Кросс-валидация

Артық бейімделумен қалай күресуге болады: Күрделілік үшін айыппұл салу

Эвристиканың артықшылығы

Тарихтың салмағы

Қашан аз ойлану керек

--- *Математикаға бейім жандар үшін, бұл — айнымалылар коэффициенттерінің абсолюттік мәндерінің қосындысы.

8. Релаксация (Relaxation)

Еркіндік беріңіз

Оңтайландырудың қиындығы

Маршрутты жоспарлау мәселесі 1930-жылдарға дейін математикалық қауымдастықтың назарын аударған жоқ, бірақ кейін ол ерекше қарқынмен зерттеле бастады. Математик Карл Менгер 1930 жылы «пошташы есебі» (маршрутты оңтайландырудың алғашқы нұсқаларының бірі) туралы айтып, барлық мүмкін нұсқаларды кезекпен тексеріп шығудан басқа оңайырақ шешім белгісіз екенін атап өтті. Хасслер Уитни бұл мәселені 1934 жылы Принстондағы баяндамасында көтерді, ол жерде бұл есеп әріптесі, математик Меррилл Флудтың жадында берік сақталып қалды (есіңізде болса, 1-тарауда ол «хатшы есебінің» алғашқы шешімін таратушы ретінде де аталған болатын). Флуд 1940-жылдары Калифорнияға көшкенде, бұл есепті RAND институтындағы әріптестеріне таратты, ал мәселенің қазіргі танымал атауы алғаш рет 1949 жылы математик Джулия Робинсонның мақаласында жарық көрді. Есеп математикалық ортада кеңінен тараған сайын, оның қиындығы туралы дақпырт та өсе берді. Ол заманның көптеген ұлы ақыл-ой иелері осы есепке бас қатырды, бірақ ешкім айтарлықтай ілгерілей алмағандай көрінді.

Сұрақ мынада: бұдан жақсырақ нәтижеге қол жеткізуге үміт бар ма?

Бұл сөздер көріпкелдік болып шықты.

Қиындықты анықтау

Жай ғана босаңсыңыз (Just Relax)

Сұр түстің сансыз реңктері: Үздіксіз жеңілдету

Жай ғана жылдамдықты асырғаны үшін айыппұл: Лагранж жеңілдетуі

Осы талаптардың бәрін ескере отырып, Триктің спорттық кестені есептеуі көбінесе осы қатаң шектеулердің кейбірін «жұмсарту» (softening) арқылы ғана мүмкін болады.

Босаңсуды үйрену

Кем дегенде, босаңсуды үйренбесек, көмектеспейді.

9 Кездейсоқтық

Қашан кездейсоқтыққа сену керек?

Самплинг

Осындай күрделі комбинаторлық есептеулерді жасап көріп, одан бас тартқаннан кейін, Улам өзінің қарапайымдылығымен тамаша басқа тәсілге тоқтады: жай ғана ойынды ойнау.

Рандомизацияланған алгоритмдер

Ол зерттеу бағытын ең ескі мәселелердің бірінен тапты: жай сандарды (тек өзіне және бірге бөлінетін сандар) қалай анықтауға болады?

Қазіргі уақытта «Миллер-Рабин жай сандық тесті» деп аталатын бұл әдіс тіпті алып жай сандарды да кез келген дәрежедегі сенімділікпен тез анықтауға мүмкіндік береді.

Сэмплингті мадақтау

Дегенмен, біз кездейсоқтыққа жүгінбейтін жағдайлар бар, бірақ, бәлкім, жүгінуіміз керек шығар.

«Бұл сізбен бөлісетін ақпараттың барлық түрлеріне деген сеніміңізді арттырады және тіпті басқа ұйымдардан да жоғары талаптарды талап етуге итермелейді деп үміттенеміз», — деп жазады Ланге.

Үш жақты ымыра

Жетістікке жеткен адамды, әсіресе әдебиетте және Шекспирде өте жоғары деңгейде болған қасиет бірден ойыма келді — мен «Негативті қабілетті» айтамын, яғни адам фактілер мен себептерге ашуланбай-ақ, белгісіздіктерде, жұмбақтарда, күмәндарда қала алған кезде.

— ДЖОН КИТС

Абсолютті сенімділік деген ұғым жоқ, бірақ адам өмірінің мақсаттары үшін жеткілікті сенімділік бар.

— ДЖОН СТЮАРТ МИЛЛ

Төбелер, аңғарлар және тұзақтар

Өзен ирелеңдейді, өйткені ол ойлай алмайды.

— РИЧАРД КЕННИ

Қателік ландшафты: шешім сапасының түрлі мүмкіндіктер бойынша қалай өзгеретінін көрсетеді.

Жергілікті максимумнан шығу

Имитациялық күйдіру

Кездейсоқтық, Эволюция және Шығармашылық

Лурия өзінің әріптестерінің бірінің ойын автоматын (slot machine) ойнап жатқанын бақылап тұрды:

Бір жағынан әлеуметтік эволюция фактілері мен нәсілдің интеллектуалдық өсуі, екінші жағынан Мистер Дарвин баяндаған зоологиялық эволюция арасында менің білуімше, бұрын байқалмаған таңқаларлық параллель бар.

Дамитын жаңа тұжырымдамалар, эмоциялар мен белсенді тенденциялар бастапқыда кездейсоқ бейнелер, қиялдар, өте тұрақсыз адам миының функционалдық белсенділігіндегі стихиялық вариациялардың кездейсоқ туындылары түрінде пайда болады, оларды сыртқы орта жай ғана растайды немесе жоққа шығарады, қабылдайды немесе қабылдамайды, сақтайды немесе жояды — қысқасы, молекулалық апаттардан туындаған морфологиялық және әлеуметтік вариацияларды таңдағаны сияқты таңдайды.

Кездейсоқ дірілдеу, жақтаудан шығу және кеңірек ауқымға назар аудару — жергілікті жақсы нәрселерден бас тартып, жаһандық оңтайлы нәрсеге ұмтылуға қайта оралудың жолын ұсынады.

Егіз жай сандар — бұл екеуі де жай сан болатын қатар тұрған тақ сандар, мысалы 5 және 7.

Біз сайттан ең бірінші оқиғаны әдейі алғанымызды ескеріңіз — яғни, біз бөлісу үшін біреуін таңдап алу үшін олардың бәрін оқып шыққан жоқпыз, бұл мақсатқа қайшы келер еді.

10 Желілік өзара әрекеттесу

Біз қалай байланысамыз

Ал мәтіндік хабарлама (SMS) 1992 жылы 3 желтоқсанда мерекелік тілекпен басталды: Sema Group Telecoms маманы Нил Папворт Vodafone қызметкері Ричард Джарвисті келе жатқан «Рождество мерекесімен» құттықтады.

«Lo» (мінекей) — Клайн байқаусызда Ескі Өсиеттегідей салтанатты әрі маңызды дыбыс шығарып алды.

Пакеттерді коммутациялау

Растау (Acknowledgment)

Визиантия генералдарының мәселесі — бұл дизайнның күрделілігі емес, бұл теориялық тұрғыдан «мүмкін еместіктің» нәтижесі.

Сонымен, біз сенімсіз адаммен немесе компьютермен қалай әрекет етуіміз керек?

Экспоненциалды шегініс: Кешірім алгоритмі

Шығыс деректері:

Ағынды бақылау және кептелістің алдын алу

Қосу мен көбейтудің арасындағы мұндай қатаң айырмашылық табиғатта сирек кездесетіндей көрінгенімен, TCP ирегі мүмкіндігінше көп нәрсені қауіпсіз алуға тырысатын әртүрлі салаларда кездеседі.

Жалпы алғанда, AIMD біз белгісіз әрі құбылмалы жағдайларда шектеулі ресурстарды бөлуге тырысатын өмірлік жағдайларға арналған тәсілді ұсынады.

Кері арналар: Тіл біліміндегі ағынды бақылау

Bufferbloat: Мәселе кідірісте, ақымағым

Кешіккеннен көрі болмағаны жақсы

11 Ойындар теориясы

Басқалардың санасы

Компьютер ғылымы бұған не дейді?

Рекурсия

Сонымен, Нэш деген не?

Тепе-теңдікке жету

Жақсы немесе жаман доминантты стратегиялар

Бұл дәстүрлі ойын теориясының негізгі түсініктерінің бірі ретінде қалыптасты: өз мүддесі үшін рационалды әрекет ететін ойыншылар жиынтығы үшін тепе-теңдік — бұл ойыншылар үшін іс жүзінде ең жақсы нәтиже болмауы мүмкін.

Ортақ пайдалану трагедиясы

Механизмдер дизайны: Ойынды өзгерту

Мұндағы таңғаларлық әрі қуатты нәрсе — біз әрбір жағымсыз нәтижені (бір жағынан өлім, екінші жағынан салықтар) нашарлату арқылы тепе-теңдікті өзгертіп, барлығының өмірін жақсарта аламыз.

Эволюция арқылы механизмдер дизайны

Ашу-ыза сияқты, жанашырлық, кінә сезімі және махаббат та осындай рөл атқарады.

Махаббат — тұтқын дилеммасы ретінде

Ақпараттық каскадтар: Көпіршіктердің трагедиялық ұтымдылығы

Өзіңе адал есептеу

*Шын мәнінде, бұл барлық заманауи компьютерлердің бастауы — дәл осы Halting problem (тоқтау мәселесі — алгоритмнің шексіз циклге түсетінін немесе тоқтайтынын анықтау) Тьюрингті есептеуді біз қазір Turing machine (Тьюринг машинасы — есептеулердің абстрактілі математикалық моделі) деп атайтын құрылғы арқылы ресми түрде анықтауға итермеледі.

Қорытынды

Есептеуіш мейірімділік

Бұл әрекеттердің ешқайсысы міндетті түрде «сыпайы» емес, бірақ олардың барлығы өзара әрекеттесудің есептеуіш шығынын айтарлықтай төмендетуі мүмкін.

Есептеуіш мейірімділік — бұл тек мінез-құлық принципі емес; бұл сонымен қатар дизайн принципі.

Есептеуіш субсидия

Мейрамханада «spinning» саясаты бос үстелдерді тезірек толтырады, бірақ бұл кезде тозатын «Орталық процессорлар» — бұл жалықтырғыш, бірақ зейін қоюды қажет ететін қырағылықтың тұзағына түскен клиенттердің санасы.

Ескертпелер

КІРІСПЕ

төрт мың жылдық шумерлік қыш тақтайша: Толық талдау Кнуттың «Ежелгі Вавилон алгоритмдері» еңбегінде берілген.

бұғы мүйізінің ұшымен ұру: Бұл әдіс «жұмсақ балғамен соғу» (soft hammer percussion) деп аталады.

«Ғылым — бұл ойлау тәсілі»: Саган, Броканың миы.

біз қисынсызбыз және қателікке бой алдырғышпыз: Мысалы, Гиловичтің «Біз солай емес нәрсені қалай білеміз» (How We Know What Isn’t So); Ариели мен Джонстың «Болжамды қисынсыздық» (Predictably Irrational); және Маркустың «Клуге» (Kluge) еңбектерін қараңыз.

1. ОҢТАЙЛЫ ТОҚТАТУ

«Барлық мәсіхшілер бастаса да»: Кеплердің 1613 жылғы 23 қазандағы «белгісіз ақсүйекке» жазған хатынан; мысалы, Баумгардтың «Иоганн Кеплер» еңбегін қараңыз.

Кез келген оңтайлы тоқтау (белгілі бір әрекетті тоқтату үшін ең жақсы уақытты таңдау) мәселесінде: Оңтайлы тоқтау математикасы туралы көбірек білу үшін Фергюсонның «Оңтайлы тоқтау және оның қолданылуы» (Optimal Stopping and Applications) еңбегі тамаша анықтамалық болып табылады.

Мозер тағы бір ақпарат қосты — билеттердің 0 мен 1 аралығындағы кез келген мәнді қабылдау ықтималдығы бірдей екендігі.

Бірнеше үміткерлерді қарастыру идеясы — кейіпкерлердің жынысы ауыстырылған күйінде — Гарднердің 1960 жылғы Гугол ойыны туралы бағанында тиісінше орын алды.

Мостеллер мәселе туралы естігенін еске алды: Гилберт пен Мостеллер, «Тізбектің максимумын тану».

Ратгерс университетінен Роджер Пинкхэм былай деп жазды: Роджер Пинкхэмнің Мартин Гарднерге жазған хаты, 29 қаңтар, 1960 жыл.

Флудтың компьютерлік ғылымға әсері: Куктың «Коммивояжердің соңынан» (In Pursuit of the Traveling Salesman); Паундстоунның «Тұтқынның дилеммасы» (Prisoner’s Dilemma); және Флудтың «Жұмсақ жаңалықтар» (Soft News) еңбектерін қараңыз.

осы уақытқа дейін көргендеріңіздің ішіндегі ең жақсысы: Әдебиетте біз «осы уақытқа дейінгі ең жақсы» (best yet) деп атайтын үміткерлерді (біздіңше, бұл сәл түсініксіз) «кандидаттар» деп атайды.

мәселенің қызықты математикалық симметрияларының бірі: Математиктер Джон Гилберт пен Фредерик Мостеллер бұл симметрияны «қызықты» деп атайды және оны Гилберт пен Мостеллердің «Тізбектің максимумын тану» еңбегінде сәл кеңірек талқылайды.

«Жыныстар арасындағы құмарлық»: Мальтус, «Халық санының принципі туралы эссе».

«алғаш сүйіскен адамыма тұрмысқа шықтым»: Көптеген дереккөздерге телінеді, мысалы, Томас, «Ақ үйдің алдыңғы қатарында».

37% ережесі 26,1 жасты берді: Сөз салу үшін кем дегенде 26 жасқа дейін күтуді талдау (18-ден 40-қа дейінгі жолдың 37%-ы) алғаш рет Линдлидің «Динамикалық бағдарламалау және шешім қабылдау теориясы» еңбегінде кездеседі, Трик бұл идеяны осы жерден алған болуы керек.

Бас тарту мен қайта шақырудың бұл интеграцияланған формуласы Петручеллидің «Белгісіздік бар ең жақсы таңдау мәселелері» еңбегінен алынған, дегенмен бұрынғы үміткерлерді қайта шақыру мәселесін бұрынырақ Янг «Кездейсоқ тізбектің максимумын тану» еңбегінде қарастырған болатын.

«Тәжірибені жинақтаудың қажеті жоқ»: Гилберт пен Мостеллер, «Тізбектің максимумын тану».

Үй сату да осыған ұқсас: Үй сату мәселесі Сакагучидің “Dynamic Programming of Some Sequential Sampling Design”, Чоу мен Роббинстің “A Martingale System Theorem and Applications” және “On Optimal Stopping Rules” еңбектерінде талданған. Біз ұсыныстардың шексіз көп болуы мүмкін жағдайына назар аударамыз, бірақ бұл авторлар ықтимал ұсыныстардың саны белгілі және шекті болған кездегі оңтайлы стратегияларды да ұсынады (олар азырақ консервативті — егер мүмкіндіктеріңіз шекті болса, шегіңіз төменірек болуы керек). Шексіз жағдайда сіз келесі ұсынысты күтудің күтілетін мәніне негізделген шекті белгілеуіңіз керек және сол шектен асатын алғашқы ұсынысты қабылдауыңыз қажет.

және оны p үшін шешу бізге мынадай жауап береді:

графикте көрсетілгендей.

“Бізге түскен алғашқы ұсыныс тамаша болды”: Лаура Альберт Маклэй, жеке сұхбат, 16 қыркүйек, 2014 жыл.

Адамдардың қалай жұмыс іздейтінін модельдеу үшін: Жұмыс іздеуді оңтайлы тоқтату мәселесі ретінде тұжырымдау Стиглердің “The Economics of Information” және “Information in the Labor Market” еңбектерінде қарастырылады. Макколл “Economics of Information and Job Search” еңбегінде үй сату мәселесінің шешіміне балама модельді қолдануды ұсынды, ал Липпман мен Макколл “The Economics of Job Search” еңбегінде бұл модельдің бірнеше кеңейтілімдерін талқылайды. Хатшы мәселесі көптеген нұсқаларға негіз болғаны сияқты, экономистер де бұл қарапайым модельді шынайырақ ету үшін әртүрлі тәсілдермен жетілдірді: бір күнде бірнеше ұсыныстың түсуіне жол беру, сатушының шығындарын түзету және іздеу кезіндегі экономикадағы ауытқуларды ескеру. Жұмыс іздеу контекстіндегі оңтайлы тоқтау туралы жақсы шолуды Роджерсон, Шимер және Райттың “Search-Theoretic Models of the Labor Market” еңбегінен табуға болады.

Енді ол сіздің шегіңізден жоғары болмайды: Жұмыс іздеу мәселесіне шолу жасағанда айтылғандай: “Бұрын қабылданбаған ұсыныстарды қайта қарау мүмкін емес деп есептеңіз, бірақ бұл шын мәнінде шектеу емес, өйткені мәселе стационарлы, сондықтан бүгін қолайлы емес ұсыныс ертең де қолайлы болмайды” (сонда).

“Оқытушылар құрамына арналған тұрақ”: Кларк Керр, “Education: View from the Bridge”, Time, 17 қараша, 1958 жыл.

“Күтілетін көлік қозғалысын жоспарлаңыз”: Дональд Шуп, жеке хат-хабар, маусым 2013 жыл.

Бұл негізгі сценарийге әртүрлі түзетулер: Тамаки “Adaptive Approach to Some Stopping Problems” еңбегінде орынның бос болу ықтималдығын орналасқан жеріне қарай өзгертуге мүмкіндік берді және бұл ықтималдықтарды жол-жөнекей қалай бағалауға болатынын қарастырды. Тамаки “Optimal Stopping in the Parking Problem with U-Turn” еңбегінде кері бұрылу мүмкіндігін қосты. Тамаки “An Optimal Parking Problem” еңбегінде ДеГрут моделінің кеңейтілімін қарастырды, мұнда тұрақ мүмкіндіктері орындардың дискретті жиынтығы ретінде қарастырылмайды. Сакагучи мен Тамаки “On the Optimal Parking Problem in Which Spaces Appear Randomly” еңбегінде осы үздіксіз тұжырымдаманы қолданды және межелі жердің белгісіз болуына жол берді. Маккуин мен Миллер “Optimal Persistence Policies” еңбегінде кварталды айналып өтуге мүмкіндік беретін мәселенің үздіксіз нұсқасын дербес қарастырды.

“Мен велосипедпен жүремін”: Дональд Шуп, жеке сұхбат, 7 маусым, 2013 жыл.

Forbes журналы Борис Березовскийді анықтады: Forbes, “World’s Billionaires”, 28 шілде, 1997 жыл, 174-бет.

Олигархтардың жаңа класының бірі: Пол Хлебников, “The Rise of an Oligarch”, Forbes, 9 қыркүйек, 2000 жыл.

“Бір рет қана, бірақ басынан ұру керек”: Владимир Путин, француздық Le Figaro газетіне берген сұхбатында, 26 қазан, 2000 жыл.

Толығымен хатшы мәселесіне арналған кітап: Березовский мен Гнедин, “Problems of Best Choice.”

Бірнеше түрлі кейіпте талданған: Алда тұрғанда тоқтау мәселесіне келудің әртүрлі жолдары бар. Біріншісі — жеңістер тізбегінің ұзақтығын барынша арттыру. Сіз тиын тастап жатырсыз деп есептеңіз, оның елтаңба жағы түсу ықтималдығы p. Сіз тиынды әр тастау мүмкіндігі үшін c доллар төлейсіз, елтаңба түскенде 1.00 доллар аласыз, бірақ сан жағы түскенде жинаған барлық табысыңыздан айырыласыз. Тиын тастауды қашан тоқтату керек? 1972 жылы Норман Старр көрсеткендей, жауап — r рет елтаңба түскеннен кейін тоқтау, мұндағы r — pʳ⁺¹ ≤ c шартын қанағаттандыратын ең кіші сан. Сондықтан, егер бұл p = 1/2 болатын кәдімгі тиын болса және оны тастау 0.10 доллар тұрса, сіз қатарынан төрт рет елтаңба түскен бойда тоқтауыңыз керек. Елтаңбалар сериясын талдау Старрдың “How to Win a War if You Must” еңбегінде кездеседі, мұнда ол қажу соғысында жеңіске жету моделі ретінде ұсынылған. Толығырақ талдау Фергюсонның “Stopping a Sum During a Success Run” еңбегінде берілген.

Оны оққағар тапқан: Қараңыз, мысалы, “Boris Berezovsky ‘Found with Ligature Around His Neck’”, BBC News, 28 наурыз, 2013 жыл, http://www.bbc.com/news/uk-21963080.

Мәйітті тексерудің ресми қорытындысы: Қараңыз, мысалы, Reuters, “Berezovsky Death Consistent with Hanging: Police”, 25 наурыз, 2013 жыл, http://www.reuters.com/article/2013/03/25/us-britain-russia-berezovsky-postmortem-idUSBRE92O12320130325.

“Березовский берілмес еді”: Хоффман, “The Oligarchs”, 128-бет.

Егер сіз мұны адамдарда ақша көбейген сайын оның құндылығы төмендейді деп есептеу арқылы шешуге болады деп ойласаңыз — яғни ақшалай сыйақыны үш есе арттыру адамдардың сол ақшаға беретін пайдалылығын үш есе арттырмауы мүмкін — онда қарапайым амалы бар: сіз әлі де пайдалылығы үш еселенетін сыйақылар ұсыну арқылы оңтайлы тоқтау ережесі жоқ ойынды ала аласыз. Мысалы, егер сіз ақшаға беретін пайдалылық ақша сомасының логарифмдік функциясы ретінде өссе, онда ойын “куб немесе ештеңе” болады — келесі бәсте алуға болатын ақша мөлшері әр жеңіс сайын үшінші дәрежеге көтеріледі.

Хатшы туралы классикалық мәселеге ең жақын келеді: Сил мен Рапопорт, “Sequential Decision Making with Relative Ranks.”

“Табиғатымнан өте шыдамсызбын”: Амнон Рапопорт, жеке сұхбат, 11 маусым, 2013 жыл.

Сил мен Рапопорт көрсеткендей: Сил мен Рапопорт, “Sequential Decision Making with Relative Ranks.”

Оңтайлы тоқтау туралы негізгі оқулық: Бұл Фергюсонның “Optimal Stopping and Applications” кітабы.

2. ЗЕРТТЕУ/ПАЙДАЛАНУ

“Сіз кеңістік табуға тырысасыз”: Скотт Плагенхоф, жеке сұхбат, 5 қыркүйек, 2013 жыл.

Көпқолды бандиттерге толық кіріспе Берри мен Фристедтің “Bandit Problems” еңбегінде берілген. Бұл тарауда біздің назарымыз әрбір “қолы” әртүрлі ықтималдықпен, бірақ барлық қолдарда бірдей пайда мөлшерімен пайда әкелетін немесе әкелмейтін бандиттерге аударылады. Бұл әдебиетте Бернулли бандиті деп аталады, өйткені тиын тастауды сипаттайтын ықтималдық үлестірімі Бернулли үлестірімі деп аталады (XVII ғасырдағы швейцариялық математик Якоб Бернуллидің құрметіне). Пайданың әр түріне тән белгісіз үлестірімдері бар көпқолды бандиттердің басқа түрлері де болуы мүмкін.

Екінші машинаның іс жүзінде қаншалықты жақсы болуы мүмкін екендігі: Күтілетін мәні жоғары қолды тартудың “қысқа мерзімді” стратегиясы кейбір жағдайларда іс жүзінде оңтайлы болып табылады. Братт, Джонсон және Карлин “On Sequential Designs for Maximizing the Sum of N Observations” еңбегінде екіқолды бандит үшін пайда алу ықтималдықтары (бірі үшін p₁, екіншісі үшін p₂) p₁ + p₂ = 1 шартын қанағаттандырса, онда бұл стратегияның оңтайлы екенін көрсетті. Олар бұл (p₁, p₂) жұптары (a, b) немесе (b, a) мәндерін қабылдайтын ықтималдықтар үшін де орынды болады деп болжады (яғни, егер p₁ мәні a болса, онда p₂ мәні b болады және керісінше). Мұның шындық екенін Фельдман “Contributions to the ‘Two-Armed Bandit’ Problem” еңбегінде дәлелдеді. Берри мен Фристедтің “Bandit Problems” еңбегінде қысқа мерзімді стратегиялар туралы толығырақ мәліметтер бар, соның ішінде p₁ және p₂ тек екі ықтимал мәнді қабылдаумен шектелгенде (мысалы, p₁ немесе p₂ екеуі де немесе біреуі 0.4 немесе 0.7 болуы мүмкін, бірақ біз бұл мүмкіндіктердің қайсысы шын екенін білмейміз) ең жоғары күтілетін мәнді таңдау оңтайлы екенін көрсететін нәтиже бар.

“X-адамдардың алтыншы бөлімі”: Ник Аллен, “Hollywood makes 2013 the year of the sequel”. Сондай-ақ қараңыз: http://www.shortoftheweek.com/2012/01/05/has-hollywood-lost-its-way/ және http://boxofficemojo.com/news/?id=3063.

«Өсіп келе жатқан шығындар арасында қысылған»: “Hollywood: Split Screens,” Economist, 23 ақпан, 2013 жыл.

Роббинс 1952 жылы дәлелдеді: Роббинстің «Some Aspects of the Sequential Design of Experiments» еңбегі Win-Stay, Lose-Shift (Жеңсең — қал, жеңілсең — ауыс: сәтті таңдауды қайталап, сәтсіздіктен кейін басқа нұсқаға көшу) алгоритмін таныстырады.

«Ымырасыздықтың символы»: Гиттинстің «Bandit Processes and Dynamic Allocation Indices» еңбегіне кіріспе.

«Өте жақсы жуықтау болар еді»: Джон Гиттинс, жеке сұхбат, 27 тамыз, 2013 жыл.

Deal or No Deal: Бұл телешоудың әлемдік нұсқалары 2000 жылы алғаш рет эфирге шыққан голландиялық «Miljoenenjacht» бағдарламасынан басталды.

Көп қарулы бандит мәселесі де сондай: Бұған дейінгі зерттеушілер де белгілі бір уақыт аралығындағы «бір қарулы бандит» мәселесінің шешімдерін тапқан болатын.

Егер ауысу құны болса: Бұл жағдай Бэнкс пен Сундарамның «Switching Costs and the Gittins Index» еңбегінде талданған.

«Өкініштер, менде олар аз болды»: Фрэнк Синатра, “My Way”, My Way (1969) альбомынан, мәтіні Пол Анканыкі.

«Өзім туралы айтсам, мен — оптимиспін»: Премьер-министр Уинстон Черчилль, сөйлеген сөзі, Лорд-мэр банкеті, Лондон, 9 қараша, 1954 жыл.

«Әрекет етіп, сәтсіздікке ұшырау — кем дегенде үйрену»: Барнард, «The Functions of the Executive».

«Өзімді 80 жаста елестеткім келді»: Джефф Безос, Academy of Achievement-ке берген сұхбаты, 4 мамыр, 2001 жыл.

«Сенімділік аралығы» ретінде белгілі: Сенімділік аралығы (статистикалық параметрдің белгілі бір ықтималдықпен табылуы мүмкін мәндер ауқымы) концепциясы Нейманның еңбектерінен бастау алады.

«Оптимистік роботтар»: Лесли Кэблинг, жеке сұхбат, 22 қараша, 2013 жыл.

57 миллион доллар қосымша қайырымдылық: Сирокер және Кумен, «A/B Testing».

A/B тестілеу келесідей жұмыс істейді: A/B тестілеу (екі нұсқаны салыстыру арқылы тиімдісін анықтау әдісі) туралы Кристианның «The A/B Test» еңбегінен және Стив Ханов пен Ноэль Уэлштің сұхбаттарынан мәлімет алынды.

Обаманың қайырымдылық жинау бетіне қатысты: Дэн Сирокер, «Президенттік сайлауда жеңіске жету үшін деректерді қалай пайдаландық» (дәріс), Стэнфорд университеті, 8 мамыр, 2009 жыл.

Өз пайдаланушыларына тікелей A/B тестілерін жүргізеді: Google алғашқы A/B тестін 2000 жылдың 27 ақпанында өткізді.

Компаниялар өз сайттарының навигациясын A/B тестінен өткізеді: Қараңыз, Сирокер және Кумен, «A/B Testing».

«Адамдарды жарнамаға қалай бастыруға болады»: Эшли Вэнс, “This Tech Bubble Is Different,” Bloomberg Businessweek, 14 сәуір, 2011 жыл.

«Ессіздіктен қираған»: Гинзберг, «Howl and Other Poems».

Онлайн коммерция жүздеген миллиардтарды қамтиды: Forrester Research бағалауы бойынша онлайн сатылымдар 2017 жылға қарай АҚШ-та 370 млрд долларға жетеді деп болжанған.

Қолданылатын ең жақсы алгоритмдер әлі де қызу талқылануда: Мысалы, Крис Стуччио «Неліктен көп қарулы бандит алгоритмдері A/B тестілеуден артық» және «Бандит алгоритмдерін қолданбаңыз — олар сіз үшін жұмыс істемеуі мүмкін» атты екі қарама-қайшы мақала жазды.

Ол Washington Star газетінде жарияланды: Жан Хеллер, “Syphilis Patients Died Untreated,” Washington Star, 25 шілде, 1972 жыл.

Белмонт есебі ретінде белгілі құжат: «Белмонт есебі: Зерттеудің адам нысандарын қорғауға арналған этикалық принциптер мен нұсқаулықтар», 18 сәуір, 1979 жыл.

Қазір өзінің қырқыншы туған күнін атап өтті: University of Michigan Health System, “U-M Health System ECMO team treats its 2,000th patient,” 1 наурыз, 2011 жыл.

«ЭКМО-ны күнделікті қолдануды ақтамады»: Уэйр мен Эпштейннің қорытындыларына сілтеме жасайтын Уэйрдің сөзі.

Әлемдегі жетекші сарапшылардың бірі: Берри өзінің 1971 жылғы докторлық диссертациясында жеңімпазда қалудың оңтайлы екенін дәлелдеді.

Қатерлі ісікті емдеудің түрлі әдістерін клиникалық сынақтан өткізу: Дон Берри, жеке сұхбат, 22 тамыз, 2013 жыл.

FDA «нұсқаулық» құжатын жариялады: FDA-ның 2010 жылғы ақпандағы «Дәрілік заттар мен биологиялық препараттарға арналған адаптивті дизайнды клиникалық сынақтар» құжаты.

Үстінде екі шамы бар қорап көрсетілді: Зерттеу Тверски мен Эдвардстың «Information Versus Reward in Binary Choices» еңбегінде сипатталған.

Әлем өзгеруі мүмкін болғанда: Наварро мен Ньюэллдің жұмыстары адамдардың шамадан тыс зерттеу (exploration) жүргізуі әлемді «мазасыз» деп қабылдауынан екенін растайтын нәтижелер береді.

«Іс жүзінде өзіндік бір үйлесімділік бар»: Торо, «Walking».

«Кола — бұл Кола»: Уорхол, «The Philosophy of Andy Warhol».

«Зерттеу мен пайдалану арасындағы тепе-теңдікті шешудің даму жолы»: Элисон Гопник, жеке сұхбат, 22 тамыз, 2013 жыл.

«Менің оқу өмірімдегі бетбұрыс кезең»: Лидия Дэвис, “Someone Reading a Book”.

Қартаю туралы алдын ала қалыптасқан түсініктерімізге күмән келтіру: Карстенсен осы бөлімде талқыланатын «әлеуметтік-эмоционалды селективтілік теориясын» ұсынды.

«Өмір бойғы сұрыптау процестері»: Карстенсен, жоғарыда аталған еңбек.

Егде жастағы адамдар әдетте көбірек қанағаттанған: Жасы ұлғайған сайын эмоционалдық әл-ауқаттың жақсаруы туралы дәлелдер Чарльз бен Карстенсеннің еңбегінде талқыланады.

3. СҰРЫПТАУ

Бөлмелесі үйіндінің ішінен шұлық суырып алды: Хиллис, «The Pattern on the Stone».

Бірақ шұлықтарды жұптауымыздың себебі — оларды қажет кезде оңай табу болса, іздеу процедурасын жақсарту арқылы сұрыптау қажеттілігін азайтуға болады.

«Құдайлардың диірмені сияқты қатесіз»: Сол жерде.

«Оны үкіметтерден басқа ешкім қолданбайды»: Austrian, Herman Hollerith кітабынан үзінді.

Холлериттің фирмасы бірнеше басқа фирмалармен бірікті: Austrian, Herman Hollerith.

IBM-нің арнайы карточка сұрыптау машиналарын артқа тастау: Сол жерде.

әлемдегі есептеу ресурстарының төрттен бірі: Knuth, [The Art of Computer Programming], 3-бет.

«сұрыптаудың бірлік құны төмендеудің орнына, жоғарылайды»: Hosken, «Evaluation of Sorting Methods».

«Mergesort сұрыптау тарихында өте маңызды»: Катажайнен және Трэфф, «A Meticulous Analysis of Mergesort Programs».

«Мен мұны тәжірибеден білемін»: Джордан Хо, жеке сұхбат, 15 қазан, 2013 жыл.

«электрондық поштаның шамадан тыс жүктелуі» туралы мақала: Whittaker және Sidner, «Email Overload».

«өмірлерінің бір бөлігін босқа өткізді»: Стив Уиттакер, жеке сұхбат, 14 қараша, 2013 жыл.

«Көгалдағы теннис турнирінде»: Доджсон, «Lawn Tennis Tournaments».

«белгісіздіктің шешілуі кешіктірілді»: Майкл Трик, жеке сұхбат, 26 қараша, 2013 жыл.

«іс жүзінде олардың кім екеніне қарамастан»: Сол жерде.

алгоритмдердегі төзімділіктің (robustness) артықшылықтарын тану: Экли, «Beyond Efficiency».

«кәсіби покер ойыншысы ретіндегі ең маңызды дағды»: Исаак Хэкстон, жеке сұхбат, 20 ақпан, 2014 жыл.

«Екі маймылды елестетіңіз»: Кристоф Нейман, жеке сұхбат, 29 қаңтар, 2014 жыл.

«әр тауыққа шаққандағы агрессивті әрекеттер көбейді»: Craig, [Aggressive Behavior of Chickens].

4. КЭШТЕУ

«Интеллектімізді практикалық қолдануда»: Джеймс, [Psychology].

«Барлық юбкаларыңызды бірге іліңіз»: Jay, [The Joy of Less].

«өте өткір сана, бірақ жады жоқтың қасы»: Davis, [Almost No Memory].

есептеудің іргелі принциптерінің бірі: Біздің Caching (кэштеу — жиі қолданылатын деректерді жылдам қолжетімді жерде сақтау) тарихымыз Hennessy және Patterson-ның [Computer Architecture] еңбегіне негізделген, онда компьютер дизайнындағы заманауи кэштеу әдістері де өте жақсы баяндалған.

электрлік «жад органы»: Burks, Goldstine, және von Neumann, [Preliminary Discussion of the Logical Design of an Electronic Computing Instrument].

«сөздерді өзіне автоматты түрде жинайды»: Wilkes, «Slave Memories and Dynamic Storage Allocation».

IBM 360/85 суперкомпьютерінде іске асырылды: Conti, Gibson, және Pitkowsky, «Structural Aspects of the System/360 Model 85».

Процессорлардағы транзисторлар саны әр екі жыл сайын екі есе артады: Мурдың 1965 жылғы «Cramming More Components onto Integrated Circuits» мақаласындағы бастапқы болжамы жыл сайын екі еселену болатын; 1975 жылы ол мұны «Progress in Digital Integrated Electronics» мақаласында әр екі жыл сайын екі еселену деп өзгертті.

«сөздер онда шексіз сақталмайды»: Wilkes, «Slave Memories and Dynamic Storage Allocation».

Сынақтарда бұл алгоритмдердің барлығы LRU-дан асып түсетінін көрсетті.

«он екі жыл — бұл шек»: Элизабет Дюпюи, жеке сұхбат, 16 қыркүйек, 2014 жыл.

«қашықтық маңызды»: Лудин, «Akamai».

«Кэштеу — бұл өте айқын нәрсе»: Джон Хеннесси, жеке сұхбат, 9 қаңтар, 2013 жыл.

«менің алдыңғы киім шкафымның еденіндегі жәшік»: Morgenstern, [Organizing from the Inside Out].

«диванның артындағы шаңсорғыштың қосымша қаптары»: Jones, [Keeping Found Things Found].

когнитивтік тұрғыдан іздеу жүйелері: Қараңыз: Belew, [Finding Out About].

киім ілгішті (valet stand) қолдануды ұсынды: Рик Белью, жеке сұхбат, 31 қазан, 2013 жыл.

«менің әдісімдегі өте іргелі принцип»: Юкио Ногучи, жеке сұхбат, 17 желтоқсан, 2013 жыл.

Өздігінен ұйымдастырылатын тізімдер туралы негізгі ғылыми еңбек: Sleator және Tarjan, «Amortized Efficiency of List Update and Paging Rules», ол сондай-ақ LRU (Least Recently Used — ең ұзақ уақыт қолданылмаған элементті бірінші өңдеу принципі) принципінің теориялық қасиеттері бойынша ең анық нәтижелерді берді.

«Қаласаңыз, бұл Құдайдың алгоритмі»: Роберт Тарьян, жеке сұхбат, 17 желтоқсан, 2013 жыл.

Егер сіз LRU принципін ұстансаңыз: LRU принципінің өздігінен ұйымдастырылатын тізімдерге бұл қолданылуы Move-to-Front (алдыға жылжыту) алгоритмі ретінде белгілі.

«Мен сол құрылымның алдымда жайылғанын көрдім»: Anderson, «The Adaptive Character of Thought».

Адамның үш ортасын талдады: Адам жады ортасын талдау Anderson және Schooler-дің «Reflections of the Environment in Memory» еңбегінде берілген.

«Адам жадының алдында тұрған міндетті бағалай алмау»: Сонында.

«Егер сіз қаланы үлкейтсеңіз»: Джон Хеннесси, жеке сұхбат, 9 қаңтар, 2014 жыл.

5. ЖОСПАРЛАУ (SCHEDULING)

«Күндерімізді қалай өткізсек»: Dillard, «The Writing Life».

«Кітап жазу, соғыс жүргізу сияқты»: Lawler, «Old Stories».

Екі минут немесе одан аз уақыт алатын кез келген тапсырма: Allen, «Getting Things Done».

Алдымен өзінің әлеуметтік кездесулерін жоспарлау: Fiore, «The Now Habit».

«Аяқталмаған тапсырманың мәңгілік мазаны алуы»: Уильям Джеймс, Карл Штумпфқа хатында, 1 қаңтар, 1886 жыл.

Істерді әдейі бірден істемеу: Partnoy, «Wait».

Бұл мәселенің шешілуі мүмкін екендігі туралы алғашқы ишара: Джонсонның маңызды нәтижесі (қазіргі таңда «flowshop» жоспарлауы деп аталатын, жұмыстар бір машинадан екіншісіне ауысатын жағдай) «Optimal Two- and Three-Stage Production Schedules with Setup Times Included» еңбегінде жарияланды.

Жануарлардың азық іздеу зерттеулерінде кездеседі: Stephens және Krebs, «Foraging Theory».

Обсессивті-компульсивті вампир: Бұл «Bad Blood» атты 5-маусымның 12-сериясы, алғаш рет 1998 жылдың 22 ақпанында көрсетілді.

«Егер сен тез тұтанғыш болсаң және аяғың болса»: Хедбергтің әңгімесін оның 1999 жылғы «Strategic Grill Locations» комедиялық альбомынан табуға болады.

«Ең маңызды нәрселер»: Бұл дәйексөздің ағылшын тіліндегі алғашқы көрінісі Covey-дің «How to Succeed with People» еңбегінде Гётеге телінген, бірақ сілтемесіз берілген.

«Мен күн сайын істерімді осылай бітіремін»: Лаура Альберт Маклей, жеке сұхбат, 16 қыркүйек, 2014 жыл.

«Ген бір нәрсені кейінге қалдырып жүр еді»: Ян Карел Ленстра, жеке сұхбат, 2 қыркүйек, 2014 жыл және жеке хат-хабарлар.

Лоулер қызықты, айналмалы жолмен жүрді: Лоулердің өмірбаяны Lawler-дің «Old Stories» және Lenstra-ның «The Mystical Power of Twoness» еңбектерінен алынған.

Кестені соңынан басына қарай құру: Лоулердің ең үлкен кешігу мәселесіндегі басымдық шектеулерін талдауы Lawler-дің «Optimal Sequencing of a Single Machine Subject to Precedence Constraints» еңбегінде берілген.

Әлі де «Ең ерте орындалу мерзімі» (EDD) алгоритмінің үзу нұсқасы: Ең ерте мерзімі бар жұмысты таңдау арқылы күтілетін максималды кешігуді азайту нәтижесі Pinedo-ның «Scheduling» еңбегінде талқыланады.

«Ең қысқа өңдеу уақыты» (SPT) алгоритмінің үзу нұсқасы: Динамикалық жағдайда өлшенген орындалу уақытының қосындысын азайту үшін өлшенген ең қысқа күтілетін өңдеу уақыты бар жұмысты таңдаудың тиімділігін Sevcik «Scheduling for Minimum Total Loss Using Service Time Distributions» еңбегінде көрсетті.

«"Жоспар" сөзін "болжаммен" алмастырыңыз»: Jason Fried, «Let’s just call plans what they are: guesses», 14 шілде, 2009 жыл.

«Пойыздан түсуге болмайды»: Ullman, «Out of Time».

Кешігулерді де, қателерді де қамтуы мүмкін: Monsell, «Task Switching».

«Менің орныма тек істермен айналысамын»: Kirk Pruhs, жеке сұхбат, 4 қыркүйек, 2014 жыл.

«Ол туралы ешкім ештеңе білмеді»: Питер Деннинг, жеке сұхбат, 22 сәуір, 2014 жыл.

«Ағымдағы жүктеме үшін кэштер қызып тұр»: Питер Зийлстра, жеке сұхбат, 17 сәуір, 2014 жыл.

Linux-те бұл ең аз пайдалы үзінді: Бұл мән Linux ядросының «Completely Fair Scheduler» жүйесіндегі `sysctl_sched_min_granularity` айнымалысында анықталған.

Бағдарламашылар психологияға жүгінді: Мысалы, Питер Зийлстра, жеке сұхбат, 17 сәуір, 2014 жыл.

Компьютерлердің өздері осыған ұқсас нәрсе жасайды: Linux 2007 жылы таймерлерді біріктіру (timer coalescing) қолдауын қосты; Microsoft оны 2009 жылы Windows 7-ге енгізді; Apple 2013 жылы OS X Mavericks-те солай жасады.

«Алгоритміңіздегі бір жолдық қате ғана»: Питер Норвиг, жеке сұхбат, 17 қыркүйек, 2014 жыл.

«Мен (контекстті) ауыстырмаймын»: Shasha және Lazere, «Out of Their Minds», 101-бет.

6. БАЙЕС ЕРЕЖЕСІ (BAYES’S RULE)

«Адамның бүкіл білімі белгісіз»: Bertrand Russell, «Human Knowledge: Its Scope and Limits», 1948, 527-бет.

Ол жерде Берлин қабырғасын көрді: Gott, «Implications of the Copernican Principle for Our Future Prospects».

«Деректердің негізсіз тиімділігі»: Баяндама Halevy, Norvig және Pereira-ның «The Unreasonable Effectiveness of Data» еңбегіне негізделген.

«Бұл дәлелдер тек ықтимал болуы керек»: «An Enquiry Concerning Human Understanding», §IV.

Байестің жеке тарихы: Біздің қысқаша өмірбаян Dale-дің «A History of Inverse Probability» және Bellhouse-тың «The Reverend Thomas Bayes» еңбектеріне негізделген.

«Сақталуға лайық»: Bayes-тің «An Essay Towards Solving a Problem in the Doctrine of Chances» еңбегіне кіріспе.

«Бос билеттердің ұтыстарға қатынасы»: Сонындағы қосымша.

Лаплас Нормандияда дүниеге келген: Лапластың өмірі мен қызметі туралы толығырақ мәліметті Гиллиспидің «Пьер-Симон Лаплас» (Gillispie, Pierre-Simon Laplace) еңбегінен көре аласыз.

«басқаларына қарағанда жүйелірек немесе ақылға қонымды емес»: Адам танымы туралы зерттеу, §IV, «Таным операцияларына қатысты скептикалық күммәндар».

мұндағы h′ қарастырылып отырған гипотезалардың толық жиынтығын қамтиды.

«әсіресе болашақ туралы»: Бұл айтылымның белгісіз шығу тегі Quote Investigator сайтындағы «Болжам жасау қиын, әсіресе болашақ туралы» мақаласында егжей-тегжейлі сипатталған.

сыни хат-хабарлардың тасқыны: Мысалы, Гарретт пен Коулздың «Байестік индуктивті қорытынды және антроптық принциптер» және Бухтың «Болашақ перспективаларды талқылау» еңбектерін қараңыз.

Коперник принципі пайда болады: Мұны Готт Бухтың «Болашақ перспективаларды талқылау» мақаласына берген жауабында көрсеткен.

бақтағы жемістер: Мысалы, 2002 жылғы Жаңа Зеландиялық авокадо өсірушілер қауымдастығының жылдық зерттеу есебі сәуір айына қарай жеміс мөлшерінің профильдері қалыпты үлестірілгенін және бақылау кезеңінің соңына дейін солай қалғанын анықтады.

Қаланың орташа халқы: Бұл көрсеткіш Клаузет, Шализи және Ньюманның «Эмпирикалық деректердегі дәрежелік үлестірімдер» еңбегінен алынған, ол өз кезегінде 2000 жылғы АҚШ халық санағына сілтеме жасайды.

Америкадағы орташа табыс: Салық декларацияларынан алынған жеке түзетілген жалпы табыстың (AGI) орташа мәні 2009 салық жылы үшін $55,688 деп бағаланған.

АҚШ халқының үштен екісі орташа табыстан аз табады: 2012 жылғы деректер бойынша, $55,688 көлеміндегі табыс шамамен ең жоғарғы 33%-дық топқа жатады.

ең жоғарғы 1% орташа табыстан он есе көп табады: 2012 жылы ең жоғарғы 1% үшін шекті мән $434,682, ал ең жоғарғы 0,01% үшін $12,104,014 болды.

«артықшылықты қосылу» процесі: Артықшылықты қосылудан (байдың байи түсуі немесе танымал нәрсенің одан әрі танымал болу принципі) туындайтын дәрежелік үлестірімдер туралы идеяны Барабашидің «Байланысқан» (Linked) кітабынан табуға болады.

тиісті болжау стратегиясы — Мультипликативті ереже: Осы бөлімде талқыланған барлық болжау ережелері Гриффитс пен Тененбаумның «Күнделікті танымдағы оңтайлы болжамдар» еңбегінде тұжырымдалған.

өлеңдер дәрежелік заңға жақын нәрсеге сүйенеді: Бұл туралы да жоғарыда аталған еңбекте айтылады.

интервалдардың таралуын формализациялады: Эрланг алғаш рет желідегі телефон қоңырауларының жиілігін Пуассон үлестірімін қолдана отырып модельдеді, кейіннен келіп түсетін қоңыраулар арасындағы интервалдарды модельдеу үшін өзінің атымен аталған Эрланг үлестірімін жасап шығарды.

мүмкіндігі шамамен 20-дан 1-ге дейін: Нақтырақ айтсақ, блэкджек ойынында бірден жеңіске жететін қолдың түсу мүмкіндігіне қарсы коэффициент 2,652-ден 128-ге немесе шамамен 20,7-ден 1-ге тең.

«Мен жеңілдеп, ұзақ күрсіндім»: Гулд, «Медиана — бұл хабарлама емес».

адамдардан болжам жасауды сұрау: Гриффитс пен Тененбаум, «Күнделікті танымдағы оңтайлы болжамдар».

адамдардың кең ауқымдағы априорлы үлестірімдері: Зерттеулер, мысалы, торлы қабыққа түсетін жарық үлгілерінен қозғалатын фигураларды қалай анықтайтынымызды, объектілердің өзара әрекеттесуінен себеп-салдарлық байланыстарды қалай шығаратынымызды және жаңа сөздердің мағынасын небәрі бірнеше рет көргеннен кейін қалай үйренетінімізді зерттеді.

әйгілі «маршмэллоу тесті»: Мишел, Эббесен және Раскофф Зейсс, «Қанағаттануды кешіктірудегі когнитивтік және назар аудару механизмдері».

бәрі жағдайдың түріне байланысты: Магвайр мен Кейбл, «Шешім қабылдаушылар уақыт аралығы тәжірибесі негізінде мінез-құлық тұрақтылығын реттейді».

анағұрлым табысты ересектер болып өсті: Мишел, Шода және Родригес, «Балалардағы қанағаттануды кешіктіру».

алдыңғы тәжірибелер мінез-құлыққа қалай әсер етуі мүмкін: Кидд, Палмери және Эслин, «Рационалды жеңіл тамақтану».

Америкалық жаңалықтардағы қарулы зорлық-зомбылық: Гласснер, «Қорқыныш тудырудың баяндау әдістері».

7. ҚАЙТА ОҚЫТУ (OVERFITTING)

«Моральдық немесе сақтық алгебрасы»: Франклиннің Джозеф Пристлиге жазған хаты, Лондон, 19 қыркүйек, 1772 ж.

«Сен не істей алсаң, мен оны жақсырақ істей аламын»: «Anything You Can Do», Ирвинг Берлиннің туындысы, 1946 ж.

сіз не білесіз және не білмейсіз: Машиналық оқыту зерттеушілерінің тілінде: «жаттығу» (training - модель үйретілетін деректер жиынтығы) және «тест» (test - модельдің сапасын тексеруге арналған жаңа деректер).

Германияда жүргізілген соңғы зерттеу: Лукас және басқалары, «Адаптацияны және бақыттың тұрақты деңгейі моделін қайта қарау».

диаграммадағы әрбір нүкте арқылы өтетін: Шын мәнінде, кез келген n нүкте арқылы әрқашан n − 1 дәрежелі көпмүшені жүргізуге болатыны — математикалық ақиқат.

адамдардың қанағаттануының бастапқы деңгейі: Лукас және басқалары, «Адаптацияны және бақыттың тұрақты деңгейі моделін қайта қарау».

Бөлшектер физикасындағы әйгілі Гейзенбергтің анықталмаушылық принципі сияқты, ығысу-дисперсия компромисі (модельдің қарапайымдылығы мен дәлдігі арасындағы тепе-теңдік) модельдің қаншалықты жақсы бола алатынына — нені білуге және болжауға болатынына іргелі шектеу қояды.

Патшалар кітабында: Нехуштан деп аталатын қола жылан Патшалардың 2-жазбасы 18:4-те жойылады.

«татуировканы өшіру үшін қомақты ақша төлеу»: Гилберт, Бақытқа сүріну.

елу жылдан аз уақыт бұрынғы дуэльдер: Егер сіз тым қорқақ болмасаңыз, 1967 жылы болған дуэльдің видеосын интернеттен көре аласыз.

«Ынталандыру құрылымдары жұмыс істейді»: Брент Шлендер, «Стив Джобстың жоғалған таспалары».

«Бас директор нені өлшеуді шешсе, сол орындалады»: Сэм Альтман, «Стартапты қалай бастау керек».

Риджуэй осындай көптеген жағдайларды каталогқа енгізді: Риджуэй, «Өнімділікті өлшеудің дисфункционалды салдары».

Жұмысқа орналастыру фирмасында: Бұл оқиғада Риджуэй Блаудың «Бюрократия динамикасы» еңбегіне сілтеме жасайды.

офицер инстинктивті түрде қаруды ұстап алды: Жоғарыдағы дереккөз бойынша.

«Егер сіз оны қарапайым түсіндіре алмасаңыз»: Бұл дәйексөз жиі Альберт Эйнштейнге телінеді, бірақ бұл шындыққа жанаспауы мүмкін.

адам миы бестен бір бөлігін жағады: Адам миының энергия тұтынуы туралы толығырақ Райхл мен Гуснардтың еңбегінен біле аласыз.

ми нейрондар санын азайтуға тырысады: Осы нейрондық стратегияны («сирек кодтау» деп аталады) қолдана отырып, зерттеушілер визуалды қыртыстағыдай қасиеттері бар жасанды нейрондарды жасап шығарды.

инновациялық «орташа дисперсиялық портфельді оңтайландыру»: Марковиц Нобель сыйлығын алған бұл жұмысы оның «Портфельді таңдау» мақаласында жарияланған.

«Мен өз жарналарымды елу де елу бөліп тастадым»: Гарри Марковиц өзінің Нобель сыйлығын алған теориясын өз инвестицияларына қолданбай, қарапайым ережені пайдаланғанын мойындады.

«аз ақпарат, есептеу және уақыт»: Гигерензер мен Брайтон, Homo Heuristicus.

1990-жылдардың ортасынан 2013 жылға дейін төрт еседен астам өсті: Солтүстік Америка Соя өнімдері қауымдастығының мәліметтері бойынша.

«Жаңғақтар қазір трендте»: Ванесса Вонг, «Ішуге болатын бадам».

2004 жылдан бері таңқаларлық үш жүз есеге артты: Лиза Рулант, «Неліктен кокос суы қазір $1 миллиардтық индустрияға айналды».

«көрінбейтін күйден қашып құтылмас күйге ауысты»: Дэвид Сигал, кокос суының нарықтағы орны туралы.

кейл (бұжыр қырыққабат) нарығы 40%-ға өсті: «Танымал аспаздар денсаулыққа пайдасын насихаттағандықтан, кейл сатылымы күрт өсті».

оны салат-барларына қосқан Pizza Hut: Айла Уити, «Кейл: диетаңызға суперфудтарды қосудың бір оңай жолы».

«Бүкіл өмірді жұмысшы ара сияқты өткізу»: Дарвин, Чарльз Дарвиннің хаттары, 2-том: 1837–1843.

8. РЕЛАКСАЦИЯ

«Пептидті тежегішті сәтті жобалау»: Меган Петерсон (туған тегі Беллоуз), жеке сұхбат, 23 қыркүйек, 2014 ж.

Беллоуз компьютердің нәтижелеріне риза болды: Меган Беллоуздың үйлену тойына қонақтарды отырғызу кестесін шешу үшін қолданған ресми негізі Беллоуз бен Петерсонның «Оңтайлы отырғызу кестесін табу» еңбегінде сипатталған.

Линкольн «дала заңгері» болып жұмыс істеген: Линкольнның аймағы туралы толығырақ Фрейкердің «Нағыз Линкольн тас жолы» еңбегінен оқи аласыз.

Математик әріптесі Меррилл Флад: Флад, «Саяхатшы саудагер есебі».

Белгілі атау алғаш рет баспа бетінде пайда болды: Робинсон, «Гамильтон ойыны туралы».

«Мүмкін еместік нәтижелері де құнды болар еді»: Флад, «Саяхатшы саудагер есебі».

«Саяхатшы саудагер есебі үшін жақсы алгоритм жоқ»: Эдмондс, «Оңтайлы тармақталу».

Саланың іс жүзіндегі «ойыннан тыс» белгісі: Шын мәнінде, көпмүшелік уақыттан баяу, бірақ экспоненциалды уақыттан жылдамырақ жұмыс істейтін алгоритмдер бар; бұл суперкөпмүшелік орындалу уақыттары да оларды тиімді алгоритмдер жиынынан тыс қалдырады.

«Сіз бәрібір онымен күресуіңіз керек»: Ян Карел Ленстра, жеке сұхбат, 2 қыркүйек, 2014 ж.

Ең кіші жайылма ағаш, оның еркін кері қайту мүмкіндігімен: Саяхатшы саудагер есебіне ең кіші жайылма ағаш арқылы келу Кристофидестің «Жаңа эвристиканың ең нашар жағдайын талдау» еңбегінде талқыланады.

Орындардың минималды жиынтығын табу: Бұл классикалық дискретті оңтайландыру есебі «жиынтықты жабу» есебі ретінде белгілі.

«Осының жартысын да істей алмасаң»: Лаура Альберт Маклей, жеке сұхбат, 16 қыркүйек, 2014 ж.

Ең көп дегенде екі есе көп шақыру қағазы: Хот және Регев, «Төбелерді жабуды 2-ε дәлдігімен жуықтау қиын болуы мүмкін».

Бізді жайлы шекке тез жеткізеді: Бұл жуықтаулар туралы көбірек білу үшін Вазиранидің «Жуықтау алгоритмдері» еңбегін қараңыз.

Сиқырлы таяқша емес: Үздіксіз релаксацияның ең кіші төбелерді жабу (тойға шақыру) есебі үшін ең жақсы жуықтауды ұсынатыны немесе одан да жақсырақ жуықтауларды табуға болатын-болмайтыны әлі де ашық сұрақ болып қала береді.

«Егер сіз бөлшек ойындармен аяқтасаңыз»: Майкл Трик, жеке сұхбат, 26 қараша, 2013 ж.

9. КЕЗДЕЙСОҚТЫҚ

«Неге және қалай екені мүлдем жұмбақ»: Шаша мен Рабиннің «Майкл Рабинмен сұхбат» еңбегінен үзінді.

Кездейсоқтандырылған алгоритм қолданады: Кездейсоқтандырылған алгоритмдер (жұмыс барысында кездейсоқ сандарды пайдаланатын алгоритмдер) Мотвани мен Рагхаванның «Кездейсоқтандырылған алгоритмдер» және Митценмахер мен Упфалдың «Ықтималдық және есептеу» еңбектерінде егжей-тегжейлі талқыланады.

Қызықты ықтималдық талдауы: Бюффон, «Essai d’arithmétique morale».

Қағазға инелерді тастау арқылы: Лаплас, «Ықтималдықтардың аналитикалық теориясы».

Лаззарини 3408 рет ине тастаған көрінеді: Лаззарини, «Un’applicazione del calcolo della probabilità».

Лаззаринидің есебін күмәнді етеді: Лаззарини нәтижелерін одан әрі талқылау үшін Гриджманның «Геометриялық ықтималдық және π саны» және Баджердің «Лаззаринидің π-ді бақытты жуықтауы» еңбектерін қараңыз.

Ол энцефалитпен ауырып қалған еді: Уламның оқиғасы оның «Математиктің шытырман оқиғалары» кітабында жазылған.

«Бірінші дәрежелі интеллекттің сынағы»: Фитцджеральд, «The Crack-Up».

Метрополис бұл тәсілді былай атады: Метрополис бұл атауға құқығын Хердтің «Ертедегі Монте-Карло есептеулері туралы ескертпесінде» жарияланған хатында мәлімдейді.

Раббилердің ұзақ әулетінен шыққан: Шаша мен Лазере, «Ақыл-ойынан тыс».

Бірақ бұл жерде бір кедергі бар: жалпыланған Риман гипотезасы әлі күнге дейін дәлелденбеген.

Құм түйіршіктерінің саны үшін: Жер бетіндегі құм түйіршіктерінің саны әртүрлі дереккөздер бойынша 10^18 бен 10^24 арасында деп бағаланады.

Тиімді алгоритмнің болу-болмауы: Мұнда «тиімді» деп біз 8-тарауда талқыланған «көпмүшелік уақытты» айтамыз.

Сондай әдістердің бірі табылды: Агравал, Кайал және Саксена, «PRIMES Is in P».

Бірнеше кездейсоқ x-терді жасап, оларды қойып көру: Көпмүшелік теңбе-теңдікті тексерудегі кездейсоқтықтың рөлі туралы негізгі нәтижелердің бірі — «Шварц-Зиппель леммасы» деп аталады.

Ол оны «бейхабарлық пердесі» деп атады: Бейхабарлық пердесі (қоғамдағы өз орныңды білмей тұрып әділеттілік туралы шешім қабылдау концепциясы) Роулздың «Әділеттілік теориясы» еңбегінде ұсынылған.

Омелас өркениеті: Ле Гуин, "The Ones Who Walk Away from Omelas".

"Жиіркенішті қорытынды" (repugnant conclusion) деп аталатын ұғым туралы толығырақ Парфиттің "Reasons and Persons" еңбегінен, сондай-ақ, мысалы, Аррениустың "An Impossibility Theorem in Population Axiology" мақаласынан қараңыз.

"философтардан гөрі инженерлердің мәселесі": Ааронсон, "Why Philosophers Should Care About Computational Complexity".

"Менің айтқым келгені — Негативті қабілет (анықталмағандық пен күмән жағдайында ақиқатқа ұмтылмай-ақ тыныштық сақтау қабілеті)": Джон Китс, Джордж бен Томас Китске хат, 21 желтоқсан, 1817 жыл.

"адам өмірінің мақсаттары үшін жеткілікті сенім": Джон Стюарт Милль, "Бостандық туралы" (1859).

URL мекенжайы теңдеулер жиынтығына енгізіледі: Блум, "Space/Time Trade-offs in Hash Coding with Allowable Errors".

бұл тәсілді кодтардың шешімін табу кезінде қолданыңыз: қараңыз Берг-Киркпатрик пен Клейн, "Decipherment with a Million Random Restarts".

"Балқымадан жалғыз кристалды өсіру": Киркпатрик, Гелатт және Векки, "Имитациялық күйдіру (металды қыздырып, баяу суыту арқылы оңтайлы күйге келтіруге ұқсас алгоритм) арқылы оңтайландыру".

"IBM-дегі ең мықты адам": Скотт Киркпатрик, жеке сұхбат, 2 қыркүйек, 2014 жыл.

отыз еке мың реттен астам сілтеме жасалған: Жасанды интеллект бойынша негізгі оқулық — "Artificial Intelligence: A Modern Approach" — имитациялық күйдірудің "қазіргі таңда жыл сайын жүздеген мақалалар жарияланатын жеке салаға" айналғанын мәлімдейді (155-бет).

оңтайландырудың ең перспективалы тәсілдерінің бірі: Бір қызығы, 2014 жылғы мақала медузалардың қорек іздеу кезінде имитациялық күйдіру әдісін қолданатынын дәлелдейтін сияқты; қараңыз Reynolds, "Signatures of Active and Passive Optimized Lévy Searching in Jellyfish".

"серендипити" (кездейсоқ жасалған құнды жаңалық) терминін енгізді: Хорас Уолполдың Хорас Маннға жазған хатында (28 қаңтар, 1754 жыл).

"Таңқаларлық параллель": Джеймс, "Great Men, Great Thoughts, and the Environment".

"Соқыр вариация және селективті сақтау процесі": Кэмпбелл, "Blind Variation and Selective Retention".

"Ньютон, Моцарт, Ричард Вагнер және басқалары": Жоғарыда аталған еңбекте келтірілген үзінді.

"түсініксіз және тұрақты тілек": Сөз — saudade (жоғалған немесе қолжетпес нәрсені аңсау сезімі), ал келтірілген анықтама Беллдің "In Portugal" еңбегінен алынған.

"оны бұдан әрі сілкілеу ақымақтық": Тим Адамс, "Dicing with Life", Guardian, 26 тамыз, 2000 жыл.

10. ЖЕЛІЛЕР (NETWORKING)

"байланыстың көптеген мағыналары бар": Серф пен Кан, "A Protocol for Packet Network Intercommunication".

"Тек байланысу": Форстер, "Howards End".

"қолға ұстайтын, портативті, нағыз ұялы телефон": Мартин Купер, "Ұялы телефонды ойлап тапқан адам: Бір күні әркімде осындай болатынын білдік", Тас Анджарваллаға берген сұхбатында, CNN, 9 шілде, 2010 жыл.

"нағыз бидғат": Джекобсон, "A New Way to Look at Networking".

"Сонымен, кішкентай бала кетіп қалды": Клейнрок, "Computing Conversations".

"екі соңғы нүктенің арасындағы келісілген елес": Стюарт Чешир, жеке сұхбат, 26 ақпан, 2015 жыл.

байланыс ядролық шабуылдан аман қалуы мүмкін еді: Бэран, "On Distributed Communications".

дамып келе жатқан желі артықшылыққа айналады: Осы мәселеге толығырақ тоқталу және желілердің тарихына (оның ішіндегі қазіргі мәселелерге) кеңірек қарау үшін Джекобсонның "A New Way to Look at Networking" еңбегін қараңыз.

"Ешқандай тасымалдау 100 пайыз сенімді бола алмайды": Серф пен Кан, "A Protocol for Packet Network Intercommunication".

"Византия генералдарын мәселесі" (бүлінген немесе жалған ақпарат беретін түйіндері бар жүйеде ортақ келісімге келу қиындығы): Лэмпорт, Шостак және Пис, "The Byzantine Generals Problem".

тізбектің қалпына келтірілгені туралы сигнал: Мұнда сипатталған процесс "жылдам қайта жіберу" (fast retransmit — пакет жоғалса, күтпей-ақ дереу қайта сұрау) ретінде белгілі.

"қалпына келтіру үшін соңғы нүктелер арасындағы қайта жіберулер": Винт Серф, Чарльз Северенспен сұхбат, "Computing Conversations: Vint Cerf on the History of Packets", 2012 жыл.

"сіз жай ғана 'оны тағы бір рет айтыңызшы' дейсіз": Жоғарыда аталған дереккөз.

"Әлемдегі аударуға ең қиын сөз": Оливер Конвей, "Congo Word 'Most Untranslatable'", BBC News, 22 маусым, 2004 жыл.

университеттегі жеті кампусты бір-бірімен байланыстыруға тырысу: Абрамсон, "The ALOHA System".

"тек бір ғана схеманың жұмыс істеуіне үміт бар": Джекобсон, "Congestion Avoidance and Control".

HOPE деп аталатын пилоттық бағдарлама: HOPE бағдарламасы Хокен мен Клейманның "Managing Drug Involved Probationers" еңбегінде бағаланған.

"өзгертуге тырысудың қандай ақылға сыйымсыз жолы": Қосымша ақпарат алу үшін қараңыз, мысалы, "Гавайидегі жаңа сынақ мерзімі бағдарламасы статистиканы жеңді", PBS NewsHour, 2 ақпан, 2014 жыл.

"бұл мың еселік кенеттен төмендеу": Джекобсон, "Congestion Avoidance and Control".

"иерархиясыз басқару": Қараңыз, мысалы, Гордон, "Control without Hierarchy".

құмырсқалардың шешімі де ұқсас: Құмырсқалардың қорек іздеуін "Баяу іске қосу" сияқты ағынды басқару алгоритмдерімен байланыстыратын зерттеулер Прабхакар, Дектар және Гордонның "The Regulation of Ant Colony Foraging Activity without Spatial Information" еңбегінде кездеседі.

"өз құзыретсіздік деңгейіне дейін көтерілуге бейім": Питер мен Халл, Питер принципі (қызметкер өзі атқара алмайтын лауазымға дейін өсе береді деген тұжырымдама).

"құрамды бақылау" (manning control) деп аталатын әрекетті жүзеге асырды: Қараңыз, мысалы, Майкл Смит, "Army Corporals Forced Out ‘to Save Pension Cash’", Telegraph, 29 шілде, 2002 жыл.

"бір мезгілде сөйлеуге де, тыңдауға да қатысады": Ингве, "On Getting a Word in Edgewise".

"Сәл-пәл қауіп төнген оқиғаларды алаңғасар тыңдаушыларға айтқан әңгімешілер": Бавелас, Коутс және Джонсон, "Listeners as Co-Narrators".

сөйлеушіден тыңдаушыға ақпарат ағынын реттеу: Толинс пен Фокс Три, "Адресаттың кері арналары" (backchannels — әңгіме барысында тыңдаушының "иә", "түсінікті" сияқты қысқа реакциялары) әңгіменің дамуына бағыт береді".

"'нашар әңгімешілер' бұған кем дегенде жартылай өз аудиториясын кінәлай алады": Джексон Толинс, жеке хат, 15 қаңтар, 2015 жыл.

"кезектердің себебі мен мағынасы туралы қате түсініктер": Николс пен Джекобсон, "Controlling Queue Delay".

"Мен көшіріп немесе rsync жасап жатқан едім": Джим Геттис, "Bufferbloat" (желідегі артық буферлеу салдарынан болатын кідіріс): Интернеттегі қараңғы буферлер", Google Tech Talk, 26 сәуір, 2011 жыл.

олар әдетте нөлге теңестірілген кезде: Қараңыз Николс пен Джекобсон, "Controlling Queue Delay".

«Бұл — ұзаққа созылатын батпақ»: Джим Геттис, жеке сұхбат, 15 шілде, 2014 жыл.

11. ОЙЫНДАР ТЕОРИЯСЫ

«Мен адамдардың асыл және құрметті екеніне сенемін»: Стив Джобс, Гэри Вулфқа берген сұхбаты, Wired, ақпан 1996 жыл.

адам табиғатқа қарсы: ХХІ ғасырдағы мектеп оқушылары «адам табиғатқа қарсы», «адам өзіне қарсы», «адам адамға қарсы» және «адам қоғамға қарсы» деген ұғымдарды көбірек үйренуде.

«өзгелердің күткенін күту»: Кейнске телінеді, Грегори Бергман, Isms, Adams Media, 2006 жыл.

«покер ойыншылары оны «деңгейлеу» (leveling) деп атайды»: Дан Смит, жеке сұхбат, 11 қыркүйек, 2014 жыл.

«Сенде екілік пен жетілік жоқ»: Бұл оқиға 2009 жылдың 17-19 қарашасында Лондондағы Les Ambassadeurs клубында өткен және Sky Sports арнасынан көрсетілген «Full Tilt Poker Durrrr Million Dollar Challenge» турнирінде болды.

«Нэштің не екенін білу немесе білуге тырысу»: Дан Смит, жеке сұхбат, 11 қыркүйек, 2014 жыл.

тепе-теңдік деп аталатын: Ойындар теориясындағы тепе-теңдік ұғымы — және ойындар теориясының өзі — Принстон университетінің ғалымдары Джон фон Нейман мен Оскар Моргенштерннің «Ойындар теориясы және экономикалық мінез-құлық» еңбегінен бастау алады.

әрбір екі ойыншылы ойында кем дегенде бір тепе-теңдік болады: Нэш, «N-адам қатысатын ойындардағы тепе-теңдік нүктелері»; Нэш, «Кооперативтік емес ойындар».

Нэш тепе-теңдігінің әрқашан болатындығы: Дәлірек айтсақ, жоғарыда аталған еңбекте шекті ойыншылар саны мен шекті стратегиялар саны бар кез келген ойынның кем дегенде бір аралас стратегиялық Нэш тепе-теңдігі (ешбір ойыншы өз стратегиясын өзгерту арқылы ұтысын арттыра алмайтын жағдай) болатыны дәлелденген.

«іргелі және жан-жақты әсер етті»: Майерсон, «Нэш тепе-теңдігі және экономикалық теория тарихы».

«компьютер маманының басты мәселесі»: Пападимитриу, «Алғысөз».

барлығы да шешілмейтін (интрактабельді) мәселелер екені дәлелденді: Гилбоа және Земель, «Нэш және корреляцияланған тепе-теңдіктер».

«сонымен қатар өзекті деп есептелуі керек»: Ааронсон, «Неліктен философтар есептеу күрделілігіне мән беруі керек».

«пессимист мұның шындық екенінен қорқады»: Кейбелл, Күміс айғыр.

қоғамдық көгалдың «ортақ пайдаланылуын» елестетіңіз: Хардин, «Ортақ ресурстар қасіреті» (жеке мүдделердің ортақ ресурсты сарқуы).

«қорғасынды бензин деген нәрсе болатын»: Аврим Блум, жеке сұхбат, 17 желтоқсан, 2014 жыл.

«жұмыстың құны бұдан жоғары жер жоқ»: «Жоғалған уақытты іздеуде», Economist, 20 желтоқсан, 2014 жыл.

15%-ы мүлдем демалыс алмайды: Glassdoor зерттеуі, жоғарыда аталған дереккөзде келтірілген.

«Дүкендер бұрынғыдан да ерте ашылуда»: Николь Массабрук, «2014 жылғы Алғыс айту күнінде ашылатын дүкендер: Walmart, Target, Best Buy және Күркетауық күніндегі басқа дүкен сағаттары», International Business Times, 26 қараша, 2014 жыл.

«Ойыншыны кінәлама, ойынды кінәла»: Ice-T, «Don’t Hate the Playa», The Seventh Deadly Sin, 1999 жыл.

«Ешқашан ешкімнің жағына шығып, отбасыңа қарсы тұрма»: «Өкіл әке» (The Godfather), Марио Пьюзо мен Фрэнсис Форд Копполаның сценарийі, Paramount Pictures, 1972 жыл.

демалыс алғаны үшін мың доллар нақты ақша: Либин мың доллар берудің себептерін, мәселен, Адам Брайантқа берген сұхбатында талқылайды, «Телефондар сөндірулі, бірақ робот жұмыста», New York Times, 7 сәуір, 2012 жыл.

«Жүректің өз себептері бар»: Паскаль айтқандай: «Le cœur a ses raisons, que la raison ne connaît point» (Жүректің ақыл білмейтін өз себептері бар).

«Орман шатырын әуедегі шабындық деп санауға болады»: Докинз, «Эволюция дәлелдері».

«Егер адамдар бізден иррационалды жауап күтсе»: Франк, «Ақыл аясындағы құмарлықтар».

«Адамдар қарым-қатынастан кетеді деген қауіп»: Сонда.

«сізге айырылысқыңыз келмейтін сезім керек»: Роберт Франк, жеке сұхбат, 13 сәуір, 2015 жыл.

«ақпараттық каскад» (адамдардың өз ақпаратына қарағанда, өзгелердің әрекетіне сүйеніп шешім қабылдауы) ретінде белгілі: Бикчандани, Хиршлейфер және Уэлш, «Сән теориясы».

«қоғамдық ақпарат қоры енді өспейді»: Дэвид Хиршлейфер, жеке сұхбат, 27 тамыз, 2014 жыл.

нарықтың иррационалдығын нашарлатады: Мәселен, Колумбия университетінің экономисі Раджив Сетхидің «flash crash» (лезде құлдырау) оқиғасынан кейінгі реакцияларын қараңыз.

механизмдер дизайнын қайта қарау тәсілі: «Алгоритмдік механизмдер дизайны» (тиімді нәтижеге жету үшін ойын ережелерін есептеуіш тұрғыдан құру) термині алғаш рет Нисан мен Роненнің еңбегінде пайда болды.

Ол Викри аукционы (жеңімпаз ең жоғары ставканы бергенімен, екінші ең жоғары бағаны төлейтін аукцион түрі) деп аталады: Викри, «Контрспеккуляция, аукциондар және бәсекелестік жабық тендерлер».

«стратегияға төзімді» (strategy-proof) немесе жай ғана «шынайы»: Стратегияға төзімді ойындар сонымен қатар «ынталандыруға сәйкес» (incentive-compatible) деп те аталады.

ойындар теориясының «кіріс эквиваленттілігі» деп аталатын принципі: Кіріс эквиваленттілігі теоремасы Викриден бастау алып, Майерсон, Райли және Сэмюэлсон еңбектерінде жалпыланды.

Викри аукционы — «керемет»: Тим Рафгарден, «Алгоритмдік ойындар теориясы, 3-дәріс (Майерсон леммасы)», 2013 жыл.

«Меніңше, бұл шынымен де ғажап»: Ноам Нисан, жеке сұхбат, 13 сәуір, 2015 жыл.

«сіз көре алатын ең жақсы нәрселердің бірі»: Пол Милгром, жеке сұхбат, 21 сәуір, 2015 жыл.

«Тозақ — бұл басқа адамдар»: Сартр, «Шығар жол жоқ».

ҚОРЫТЫНДЫ

«мұны ең ақылды әрекет деп анықтау»: Рассел, «Этика элементтері».

есептеуіш стоицизм (сыртқы факторларға емес, шешім қабылдау процесінің сапасына назар аудару): Мәселен, Балтцли, «Стоицизм».

жақсы әнді естігенде тани білу: Бұл сонымен қатар P және NP кластары арасындағы айырмашылық болып табылады.

олардың ешқайсысы корриданы көргісі келмеген: Осыған ұқсас сценарийлер кейде «Абилин парадоксы» (топ мүшелері өздеріне ұнамайтын шешімді, басқаларға ұнайды деп қате ойлап, бәрі болып қабылдауы) деп аталады.

тиындар санын азайту: Шаллит, «Бұл елге 18 центтік тиын қажет».

Үлкен автотұрақты елестетіп көріңіз:

«Спиннинг» және «блоктау»:

Библиография

Алғыс хат

Кинг округінің қоғамдық кітапханасына, Сиэтл қоғамдық кітапханасына, Солтүстік аймақтық кітапханасына және Берклидегі Калифорния университетінің (UC Berkeley) кітапханаларына өз жұмыс процестерімен танысуға мүмкіндік бергендері үшін алғыс айтамыз.

Осы кітаптағы көптеген түсініктерге жол ашқан әңгімелеріміз үшін келесі жандарға алғыс айтамыз (бұл тізім толық емес болуы мүмкін): Эллиот Агилар, Бен Бакус, Лиат Бердуго, Дейв Блей, Бен Блум, Джо Дамато, Ева де Вальк, Эмили Друри, Питер Экерсли, Джесси Фармер, Алан Файнберг, Крикс Финн, Лукас Фоглия, Джон Гонт, Ли Гилман, Мартин Глейзер, Адам Голдштейн, Сара Гринлиф, Графф Хейли, Бен Хьертманн, Грег Дженсен, Генри Каплан, Шармин Карим, Фальк Лидер, Пол Линке, Роуз Линке, Таня Ломброзо, Брэндон Мартин-Андерсон, Сэм Маккензи, Илон Маск, Колумбия университетіндегі Neuwrite тобы, Ханна Ньюман, Эйб Отман, Сью Пенни, Диллон Планкетт, Кристин Поллок, Диего Понториеро, Ави Пресс, Мэтт Ричардс, Энни Роуч, Фелисити Роуз, Андерс Сандберг, Клэр Шрайбер, Гейл және Рик Шэнли, Макс Шрон, Чарли Симпсон, Наджиб Тарази, Джош Таненбаум, Питер Тодд, Питер ван Весеп, Шон Вен, Джеред Вержбицки, Майя Уилсон және Кристен Янг.

Осы жұмыстың жүзеге асуына мүмкіндік берген кейбір керемет еркін және ашық бастапқы кодты бағдарламалық жасақтамаларға алғыс айтамыз: бастапқыда Git, LaTeX, TeXShop және TextMate 2.

Түрлі бағыттарда өз дағдылары мен күш-жігерін аямаған жандарға: библиографиялық және мұрағаттық ізденістері үшін Линдси Баггетке, Дэвид Буржэнге және Таня Ломброзоға алғыс айтамыз.

Дарвиннің керемет күнделік бетін басып шығаруға рұқсат бергені үшін Кембридж университетінің кітапханасына және оны ұқыпты қалпына келтіргені үшін Майкл Ланганға алғыс айтамыз.

Әсерлі портрет үшін Генри Янгқа алғыс айтамыз.

Редакторымыз Григорий Товбиске және Henry Holt баспасының ұжымына кітаптың барынша жақсы болуына атсалысқан зерек, қажымас әрі ынталы еңбектері үшін және оны әлемге мақтанышпен паш еткендері үшін алғыс айтамыз.

Бала күтіміне бірнеше рет көмектескен Таня Ломброзоға, Вивиана Ломброзоға, Энрике Ломброзоға, Джуди Гриффитске, Род Гриффитске және Джулиет Мореноға, сондай-ақ Ломброзо Гриффитс отбасына, Берклидегі Калифорния университетінің Есептеуіш когнитивтік ғылым зертханасының мүшелеріне және кітап жазуға байланысты уақыт тығыздығына түсіністік пен шыдамдылық танытқандардың барлығына рақмет айтамыз.

Роуз Линкеге —

Таня Ломброзоға —

— оқырман, серік, қолдаушы және шабыт беруші ретінде әрқашан алғысымыз шексіз.

СОНДАЙ-АҚ БРАЙАН КРИСТИАННЫҢ АВТОРЛЫҒЫМЕН:

Авторлар туралы

Пікірлер (0)

Әзірге пікір жоқ.