Математика и секс
Июль 15th, 2014

Воздушая тревога

Сегодня на всем Кипре утром взвыли сирены, оповещающие, что бомбят. Все попросыпались и перепугались.

Оказалось, что каждый год таким образом на Кипре (или по крайней мере в Лимассолне, не знаю) проверяют готовность систем тревоги, всё ли работает.

Впрочем, я сам этого не слышал — меня разбудить это не смогло. Во время любой войны я наверное погиб бы первым, мирно спя в своей постели. Но жёны коллег пересрали.

UPD. В комменатриях сообщают, что серена была потому что сегодня годовщина военного переворота 15 июля 1974 года.

Июль 15th, 2014

Вторая неделя курса

Немного расскажу про как идёт курс. Идёт на самом деле предсказуемо: постепенно глохнет, главным образом из-за того, что энтузиазм видимо и у учеников и у учителей пропал. Студентов в итоге набралось аж 47 человек, учителей — 10. Реально из десяти учителей только трое, не считая меня, хоть как-то провлялись на курсе, впрочем, это нормально, так как пока не началось ничего по непосредственно их части. Из студентов пятеро только зарегистрировалось и не появилось на курсе больше не разу, основная масса зарегистрировалась, пару раз зашла и так же больше не появлялась.

На этих выходных я выложил задания второй недели, но их пока сделали всего 5 человек, причём мне кажется, что цифра так мала не потому что сложно, а потому что большинство забило. Но не ясно. Возможно, многие просто ждут, что все материалы будут отправляться по почте, но такого пока не будет — может быть потом, пока я просто не успеваю всё сделать. Я в общем-то пишу это как раз на всякий случай, что возможно кто-то просто не знает, что на форум курса надо заходить самому регулярно.

Ну а там посмотрим что дальше будет. Пока активность хоть и снизилась, но вполне достаточная для того, чтобы продолжать. Но если тенденция сохранится, то через пару недель придётся сварачиваться.

Если кто-то не учится, но из любопытства интересно что там просиходит, то на первой неделе были if/while в Питоне, на этой функции (включая рекурсии) и Git. Пока в общем ничего такого особого, разбираемся с самыми основами.

Июль 10th, 2014

Хуже пишу

Замечаю, что стал намного хуже писать, чем писал раньше. Это касается и стиллистики, и грамматических ошибок и банальных опечаток. Не понятно из-за чего так происходит и что с этим можно делать.

Из числа гипотез: сказывается жара, сказывается психологическая расслабленность (в России всегда ожидаешь, что проломят голову либо посадят и отпетушат, а на Кипре всегда ожидаешь хорошей погоды), сказывается то что не читаю художественной литературы, сказывается что в принципе пишу реже, сказывается возраст либо просто боженька наказывает меня таким образом.

Но что бы тут ни сказывалось, факт кажется очевидным: писать я стал хуже. Мне это не нравится и хочется что-то с этим сделать. Наивно конечно полагать, что читатели сталкивались с такой проблемой, но всё же: что делать-то, а?

Июль 4th, 2014

Начало курса

На этих выходных начинаем курс. Группа расширилась, как-то отказывать желающим не хотелось, поэтому всех, кто писал не смотря на объявление о прекращении приёма, записали после совместного обсуждения. На данный момент на форуме зарегистрировалось 35 человек. Из тех, кто писал мне на почту, но потом никак не проявился на курсе, есть ещё 9 человек. Больше принимать уже не будем совсем-совсем, в течение недели будем ещё принимать из числа тех девяти не откликнувшихся, но со следующей недели и их прекратим пускать, если не будет активности.

На форуме имеют место пока некоторые технические проблемы, постепенно их решаем. Если у кого-то что-то не получается, либо если кто-то не получил моего письма и поэтому не записался в итоге на форум, пишите, будем разбираться. После регистрации я руками выдаю студентам права на просмотр форума, так что сразу после регистрации вы ничего не увидите. В течение дня, однако, у вас должен появиться доступ для чтения и писания на форум. Если этого не происходит, опять же пишите, буду решать проблему.

Июль 2nd, 2014

Русский антифашист

5ecVfWLFdg8jGjQ2dVDMQM

Парень на фото — ополченец, защищает русских людей от ужасных украинских фашистов.

Про парня этого я давно наслышан, два года назад зоозащитники пытались привлечь его к ответственности за то, что он, видимо из патриотических соображений, отрезал щенкам головы, жестоко убивал животных и позировал с трупами на фотографиях в Интернете. Зовут его Алексей Юрьевич Мильчаков, в Интернете про него можно много найти по его ФИО. Вот он же два года назад:

10482901_588935927891372_8740011578179521452_n

Прокремлёвские антифашисты такие антифашисты. Страница героя ВКонтакте.

Июнь 29th, 2014

Закрыл набор

