![[info]](http://l-stat.livejournal.com/img/userinfo.gif?v=92.1){kind=small}
http://habrahabr.ru/post/144648/
Всем приятного чтения, кому вдруг интересно =)
Многим известна старая задача: дана матрица N*N, в которой все строки и все столбцы отсортированы по неубыванию (независимо!). Необходимо найти в ней данный элемент.
Пример матрицы:
1 5 8 20 2 9 19 21 12 15 25 30 16 17 28 32Задача поиска элемента в такой матрице за O(N) совершенно несложна. Если (вдруг) кто не знает, может подумать пару минут на досуге.
Гораздо более интересна другая задача: докажите строго, что не существует алгоритма с оценкой времени в худшем случае быстрее O(N).
Вот незадача.
С 9 по 14 июля проходит KPI-Open 2012, контест, в организации которого я принимаю участие. (Кстати, всем олимпийцам очень рекомендую: в отличие от многих лет позади, на этот раз задачи делают люди, которые знают, что такое спортивное программирование — проблемсет у нас очень интересный, всех приглашаю.)
С 14 по 16 июля, в то же время, проходит знаменитый ICFP Contest 2012. После прошлого раза, когда мы с первой своей попытки заняли 15 место среди всех команд мира, я серьезно настроен на работу :) Пора начинать собирать команду.
При этом весь июль теоретически у меня сжирают сборы на военной кафедре. С этим вопросом стоит разобраться, если я не хочу, чтобы украинские органы еще ближайших 5 лет проявляли ко мне повышенный интерес дважды в год. Так что, учитывая все факторы, эта неделька пройдет под крайне активным лозунгом :)
- уметь водить машину;
- уметь стрелять из огнестрельного оружия;
- уметь сделать ремонт своими руками;
- уметь выполнять (подставьте произвольный спортивный норматив);
- раз в год бывать на море;
- путешествовать везде, где только можно;
- смотреть новости
- разбираться в политике, иметь личное мнение и активную гражданскую позицию;
- попробовать (подставьте алкогольные напитки и коктейли);
- разбираться в экономических реалиях, отличать опцион от депозита и дебет от кредита.
- to be continued... здесь только то, что на натыкался недавно лично я.
Уважаемые приверженцы традиционной формы жизни. Пожалуйста, запомните: я никому вокруг ничего не должен. Единственный долг у меня — перед самим собой: я должен тратить время только на то, что мне интересно и нужно. А никак не на то, что въелось в большинство голов как общественные нормы и стандарты.
Оценка ценности потраченного на что-либо времени зависит от выбранной success metric.
Вот скажем, посмотрел я сейчас одну лекцию из трех по курсу ML в ШАД.
С моей точки зрения, я узнал 1/3 ценного и интересного мне материала.
С точки зрения гипотетического проверяющего домашние задания, пока что я умею решать задач 1/7.
У меня есть жизненное правило: каждый год выучивать на более-менее профессиональном уровне минимум 2-3 инструмента, которые впоследствии будут экономить мне время.
Многие люди не умеют пользоваться компьютером. Для них существует одна-единственная вещь, с помощью которой они делают все на свете, даже всем своим любимым софтом они пользуются на уровне детского сада — как научили, так и пользуюсь. Борьба с ошибками софта у них сводится к чему-то среднему между карго-культом и манерой дебаггинга off-by-one error посредством последовательных «А что будет, если я добавлю здесь -1?» Так и с программами: «А что будет, если я уберу эту галочку? О, заработало!»
Для каждой задачи существует свой инструмент. Многие из инструментов, используемых вами по жизни, имеют бездну возможностей, параметров и вариаций. Если разобраться в них глубоко, это может сэкономить кучу бесценного времени каждый раз, когда вам что-нибудь нужно.
LaTeX спасает, когда вам нужно набрать произвольный технический текст, в котором важно оформление. Гибкость LaTeX поражает. Его невозможно выучить полностью, но одна-единственная прочитанная полностью книга (например, С. Львовский «Набор и верстка в системе LaTeX») позволит достаточно свободно верстать произвольной сложности документы.
Подмножество разметки LaTeX перенесли в свою систему программисты Microsoft Word, внедрив, начиная с версии 2007, продвинутый редактор формул. Поверьте, читатели вам будут благодарны, если в ваших отчетах и презентациях в формулах можно будет разобраться с первого взгляда, как в обыкновенном учебнике. Михаил Баландин описал все эти возможности в одном документе. Документ читается за полчаса. Количество кликов мышкой, которое вы потратили по сей день, чтобы набрать ту или иную формулу в Word 2003 или Word 2007, составляет суммарно дни, если не недели.
Если вам нужно скачать из интернета 1000 текстовых файлов, распарсить их содержимое по пробелам, и покидать результаты в другой текстовый файл, скрипт на Python будет компактнее, проще и гибче, чем специально созданный одноразовый проект на C#/C++. То же самое относится к вашей музыкальной коллекции, которую вам однажды вздумалось рассортировать по тегам или альбомам.
В то же время не нужно создавать еще один безымянный проект, чтобы проверить какую-нибудь фичу в C# или протестировать, что выдаст кусок кода. Для этого есть LINQPad.
Математические вычисления оставьте математическим средам. Их создают команды образованных людей годами, они неисчислимы в своих фичах. Мой выбор — Wolfram Mathematica. Лично мне кажется, что MATLAB давно уснул в своих 90х, но это дело вкуса, конечно же. Я использую Mathematica для:
- любых математических вычислений сложнее calc.exe
- анализа данных. Многие предпочитают R. Не знаю, не пробовал, не могу сказать. Пока фичи Mathematica меня всем устраивают.
- построения графиков. Речь идет о гистограммах и графиках функций (2d, 3d). Все остальное уже не в прерогативе Mathematica, хотя она это и умеет (честно говоря, она умеет все).
Чтобы пользоваться ей адекватно, прочтите книгу или документацию. Опять-таки, на это у вас уйдет несколько дней. Сэкономленное время — годы.
Я часто вижу людей, которые используют Mathematica как консоль, умея только посылать ей кусочки вычислений на вход, и пытаясь по выходу понять, где у них ошибки в синтаксисе. Они переписывают половину стандартных функций самостоятельно с помощью For и While, поскольку не знают, что нужные функции уже кем-то написаны. Они даже не подозревают, что Mathematica умеет создавать динамические пользовательские интерфейсы, связываться с другими языками программирования, работать с графами, вероятностями, ML, и кучей химических/физических/экономических данных. Я сравниваю таких людей с операторами ПК в фотоателье, которые любую папку открывают методом «правая кнопка мыши → открыть».
Слова «прочтите %s», которые я повторяю все время — главный посыл этой заметки. Не пропускайте их мимо глаз. Знать название инструмента — ничто. Пользоваться им продуктивно — всё.
Мне часто нужно делать иллюстрации к своим статьям, отчетам и прочему. Для каждого типа иллюстрации существует свое удобное средство.
- Чтобы нарисовать граф, нет ничего лучше GraphViz.
- Чтобы сделать диаграмму, блок-схему, дерево, UML или любую другую типичную фигуру — Microsoft Visio 2010.
- Для гистограмм и графиков есть Mathematica.
- Для геометрических построений — GeoGebra.
Когда у вас есть текстовый файл, в котором нужно найти и заменить какие-то конструкции на другие похожие, на помощь придут регулярные выражения. Да, я опять дал ссылку на книгу.
В то же время, если вы будете использовать регулярные выражения, чтобы выдирать какие-то кусочки из кода чужих HTML-страниц, потусторонние твари прорвут дыру в пространстве-времени и сожрут вас живьем. Для этого есть специальный язык — язык запросов к XML. Называется он XPath. Любой уважающий себя язык программирования имеет где-то в глубинах гугла библиотеку для работы с XML с поддержкой запросов на этом языке (например, для C# это HTML Agility Pack). Для тестирования своих запросов есть XPath Visualizer.
Продвинутым программистам нет смысла доказывать преимущества систем контроля версий. Для меня лучшая — это git или Team Foundation Server. Часто git удобно использовать, даже если в проекте не участвует никого, кроме тебя. В то же время многие даже в проекте на двоих предпочитают перекидываться кусочками кода по почте или скайпу.
Отмечу — в системе контроля версий можно держать любой проект, не обязательно исходный код программы/сайта. Это может быть ваша статья в LaTeX или финансовый квартальный отчет.
Список можно дополнять бесчисленно. Я мог бы сказать, что он в первую очередь направлен на студентов первых курсов технических специальностей, которые еще не умеют организовывать свое рабочее пространство... эх, если бы это было так :( Когда видишь тридцатилетнего дядьку-менеджера, который выравнивает строчки в Word пробелами, становится грустно за человечество.
Учиться никогда не поздно, просто составьте себе маленький планчик и прочтите наконец в следующем месяце в метро книжку, которая упростит вам сотни ежедневных действий. Например, у меня на очереди — качественное изучение командной строки. Будучи убежденным пользователем Windows, я достаточно плохо знаком с шеллами, к стыду своему. Осталось только выбрать между PowerShell и каким-нибудь Cygwin.
Приглашаю каждого делиться в комментариях инструментами, которые ему удобно использовать. Любые, для любых целей. Пусть все возьмут себе на заметку что-нибудь от кого-нибудь.
Поступают онлайн запросы <l, k>: найти наименьшую правую границу r такую, что подотрезок a[l..r] имеет ровно k различных чисел.
За какую асимптотику времени-памяти вы умеете отвечать на запрос и как? :)
UPD: Мне известно красивое решение за O(N log N) памяти, O(log N) времени ответа на запрос, и O(N log N) времени препроцессинга. Расскажу, когда все выскажутся, какие у них есть идеи.
В общем, вот такая у них будет домашка.
- Реализуйте простейшую версию чисто функциональной хеш-таблицы «ключ-значение». Хеш-функция (по вашему выбору) отображает пространство ключей на пространство хешей 0..M-1. Для каждого хеша хранится список значений-коллизий с таким хешом. Чисто функциональный массив хешей (не списки коллизий!) реализуйте как любое дерево поверх него: Rope или дерево отрезков.
Дополнительный плюс в карму, если хеш-таблица будет еще и персистентной. - Имеется тип данных «арифметическое выражение» с конструкторами Const, Plus, Multiply, IfThenElse, UnaryMinus. При желании можно расширить синтаксис ещё конструкторами. Опишите тип «Zipper для арифметических выражений».
- В современных IDE с помощью сочетания клавиш (скажем, Ctrl+U) можно выделять текущую синтаксическую конструкцию, на которой стоит курсор. Нажав то же сочетание клавиш еще раз, можно расширить выделение до ближайшей цельной конструкции, содержащей текущую, еще раз нажав – расширить еще больше, и т.д. Другое сочетание клавиш (скажем, Ctrl+N), перемещает выделение на следующую синтаксическую конструкцию на том же уровне с текущим выделением.
Так, пусть есть строка:
int n = f(1, 2+3) - g(4);
Пусть курсор сейчас находится рядом с цифрой “2”. Последовательность нажатий “Ctrl+U, Ctrl+N, Ctrl+U, Ctrl+U, Ctrl+N, Ctrl+U” породит следующую последовательность выделений: “2”, “3”, “2+3”, “f(1, 2+3)”, “g(4)”, “f(1, 2+3) - g(4)”.
Дана ссылка на zipper c вершиной синтаксического дерева и список команд (команда – отдельный алгебраический тип данных). Верните ссылку на вершину, которая в итоге окажется выделенной. - (*) Упражнения на понимание основ теории рекурсивных типов данных. Напоминаю: мы манипулируем переменными этих типов «с точностью до концептуального равенства»: два типа концептуально одинаковы, если переменные этих двух типов несут в себе одну и ту же информацию. Так,
, потому что «либо A, либо A» — это то же самое, что «A с булевским флагом».- Докажите закон дистрибутивности:
- Производная типа данных — тип его контекста. Исходя из этого понимания, докажите законы производных:
- Важно! Рассмотрим бинарное дерево:type Tree<’a> =
| Leaf
| Node of ’a * Tree<’a> * Tree<’a>
Его алгебраическое представление:
(проверьте). Решите это квадратное уравнение, выбрав решение со знаком «-». Раскройте его в ряд Тейлора. Внимательно посмотрите на последовательность коэффициентов: они должны легко гуглиться и напомнить вам один очень известный ряд. А теперь докажите полученное выражение для T (в виде ряда) с точки зрения теории типов, забыв про квадратное уравнение и ряд Тейлора.
- Докажите закон дистрибутивности:
- (*) Данная задача исключительно для тех, кто знаком с упомянутыми в ней терминами.
Union-Find (Disjoint-Set Union, система непересекающихся множеств) – структура данных, которая умеет быстро отвечать на запросы find(u) – «к какому множеству принадлежит данный элемент?» и unite(u, v) – «объединить два данных множества». С помощью нее можно, например, поддерживать граф, в который добавляются ребра, и отвечать на вопрос «Сколько сейчас в графе компонент связности?» Это простейшая версия так называемой Dynamic Connectivity Problem.
Классическая реализация Union-Find полагается на две эвристики: эвристику рангов и эвристику сжатия пути. С ними обоими амортизированная стоимость запроса есть
, где 
– обратная функция Аккермана. Если оставить только любую одну эвристику из двух, то стоимость запроса упадет до 
.
Union-Find традиционно считается одной из структур, которые невозможно сделать чисто функциональными и персистентными с сохранением ассимптотики времени работы, потому что она императивная по духу и сути своей. Тем не менее, если избавиться от одной из эвристик (какой?), и воспользоваться чисто функциональными массивами (например, деревьями отрезков), то можно легко реализовать персистентный Union-Find.
Сделайте эту реализацию (запросы find и unite принимают дополнительный параметр «номер ревизии»). Укажите, какой теперь стала ассимптотика ответа на запрос.
Это цитата из фильма The Prestige. Она вообще про иллюзионный жанр. Но слова, которые я выделил в конце — квинтэссенция того чувства, ради которого я все время рвусь рассказывать людям красивые вещи.
Попробуйте познать его.
"You never understood... why we did this. The audience knows the truth. The world is simple, miserable, solid all the way through. But if you can fool them, even for a second... then you can make them wonder. And you get to see something very special. ... You really don't know. ... It was the look on their faces".
Правильный ответ совершенно очевиден любому, кто знаком с волшебным словом «логика». Тем не менее, в опросе он... на последнем месте!
Проголосовало 2500+ человек из числа обычных киевских вконтактовцев. Общее резюме — мне жаль человечество :(
P.S. "Dear God, what is it like in your funny little brains, it must be so boring!"
"Sherlock" (BBC).
Вопрос: может ли иррациональное число в иррациональной степени дать рациональный результат?
Да, может. Доказательство:
Рассмотрим число
. По предположению от противного, оно обязательно иррационально. Но тогда 
— рационально. Значит, предположение неверно.Доказательство примечательно несколькими фактами:
- оно использует принцип исключенного третьего;
- оно неконструктивно: несмотря на использование конкретных чисел и построений в ходе док-ва, мы все равно не получаем в результате конкретного примера рациональной степени.
- более того, в итоге док-ва мы даже не знаем, рационально ли все-таки число A или нет (на самом деле иррационально, но это очень сложно доказать).
- наверное, это самое простое и «школьное» из доказательств, обладающих вышеуказанными свойствами.
Красота против интуиционизма.
*ведущий подходит к фортепьяно и нажимает до*
Третье можно описать звуковым образом вот так:
*нажимает до-диез*
Обратите внимание, разница между звуками в полтона.
Это было первое и третье. К сожалению, второе, появившееся в 1985 году, мы охарактеризовать таким же способом не сможем. Назовите это второе.
