Как не нужно решать задачи

Мазурок Игорь Евгеньевич

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах
Мазурок Игорь Евгеньевич

Latest posts by Мазурок Игорь Евгеньевич (see all)

Есть довольно подробные рекомендации, как нужно решать задачи по программированию (в т.ч. для студентов). В конце заметки я дам ссылки на одну из таких статей.
Но я хотел бы сейчас привести наглядный пример того, как не надо решать задачи.
Вот довольно простая задача про разрезание брусочка сыра (точнее прямоугольного параллелепипеда) на кубики со стороной 1. Это одна из задач с которых первокурсники начинают у нас изучать программирование. Решается она одной формулой:

Моделирование и системный подход. Вся супер идея решения состоит в наблюдении, что разрезая что-либо несколькими параллельными разрезами, вы получаете на один кусок больше чем было разрезов. Например, один разрез — два куска. Правда сложно заметить?
Да, придется понаблюдать за тем, что происходит если производить дополнительные разрезы в перпендикулярном направлении. Т.е. после разрезов в одной плоскости получаются пластины, во второй — соломка, в третьей — кубики. Понаблюдайте:

    Именно так человек решает задачи.

  1. Читает условие — иногда несколько раз и обязательно все буквы. Отделяет существенное от неважного.
  2. Представляет себе описанный процесс и его конечный результат отсекая ненужные для решения детали.
  3. Пытается описать формулами процесс или результат. Упрощает формулы.
  4. И наконец — кладет руки на клавиатуру и кодирует.

Возможно Вы заметили, что в первом коротком решении мы не выполнили собственную рекомендацию — не упростили формулу. Действительно, хотя все измерения абсолютно равнозначны, формула не выглядит симметричной. Это сделано чтобы понятнее был процесс вывода формулы. Первое слагаемое [latex]A-1[/latex] в общем числе разрезов показывает как мы резали перпендикулярно оси [latex]Ox[/latex]. Мы сделали [latex]A-1[/latex] разрез и получили [latex]A[/latex] пластин. Второе слагаемое [latex]A\cdot\left(B-1\right)[/latex] показывает как мы резали перпендикулярно оси [latex]Oy[/latex]. Мы сделали [latex]B-1[/latex] разрез в каждой из [latex]A[/latex] пластин полученных при предыдущей серии разрезов. И наконец, на последнем этапе, мы режем каждый из [latex]A\cdot B[/latex] брусочков на кубики при помощи [latex]С-1[/latex] разрезов. Получаем [latex]A\cdot B\cdot\left(C-1\right)[/latex] разрезов. Конечно, результат не должен измениться, если резать в каком-то другом порядке. Если раскрыть скобки и привести подобные мы увидим короткую симметричную относительно измерений формулу.

[latex]\left(A-1\right) + A \cdot \left(B-1\right) + A \cdot B \cdot \left(C-1\right) = ABC-1[/latex]

Аналитический подход. Эта новая формула может быть получена другими очень простыми рассуждениями.

Вначале был один большой кусок. После каждого разреза количество кусочков увеличивается на 1. В самом конце получится [latex]ABC[/latex] кусочков, значит разрезов было на 1 меньше — [latex]ABC-1[/latex].

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

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

Код программы с новой формулой

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

Я позаимствовал это решение с форума, но у нас имеются и свои подобные решения. Они работают правильно. Вот только долго. Но это еще не всё. Представляете количество времени потраченное на его качественную отладку и тестирование? А в реальных проектах этот код возможно потом придется долгие годы поддерживать и переписывать на новые языки программирования!
Чтобы разобраться как работает это второе решение достаточно посмотреть следующее видео

Пожалуйста! Не решайте задачи так!

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

Минутка мотивации

Таня Романова
Таня Романова

Latest posts by Таня Романова (see all)

Беседа Татьяны Романовой (Google Inc.) с первокурсниками прикладной математики ОНУ 15 сентября 2016

Беседа Татьяны Романовой (Google Inc.) с первокурсниками прикладной математики ОНУ 15 сентября 2016