Меньше чем за сутки набрался 21 желающий стать учеником на курсе, поэтому с этого момента набор больше продолжаться не будет. Большее количество мы не понятем явно. Учителей на данный момент вроде как 5 человек (с двумя пока не очень понятно). Их них специалисты по тестированию, веб-разработке, Яве и C#, ну и я. В общем будем начинать тогда в ближайшее время.

Июнь 28th, 2014

Кто хочет стать программистом?

После вчерашней заметки и разговора с девушкой я лежал ночью в кровати, смотрел в потолок и думал. Ниже я издагаю те мысли, которые меня вчера посетили и которые всё ещё не забыл. Я сейчас буду говорить только об IT-сфере.

Обычный карьерный путь человека в IT выглядит так: он поступает в технический ВУЗ на любую специальность, ему пять лет капают в мозг всякой чушью, но среди этой чуши он начинает понимать как писать циклы while и условия if. Если ВУЗ топовый, то он узнает что такое классы и объекты. В качестве очень редких исключений можно попасть к хорошему преподавателю на какой-нибудь спецкурс, где тебе расскажут нормально про что-то ещё, например про XML или про то же теситрование или про современный веб, но это редко. В МИФИ, например, когда говорят про HTML, до сих пор рассказывают про тег FONT.

Потом человек как правило читает одну-две книжки, которая уже учит его какому-то взрослому языку, а институт его по распределению пихает в какую-нибудь контору на позицию джуниор-разработчика или тестировщика. Именно на работе человек получает свои первые реальные навыки, после чего он может искать уже новое место работы, изучать ещё что-то новое, расти профессионально и карьерно. Профессионал, можно считать, получился.

Альтернативный подход — это самообразование. К сожалению, это почти никогда не работает. В редких случаях, когда это работает, человек вырастает в куда более хорошего специалиста, нежели он мог бы вырасти окончив институт. Другое дело, что у 99% заниматься самообразованием не получается. Получается, что институт оказывается в общем-то на порядок предпочтительнее самостоятельной учёбы. Полезно понять как именно выглядит неудачный сценарий самообразования.

Начинается всё с того, что у человека возникает желание освоить какую-то профессию и научиться что-то делать. В случае с моей девушкой это желание стать тестировщиком. В случае меня это было желание стать хакером (мне было тогда очень мало лет и я думал, что уж хакерам-то точно бабы дают). Первый шаг такого человека — начать задавать доступным ему людям вопросы в духе «как научиться».  Тут случается первая засада. Ему начинают давать советы все кому ни лень, в итоге по одному только какому-нибудь языку программирования у него оказывается список из 20-ти книг и он не знает что выбрать. Из этих 20-ти книг легко может не оказаться ни одной, которая действительно заслуживает прочтения. Часть из них окажется просто плохими книгами, часть будет ориентирована на сложивщихся профессионалов, часть на людей просто интересующихся, без прицела на освоение именно профессии.

Человек выбирает одну какую-то книгу и начинает её читать. Например, это может быть какая-нибудь книга «Java для начинающих» на 500 страниц текста. После прочтения книги человек узнаёт про все возможные операторы, типы данных, несколько паттернов, но зачастую не может написать ничего сложнее каких-то консольных программ, которые считают числа Фибоначчи. Учитывая, какого труда это ему стоило, человек утверждается в мысли, что программирование это не для него. Конец.

Чем институт оказывается в выигрышном положении? Главным образом он выигрывает в том, что на лекциях дают лишь необходимую выжимку. Вместо чтения 500 страниц по Яве достаточно прослушать несколько которотких лекций (обычно всего навсего 3-4), чтобы уметь делать ровно то же самое и даже больше, чем ты сможешь делать после прочтения книги. Конечно, знания будут обзорными и неглубокими, но начинающему знать что-то глубоко и не нужно. Углубиться можно уже в процессе работы и заробатывания денег.

Институт так же поддерживает темп. Если на лекции были while, if и алгоритмы сортировки, то через неделю надо сдать домашнее задание на эту тему. Конечно, кто-то может скопировать программу из Интернета, кто-то может получить хвост, про который потом все забудут, но само присутствие на лекцией и в лабораторном помещении откладывается в мозгах. По крайней мере даже если студент не делает никаких заданий, он примерно себе представляет как выглядит процесс программирования, как программа компилируется, дебажется и запускается. А это уже половина успеха, даже если программируют на отсталом языке типа Pascal и программируют чушь. Это всё равно навыки программирования, пусть и пассивные.

Следующее важное свойство института, это то что он даёт кругозор. Вопрос новичка обычно выглядит так: «А как мне научиться программировать на Яве?» Человеку после такого вопроса вполне справедливо начинают давать рекомендации по изучанию именно Явы. Мало кому придёт в голову сказать человеку, что чтобы стать программистом, помимо Явы надо знать какие-то алгоритмы, процесс тестирования, системы контроля версий, форматы XML и JSON, HTML, какие-нибудь скриптовые языки, основы криптографии, базы данных, устройства сетей и операционной системы, принципы многопоточного программирования и так далее. Даже не смотря на то, что половина перечисленного легко изучается за неделю, об этом просто никто не скажет, не даст тестового задания или домашнего упражнения. В итоге даже освоив на каком-то уровне Яву человек всё равно не способен писать что-то сложнее совсем тривиальных окошечек.

