typedef

Кросспост с личного блога.

У меня ни школьные, ни институтские курсы математики никогда не вызывали особых проблем. Я даже участвовал в каких-то математических олимпиадах и даже, не поверите, занимал призовые места. Это сейчас я обленился  и все забыл, но когда-то решение задачек и головоломок меня весьма увлекало. Однако у меня была и остается одна черта, раз за разом основательно портящая всю малину, — невнимательность.

Помню, как дважды досрочно (каково, а?) сдавал экзамен по дифурам. Оба раза я был идеально готов, и преподаватель об этом знал. И оба раза я сделал глупейшие, хотя и разные, ошибки и пришел к неправильным результатам. Если бы я сам у себя принимал экзамен, то ошибки эти заметил бы непременно, настолько они бросались в глаза! В результате получил «хорошо», и это было очень обидно, но правильно и справедливо.

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

Приведу на тему самопроверки несколько поучительных примеров.

1. True story. Наверняка все уже слышали эту историю.

Был он [преподаватель математики] человеком крупным и покушать любил. В столовой однажды взял он два супа, два вторых… словом, обед в двух экземплярах. Подходит к кассе. Молоденькая кассирша щелк-щелк-щелк на счетах:«С вас 2-17», он в ответ «Неправильно». Кассирша снова за счеты: «2-05», он в ответ «Неправильно». Кассирша, окончательно смущенная и напуганная, — щелк-щелк-щелк — «1-97», а сей ученый муж ей в ответ: «Снова неправильно!» Отчаявшаяся кассирша: «А сколько должно быть?!» Он в ответ: «Не знаю. Но два одинаковых обеда — четное число!»

2. Взвешивание монет.

У нас есть 9 монет, 8 из которых имеют одинаковый вес, а вес одной (фальшивой) больше весов остальных. Также у нас есть равноплечные весы с чашами. Необходимо найти фальшивую монету за минимальное число взвешиваний.

При таком малом количестве монет найти правильное решение можно просто перебором, это вряд ли займет больше минуты. Взвешивая по 3 монеты на каждой чаше, мы найдем группу из 3 монет, вес которой больше веса каждой из двух других групп. Затем, взвешивая 2 из этих 3 монет, находим фальшивую. Итого 2 взвешивания.

Попробуем подойти с другого бока. Представим номер фальшивой монеты в двоичном виде. Очевидно, 3 бит недостаточно, в них можно закодировать только 8 номеров, а 4 — уже слишком много, в них можно закодировать целых 16. Точное значение количества требуемых битов выражается двоичным логарифмом: log₂9. Теперь заметим, что каждое взвешивание может иметь 3 возможных исхода: левая чаша тяжелее, правая чаша тяжелее, чаши в равновесии. Таким образом, результат взвешивания можно представить log₂3 битами. Теперь чтобы найти минимальное необходимое количество взвешиваний, нужно найти отношение количества неизвестных нам битов к количеству битов, получаемых за одно взвешивание, и округлить вверх: ceil(log₂9 / log₂3) = ceil(log₂(9/3)) = ceil(log₂3) = 2.

Понятно, что для 9 монет все это имеет мало смыла в силу очевидности ответа, но что если монет не 9, а 999? Слабо найти минимальное число взвешиваний? Да легко: ceil(log₂999 / log₂3) = ceil(log₂333) = 9. И теперь, зная ответ, гораздо проще подобрать искомую последовательность взвешиваний.

3. Самые быстрые лошади.

В скачках участвует 25 лошадей. В каждом заезде может участвовать не более 5 лошадей. Результатом заезда является последовательность прохождения участниками финишной черты, времена не фиксируются. Две лошади не могут финишировать одновременно. Скорости лошадей постоянны: в каждом заезде лошадь скачет с одной и той же скоростью. Требуется за минимальное количество заездов определить первую, вторую и третью быстрейшую лошадь.

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

Что ж, попробуем подумать. Из условия следует, что если взять любые две лошади, то или первая будет быстрее второй, или вторая быстрее первой. Сформулируем, что именно нужно найти:

• лошадь, которая быстрее каждой из 24 остальных лошадей;
• лошадь, которая быстрее каждой из оставшихся 23;
• лошадь, которая быстрее каждой из оставшихся 22.

Таким образом, для получения ответа нужно знать по меньшей мере 24 + 23 + 22 = 69 отношений «быстрее».

Теперь заметим, что каждый заезд из 5 лошадей дает нам 4 + 3 + 2 + 1 = 10 отношений. После этого легко найти минимальное количество заездов: просто поделим 69 на 10 и округлим вверх. Выходит, что нужно как минимум 7 заездов. Конкретную расстановку лошадей не буду приводить, можете сами определить, если хотите.

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

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

(3 голосов, средний: 5,00 из 5)

 Loading ...

Иногда встает такая задача: зная имя файла или его фрагмент, найти пакет(ы), которому(ым) этот файл принадлежит.

Если область поиска ограничивается установленными пакетами, то подойдет любой из вариантов:

dpkg -S pattern
dpkg --search pattern
dpkg-query -S pattern
dpkg-query --search pattern

Понятно, что dpkg здесь — просто фронтенд к dpkg-query.

Шаблон имени файла pattern может включать shell-style wildcards (можно я не буду переводить?).

Если же хотим искать во всех пакетах вообще, даже неустановленных, то:

apt-file search pattern

Если задать опцию --regexp|-x, то pattern становится перловой регуляркой.

Кстати, apt-file использует собственную БД, поэтому перед первым использованием нужно выполнить

apt-file update