Слайды выступления Татьяны Романовой (Google Inc.) перед первокурсниками Прикладной математики ОНУ 15 сентября 2016.

Мотивация

Мазурок Игорь Евгеньевич

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах
Мазурок Игорь Евгеньевич

Latest posts by Мазурок Игорь Евгеньевич (see all)

Мотивация это то, что заставляет нас поступать так, как мы поступаем. В этой заметке я хотел бы предложить несколько причин, по которым стоит глубоко изучать (и практиковать!) математику, алгоритмы и программирование именно с точки зрения студентов нашего университета.
Конечно, основной мотивацией является хорошее трудоустройство, интересные проекты, высокая зарплата и хорошее интересное общение. Всем этим не обделены специалисты в области информационных технологий и разработки программного обеспечения. Я уже рассказывал о наших студентах, успешно занимающихся спортивным программированием, которые проходят стажировки в Google, Facebook и конечно в местных филиалах компьютерных фирм. Рассказывал также об основанном нашими студентами успешном стартапе Looksery, который весной этого года был приобретён компанией Snapchat за 150 миллионов долларов.

Письмо из Google

Письмо из Google

Недавно появилось ещё одно свидетельство внимания крупных компаний к нашим выпускникам.
За последнюю неделю выпускники прикладной математики разных лет получили похожие письма от компании Google с приглашением на работу. Приглашение в частности обосновывается высоким уровнем подготовки выпускников ОНУ уже работающих в компании. Здесь приводится копия экрана с текстом письма Андрею Терещенко. Аналогичные письма получили Кирилл Чеканов, Михаил Герасименко, Денис Щелконогов и др. Поиск наших выпускников Google провёл по профессиональной социальной сети linked.in.

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

Это всё со стороны студента. А какая мотивация у преподавателя? Стыдно признаться, но единственный разумный ответ мне подсказывает неизвестный переводчик одиннадцатого сонета Шекспира

Ничто не вечно под луной. Но жизнь
Бессмертна эстафетой поколений.
Коль этим даром, друг мой, дорожишь,
Оставь свой след, отбросив яд сомнений.

Пусть красота живительной струёй
В преемнике, как Феникс, возродится,
А бездарь обойдёт вас стороной.
И злу чтоб не дано было свершиться.

Иначе человечеству конец
и жить ему лишь шесть десятилетий.
Хвала природе, ты – её венец,
За сохраненье рода ты в ответе.

Да не иссякнет мудрости печать,
Что ты сумел потомкам передать!

Related Images:

Дистанционные учебные курсы

Мазурок Игорь Евгеньевич

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах
Мазурок Игорь Евгеньевич

Latest posts by Мазурок Игорь Евгеньевич (see all)

Последнее обновление 8 октября 2016.

http://www.princeton.edu/

http://www.princeton.edu/

Хочу порекомендовать пройти некоторые дистанционные учебные курсы на сайте Coursera.

  • 10 октября 2016 стартует курс по Структурам данных. Довольно полезный. К сожалению, все больше учебных курсов становятся платными. Однако, есть возможность получить его бесплатно как вольный слушатель. Сертификата Вам в этом случае не выдадут, но знания получите
  • Во-первых, 3 октября 2016 началась первая часть учебного курса по Алгоритмам. Один из ведущих преподавателей знаменитый Роберт Седжвик. Даже если Вы опоздали к указанной дате (даже на год или два) стоит записаться и пройти.
  • Во-вторых, одновременно с предыдущим запускается ещё один курс Седжвика — Анализ алгоритмов

Заявленная трудоёмкость каждого из этих курсов 6-8 часов в неделю. Продолжительность — до начала марта.
Хочу предупредить, что оба курса очень сложны и реально придётся потратить много больше времени, чтобы во всём полностью разобраться.

По обоим курсам указано, что

No certificates, statements of accomplishment, or other credentials will be awarded in connection with this course.

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

http://online.stanford.edu/

http://online.stanford.edu/

Наша выпускница Татьяна Полунина порекомендовала другой курс, который только начался 3 октября 2016. Я не знаком детально с этим курсом, но полностью полагаюсь на рекомендацию и добавляю курс в список:

Это курс из Стэнфордского университета и по окончании можно получить сертификат от преподавателя.

Также можно пройти курс Основы алгоритмов. Это первый из набора в шесть курсов. Если брать все шесть, то нужно платить. Если брать каждый по очереди и без сертификата, то получится бесплатно.

Не все студенты морально готовы проходить онлайн курсы на английском языке. Я уверен, что это стоит делать при любом уровне невладения английским. Однако, идя на уступки этой нерешительности, рекомендую несколько полезных курсов на русском языке. Все они стартуют с понедельника 10 октября 2016 и подготовлены для Coursera сотрудниками МФТИ.

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

Решаем задачи

Чтобы тренироваться решать задачи мы будем чаще всего использовать сайт e-olymp.com. Также можно обратиться к

  • codewars.com — Решаем задачи («ката») разного уровня сложности и набираем уровень.
  • programmr.com — Будьте внимательны, есть ошибки в тестах. Например, задача на площадь треугольника предполагает целочисленное деление при вычислении полупериметра. (Проверялось 11.5.2017).
  • tutorialspoint.com — учебный курс с задачами.

Образец: Принадлежит ли точка треугольнику?

Мазурок Игорь Евгеньевич

Мазурок Игорь Евгеньевич

Разработчик программного и информационного обеспечения.
Доцент Одесского национального университета имени И.И.Мечникова
Учёный в области защиты и противодейтствия в интеллектуальных информационных системах
Мазурок Игорь Евгеньевич

Latest posts by Мазурок Игорь Евгеньевич (see all)

Задача. Даны три попарно не совпадающие и не лежащие на одной прямой точки [latex]A, B[/latex] и [latex]C[/latex], заданные своими координатами. Определить принадлежит ли точка [latex]D(x_d,y_d)[/latex] треугольнику [latex]ABC[/latex].
Сразу заметим, что задача легко обобщается для любого выпуклого многоугольника.

Тесты

В тестах нужно обязательно отразить следующие случаи:

  1. Точка строго вне треугольника
  2. Точка строго внутри треугольника
  3. Точка совпадает с одной из вершин треугольника
  4. Точка лежит на одной из сторон треугольника
  5. Точка лежит на продолжении одной из сторон треугольника
  6. Одна из сторон треугольника параллельна одной из осей координат
  7. Две стороны треугольника параллельны осям координат
xa ya xb yb xc yc xd yd Принадлежит?
-1 -1 1 -1 0 1 2 2 нет
-2 -2 1 -1 0 1 0 0 да
-1 -1 1 -1 0 1 0 1 да
-1 -1 1 -1 0 1 0.5 0 да
-1 -1 1 -1 0 1 1 3 нет
-1 -1 1 -1 0 1 0 0 да
0 0 2 0 0 2 1 1 да
0 0 2 0 0 2 5 5 нет

Плохое решение

В школьных учебниках такие задачи часто рекомендуют решать проверкой условия [latex]S_{ABC}=S_{ABD}+S_{BCD}+S_{CAD}[/latex]. При компьютерной реализации это приводит к необходимости сравнения двух действительных чисел на равенство. Эта крайне неприятная операция может быть проделана только с определённой степенью достоверности. Т.е. придётся проверять не превышает ли некоторого «с потолка» выбранного малого числа абсолютное [latex] \left| S_{ABD}+S_{BCD}+S_{CAD}-S_{ABC} \right| < \varepsilon[/latex] или относительное [latex]\left| 1-\frac{S_{ABD}+S_{BCD}+S_{CAD}}{S_{ABC}} \right| < \varepsilon[/latex] отклонение. Оставим эти вопросы для курса численных методов и методов приближённых вычислений и не будем идти по этому пути.

Неплохое решение

Начнём с простого наблюдения:

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

Запишем уравнение прямой, проходящей, например, через точки [latex]A[/latex] и [latex]B[/latex]. Получим [latex] \left( x-x_A \right) \left( y_B-y_A \right)-\left( y-y_A \right) \left( x_B-x_A \right) = 0[/latex]. Уравнение я записал в такой форме, чтобы не приходилось выполнять деление и переживать о нуле в знаменателе.