Российские институты из необходимых навыков дают программисту лишь малую часть и дают её некачественно. Но опять же это полезно — это расширяет кругозор. Даже если в институте рассказали про тег FONT, если вдруг человеку придётся становиться разработчиком под веб, он сможет довольно легко переключиться на новые стандарты. Важно однако что он уже имеет представление в какую сторону хотя бы смотреть. Самоучка в Яве зачастую даже примерно не знает что из себя представляет страничка в Интернете.

Так же очень важным преимуществом института является то, что он создаёт внутри себя некоторое комьюнити. Если студент не понимает почему у него не компилируется «Hello World!», он может всегда спросить об этом у соседа. Если вы учитесь сами по книжкам, то спросить вам как правило неукого. Есть, конечно, форумы, но в большинстве мест, если вы будете задавать много «глупых» вопросов, местные эксперты вам вначале будут кивать на Гугл, потом заминусуют, потом назовут «ламером» и потом забанят. На этом ваше самообучение скорее всего прекратится из-за полной вашей демотивации.

В последнее время появились различные онлайн-курсы, вот эти самые MOOC, которые в самообучении помогают очень здорово. Во-первых, они дают кругозор (не идеальный, но сравнимый с университетским, если вы беретё несколько курсов), во-вторых, они не заставляют читать книжку, а дают вам быструю необходимую выжимку материала, а так же устанавливают дедлайны, что не позволяет вам лениться. В-третьих, они формируют так же как и институт комьюнити, где вас никто не забанит за глупые вопросы. В отличие от института такие курсы так же объясняют что-то современное и реально прикладное, а не доисторичскую чушь типа Pascal или HTML4. Почти идеально.

Однако, MOOC имеет и недостатки. Главный недостаток заключается в том, что у ученика нет куратора, который мог бы направлять процесс обучения. Всё что вы видите — это набор курсов, но вы не знаете какой из них вам надо выбрать и нет человека, который сказал бы вам, что «Курс по „Hadoop” тебе рановато пока брать, научись для начала хотя бы массив сортировать».

Второй недостаток заключается в том, что подход MOOC не индивидуален. Вы можете написать программу, но её никто не проверит и никто вам не скажет: «Да, молодец, всё круто, но вот эта функция берёт на себя слишком много ответственности, лучше бы разбить её на несколько подпроцедур», — а такие комментарии между тем крайне важны, без них стать профессионалом куда сложнее, нежели с ними. Отсюда же следует, что в MOOC вам не дадут на выполнение какие-то большие и сложные проекты, требующие коллективной разработки, понимания архитектуры и должного тестирования. В институтах этого тоже нет, но это решается тем, что на четвёртом курсе вас обычно пихают в какую-нибудь конторку, где вы это всё начинаете потихоньку осваивать.

Помимо MOOC существуют ещё и оффлайновые курсы, но они как правило совершенно неэффективны и максимум могут подготовить вас к сдаче экзамена на какой-нибудь сертификат.

Я сейчас задался целью научить свою девушку профессиональному тестированию ПО, и получается, что я в каком-то смысле должен решать все проблемы, которые имеют MOOC, институты и оффлайн-курсы. При том, что я сам не являюсь тестировщиком. Задача сложная и не факт, что у меня что-то получится, но рассуждения о том, как построить процесс её скорейшего и простейшего обучения профессии, натолкнул меня на мысль, что эксперимент можно провести и более масштабный.

По суди единственное, что я могу дать своей девушке — это отвечать на её вопросы, напрявлять на какие-то конкретные учебные материалы, делать код-ревью и давать проекты для самостоятельного выполнения. По идее это не должно отнимать у меня много времени и с тем же успехом я могу учить ни одного человека, а, скажем, десять. И вот у меня родилась мысль начать такой «курс».

Я опишу, как я себе представляю каким образом это всё может выглядеть на практике.

Во-первых, сам курс будет представлять собой закрытый форум (по крайней мере на первое время), на котором будут общаться ученики и учителя. Иногда будут созвоны в скайпе. Еженедельно учителями будут поститься ссылки на учебные материалы и даваться какие-то разъяснения и рекомендации, а так же самостоятельные задания. Решенные задания ученики будут выкладывать для обсуждения другими учителями и учениками. Так будет продолжаться до тех пор, пока из ученика не получится профессионал.

Требования для того, чтобы стать учеником, такие:

1. Вы не должны быть программистом и не должны быть студентом топового технического ВУЗа. Студенты МГТУ, ВШЭ, МИФИ, МФТИ, МГУ не принимаются (хотя если вы сейчас не студент этих вузов, а потом вдруг станете, выгонять мы вас не будем). Речь конечно только о технических специальностях. Этот курс — эксперимент, целью которого является вырастить профессионала с нуля, а не объяснить какую-то одну технологию человеку, который уже что-то знает.