чтобы синхронизироваться с репозиториями из /etc/apt/sources.list.

(Еще не оценили)

 Loading ...

А я ведь тоже их осилил, и даже получил 98.1% за AI, завидуйте! Коллеги-блоггеры, к счастью, все уже написали за меня, так что кто интересуется темой, наверняка уже в курсе. Я добавлю только немного личных ощущений.

ML Class близок к идеалу. Именно таким должен быть настоящий учебный курс — невероятно простым, невыносимо нудным, но при этом дающим твердое понимание того, что происходит и как это работает. Рижским бальзамом на душу льются слова Andrew Ng: «Если вы это не понимаете, не переживайте, сейчас я расскажу, поймете» или «Если вы это не понимаете, не переживайте, я тоже не понимаю, это вам не нужно«. Ну и прочие подобные высказывания и шутки вроде «Если вы эксперт в линейной алгебре и знаете, что такое собственные вектора, то …» доставляют. Столько студентов сразу почувствовали себя экспертами в линейной алгебре! Отдельная благодарность за возможность ускорить лекции в 1.2 и 1.5 раза.

AI Class имеет гораздо больший охват материала, но при этом он менее проработанный. Куча несогласованной терминологии, много недосказанного, вопросы иногда расплывчаты и имеют слабое отношение к тексту. Постоянно происходят какие-то технические накладки, то сроки отодвигаются, то публикуются уточнения к вопросам, то еще какая напасть. Это не говоря уже об очаровательном немецком акценте Prof. Sebastian Thrun, которого я, в отличие от ускоренного Andrew Ng, понимал только процентов на 95 — некоторые фразы не могли понять даже native speakers. Но, несмотря на все недостатки, получился очень неплохой обзорный курс.

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

В целом нисколько не жалею, но курсы будущего семестра — разве что в пассивном режиме посмотрю.

Thanks for LISP and AI.
RIP.

Черт, да что же это за месяц такой…

Thanks for C and UNIX.
RIP.

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

Категорически не соглашусь. Лично для меня курс философии науки стал, не побоюсь этого слова, откровением. Можно сказать, поворотным пунктом. Когда в школе и в вузе проходят различные науки, совершенно не затрагивают тему того, насколько мы можем быть уверены в предлагаемом знании. И у каждого слушателя формируется своё весьма наивное представление о сущности истины и человеческого знания. Кто-то, например, освоил какой-то метод в какой-то области, сидит и только его применяет, а всё остальное считает ересью. А кто-то, скажем, любое порождение своего мозга принимает за великое открытие. Кто-то считает математику непогрешимой, а кто-то – что математика вообще ни на что не способна. Немалая доля людей вовсе науку не признаёт, а верит в различное НЛО и т. п.

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

Возможно, автору просто не повезло с преподавателями оного курса.

Я вам тоже могу открыто признаться, что не мог терпеть философию до тех пор, пока не прослушал курс философии науки в аспирантуре. В том числе когда проходил «философию» на четвёртом курсе.

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

> В этой области множество людей столетиями придумывали термины, «законы» и «принципы».

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

> до какого-нибудь Витгенштейна

Витгенштейн, равно как и вся философия науки двадцатого века, совершенно напрямую связан с математикой и проблемами построения искусственного интеллекта. Ещё раз повторю, что ни его, ни любого другого философа не следует принимать на веру. Просто полезно на минуту представить себя в его шкуре.

> И думается мне, что те принципы, которые, по идее, должна прививать ученому философия, нормальный ученый прививает себе сам.

А вот для чего, скажем, программисты алгоритмы проходят? Достаточно было бы обучить кодить и компилять, а коли человек достаточно умный, то до всех необходимых алгоритмов сам додумается. Конечно, это грубая аналогия, но смысл именно такой. Мировоззрение, конечно, за самого человека никто не сформирует. Но если он будет выбирать подходящее мировоззрение не только из собственных домыслов, но и на основании предыдущего опыта человечества – то он сможет сделать это более адекватно. Конечно, научное мировоззрение неявно сквозит в большинстве специальных курсов. Но, как известно, явное лучше неявного.

> Нет, я согласен, что при наличии хорошего преподавателя это может быть даже интересно, но нужно ли?

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

Ежели спрашивать лично меня – то я бы исключил литературу и русский язык из школьной программы за полной бесполезностью. Оставил бы только чтение-запись в начальной школе.

Кстати, вот ещё вспомнил. Одна из основных задач философии науки – это отличать науку от ненауки. В связи с нынешним засильем мракобесия и «альтернативной» науки это становится как никогда актуально. Грубо говоря, учёный, занимавшийся только наукой и не занимавшийся философией, скорее всего, правильно определит, кто есть кто, по крайней мере в своей области. Но вот убедить другого человека, что это так – это уже задача посложнее. Скорее всего, его аргументы сведутся к «это же очевидно любому здравомыслящему человеку» и «пойди ещё раз поучись в школе». Тогда как знакомство с философией и методологией науки даёт некоторые критерии (прежде всего фальсифицируемость) и приёмы убеждения. Хотя, к сожалению, переубедить «адепта» всё равно почти никогда не получается, но по крайней мере ты сам от такого спора не будешь погружаться в состояние отчаяния от осознания своего бессилия оправдать научную точку зрения.

Из конкретных философских трактатов могу порекомендовать разве что статью Карла Поппера об эволюционной эпистемологии http://www.keldysh.ru/pages/mrbur-web/philosophy/popper.html . Также не совсем по теме, но всё же – Ричард Докинз «Эгоистичный ген».