Дискретные структуры: матан для айтишников
Посмотришь на любую программу обучения по IT-специальности, и тут же увидишь дисциплину «Дискретная математика» (возможно, под другим названием), обычно для перво- или второкурсников. И её наличие вполне разумно, поскольку дискретная математика и непрерывная математика (представленная на первом курсе институтов с незапамятных времён математическим анализом) — две грани единой Математики, — красивой, могучей науки.
Хотя раньше такого понятия, как «дискретная математика» вовсе не было, это не значит, что не возникало дискретных задач: Абель, Дирихле, Фибоначчи, Эйлер, чьи имена возникают по ходу изучения дискретной математики, — отнюдь не наши современники! Но просто в те времена для выделения самостоятельной ветви математики ещё не сложилось критической массы задач и приёмов, не было видно взаимосвязей между ними. А большое количество плодотворных взаимосвязей между, на первый взгляд, различными понятиями, — то, что математики в своей науке очень ценят.
Ну хорошо, математикам всё математическое интересно. А зачем дискретная математика программисту?
Зачем это айтишнику
Во-первых, многие идеи, которые особенно ярко иллюстрируются на дискретных задачах, неотъемлемы и для информатики. Взять, хотя бы, фундаментальные понятия рекурсии и индукции.
Рекурсия — это, дословно, возврат, обращение к самому себе. Хорошо известные вездесущие числа Фибоначчи проще всего определяются рекурсивно: первые два числа Фибоначчи равны единице, а каждое следующее число равно сумме двух своих предшественников: 1,1,2,3,5,8,… Таким образом, для вычисления очередного числа мы обращаемся к уже рассчитанным числам такого же вида. Трудно представить, как можно изучить функциональное программирование, да и многое из других областей информатики, не освоившись хорошо с рекурсией. Очень близкий процесс к рекурсии — это индукция, способ доказательства математических утверждений, при котором в доказательстве сложных случаев мы опираемся на более простые. Параллели с рекурсией очевидны, и действительно, обычное дело, когда индуктивное доказательство существования какого-то объекта можно переформулировать в описание рекурсивного способа построения этого объекта.
Раз речь зашла о таких фундаментальных вещах, как индукция и рекурсия, не могу не сказать, что многие приёмы, которые очень хорошо видны на примерах из дискретной математики, эффективны в математике в целом. Это не только индукция, но и принцип Дирихле, принцип выбора по среднему значению и другие.
Следующий элемент, без которого информатику нельзя представить — это графы. Простейшие алгоритмы на графах обязательно входят в любой, даже самый вводный, курс по алгоритмам. Скажем, с понятием гамильтонова цикла связана одна из классических задач информатики, задача коммивояжёра.
Ещё одно архиважное умение — считать точно и оценивать приблизительно количества. Например, как вычислить количество раз, которые выполняется операция сравнения в цикле:
Или вот ещё пример. Нужно из списка из 100 товаров выбрать 20, так, чтобы их суммарная стоимость была ровно 2000 рублей («без сдачи»). Это вариант классической задачи о рюкзаке. Допустим, ваш коллега, подумав ночь, предложил решать задачу перебором: перебрать всевозможные наборы из двадцати товаров, и, как только в ходе перебора возникнет нужный набор, выдать его в качестве ответа. Между прочим, характеристика «переборный» далеко не всегда ставит клеймо на алгоритме. Всё зависит от размера входных данных. Так вот, как прикинуть, удастся ли за разумное время решить перебором эту задачу выбора 20 объектов из 100?
Наконец, для современного «дизайнера алгоритмов» обязателен к пониманию и вероятностный метод. Это общий метод, позволяющей решать многие задачи в современной комбинаторике. Очень часто наилучшие решения задач, известные на сегодняшний день, получены именно этим методом. Для практика же овладение этим методом полезно постольку, поскольку вероятностные алгоритмы прочно заняли место в современной информатике. И при анализе работы таких алгоритмов очень помогает интуиция, развитая в ходе изучения вероятностного метода.
Онлайн-курс «Дискретные структуры»
С верой в то, что перечисленные понятия из дискретной математики действительно не помешают любому программисту, а, скорее, помешает их незнание, я читаю соответствующий курс на факультете ФИВТ МФТИ. А недавно у меня появилась возможность сделать онлайн-курс, чем я с радостью воспользовался. Записаться на него можно по ссылке. Главное, чего я пожелаю всем записавшимся: не побоявшись трудностей, пройти курс до самого конца, и получить заслуженное звание Дипломированного Дискретчика. В общем, чтобы MOOC прошёл без мук и обогатил знаниями! Да и собственная корысть у меня тут тоже есть: чем больше онлайн-учеников у меня будет, тем большему я смогу научиться, читая обсуждения и наблюдая статистику решения задач. Ведь учиться учить тоже никогда не поздно!
Какие знания потребуются
Для прохождения первых двух модулей потребуются только школьные знания. Третий модуль потребует знание основ математического анализа на уровне «что такое предел» и «какая из функций x 20 или 2 x растёт быстрее (чему равны производные функций)». Для последних трёх модулей понадобится представление о том, что такое вероятность, условная вероятность, математическое ожидание, дисперсия. Также хорошо бы знать, что такое базис и размерность линейного пространства. Если с вероятностью и линейной алгеброй вы не знакомы, можно записаться заодно на эти вводные курсы. Тогда как раз, к моменту, когда нам потребуются эти знания, они у вас будут.
Post scriptum
Меня можно было бы упрекнуть в конфликте интересов, всё-таки я математик, и, естественно, хочу приобщить к своей секте как можно больше завсегдатаев Хабра. В своё оправдание могу сослаться на этот ответ на Quora. Под большей частью тем, перечисленных в этом ответе, я готов лично подписаться, в онлайн-курс многие из них вошли. Ещё сошлюсь на подборку мнений яндексоидов.
Математика для программистов
В статье пойдет речь о роли математики в жизни разработчика ПО. Мы не будем углубляться в частные области вроде машинного обучения, моделирования или же компьютерной графики, а сделаем упор на базовых математических вещах.
Этот материал предназначен в первую очередь для тех, кто уже сделал свои первые шаги в IT-индустрии, но в своем образовании уделял больше времени языкам программирования и конкретным технологиям, нежели фундаментальным вещам.
Как изучать математику
Многим людям математика кажется очень сложной для понимания наукой. Чаще всего, такое мнение складывается из-за неправильного подхода к ее изучению. На самом деле можно сильно упростить себе жизнь, следуя рекомендациям ниже.
В освоении математики есть два уровня понимания. Первый уровень — идейный. Это осознание того, для чего нужны определенные объекты, какая задача решается и где это используется. Второй уровень понимания — детальный; это подробное изучение подробностей решения задачи. Иногда нужно разобраться в задаче на детальном уровня понимания, но в большинстве случаев — достаточно идейного.
Математика не любит баззвордов. Если вы читаете книгу и видите слова, смысл которых вам непонятен, пропускать их опасно, потому как вы можете поймать себя на том, что с какого-то момента не понимаете вообще ничего. Очень важно сразу останавливать себя, когда вам что-то непонятно.
Дискретная математика
Область математики, которая занимается дискретными структурами (например: графами, автоматами, утверждениями в логике). Основное ее отличие от обычной математики, которую вы изучали в школе, — ее объекты не могут изменяться так же гладко, как и вещественные числа.
В каком-то смысле все задачи, которые решаются в программировании, так или иначе относятся к дискретной математике, поэтому ее знание очень вам пригодится.
Логика
Это наука о формальных системах и доказательствах. Она лежит в основе компьютерных наук, ведь любой язык программирования — формальная система. Но не нужно заглядывать глубоко в теорию, чтобы найти применение этой науке в написании программ, да и вообще в решении задач.
Хорошо, если вы умеете писать решение задачи. Но так же важно понимать, каким образом вы можете доказать, что ваш код работает правильно. Большинство программ решает какую-либо математическую задачу, и вам нужно уметь доказывать, что ваша задача решена правильно. Тогда на помощь приходят методы логики и в частности исчисление высказываний.
Изучение логики целесообразно начинать с простых вещей: например с того, что такое высказывание, какие есть операции между ними, что такое правила вывода. Далее можно перейти к более прикладным областям: старайтесь решать логические задачи, пробуйте оптимизировать разные проверки, которые вам приходится писать в коде. Далее, стоит обратить внимание на логику первого порядка: она может пригодиться в тестировании программ.
При этом решение, которое первым пришло вам в голову, не всегда самое правильное и красивое. Часто формальными преобразованиями можно сократить объем кода и сделать его более читаемым. А кроме того, некоторые логические трюки позволяют сделать само решение короче, быстрее и эффективнее.
Ресурсы:
- На Codeforces в разделе «Архив» стоит потренироваться на задачах как минимум класса С — многие из них содержат подводные камни;
- Проект The KeY to Software Correctness подойдет тем, кому интересно, как можно автоматически доказывать правильность работы кода. Он автоматизирует проверку кода на Java;
- Автоматический доказатель теорем z3, написанный Microsoft, для тех, кто пользуется другими языками. Краткая инструкция по его использованию находится на ресурсе rise4fun.
Комбинаторика
Комбинаторика изучает разные дискретные множества и отношения их элементов. Наиболее часто встречаемая программистами комбинаторная задача — вывести количество элементов, которые необходимо перебрать, чтобы получить решение в зависимости от некоторых параметров. Таким образом вы можете вывести асимптотическую сложность алгоритма.
Комбинаторные задачи формулируются в виде задачи подсчета количества элементов некоторого (в математике используют термин мощность) множества. Чтобы решать такие задачи, полезно иметь базовые знания в теории множеств из разряда свойств операций над множествами. Тогда задача сводится к выражению искомого множества через множества, мощности которых вычисляются по известным правилам. Для подсчета количества элементов применяются правила умножения или сложения, числа сочетаний или размещений. Хотя есть и более сложные задачи, лучше начинать с простого.
Ресурсы:
- С основами можно ознакомиться на сайте Mathprofi, который посвящен прозрачному и популярному описанию математики;
- Если вы владеете английским, можете посмотреть более продвинутую книгу An Introduction to Combinatorics and Graph Theory;
- Задачи по комбинаторике можно взять из задачника «Дискретная математика», в конце есть ответы.
Теория вероятностей
Иногда на собеседовании интервьюер, дабы проверить насколько крут кандидат, задает такую задачу: «Вот у нас есть отрезок, который начинается с числа А и заканчивается числом Б. Мы кидаем на него две точки случайным образом. Какая будет средняя длина наибольшего отрезка?» или же «Пусть у нас есть треугольник, на вершине которого сидит муха. Пусть она перелетает с вершины на вершину за 3 секунды и отдыхает на каждой вершине по секунде, каждый раз случайно выбирая себе путь. Через какое время она в среднем вернется в начальную точку?».
Это задачи по теории вероятностей. В программировании часто приходится применять вероятностный подход, для того чтобы оценить среднюю скорость работы алгоритма или же подогнать параметры вашего решения задачи под те запросы, которые чаще всего встречаются на практике.
Теория вероятности делится на две части: дискретную и непрерывную. Хотя в теории дискретная — это подкласс непрерывной, методы решения задач несколько различаются. Опять же лучше начинать с простого — дискретная теория вероятности часто сводится к комбинаторным задачам. И теоретическая часть у дискретной формулируется проще.
Непрерывная теория вероятности для полного понимания требует знания элементарных основ мат. анализа, в частности понятия интеграла, хотя многие задачи требуют лишь умения считать площади простых фигур. Именно непрерывная теория вероятности является фундаментом для математической статистики и машинного обучения. Поэтому, если хотите работать в этой области, стоит начать с изучения книги Ричарда Хэнсена Probability Theory and Statistics или Probability Theory with Simulations.
Ресурсы:
-
— сайт, на котором доступно и просто изложена высшая математика. На нём есть множество разделов с теорией, таблицами и задачами, в том числе и по теории вероятностей
- Книга Чарльза М. Гринстеда и Лори Снелла Introduction to Probability.
Теория графов
Слышали ли вы задачу о мостах Кенигсберга?
«Можно ли пройти по всем семи мостам города Кенигсберга, не проходя по каждому из них дважды?». Нам известно, что ответ на эту задачу — нет. Решить подобные задачи помогает теория графов.
Графы — это очень удобные формализованные представления нелинейных структур, которые довольно часто встречается в прикладных задачах. В отличие от простых линейных структур, таких как массивы или списки, работа с графами более сложна.
Изучите классические результаты и алгоритмы из теории графов, потому как некоторые задачи на графах являются NP-полными, и для них доказано существование более эффективного решения.
Ресурсы:
- Познакомиться с основными понятиями можно в краткой методичке «Введение в теорию графов»;
- По части алгоритмов можно заглянуть на сайт e-maxx и наш;
- Практиковаться можно на задачах с Codeforces, там есть задачи на графах.
Теория чисел и криптография
Задумывались ли вы, почему к простым числам такой большой интерес? Почему работает шифрование RSA? Чем отличается http от https и что такое сертификат безопасности?
Все эти вопросы изучает криптография. Сразу скажем, что эта наука достаточно сложная и не интуитивная — бывает непонтяно, как реализовать тот или иной алгоритм совершенно безошибочно. Тем не менее алгоритмы в криптографии не могут быть «чуть-чуть нерабочими». Малейшая ошибка может привести к компрометации всей криптографической системы.
Дискретная оптимизация
Чтобы найти экстремум (максимум либо минимум) функции, надо взять ее производную и приравнять к нулю. Решение уравнения дает локальный экстремум. Но если вам нужно искать максимум не на каком-то промежутке, а только по целым числам, то вам уже нужно будет задумываться о том, какое из соседних целых чисел нужно выбрать. Когда задача многомерная, вариантов с целыми числами становится все больше, и выбирать приходится из все увеличивающегося количества. Но бывают случаи еще хуже — когда вовсе нет никакой непрерывной функции, от которой можно было бы взять производную. Или же когда количество вариантов очень велико (в том случае, когда сами варианты нужно вычислять).
Бывает, что в таких задачах нельзя найти точное решение за приемлемое время — его можно получить только полным перебором. Такова, например, задача Коммивояжера, или задача линейного программирования. Иногда можно отказаться от точного решения, и использовать некоторые приближения. Обо всем этом можно узнать в курсе Discrete Optimization на Coursera.
Источники
Небезызвестная серия курсов Introduction to Discrete Mathematics for Computer Science на Coursera по дискретной математике. Она довольно обширна и дает общее представление о всех нужных областях дискретной математики — логике, комбинаторике, теории вероятностей, теории графов, теории чисел и криптографии. Последний курс затрагивает проблему дискретной оптимизации.
Кроме того, для тех, кому не очень нравится формат курсов, будет полезной книга Discrete Mathematics. An Open Introduction. Книга довольно большая и подробная, поэтому можно сделать упор на основных понятиях и определениях.
Напоследок для тех, кого заинтересовала дискретная математика, приведем одну из наиболее подробных практико-ориентированных книг по дискретной математике. Довольно известная книга Кнута, Грехема и Паташника «Конкретная математика». Она написана в неформальном стиле, изложение разбавлено комментариями на полях. Книга очень полезна для развития умения решать разные задачи. Однако в ней много частных вещей, которые могут пригодится только в олимпиадном программировании.
Что дальше?
В целом, для того чтобы иметь достаточный математический фундамент для изучения большинства областей, достаточно первых двух курсов, изучаемых на математических специальностях. К дискретной математике добавляются некоторые разделы непрерывной: линейная алгебра, общая алгебра, математический анализ, аналитическая геометрия, обыкновенные дифференциальные уравнения, методы оптимизации. В зависимости от специфики решаемых задач, к ним могут добавиться и дифференциальная геометрия, если вы собираетесь заниматься компьютерной графикой, или же теоретическая механика и мат. физика, если вы собираетесь заниматься физическими движками.
Научный форум dxdy
Нужна ли дискретная математика программисту?
Здравствуйте, Уважаемые.
Заранее понимаю, что наверняка открываю тему-холливар. Хотя учитывая математическую направленность форума — вовсе не факт.
Уже больше дня спорю со знакомым, нужна ли дискретная математика программисту?
Мне кажется, что всё-таки хотя бы какие-то основы, но нужны. Он считает, что это надо оставить математикам, да и если что — их можно нанять для решения мат. задач, которые потом будут записаны кодерами.
Однако ни он, ни я толком доказать свою точку зрения не можем — опыт крайне малый.
Хотелось бы услышать мнение знающих людей, желательно с примерами, где в программировании всё это может пригодиться.
Причём не только на примере задач с условиями из разряда «идеально гладкий полый сферический объект завис в невесомости в абсолютном вакууме», а на реальных практических задачах, с которыми приходится встречаться среднему (и не только) программисту.
Как Вы считаете: нужна или нет? Почему да, а почему нет?
Хмм.
В общем-то я имел ввиду не только конкретно дискромат, но и другие разделы, которые традиционно считаются полезными для информатики и смежного.
Логика, теория графов, автоматом, ТАУ, лямбда-исчисления, рекурсия, разработка, анализ и проектирование алгоритмов, теория кодов, функции и матрицы, деревья, сети, алгебра (имею ввиду не ту, что в школе), комбинаторика, вероятность, теория множеств, чисел и т.д. и т.п.
Большую часть слов я даже не понимаю, оттого не берусь самостоятельно судить, что да к чему.
Но для пущей конкретности упрощу вопрос: «Нужна ли математика программисту?».
Cobert , это факт. Знать синтаксис и не знать основ — это тоже самое, что знать все падежи, времена и прочие особенности синтаксиса русского (английского) языка, но при этом не уметь их применять.
Ведь в принципе все императивные языки пользуются примерно одним инструментарием — циклы, условия, арифметика, ввод/вывод и тем, что уже выводится из этих кирпичиков.
Но понимая это, я ловлю себя на мысли, что примера полезности фундаментальщины привести я всё-таки не могу.
Основы логики однозначно нужны. Основы теории алгоритмов — наверняка тоже понадобятся (сортировка там, быстрый поиск в упорядоченном массиве — эти задачи встречаются на каждом шагу).
Без деревьев и рекурсии, например, не сможете перечислить все файлы, лежащие в каком-то каталоге и всех его подкаталогах, а подобные задачи встречаются на практике (то есть можно, конечно, их решить без рекурсии, но это уже сложнее, и теории знать нужно больше ).
Если будете программировать графику (что-нибудь сложнее, чем «просто нарисовать график и всё», это тоже часто встречается на практике), то знания основ линейной алгебры очень помогают. Хотя «просто нарисовать график» можно, используя уже готовые библиотеки.
Сложные математические теории, действительно, требуются не всем. Например, если Вам доведётся моделировать какие-то физические процессы, то не обойтись без знаний в области математического и функционального анализа, дифференциальных уравнений. Если будете разрабатывать язык программирования, нужны будут разделы математики, которые часто объединяют под термином «дискретная» — конечные автоматы, формальные грамматики и т.п.
Т.е. дальше всё уже зависит от задач, которые перед Вами поставят работодатели/заказчики.
Однако следует иметь в виду, что при прочих равных условиях даже для решения относительно простых практических задач предпочтительнее будет выглядеть человек с хорошими знаниями в математике, чем без таковых. Вероятнее, он сможет решать эти задачи лучше и быстрее, чем человек с гуманитарным образованием или без (высшего) образования, хотя из этого правила бывают исключения. Кроме того, тренировка ума, даваемая математикой, может сослужить хорошую службу при изучении имеющихся инструментов и технологий программирования (хотя бы потому, что почти все эти инструменты и технологии преимущественно рассчитаны на человека математического склада ума).
Всё зависит от языка, от приложения.
Графы безусловно — в системном программировании, например в приложениях работы с сетью, это просто букварь. Алгоритмы — безусловно в системном и прикладном программировании, потому что инструментов не хватает, иногда приходиться всё делать самому. Лямда-исчисления — это уже факт, который имеется в C# и в др. языках, не быть знакомым с основами уже не серьезно.
Теория кодирования — вперёд в криптографию, архивация, конвертирование и т.д. — безусловно данные типы приложений нужны. Деревья — к теории графов.
Комбинаторика — реально нужна, например может потребоваться генерировать полный перебор значений, например я давно делал такой перебор, чтобы пройти уровень в игре «Таинственный остров». Уж логика никак не поддавалась, пришлось программно генерировать все комбинации, в итоге так и не получилось пройти, по видимому из-за неверного комбинаторного алгоритма.
Некоторые предметы очень важны, для других достаточно знать основы и где искать информацию. Для серьёзных приложений нужна соответствующая подготовка.
По поводу программистов и математиков, есть книга от человека, который учавствовал в разработке поисковой системы Рамблер, в ней по опыту он не очень отзывается о «математиках в программировании».
Математик видит абстракцию.
Программист видит код, который в конечном счёте представляет из себя набор ассемблерных директив и не всегда понятно, зачем иногда нужны математические «замудренности».
И еще, пользоваться чужими наработками не всегда полезно, т.к. их порой пишут «тяп ляп».
worm2 , спасибо за чёткий и развёрнутый ответ.
А с формулировкой того, что эти инструменты изначально были созданы для математиков, как сказано в посл. абзаце, я вообще столкнулся впервые, однако мысль сильная.
И ещё, конкретно подразумевается под основами логики?
Только логические операции, условные высказывания, таблицы истинности и упрощение лог.выражений (как мне кажется, для практики именно этого из логики и достаточно), или в том числе какие-нибудь дополнительные понятия вроде аксиоматические систем, умозаключений и предикатов тоже нужны?
Спасибо также за примеры.
AlexDem , ух. Что есть программист — это вообще отдельный разговор, причём очень часто перерастающий в многостраничный флуд чуть ли не из разряда «какой язык круче».
А вообще, конечно, это действительно два разных понятия, которые, к сожалению, очень многие не различают в принципе, отчего считают, что программирование — тривиальная задача. Пример тому — многие школьники, научившиеся делать ввод/вывод в паскале, которым потом кажется, что море по колено и вообще ничего сложного в программировании нет (ну как же, конечно! Ведь всё есть, по сути, I/O).
Впрочем, поговорка «чем меньше знаем мы, тем кажется, что больше» работала, работает, и, к сожалению, довольно долго ещё будет работать.
Будь я работодателем, если бы передо мной стоял выбор «программист» или «кодер», я бы принял положительное решение, скорее всего, в сторону первого, так как второму обязательно бы пришлось часами в рабочее время спрашивать на форумах и тематических сайтах «а как это сделать», «а как то сделать», скачивать тонны чужого кода, библиотек и так далее. Словом, суммарные издержки на кодера, если, конечно, задача не совсем тривиальная, могут оказаться намного больше (скорость, отладка, качество кода, эффективность алгоритмов и СД и т.д.), отсюда и выбор.
Что же, получается, чистый кодер умеет? Выкликивать мышкой GUI и ставить ему на ивенты скопированный из сети код? Не лучший, на мой взгляд, вариант.
Тем более, как уже сказал delphiec , не всегда код в сети оказывается достаточного качества.
EtCetera , в общем-то согласен. Первыми программистами были чистые математики, но и задачи были чисто математические, отсюда и конфуз «математик — идеальный программист», хотя на деле программист — это совершенно другая специальность, но в которой всё же нужна математическая грамотность. Никто же не говорит, что идеальнейший физик или экономист — математик, хотя первые двое тоже оперирует множеством математических понятий. И всё же математик по разуму как физику, так и программисту ближе, чем, скажем, филолог или юрист.
Да, согласен. У хорошего программиста ещё должно и быть и какое-то эстетическое чувство, чувство стиля, так как написать код — это мало, надо ещё его поддерживать и развивать. А как его будешь улучшать, если архитектура изначально спроектирована так, что чтобы хоть что-то добавить приходится перелопачивать ровно треть, а то и половину, кода? И здесь как раз очень помогает в том числе и умение правильно абстрагировать и разделять вещи по каким-то схожим характеристикам.
Совсем недавно я видел код примерно на 1000 строк, где все переменные были названы a, b, c, ab, adfg, asdf (и это не названия переменных, содержащих длины и площади фигур) и так далее, а также не было ни одного отступа, хотя код реализовывал какой-то сложный мат. метод.
Вопрос — как долго кто-то, кроме самого автора (да и он тоже через 3-4 месяца), будет разбираться в этом коде и делать его понятным хотя бы специалисту в данной области? Увы, примерно 1/2-3/4 времени, которое квалифицированному читающему понадобилось бы чтобы написать эквивалентный, но читаемый код.
Словом, для промышленного программирования только математики действительно недостаточно хотя бы только из-за того, что на рынке доминирует парадигма ООП и всего лишь написать код — мало.
Системное программирование, в свою очередь, более близко к математике, так как оно ближе и к аппаратуре.
Вот именно поэтому я с вами абсолютно согласен. И ваше мнение не должно быть скромным — вполне похоже, что вы по профессии (бывшей али текущей) и есть программист, если оценивать по сказанному вами.
70% разработчиков только этим и занимаются, на более низком уровне всего лишь подключая чужие библиотеки к этим окошкам и кнопочкам.
Да и оно неудивительно — очень многим нынешним программистам работодатель ставит задачи из разряда «клонировать 1С специально для нашей фирмы», а тут, конечно же, уже есть наработанная база, состоявшиеся методики, технологии и удобные библиотеки. Вывод очевиден.
Какая знакомая ситуация! Где-то 2/3 месяца назад факт того, что я не могу проходить игру «пятнашки» за приемлемое время, если не начинаю думать, меня так оскорбил, что я взялся писать программу для решения этой задачи методом «грубого подбора».
delphiec , вроде как-то так получается, что основная нужда программистов в математике находится в области системного программирования — компиляторов, операционных систем, работы с оборудованием, сетью и так далее, а для прикладного программирования достаточно основ?
Забыл сказать: сейчас же вроде как развивается так называемые параллельные вычисления, многоядерные процессоры и т.д. А что по этому поводу? Ведь в ближайшее время не предвидится сильно большой простоты в этом вопросе.
Да. Во всяком случае, мне из «сложной» логики пока ничего не понадобилось.
X Международная студенческая научная конференция Студенческий научный форум — 2018
ПРИМЕНЕНИЕ ДИСКРЕТНОЙ МАТЕМАТИКИ В ПРОГРАММИРОВАНИИ
Бурное развитие дискретной математики обусловлено прогрессом компьютерной техники, необходимостью создания средств обработки и передачи информации, а также представления различных моделей на компьютерах, являющихся по своей природе конечными структурами. Большинство задач исследования операций (распределение ресурсов, сетевое планирование и управление, календарное планирование) описываются математическими моделями дискретного программирования. [2, 9]
Умение логически понимать и решать задачу, которая будет поставлена перед любым программистом (независимо от языка программирования) является основополагающей, без логики невозможно полноценно и правильно решить задачу. Корректной можно считать только ту программу, которая исполняет функции, указанные в её технической спецификации, однако результат на уровне тестирования может кардинально отличаться в условиях реальной работы, поэтому необходимо проверить корректность алгоритма: нужно проверить изменения переменных программы, которые оно используется на всех этапах работы алгоритма (до, во время работы и после). Данные изменения будут рассматриваться как предикаты.
Пусть — предикат, верный для входных значений алгоритма , а — предикат, содержащий условия, которые удовлетворяют выходные значения. Высказывание означает следующее: «если алгоритм начинается с корректного значения , то она закончится при истинном значении ». Предикат называется предусловием, — постусловием. Высказывание тоже предикат, поэтому доказательство алгоритма равносильно доказательству верности . Основываясь на этом, можно доказать правильность алгоритма «Квадратный многочлен» на языке Pascal:
Поделим алгоритм на части и зафиксируем обозначения пред- и постусловий.
Подстановки показывают, что высказывания:
Верны. Таким образом, предикат
Верен, таким образом, алгоритм «Квадратный многочлен» корректен.
Алгоритм условных высказываний тоже поддается такому доказательству, необходимо только отразить альтернативные пути в алгоритме. [6]
Предположим, что высказывание
if условие then
вводит предусловие P и в конце даёт условие Q. Поэтому необходимо доказать истинность двух предикатов:
высказывание 1
Теория множеств используется для наиболее удобного описания массы концепций в информатике. Одним из примеров применения теории множества в программировании является база данных. Возьмём за пример экспертную систему. [10]
Экспертная система создаётся с целью подмены собой специалистов в данной области. Реализуется это благодаря накоплению базы знаний известных событий с определением набора правил вывода, из-за чего ответы на запросы могут быть выведены логическим путём из базы знаний.
Создадим экспертную систему под названием «Королевская династия Англии». Для начала подготовим список фактов, используя предикаты «родитель» и «жена».
Родитель (Георг I, Георг II) жена (София, Георг I)
Родитель (Георг III, Георг IV) жена (Вильгельмина, Георг II)
Родитель (Георг III, Вильгельм IV) жена (Шарлотта, Георг III)
Родитель (Георг III, Эдвард) жена (Каролина, Георг IV)
Родитель (Эдвард, Виктория) жена (Аделаида, Вильгельм IV)
Родитель (Виктория, Эдвард VII) жена (Виктория, Альберт)
Родитель (Эдвард VII, Георг V) жена (Александра, Эдвард VII)
Родитель (Георг V, Эдвард VIII) жена (Виктория Мари, Георг V)
Родитель (Георг V, Георг VI) жена (Елизавета, Георг VI)
Родитель (Георг V, Елизавета II) жена (Елизавета II, Филипп)
Родитель (Виктория, Элис)
Родитель (Элис, Виктория Альберта)
Родитель (Виктория Альберта, Филипп)
Родитель (x, y) означает, что x является родителем y, а жена (x, y) означает, что x — жена y. Это стандартное чтение предикатов, используемых языками программирования, как, например, PROLOG. [4]
Для извлечения информации необходимо отправлять запросы в базу данных. Пример: «является ли Георг I отцом Георга III?», то ответ будет отрицательным, поскольку предикат родитель (Георг I, Георг III) не существует в списке. Формат запроса зависит от языка программирования, который поддерживает та или иная база данных. Таким образом, использование баз данных в работе помогает упорядочить информацию и наиболее эффективно работать с ней. Запросы формируются по принципу: «? — предикат». При этом подразумевается наличие переменной в предикате, которое будет равносильно вопросу о существовании того или иного элемента. [7]
Сформулируем правило вывода для получения информации о матерях из системы. Необходимо обозначить правило мать(x) так, чтобы положительный ответ на этот запрос формировался только в том случае, если x — жена чьего-то родителя или x — женщина и родитель. Правило такого вывода определяется таким образом:
Но данное правило вывода не найдёт всех матерей из-за того, что база данных не полная — в ней не записаны, например, дети Елизаветы Второй. Полученный результат показывает трудности, возникающие при попытках ограничения реального мира рамками математической модели. [5, 8]
1. Бондаренко В.А., Цыплакова О.Н., Родина Е.В Использование компьютерных математических систем в обучении математике.// Информационные системы и технологии как фактор развития экономики региона: сб. научных статей по материалам Международной НПК / Ставрополь: АГРУС Ставропольского ГАУ, 2013. С. 46-50.
2. Долгих Е.В., Тынянко Н.Н. Теоретические экономико-математические модели // Современные проблемы развития экономики и социальной сферы: сборник материалов Международной научно-практической конференции, посвященной 75-летию Ставропольского государственного аграрного университета. Ответственный редактор: Н. В. Кулиш. 2005. С. 553-556.
3. Дискретная математика для экономистов, Шелковой А.Н., Ююкин Н. А., 2014.
4. Зепнова Н.Н., Кузьмин О.В. Применение методов дискретной математики при решении логических задач // Омский научный вестник. 2014. № 2 (130). С. 14-17.
5. Попова С.В. Формирование алгоритмической культуры у студентов на занятиях по математике // Экономика регионов России: анализ современного состояния и перспективы развития: Сборник научных трудов по материалам ежегодной 68-й научно-практической конференции. Ответственный редактор Кулиш Н.В. 2004. с. 423-426.
6. Попова С.В., Колодяжная Т.А. Применение алгоритмов при обучении математике в вузе // Моделирование производственных процессов и развитие информационных систем: Даугавпилсский университет, Латвия, Европейский Союз Белорусский государственный университет, Беларусь Днепропетровский университет экономики и права, Украина Московский государственный университет им. М.В. Ломоносова, Россия Санкт-Петербургский государственный политехнический университет Северо-Кавказский государственный технический университет Ставропольский государственный университет Ставропольский государственный аграрный университет. Ставрополь, 2011. С. 278-281.
7. Попова С.В., Смирнова Н.Б. Элементы алгоритмизации в процессе обучения математике в высшей школе // Современные проблемы развития экономики и социальной сферы: сборник материалов Международной научно-практической конференции, посвященной 75-летию Ставропольского государственного аграрного университета. Ответственный редактор: Н. В. Кулиш. 2005. с. 526-531.
8. Смирнова Н.Б., Попова С.В. Основные принципы проектирования компьютерной математической модели // Сборник научных трудов по материалам Ежегодной 69-й научно-практической конференции, посвященной 75-летию СтГАУ. Ответственный редактор: Кулиш Н. В.. 2005. С. 185-189.
9. Смирнова Н.Б., Попова С.В. Модели, подходы к классификации моделей // Экономика регионов России: анализ современного состояния и перспективы развития: сборник научных трудов по материалам Ежегодной 69-й научно-практической конференции, посвященной 75-летию СтГАУ. Ответственный редактор: Кулиш Н. В. 2005. С. 181-185.
10. Смирнова Н.Б., Попова С.В., Хачатурян Р.Е. Использование логической символики при обучении математике в вузе // Совершенствование информационных и коммуникационных технологий с целью активизации учебного процесса в вузе. Ставрополь, 2006. С. 191-195.