2. Вы должны быть готовы уделять на курс до 14-ти часов в неделю (чаще всего меньше), плюс дополнительно к обязательным заданиям и статьям уделять время на рекомендуемые книги. Про чтение художественной литературы, компьютерные игры и прочую трату времени придётся забыть на какой-то период.

3. Вам потребуется безлимитный Интернет. Регулярно потребуется скачивать различные среды разработки, библиотеки и подобное. Это файлы размером зачастую в несколько сотен мегабайт.

4. Обязательным является изучение английского языка. Иногда вам придётся либо печатать учебники из Интернета, либо покупать их в бумажном виде (не всё что я потребую купить может быть найдено в Сети). Как альтернатива — вы должны будете пойти на курсы английского. Максимум через пол-года курс целиком перейдёт на английский язык, включая общение на форуме. Учебные материалы с первой же недели будут на английском языке (необходимые комментарии будут даны на русском).

5. Вы должны хотеть получить профессию программиста или тестировщика, это является целью курса. Мне хотелось бы, чтобы через год ученик мог зарабатывать фрилансом, а через два года устраиваться на работу в большие компании.

Так же интересно, если ко мне захотят присоединиться другие учителя. Очень интересны люди, которые:

1. Являются профессионалами Java-разработки.

2. Являются профессионалами веб-разработки.

3. Профессионально занимаются тестированием.

4. Занимаются хантингом программистов и тестировщиков.

5. Веб-дизайнеры и верстальщики.

6. Системные архитекторы.

7. Фрилансеры, которые реально этим зарабатывают и знают как начать фрилансить, найти заказчиков и не боятся научить этому других.

8. Менеджеры в IT, которые знают, как построен процесс разработки приложений с точки зрения бизнеса.

9. Люди, занимающиеся маркетингом в IT.

10. Все прочие люди, профессиональные знания которых, как они считают, могут пригодиться человеку, занятому в IT-сфере.

Учитель должен будет делать всё то что я написал: отвечать каждый день на глупые вопросы на форуме, направлять учащихся на конкретные статьи, давать задания, проверять их. Подход «держите парни 20 книг, как прочитаете, отчитаетесь» не интересен. Каких-то лекций читать не надо, специальных учебных материалов готовить не надо, надо лишь направлять сообучение, указывать конкретные статьи в блогах и на сайтах, конкретные параграфы в книгах. Должна быть постоянная обратная связь, причём проект должен быть длительным. Конечно, если вы хотите рассказать только об одной какой-то теме и на этом закончить, длительным он быть не обязан, но в силу того, что мы не можем давать высокой нагрузки учащимся, даже краткий курс скорее всего окажется более длительным, чем вы ожидаете. Вероятно, кто-то из учителей сможет утолить и корыстный интерес: предложить в качестве домашнего задания реальную задачу для своего бизнеса или найти себе сотрудников, удалённых или настоящих. Учитывая, что на этом курсе скорее всего будут учиться высокомотивированные люди, я думаю, это будут хорошие сотрудники и в итоге специалисты. Ну и учитель, если проект вдруг станет успешным, всегда сможет с гордостью говорить, что это он его таким успешным сделал.

Ну и да, подавляющее большинство учителей скорее всего станут как-то полезны лишь через пару месяцев после начала курса, так как в самом начале будут совсем примитивные вещи.

Я думаю тут необходимо сказать почему я думаю, что это стоящая затея. Я знаю, что спрос на такой курс скорее всего будет у учеников. Я регулярно по почте делаю ровно то, о чём я описал в этой заметке: отвечаю людям на глупые вопросы, говорю, что читать дальше. Людям это нужно, поэтому я думаю, что проект по крайней мере сможет запуститься.

С точки зрения учителей выгода в том, что это возможность поучавствовать в уникальном эксперименте. Многие профессионалы стремятся поделиться знаниями: пишут в блоги, открывают школы в своих больших компаниях, читают лекции в онлайн-университетах. Такой проект — это ещё один способ донести до людей свои знания, и, как мне кажется, способ весьма интересный.

И ещё несколько комментариев о том, что будет в курсе по составу.

1. Не будет жести. Не будет Хаскеля и Лиспа, не будет сложных параллельных алгоритмов, не будет ассемблера и так далее. Для изучения этого куратор нужен куда в меньшей степени и при желании это ученик освоит потом сам. Основная задача — дать основное и вывести человека на уровень успешного прохождения собеседований.

2. Зато будет много надрочки на собеседования. Проходить собеседования — отдельный навык, причём для успешной карьеры чуть ли не самый важный, так что этого будет много.

