Пользователь
0,0
рейтинг
3 марта 2015 в 18:33

Разработка → Дискретные структуры: матан для айтишников из песочницы



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

Хотя раньше такого понятия, как «дискретная математика» вовсе не было, это не значит, что не возникало дискретных задач: Абель, Дирихле, Фибоначчи, Эйлер, чьи имена возникают по ходу изучения дискретной математики, — отнюдь не наши современники! Но просто в те времена для выделения самостоятельной ветви математики ещё не сложилось критической массы задач и приёмов, не было видно взаимосвязей между ними. А большое количество плодотворных взаимосвязей между, на первый взгляд, различными понятиями, — то, что математики в своей науке очень ценят.

Ну хорошо, математикам всё математическое интересно. А зачем дискретная математика программисту?

Зачем это айтишнику


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

Рекурсия — это, дословно, возврат, обращение к самому себе. Хорошо известные вездесущие числа Фибоначчи проще всего определяются рекурсивно: первые два числа Фибоначчи равны единице, а каждое следующее число равно сумме двух своих предшественников: 1,1,2,3,5,8,… Таким образом, для вычисления очередного числа мы обращаемся к уже рассчитанным числам такого же вида. Трудно представить, как можно изучить функциональное программирование, да и многое из других областей информатики, не освоившись хорошо с рекурсией. Очень близкий процесс к рекурсии — это индукция, способ доказательства математических утверждений, при котором в доказательстве сложных случаев мы опираемся на более простые. Параллели с рекурсией очевидны, и действительно, обычное дело, когда индуктивное доказательство существования какого-то объекта можно переформулировать в описание рекурсивного способа построения этого объекта.

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

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

Ещё одно архиважное умение — считать точно и оценивать приблизительно количества. Например, как вычислить количество раз, которые выполняется операция сравнения в цикле:
for i ≔ 1 to n do
	for j ≔ i to n do
		for k ≔ i to j do
			if a[i] > a[k] then
				…


Или вот ещё пример. Нужно из списка из 100 товаров выбрать 20, так, чтобы их суммарная стоимость была ровно 2000 рублей («без сдачи»). Это вариант классической задачи о рюкзаке. Допустим, ваш коллега, подумав ночь, предложил решать задачу перебором: перебрать всевозможные наборы из двадцати товаров, и, как только в ходе перебора возникнет нужный набор, выдать его в качестве ответа. Между прочим, характеристика «переборный» далеко не всегда ставит клеймо на алгоритме. Всё зависит от размера входных данных. Так вот, как прикинуть, удастся ли за разумное время решить перебором эту задачу выбора 20 объектов из 100?

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

Онлайн-курс «Дискретные структуры»


С верой в то, что перечисленные понятия из дискретной математики действительно не помешают любому программисту, а, скорее, помешает их незнание, я читаю соответствующий курс на факультете ФИВТ МФТИ. А недавно у меня появилась возможность сделать онлайн-курс, чем я с радостью воспользовался. Записаться на него можно по ссылке. Главное, чего я пожелаю всем записавшимся: не побоявшись трудностей, пройти курс до самого конца, и получить заслуженное звание Дипломированного Дискретчика. В общем, чтобы MOOC прошёл без мук и обогатил знаниями! Да и собственная корысть у меня тут тоже есть: чем больше онлайн-учеников у меня будет, тем большему я смогу научиться, читая обсуждения и наблюдая статистику решения задач. Ведь учиться учить тоже никогда не поздно!

Какие знания потребуются


Для прохождения первых двух модулей потребуются только школьные знания. Третий модуль потребует знание основ математического анализа на уровне «что такое предел» и «какая из функций x20 или 2x растёт быстрее (чему равны производные функций)». Для последних трёх модулей понадобится представление о том, что такое вероятность, условная вероятность, математическое ожидание, дисперсия. Также хорошо бы знать, что такое базис и размерность линейного пространства. Если с вероятностью и линейной алгеброй вы не знакомы, можно записаться заодно на эти вводные курсы. Тогда как раз, к моменту, когда нам потребуются эти знания, они у вас будут.

Post scriptum


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

