• Как я пишу конспекты по математике на LaTeX в Vim

    • Translation
    • Tutorial
    Некоторое время назад на Quora я отвечал на вопрос: как успевать записывать за лектором конспект по математике на LaTeX. Там я объяснил свой рабочий процесс по конспектированию в LaTeX с помощью Vim и Inkscape (для рисунков). Но с тех пор многое изменилось, так что я хочу опубликовать несколько постов в блоге с описанием нового процесса. Это первая из статей.

    Я начал использовать LaTeX для конспектирования во втором семестре курса математики, и с тех пор написал более 1700 страниц. Вот несколько примеров, как выглядит конспект:


    Читать дальше →
  • Как я рисую иллюстрации для конспектов по математике в Inkscape

    • Translation
    В прошлой статье я рассказал, как пишу конспекты по математике на LaTeX в Vim. В этой статье покажу, как создаются рисунки для этих конспектов с помощью Inkscape, а также расскажу о своём самодельном менеджере горячих клавиш.

    Некоторые примеры


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

    Читать дальше →
  • Игры для программистов

      Должен признаться, что я плохой программист. Я не люблю настраивать Maven и писать конфигурации для Spring Framework. Я не знаю в деталях, как работает JVM (да и в общих чертах представляю это себе довольно смутно). Я плохо понимаю паттерны проектирования, а любая новая технология вводит меня в уныние. И тем не менее, я люблю программировать.

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

      Минуточку внимания.

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

      Так о чём же статья?
    • Игры для программистов, часть вторая

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

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

        Infinifactory


        image
        И что же это за майнкрафт такой?
      • Обучаемся самостоятельно: подборка видеокурсов по Computer Science

        • Translation
        image

        Содержание


        1. Введение в Computer Science
        2. Структуры данных и Алгоритмы
        3. Системное программирование
        4. Распределенные системы
        5. Базы данных
        6. Объектно-ориентированный дизайн и разработка софта
        7. Искусственный интеллект
        8. Машинное обучение
        9. Веб-разработка и интернет-технологии
        10. Concurrency
        11. Компьютерные сети
        12. Разработка мобильных приложений
        13. Математика для программистов
        14. Теория информатики и языки программирования
        15. Архитектура компьютера
        16. Безопасность
        17. Компьютерная графика
        18. Работа с изображениями и компьютерное зрение
        19. Интерфейс Человек-Компьютер
        20. Вычислительная биология
        21. Прочее

        Поддержка публикации — компания Edison, которая тестирует критические системы на отказоустойчивость, а так же проектирует и разрабатывает ПО для кластерных вычислений.
        Читать дальше →
      • Поиск кратчайших путей в дорожных сетях: от теории к реализации

          image

          В ближайшую субботу Виталий Осипов (Технологический институт Карлсруэ) начнёт читать в Computer Science клубе в Санкт-Петербурге курс по алгоритмам поиска кратчайших путей в графах. В ходе курса будут изучаться и реализовываться алгоритмы, используемые миллионами людей в таких сервисах, как Google/Bing/Yandex карты. Как всегда, вход свободный, регистрация не требуется, приглашаются все желающие.

          » Страница курса на сайте CS клуба
          Первая лекция: суббота, 5 ноября, 17:20
          Место: Математический институт Стеклова, Санкт-Петербург, Фонтанка 27, Мраморный зал (второй этаж)
        • Теоретическая информатика в Санкт-Петербурге


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

            В прошлом году в Санкт-Петербургском академическом университете открылся бакалавриат (А), готовящий студентов по информатике с дальнейшей специализацией по теоретической информатике, разработке программного обеспечения или биоинформатике.

            В этом году в Санкт-Петербургском государственном университете открывается бакалавриат (Ч) по математике и теоретической информатике.

            Поскольку я принимал участие в создании обеих этих программ, коллеги настойчиво рекомендуют мне объясниться. (Зовут меня Эдуард Гирш, и я работаю в лаборатории математической логики ПОМИ РАН.)
            Читать дальше →
            • +19
            • 10.7k
            • 1
          • Планеты и четвёртое измерение

            • Translation
            Наверняка вам известно, что планеты движутся вокруг солнца по эллиптическим орбитам. Но почему? На самом деле, они двигаются по окружностям в четырёхмерном пространстве. А если спроецировать эти окружности на трёхмерное пространство, они превращаются в эллипсы.

            image

            На рисунке плоскость обозначает 2 из 3 измерений нашего пространства. Вертикальное направление – это четвёртое измерение. Планета движется по кругу в четырёхмерном пространстве, а её «тень» в трёхмерном движется по эллипсу.

            Что же это за 4-е измерение? Оно похоже на время, но это не совсем время. Это такое особенное время, которое течёт со скоростью, обратно пропорциональной расстоянию между планетой и солнцем. И относительно этого времени планета двигается с постоянной скоростью по кругу в 4 измерениях. А в обычном времени его тень в трёх измерениях двигается быстрее, когда она находится ближе к солнцу.
            Читать дальше →
          • Как покупать электронику на Amazon

              Amazon logo
              Наверняка многие из вас попадали в ситуацию, когда в американском интернет-магазине есть интересующая вас вещичка по заманчивой цене, но доставку магазин осуществляет только в пределах США. Например, в крупнейшем интернет-магазине Amazon жители из стран СНГ могут заказывать лишь книги и фильмы, и то не все. Конечно же, можно компенсировать данный недостаток с помощью ebay, но где еще у вас может быть шанс купить iPod Touch 32 GB 3rd Gen за $269.99, а Nokia N900 за $559.99? А может, грешным делом заказать Nexus One? Падение доллара и ценовая политика производителей сделала покупки в США достаточно заманчивым делом.
              Все самое интересное под катом
            • Хочется взять и расстрелять, или ликбез о том, почему не стоит использовать make install

                К написанию сей заметки меня сподвигло то, что я устал делать развёрнутые замечания на эту тему в комментариях к статьям, где в качестве части инструкции по сборке и настройке чего-либо для конкретного дистра предлагают выполнить make install.
                Суть сводится к тому, что эту команду в виде «make install» или «sudo make install» использовать в современных дистрибутивах нельзя.

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

                Читать дальше →
              • «Что такое доказательство?»: взгляд из теоретической информатики

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



                  Чтобы объяснить, о какого рода доказательствах пойдет речь, рассмотрим пример: есть компьютерная программа, авторы которой утверждают, что программа делает что-то определенное (конкретные примеры будут чуть позже). Программу можно запустить и получить ответ. А как можно удостовериться, что программа делает то, что должна делать? Хорошо бы, если кроме ответа программа выдавала бы доказательство того, что этот ответ правильный.

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



                  Напомним, что граф называется двудольным, если его вершины можно покрасить в два цвета так, что ребра графа соединяют вершины разных цветов. Паросочетанием в графе называется такое множество ребер, что никакие два из них не имеют общего конца. Множество вершин графа называется покрывающим, если каждое ребро графа имеет как минимум один конец в этом множестве. Теорема Кенига гласит, что в двудольном графе размер максимального паросочетания совпадает с размером минимального покрывающего множества. Таким образом, чтобы доказать, что паросочетание является максимальным, можно предъявить, покрывающее множество, размер которого совпадает с размером данного паросочетания. Действительно, это покрывающее множество будет минимальным, поскольку каждое покрывающее множество обязано покрыть хотя бы один конец каждого ребра этого паросочетания. Например, в графе на рисунке паросочетание (M1, G3), (M2, G2), (M4,G1) будет максимальным, поскольку есть покрывающее множество размера 3, которое состоит из G2, G3 и M4. Отметим, что проверить такое доказательство гораздо проще, чем вычислять максимальное паросочетание: достаточно проверить, что размер паросочетания совпадает с размером покрывающего множества и проверить, что все ребра покрыты.

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



                  Как можно доказать правильность результата? Если система совместна, то доказательством совместности может стать решение этой системы (нетрудно доказать, что если у такой системы есть решение, то есть и рациональное решение, т.е. его можно записать). А как доказать, что система несовместна? Оказывается, что это сделать можно с помощью леммы Фаркаша, которая утверждает, что если система нестрогих линейных неравенств несовместна, то можно сложить эти неравенства с неотрицательными коэффициентами и получить противоречивое неравенство 0≥1. Например, система на рисунке несовместна, и если сложить первое уравнение с коэффициентом 1, второе с коэффициентом 2, а третье с коэффициентом 1, то получится 0≥1. Доказательством несовместности будет как раз набор неотрицательных коэффициентов.

                  В этой статье мы поговорим о том, нужны ли доказательства, или проверка доказательства всегда не проще, чем самостоятельное решение задачи. (В примере про максимальное паросочетание мы не доказали, что не существует алгоритма, решающего задачу за то же время, сколько занимает проверка доказательства.) Если мы не ограничиваем размер доказательства, то окажется, что доказательства нужны, а если будем требовать, чтобы доказательства были короткими, то вопрос о нужности доказательств эквивалентен важнейшему открытому вопросу о равенстве классов P и NP. Потом мы поговорим об интерактивных доказательствах (доказательства в диалоге). Обсудим криптографические доказательства, которые не разглашают лишнюю информацию, кроме верности доказываемого утверждения. И закончим обсуждением вероятностно проверяемых доказательств и знаменитой PCP-теоремы, которая используется для доказательства трудности приближения оптимизационных задач.

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

                  Читать дальше →
                • Что нужно знать про арифметику с плавающей запятой



                  В далекие времена, для IT-индустрии это 70-е годы прошлого века, ученые-математики (так раньше назывались программисты) сражались как Дон-Кихоты в неравном бою с компьютерами, которые тогда были размером с маленькие ветряные мельницы. Задачи ставились серьезные: поиск вражеских подлодок в океане по снимкам с орбиты, расчет баллистики ракет дальнего действия, и прочее. Для их решения компьютер должен оперировать действительными числами, которых, как известно, континуум, тогда как память конечна. Поэтому приходится отображать этот континуум на конечное множество нулей и единиц. В поисках компромисса между скоростью, размером и точностью представления ученые предложили числа с плавающей запятой (или плавающей точкой, если по-буржуйски).

                  Арифметика с плавающей запятой почему-то считается экзотической областью компьютерных наук, учитывая, что соответствующие типы данных присутствуют в каждом языке программирования. Я сам, если честно, никогда не придавал особого значения компьютерной арифметике, пока решая одну и ту же задачу на CPU и GPU получил разный результат. Оказалось, что в потайных углах этой области скрываются очень любопытные и странные явления: некоммутативность и неассоциативность арифметических операций, ноль со знаком, разность неравных чисел дает ноль, и прочее. Корни этого айсберга уходят глубоко в математику, а я под катом постараюсь обрисовать лишь то, что лежит на поверхности.
                  Читать дальше →
                • Международная конференция Computer Science Symposium in Russia (CSR 2011)


                    С 14 по 18 июня 2011 года в Санкт-Петербурге пройдёт 6-я Международная конференция Computer Science Symposium in Russia (CSR 2011). Темы конференции включают в себя алгоритмы и структуры данных, комбинаторную оптимизацию, теорию сложности вычислений, криптографию, комбинаторику, формальные языки и автоматы и др. Крайний срок подачи статей — 6 декабря 2010 года. Подробности на сайте конференции: http://logic.pdmi.ras.ru/csr2011
                    Ниже приведён список приглашённых докладчиков конференции.
                    Читать дальше →
                  • Частые ошибки программирования на Bash (окончание)

                    • Translation
                    Окончание перевода Bash Pitfalls. Предыдущие части доступны в блоге «Оболочки» (часть 1, часть 2) и в моём блоге.

                    22. echo "Hello World!"


                    Проблема в том, что в интерактивной оболочке Bash эта команда вызовет ошибку:
                    bash: !": event not found

                    Это происходит потому, что при установках по умолчанию Bash выполняет подстановку истории команд в стиле csh с использованием восклицательного знака. В скриптах такой проблемы нет, только в интерактивной оболочке.

                    Очевидное решение здесь не работает:
                    $ echo "hi\!"
                    hi\!

                    какое же тогда неочевидное решение?
                    • +43
                    • 14.7k
                    • 7
                  • Частые ошибки программирования на Bash (продолжение)

                    • Translation
                    Продолжаю знакомить сообщество с переводом Bash Pitfalls.
                    Часть первая.
                    Первоначальная публикация перевода.

                    11. cat file | sed s/foo/bar/ > file


                    Нельзя читать из файла и писать в него в одном и том же конвейере. В зависимости от того, как построен конвейер, файл может обнулиться (или оказаться усечённым до размера, равному объёму буфера, выделяемого операционной системой для конвейера), или неограниченно увеличиваться до тех пор, пока он не займёт всё доступное пространство на диске, или не достигнет ограничения на размер файла, заданного операционной системой или квотой, и т.д.
                    Что же делать?
                  • Частые ошибки программирования на Bash

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

                    Большинство имеющихся руководств посвящено тому, как надо писать. Я же расскажу о том, как писать НЕ надо :-)

                    Данный текст является вольным переводом вики-страницы «Bash pitfalls» по состоянию на 13 декабря 2008 года. В силу викиобразности исходника, этот перевод может отличаться от оригинала. Поскольку объем текста слишком велик для публикации целиком, он будет публиковаться частями.

                    Поехали!
                  • резервное копирование rsync-ом

                      Если у тебя на компьютере не хранится дорогих тебе фотографий или
                      документов, эта заметка будет тебе не интересна. Если ты уже делаешь резервные копии и механизм работы с ними тебя полностью устраивает, эту заметку тоже лучше пропустить. Если ты считаешь, что хорошо разбираешься в linux, то вряд ли почерпнёшь в ней что-то новое. Для остальных — делюсь
                      своим опытом
                    • 10 трюков в командной строке, о которых вы не знали. Честное слово.

                      • Translation

                      1. Простой способ перехватить вывод и ошибки


                      Хотите направить stdout и stderr в один файл?
                      command &> file
                      Может вы разбираетесь в некой программе при помощи strace, и желали бы видеть системные вызовы вместе с ошибками программы?
                      strace badapp &> errors_and_output

                      Плюсы: легко запоминается, и проще чем
                      Читать дальше →
                    • Немного логики…

                        image

                        Задача #2 «Позитивные автоматы»



                        Для тех, кто не хочет читать:

                        Найти значение выражения: |x — |y||
                        X, Y — любые целые ( и отрицательные тоже )

                        Ограничение: нельзя пользоваться sub, dec… и любое другое вычитание, нельзя пользоваться регистрами флагов и бинарными операциями. (в частности сдвигами)
                        Все что у вас есть: je, cmp (нельзя смотреть флаги), jmp, inc, mov. (я же сказал, немного)

                        Для того, что бы лучше разобраться в задаче:

                        Есть такая замечательная штуковина, называется:
                        Машина с неограниченными регистрами (МНР)
                        Итак, зачем это? Лично для меня — расшевелить мозги.

                        Теперь попробуем в деле!

                        Читать дальше →
                      • Рекурсия с помощью Y–комбинатора

                          Поводом для написания этой статьи стало желание разобраться с тем, как работает Y-комбинатор.

                          Чтобы мозги не ржавели и работали как часы, я стараюсь пробовать новые и необычные вещи.
                          Интереса ради, я скомпилировал Lua 5.x под DOS, с этим никаких проблем не было, но при проверке Lua на её стандартных тестах, я обнаружил код вычисления факториала, работу которого я не понял.
                          Но ясно осознал, что это нечто относится к функциональному программированию.

                          Читать дальше →