3. Не будет математики. Ну вернее будет, но только самая тривиальная, чтобы человек хотя бы примерно понимал что такое O-нотация и мог решать задачки на собеседованиях на решето Эратосфена и числа Фибоначчи. Это всё совершенно не нужно IT-специалисту, но бизнес любит такие вопросы при отсеве соискателей. Глупо со стороны бизнеса, но с этим надо считаться.

4. Основная направленность будет в Java-программирование, поскольку пока это наиболее востребованный язык. (По этой причине профессионал Java нужен ну очень-очень сильно; я сам смогу дать лишь основы). Обзорно и неподробно будет рассказано и о других профессиональных областях, если найдутся желающие профессионалы, чтобы стать учителями. Было бы здорово при заинтересованности учеников подготовить так же тестировщиков/дизайнеров/верстальщиков. Но в целом никакой конкретной программы нет, никаких жестких временных рамок нет.

5. Проект полностью некоммерческий и будет оставаться таким. Никаких дипломов по окончании, никаких сертификатов не будет. Однако, в процессе обучения ученик будет выполнять нетривиальные проекты, которые смогут пойти в его портфолио работ. Для многих компаний это куда более весомо, нежели диплом или сертификат.

Когда наберётся какое-то количество желающих учиться, курс начнётся. Я ожидаю, что можно начать с 15-ю учащимися, впоследствии добирать учеников не планируется. Если 15 не будет набираться, но можно начинать и с меньшим числом учащихся, но только если их будет не меньше пяти. Но в этом случае мы всё же будем ждать, пока набирётся более крупный класс, посольку какая-то часть в процессе наверняка отсеится (выгонять никого не будем, подход будет индивидуальным, но кому-то наверняка курс просто не подойдёт и он решит уйти сам). Если ученики не будут набираться совсем никак, то проект отменяется и можно рассматривать эту заметку просто как философские рассуждения.

Учителя получат доступ до форума сразу же, хотя в какой именно момент они начнут доносить свою тему, будет решено совместно по ходу курса.

Желающим стать учениками или учителями, писать мне на почту heller@heller.ru или heller@riseup.net. Если мало ли я не буду вам отвечать в течение двух дней, напишите об этом в комментарии, оба почтовых ящика иногда бывает глючат и не принимают письма.

UPD. Класс уже сформировался, так что новых учеников набирать не будем.

Июнь 27th, 2014

Как стать тестировщиком?

Моя девушка увидела в инстаграмме у какой-то бабы, что та устроилась работать тестировщиком. Вернее даже не тестировщиком, а инженером по автоматизации тестирования. Причём устроилась в Яндекс. И говорит мне такая: «Смотри Рома, какая крутая баба, я бы тоже так хотела». И я подумал, что это в принципе вполне реально. Ну то есть работа кажется одновременно и денежной, и довольно интеллектуальной, и девушек довольно много в этой области работает, и конкуренция низкая, и перспективы есть и т.д. И главное как кажется вполне можно освоить профессию самостоятельно.

Но тут возникла проблема с тем, что я совершенно не знаю как стать тестировщиком. Самостоятельно вырастить из себя программиста мне удалось, а вот как вырастить из человека вменяемого тeстировщика, который мог бы устраиваться в хорошие компании мне совершенно не ясно. Что надо изучать? Если среди читателей есть люди, либо занимающиеся тестированием профессионально (именно настоящим таким, а не юнит-тестами и кликами по всем кнопкам), либо если есть всякие люди, которые занимаются хантингом тестировщиков, то было бы круто, если бы они дали советы в комментариях.

Сам я пока вижу только что надо для начала видимо хотя бы на минимальном уровне освоить какое-то программирование и какие-то основы того как работают сети/Интернет, операционная система и минимальное программирование, пусть хотя бы и скриптовое. А вот что дальше? Как из начинающего программиста пойти дальше и понять как пройти собеседование, чтобы стать тестером? В общем нам нужны советы читателей.

Июнь 25th, 2014

Конец третьей главы

Третью главу учебика я считаю завершённой. Возьму опять паузу с целью привести в божеский вид вторую главу, и затем начну главу, которую придумал озаглавить как «Элентарные алгебраические понятия». Ожидать каких-то откровений не следует, я буду рассказывать довольно стандартные вещи о том как получить из N Z, потом Q, потом R, C и H попутно немного говоря о многочленах. Конечно я при этом буду произносить всякие слова типа «поле» или «кольцо», но это будет на уровне просто знакомства, то есть даже такие фамилии как Нётер или Джекобсон звучать не будут (вообще не хочу забивать голову читателя большим количеством понятий, пока они не нужны). Логический ряд повествования немного нарушу, рассказав и об основной теореме алгебры и об алгебраических замыканиях, но конечно полноценно это сделать не получится без линейной алгебры и леммы Цорна. Пробел этот закрою в дальнейших главах. Линейной алгебры пока касаться тоже не буду. Ну в общем посмотрим что получится.