Неважно как называть стороны, важно научиться их различать.

Неважно как называть стороны, важно научиться их различать.

Теперь для любой точки [latex] \left( x;y \right)[/latex] мы можем вычислить левую часть приведенного равенства. Для точек, лежащих на прямой мы должны получать ноль. В тоже время прямая разобьёт плоскость на две полуплоскости. Точки лежащие в одной полуплоскости будут давать положительные значения. А точки из другой полуплоскости — отрицательные.
Мы готовы проверить первое условие — принадлежит ли точка [latex]D \left( x_d,y_d \right) [/latex] той же полуплоскости, что и точка [latex]C \left( x_c,y_c \right) [/latex] относительно прямой [latex] \left( AB \right) [/latex]? Для этого подставим обе точки в левую часть приведенного выше уравнения прямой и убедимся, что получены значения одного и того же знака. А если одна из точек даст точно ноль? Это означает, что точка лежит на прямой. По условию задачи это может быть только точка [latex]D[/latex]. Тогда она принадлежит треугольнику независимо от знака выражения, вычисленного для точки [latex]C[/latex].

Обратите внимание, что мы не утверждаем, что для любой точки на прямой наши приближённые вычисления обязаны дать точный ноль. Это было бы неверно. Мы только утверждаем, что если проведенные с доступной нам точностью вычисления всё же дали точный ноль, то мы вынуждены считать данную точку лежащей на данной прямой.

Естественно, что нам придётся записать аналогичные условия для двух оставшихся сторон треугольника (или для всех оставшихся сторон выпуклого многоугольника).

Плохой код

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

Нажмите здесь, чтобы выполнить этот код.

Приведенный код имеет существенные недостатки. Нам пришлось трижды записывать уравнение прямой проходящей через две точки и дважды подставлять в каждое из них координаты, чтобы проверить знак. Это значит, что нам пришлось шесть раз написать некоторую формулу с различными подстановками. При том подходе, что мы использовали имеем две проблемы. Во-первых, условие стало слишком сложным, чтобы его можно было легко воспринять. Во-вторых, и это гораздо хуже, такой код в [latex]\frac { 1-{ \left( 1-p \right) }^{ 6 } }{ p }[/latex] раз увеличивает вероятность совершить ошибку. Забавно, но это означает, что вероятность ошибки начинающего программиста увеличивается вдвое, а у опытного — в шесть раз. Хорошо, что опытные программисты не пишут такой код.

Неплохой код

Воспользуемся тем, что мы уже умеем создавать собственные функции для того, чтобы несколько сократить объём кода и сделать его более лёгким для восприятия.
Запишем условие на языке программирования С++:

Нажмите здесь, чтобы выполнить этот код.
Трудно сказать, стал ли код боле понятным или лаконичным. Однако можно точно сказать, что в нём отсутствуют повторяющиеся алгоритмические блоки. Все участки кода написаны строго по одному разу. Это уменьшает вероятность ошибки.

Чеширский код

Этот код содержит пока не изученные вами конструкции. Из-за этого он может показаться немного загадочным. Но если продолжать грызть гранит науки, то всё легко освоите. Или можно подождать...

Этот код содержит пока не изученные вами конструкции. Из-за этого он может показаться немного загадочным. Но если продолжать грызть гранит науки, то всё легко освоите. Или можно подождать…

Возможно слишком смело называть это хорошим кодом, но мы сделаем ещё один шаг в нужном направлении. В прошлом коде мы избавились от повторов в кодировании алгоритма. Однако остались повторы в кодировании данных. Вы заметили, что у нас четыре пары переменных? Т.е. просматривается структура состоящая из пары координат x и y, которую стоит объединить и назвать «точкой». Такие структуры в программировании на Си описывают с помощью ключевого слова struct. Это полезная промежуточная структура перед переходом к объектно-ориентированному программированию при помощи классов.

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