Александр Дайняк @dainiak
карма
19,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (43)

  • +6
    Самые интересные статьи прилетают в мою ленту как правило из песочницы.

    А по теме — жаль, что я в своё время не уделял должного внимания дискретной математике в университете.
    • +3
      Ещё есть шанс…
  • –11
    Немного оффтопика:
    >Хорошо известные вездесущие числа Фибоначчи проще всего определяются рекурсивно
    Сложно представить более неправильный способ. Во всех случаях нужно максимально избегать рекурсии, заменяя на линейный алгоритм.
    • +12
      В чем разница между математическим определением и алгоритмом вычисления представляете?
    • +4
      В общем случае, линейный алгоритм может быть и рекурсивным – одно другое не исключает. Например, depth-first search.
      • 0
        Собственно, всё понятие хвостовой рекурсии именно об этом.
    • НЛО прилетело и опубликовало эту надпись здесь
    • +2
      «Итерация свойственна человеку, рекурсия божественна». Л. Питер Дойч

      В некоторых случаях рекурсия дает очень красивое и элегантное решение/определение.
      • 0
        >В некоторых случаях рекурсия дает очень красивое и элегантное решение/определение.
        Согласен, погорячился, в некоторых случаях да, но не в случае чисел Фибоначчи. То что устоявшееся определение данной последовательности в программировании через рекурсию, не означает что это правильно, поскольку дает нам экспоненциальных рост сложности алгоритма. Нетрудно посчитать сложность рекурсивной алгоритма при n=100, при этом если получить тоже число с помощью элементарного цикла от 2 до n, мы получим сложность функции О(n), при этом определение сложнее не будет.
        • +1
          Вам же уже сказали, что нужно отличать «Что такое числа Фибоначчи?» и «Как посчитать числа Фибоначчи?» И если вам не нравится текущее определение (а ведь и натуральные числа определяются рекурсивно, см. аксиомы Пеано), попробуйте дать своё.
        • 0
          Рекурсивное, однако весьма эффективное определение последовательности чисел Фибоначчи. Функция высшего порядка zipWith берет два списка и применяет к их элементам с одинаковыми указанную функцию (в данном случае — функцию сложения):

          fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
          
  • –8
    никогда не понимал заявлений о вездесущести чисел Фибоначчи и золотого сечения. фибоначчи — только филлотаксис, золотое сечение и вовсе миф.
  • 0
    Нам на первом курсе на Физтехе читал лекционный курс товарищ Стрыгин (я с РТ, но вроде он не только РТ читал). По ощущениям был сплав дикой тривиальщины и каких-то баек. Пару забавных методов и алгоритмов запомнилось, но, если честно, то по делу там почти ничего не было.
    Надеюсь, что у вас получится значительно лучше!:)
    • 0
      В моём универе дискретку, а также тервер вел примерно такого же типа препод. За лекцию он успевал рассказать очень мало, но настолько подробно, что становилось скучно. На практику времени практически не оставалось по этой причине, а также потому, что очень много времени тратилось на немногочисленные задачи из дз, которые тоже были жутко тривиальными.

      Именно поэтому когда я увидел эту статью, сразу же записался дабы послушать адекватные лекции и порешать побольше разных задач. Очень хотелось бы увидеть аналогичный курс по терверу.
  • –1
    А почему все думают что программистам нужна только дискретка? Попробуйте попрограммировать системы для биржевой торговли: тут вам и Ито и Маллиавэн и еще вагон всего.
    • +4
      Дмитрий, разве из статьи следует, что нужна только дискретка? Но она определённо важна – попробуйте попрограммировать те же системы для биржевой торговли, не зная дискретку.

      Кстати, вводный курс по статистике уже идёт stepic.org/course/Основы-статистики-76/, а по матанализу скоро начинается – stepic.org/course/Введение-в-математический-анализ-95/.
      • 0
        А разве в вводном курсе по статистике может быть интеграл Ито? :) Тем более, судя по описанию, он заточен на неподготовленного слушателя.
    • +1
      Да, а, например, разработчикам 3D-шутеров нужен матан.
      Каждый раздел математики может пригодиться для программирования некоторых задач. Но из всех разделов математики дискретка имеет наиболее широкое применение всякими программистами. Имхо.
      • 0
        Именно матан, а не ангем/линал? Хотя я не знаю, дискретными их назвать или непрерывными :)
        • 0
          В т.ч. и матан, например, интегралы часто применяются при расчете BRDF.
  • НЛО прилетело и опубликовало эту надпись здесь
  • +4
    Не подскажете, каков процесс обучения на самой платформе? Не приходилось до сих пор принимать участия в онлайн курсах. Ряд видеолекций + регулярные задания? Задания проверяются, или делаются «для себя»?
    • 0
      Да, регулярные видеолекции и задания с дедлайнами. Видео можно смотреть в любое удобное время. Все задания проверяются автоматически, задания можно сдавать много раз, пока не получится.
  • 0
    Меня честно говоря во всей статье порадовал выбор картинки, она очень необычна и в то же время приятна — искусство со смесью математики и физики.
  • +1
    Не владею даже школьной математикой уровня физ-мат класса, но записался все равно, буду пытаться учить и понимать. Обещаю приложить максимум усилий, жаль отпуск не смогу взять на время обучения)
    • +2
      Я вот оказался ниасилятором. До сих пор на первом блоке, хотя открыт третий уже. К концу первого блока начал очень сильно буксовать: хорошо если получается одну задачу за день осилить. Мозги просто отказываются думать. Интересно, сколько задачи будут доступны для решения, а то хорошо, если к концу лета осилю :)
      • +1
        Что же, будем собратьями по «несчастью». Можем скооперироваться для прохождения, вдвоем все же легче, да и мотивация повышается.
        • +1
          Берите меня к себе:)
          • +2
            monah_tuk пока не ответил. Но уже больше одного и можно кооперироваться.
            • +2
              Я думаю, что после курса нужно факультатив устроить. Для отстающих.
              • +1
                Задачи не будут закрыты для прорешивания даже после окончания курса. Так что проходить курс можно в своём темпе. Ближе к осени, возможно, часть уроков я буду закрывать на доделку, чтобы учесть возникшие замечания.
          • 0
            Я уже начал, можно организоваться с помощью слаки, либо любого другого канала коммуникации. Предупрежу, что времени для неподготовленного человека уходит порядочно. Хотя мне кажется, если думать совместно, то дело пойдет веселее.
  • –3
    В сторону… А что, в паскале уже можно присваивать оператором "=" без двоеточия? Я про пример с вложенными for.
    • 0
      А вы присмотритесь к оператору из кода внимааательнее ;)
      Я тоже сначала не заметил.
      P.S. А вообще, это мог быть какой-нибудь GML. Или просто псевдокод.
      • 0
        Да уж. Это не «равно» и не «двоеточие равно», а совсем даже U+2254. Откуда это, интересно, он, такой красивый, тут взялся? :)
  • 0
    Дискретные структуры: матан для айтишников
    Недостаточно абсурда. Нужно так:
    Дискретные структуры: матан для айтишников (на самом деле линейная алгебра твёрдого тела)
  • +1
    Плюсую курс.
    Прослушал его лично от автора поста в качестве студента ФИВТ МФТИ.
    Сначала думал, не понадобится.

    А через год писал LCS через цепи в булеане.
    Так что всем рекомендую)
  • 0
    какая из функций x^20 или 2^x растёт быстрее (чему равны производные функций)

    Производные равны 20∙x^19 и 2^x∙ln(2) соответственно.
    Пока я не вижу, как производные помогут ответить на вопрос (для x=10 у первой ф-ции производная больше, и что?)
    • 0
      Берем производную 20 раз и слева у нас оказывается константа, а справа — функция. Функция растет быстрее константы, хотя и к этому можно не прибегать, а взять производную в 21 раз. Тогда слева ноль, а справа — везде положительная функция. Вот и ответ.
      • 0
        Это вы подобрали принцип под мой конкретный пример, на другом примере он не сработает.
        Сравните 2x и 22x
        • 0
          Отлично, логарифмируем по основанию 2 (очевидно, это не влияет на неравенство), после этого сравниваем х и 2^x. Дважды дифференцируем, получаем что 2^2^x > 2^x. ЧТД.

          Можно доказать и иначе, 2^x = y, тогда y vs 2^y, дальше аналогичные вычисления и ответ.

          Ну и чтобы 2 раза не вставать: как вы предлагаете оценивать рост функций без вычисления производных?
          • 0
            как вы предлагаете оценивать рост функций без вычисления производных?

            Никак. Мне кажется, это алгоритмически неразрешимая задача.

            Отлично, логарифмируем по основанию 2

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

            Да, инструмент хороший, но только как дополнительный, в связке с другими (а для некоторых примеров и не пригодится вовсе).
    • 0
      Если брать физический смысл, то производная от функции перемещения — это скорость. Чем больше скорость, тем быстрее растет пройденный путь.

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