Что касается второй главы, то там мне надо откорректировать последние два параграфа в соответствии с изменениями, сделанными ранее в главе по логике, хотя содержание останется тем же. Основная проблема второй главы — это иллюстрации. Я большую часть из них постараюсь сделать сам, но иллюстрации из параграфа 2.3 я боюсь не сдюжить. Очень большая просьба к читателям, работавшими с TikZ и/или хотя бы с TeX и какими-то пригодными векторными форматами − помогите с картинками. Сам действительно скорее всего не справлюсь. Правку параграфа 2.3 оставлю на самый конец, если никто не поможет, то придётся стараться делать самому, но на данный момент я даже примерно не представляю себе как это всё оформить грамотно.

Ссылки: учебник в pdf, страница учебника на GitHub.

Июнь 22nd, 2014

Невычислимое, недоказуемое

Предположим, что у нас есть какое-то логическое утверждение, зависящее от натурального числа P(n). Это утверждение, предположим, можно легко проверить для любого конкретного числа, но не понятно верно ли оно для любого числа.

Например, можно рассмотреть гипотезу Гольдбаха о том, что любое чётное число может быть представлено в виде суммы двух простых чисел (так, например, 50=19+31 или 100=11+89). Для любого конкретного чётного числа можно довольно легко перебором подобрать его разложение на сумму двух простых чисел. По крайней мере всегда у людей это получалось. А вот возможно ли это сделать в общем случае, то если получится ли представить в виде суммы двух простых вообще любое чётное число — вопрос, на который наука пока не нашла ответа.

Или вот можно рассмотреть последовательности Коллатца. Начальный элемент последовательности — это произвольное натуральное число, которое мы обозначим как K_0. K_{n+1} получается из K_n по следующему правилу: если K_n чётное, то K_{n+1}=\frac{K_n}{2}. Если K_n нечётное, то K_{n+1} = 3K_n  + 1. Например, если за K_0 принять число 15, то мы получаем следующую последовательность:
15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
Как видим, последовательность пришла в единицу. До сих пор с какого бы числа люди не начинали писать последовательность Коллатца, она всегда приходит в единицу, но приходит ли она в единицу всегда, или всё же есть исключения — никто не знает, это открытый вопрос математики.

Интуитивно должно казаться ясным, что чтобы ответить на такие вопросы, не достаточно перебрать просто большое количество вариантов. В обоих упомянутых проблемах математики перебрали уйму чисел (фактически все числа, на которые хватило вычислительных возможностей), но примера, чтобы какое-то число не раскладывалось в сумму двух простых или чтобы последовательность Коллатца для него не приходила в единицу, так и не нашли. Доказывает ли это что-либо? Конечно нет, потому что чисел, которых математики не проверили, куда больше — их ещё целая бесконечность, а проверена лишь малая конечная часть.

Так вот. Примерно 50 лет тому назад было доказано, что на самом деле для почти любого утверждения достаточно проверить лишь конечное число случаев. То есть если вплоть до некоторого номера M нам не встретятся чётные числа, не представимые в виде суммы двух простых, или не встретится последовательность Коллатца, не приходящая в единицу, то такие числа нам не встретятся вовсе никогда.

Теорема. Для установления истинности почти любого утверждения P(n) достаточно проверить лишь истинность конечного числа утверждений P(n) для n от 1 до некоторого M.

Доказательство. Давайте представим себя на минуточку программистами. Мы хотим найти такое число f\in\mathbb{N}, что P(f) окажется неверным, то есть мы ищем контрпример к нашей гипотезе.

Будем считать, что мы можем написать программу для проверки утверждения P для любого конкретного номера (это предположение и составляет значение слова «почти» в формулировке теоремы). Напишем программу, которая будем перебирать все числа подряд начиная единицей и которая остановится лишь когда она найдёт такое f\in\mathbb{N}, что P(f) не выполняется. Возможно, что мы не найдём его никогда и тогда программа будет работать бесконечно долго, а это значит, что у нас есть время попить чай и поразмышлять.

Код нашей программы имеет конечную длину, обозначим её N. Если рассмотреть все возможные программы длины N, то среди них найдутся конечно же те, которые будут работать бесконечно долго (можно сказать, что они «зависнут») и те, которые в итоге остановятся. Обозначим за B_N самое долгое время работы программы длины N (на английском эти числа называются Busy Beaver Numbers по фольклорным причинам, а как это адекватно переводится на русский я и не знаю). Как вычислить это самое B_N не очень понятно, но такое число вполне определено. Предположим пока, что мы его знаем.

Посмотрим на часы, сколько уже работает наша программа по поиску контрпримера, пока мы пили чай? Что? Уже дольше, чем B_N? Но ведь B_N это самое долгое время, которое может работать программа, которая останавливастся. Значит мы знаем, что программа не остановится уже никогда, то есть контрпример не будет найден. Утверждение об истинности P можно считать доказанным, программу можно выключать.

Конечно же, наша программа за конечное время B_N успела проверить лишь конечное число вариантов от 1 до некоторого M, но из рассуждений, приведенных выше, следует, что нам этого каким-то образом оказалось достаточно для того, чтобы утверждать об истинности P для совсем любого n. В чём тут подвох? Подвоха тут нет.
\square

Задумайтесь на секундочку: почти любой сложный вопрос математики, касающийся натуральных чисел, может быть установлен путём перебора конечного числа вариантов. Будь то теорема Ферма, гипотеза Гольдбаха, Коллатца или кого ещё: достаточно проверить конечное число случаев. Не знаю как вам, но на меня в своё время этот факт произвёл неизгладимое впечатление.

Насколько этот результат практичен? На самом деле совершенно не практичен. Во-первых, не понятно как вычислить значение B_N. Во-вторых, даже если мы его вычислим для какого-то N, то оно наверняка окажется настолько гигантским, что вряд ли поместится в наш калькулятор. Так что выгоды мы из этого всего извлечь судя по всему не сможем, увы. Но сам факт!

Логично было бы, если бы после изложения этого результата я тут же показал бы, как считать числа B_n, однако сейчас мы уйдём в сторону и я покажу как эти числа ещё можно было бы использовать, если бы они были в нашем распоряжении.

Попробуем написать такую программу, которая будет анализировать другую программу, и говорить нам о том, зависнет она или же нормально остановится. Можно рассматривать такую программу как функцию H:P\to\{0,1\}, где P — множество всех возможных программ. 0 означает, что программа зависнет, 1 что остановится.

При условии, что мы можем написать программу, вычисляющую B_n, мы нашу задачу можем очень легко решить. Пусть нам дана программа x длины n, для которой надо установить остановится ли она. Поскольку программа — это просто описание каких-то действий, мы можем заставить выполнять эти действия не компьютер, а нашу программу H, то есть мы как бы будем симулировать выполнение программы x внутри программы H. Это не сложно технически, но я не буду углубляться в детали как это реализуется. Если вы знакомы с компьютерными технологиями, то наверняка слышали про интерпретаторы, виртуализацию, виртуальные машины и подобное. Это именно то, это возможно и это не особо сложно.

По ходу выполнения программы x, программа H будет считать, как долго x работает. Если вдруг окажется, что программа x работает дольше, чем время B_n, то мы знаем, что она не закончится, и H останавливает x, выдавая нам результат 0. Если же x остановится сама раньше, то H даст результат 1. Вроде всё.

А теперь давайте напишем такую программу A, которая так же будет принимать на вход какую-то другую программу x, затем будет запускать на ней программу H, и если H(x)=1, то A будет зависать (например, начнёт считать все натуральные числа подряд), а если же H(x)=0, то она будет возвращать какой-то результат. Такую программу так же легко написать.

Попробуем понять какой результат мы получим, если на вход программе A мы дадим её же саму, то есть попробуем выполнить A(A). Что будет? Предположим, что H(A)=0, тогда программа A должна завершиться, вернув результат. Но это противоречит тому, что H(A)=0. Из этого противоречия видно, что H(A)\not=0. Пусть теперь H(A)=1, но тогда A должна зависнуть, что противоречит тому, что H(A)=1, а значит H(A)\not=1. Как так? H оказывается не равно ни одному своему возможному значению!

Это противоречие означает, что программа H не может быть написана, не существует такой программы и существовать не может. Но как так, ведь мы же чётко указали, как её можно написать! Если вглядеться, то при описании работы программы H мы опирались на то, что мы можем как-то вычислить числа B_n, но мы не показывали этого. И это единственный момент во всём рассуждении, который мы никак не обосновали. Значит, числа B_n вычислить невозможно.

Тот факт, что есть такая функция B, которая вполне определена, но которую невозможно вычислить, может показаться невероятным. На самом деле если подумать, то это довольно не сложно. Из определения функции B мы могли бы попробовать вычислить B(n), запустив одновременно все возможные программы длины n, и, заведя таймер, пытаясь понять, какое самое большое время работы программы. Однако с учетом того, что есть программы, которые зависают, мы никогда не узнаем, когда таймер пора выключать, хотя конечно же такой момент во времени существует. Это и есть пример того, что функцию невозможно вычислить.

Мы получили два результата.

Теорема. Невозможно написать программу, которая бы могла по коду другой программы определить остановится ли она или зависнет.

Теорема. Числа B_n невычислимы. Другими словами невозможно определить максимальное время, которое может работать независающая программа длины n.

Приведённые рассуждения можно вывернуть ещё и вот под каким углом. Напишем программу E, которая будет проверять истинность произвольного утверждения x путём последовательного перебора всех возможных доказательств (программа может начинать с коротких доказательств и постепенно переходить к более длинным, так что такая программа определённо может быть написана). Если предположить, что всё можно доказать или опровергнуть, то через какое-то время наша программа либо найдёт доказательство для x, либо доказательство для \neg x.

Используя эту программу, однако, мы опять же легко можем написать пресловутую программу H проверяющую, остановится ли программа y или нет. Просто вместо запуска программы y и ожидания времени B_n мы на этот раз будем искать доказательство остановки или зависания y. Поскольку мы уже знаем, что программа H не может существовать, наше предположение, что программа E всегда либо найдёт доказательство x либо \neg x так же не верно. Это значит, что существуют такие утверждения x, которые невозможно ни доказать ни опровергнуть. Как вы вероятно помните, это есть ни что иное как теорема Гёделя о неполноте:

Теорема. Существуют утверждения, которые невозможно ни доказать ни опровергнуть.

Я упомянул, что числа B_n окажутся скорее всего довольно большими. Оказывается, мы можем примерно прикинуть насколько именно большими они будут.

Теорема. Числа B_n с ростом n растут быстрее, чем любая последовательность, которую мы могли бы вычислить.

Доказательство. Предположим, что это не так, и что существует некоторая последовательность x_n такая, что мы можем её вычислить и что B_n\le x_n. Но тогда мы можем запустить все программы длины n и останавливать их как только они отработают время x_n. Среди программ, остановившихся раньше, выберем ту, что работала дольше. Время, которое она работала — это и есть B_n. Но это значит, что мы смогли их вычислить, а это противоречит теореме 3.51. Значит, такой последовательности x_n всё же не существует.
\square

Упражнение. Если предположить, что мы имеем в нашем распоряжения числа B_n и неограниченный вычислительный ресурс, проверка истинности произвольных утверждений может всё равно вызывать трудности. Гипотеза Коллатца является как раз таким примером. Если наша программа поиска контрпримера не остановилась за время B_n, то она не остановится действительно никогда, но это может иметь разное значение: либо она нашла такое m, что последовательность Коллатца для него будет бесконечной (и соответственно программа будет бесконечно долго вычислять её значения), либо же что она такого m никогда не найдёт. Таким образом мы не получили из работы программы никакой полезной информации. Однако простая модификация алгоритма поиска контрпримера может всё таки дать нам способ понять найден ли контрпример либо же он не будет найден никогда. Придумайте эту модификацию.

Упражнение. Великая теорема Ферма (на английском её называют последней теоремой) утверждает, что уравнение
x^n + y^n = z^n
не имеет решений для n>2. Покажите, как можно было бы её доказать при неограниченном вычислимом ресурсе и известных B_n.

У Великой теоремы Ферма интересная история. Ферма сформулировал её в 1637 году в виде пометки на полях книги, которую он читал. Там же он указал, что он нашёл элементарное доказательство этой теоремы, но поскольку места недостаточно, он его приводить не будет. В итоге первое доказательство этой теоремы появилось только в 1994 году (спустя 356 лет!) и занимало оно 130 страниц. В этом доказательстве спустя год была найдена ошибка, которую ещё год исправляли. В итоге финальное доказательство без ошибки было представлено лишь в 1996 году. Такая вот история.

В заключение этого параграфа я замечу, что конечно всё написанное здесь очень неформально. Из написанного мной совершенно например не понятно каким образом компьютерные программы увязываются с аксиоматикой натуральных чисел и теорией множеств. Так же совершенно не понятно что именно из себя представляют сами программы. Использовать в качестве модели реальные компьютеры и реальные языки программирования не получится, так как в реальных системах есть много факторов, которые мешают идеализированному математическому описанию вычислительного процесса: механизмы мультипоточности, пайплайнинг, всякие мьютексы, графический интерфейс, ввод-вывод и вот всё подобное не дают оставляют возможности рассуждать о вычислениях абстрактно.

Чтобы избавиться от всех мешающих факторов реальных компьютеров используется модель машины Тьюринга, которая представляет собой видимо самую простую модель компьютера. Я не буду её описывать, но если вы хотите понять как примерно устроен формализм того что я здесь изложил, вы можете поискать статьи о ней и о том как она соответствует реальным вычислительным машинам, рекурсивным функциям и понятию множеств. Так же рекомендую почитать трагичную и важную биографию самого Алана Тьюринга: будучи блестящим учёным, работающим в области вычислимости и криптографии (благодаря значительным образом его работе союзники могли перехватывать шифрованные сообщения Германии во Вторую Мировую войну; теорема 3.50 так же была сформулирована и доказана именно им), он был обвинён в гомосексуальных связях и принуждён к химической кастрации и употреблению гормональных таблеток «для лечения гомосексуализма». Закончилась история лишением его всех военных наград и званий, а так же полным запретом на занятия накой. Итогом таких мер по борьбе с гомосексуализмом стал его суицид.

Сегодня ему ставят памятники, его именем названа самая престижная награда в области компьютерных наук. На этой трагичной ноте мы и закончим эту главу.

Этот текст последний параграф третьей главы учебника. Напомню, что учебник целиком доступен в pdf, что гораздо удобнее читать.

This work is licensed under GPL - 2009 | Powered by Wordpress using the theme aav1
SEO Powered by Platinum SEO from Techblissonline