Программирование: теоремы и задачи +4


После неудачного (с точки зрения эффективности траты времени) погружения в "Грокаем алгоритмы" по совету Яндекс Практикум и решения нескольких задач в "Бесплатный курс: подготовка к собеседованиям" от того же Яндекса решил поискать литературу на тему разбора задач. Довольно много рекомендаций указывало на книгу "Программирование: теоремы и задачи" от Александра Шеня. Книгу можно, кстати, официально скачать с сайта издательства Московского Центра Непрерывного Математического Образования.

Сам автор характеризует книгу как справочник и задачник для преподавателя. Причем во введении и аннотации упоминает школу на порядок чаще университета. Да и формулировки многих задач намекают на школьную аудиторию. На этом стоит остановиться сразу. Речь может идти только об очень очень особой школе и очень очень особых школьниках. Например, таких, которые ходят на математический кружок мехмата МГУ, где математически доказывают выигрышную стратегию при игре в крестики-нолики. 90% материала выходят за рамки школьной программы по информатике. Да и некоторые задачи используют математический аппарат, который тоже в школьный стандарт не входит. Не стоит отметать эту книгу как что-то для маленьких и неразумных.

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

  • Поиск: в принципе, предметный указатель в конце книги позволяет найти нужные вещи по ключевым словам. Но о какой-то каталогизации и систематизации алгоритмов и приемов речь не идет.

  • Охват: здесь описана классика вроде поиска, сортировки, структур данных (графы, стеки, хеш таблицы, деревья и т.п.), конечных автоматов; также тут описаны более редкие темы наподобие динамического программирования, теории игр, потоков (не в плане многозадачности, а в смысле сетей и пропускной способности), сжатия данных, синтаксического разбора. К сожалению, формат книги (320 небольших страниц) предопределяет небольшую глубину погружения в каждую из тем. По каждой теме автор дает введение и, на его взгляд, самое интересное. Здесь не найти всех сортировок, всех алгоритмов на графах, всех типов деревьев. Конечно, владеть тем, что описано - это уже немало. Но все-таки не формат справочника.

  • Формулировка задач: большинство задач сформулированы нейтрально и четко вроде "дан массив таких-то чисел, дано такое-то число, надо найти то-то". Во многих местах есть поясняющие примеры или пояснения. Однако, если мы говорим о классических справочниках вроде GoFEIP и тому подобном, то все же такие формулировки не слишком удобны. Тем более, что найти нужную задачу сложно. У задач есть только номер и они никак не каталогизированы.

  • Разбор решений: решения приведены примерно для половины задач. В большинстве случаев это готовые программы на паскале. Иногда псевдокод, но не забывающий про начальные и граничные условия. Часть задач не предполагает написание программы и тогда в решении даётся текстовое объяснение. Сложные решения тоже снабжены объяснениями. Иногда тема разбита на несколько подзадач и полное решение строится постепенно. Стоит отметить, что задачи с решениями - это примерно половина книги. Есть главы, где только теория или алгоритм приводится только в виде общего описания. Я не отказался бы почитать реализацию поиска минимальной стоимости разрезания многоугольника или реализацию подсчета пропускной способности сети трубопроводов. Итого получается, что готовые решения приведены для четверти-трети материала. Иллюстраций маловато, а они были бы полезны для пояснения работы многих нетривиальных алгоритмов.

  • Особенности и ограничения: часто встречаются пометки, что если бы условия были немного другими, то можно было бы решить проще. Естественно указывается какими и как. Иногда встречаются хитрости вроде вставки фиктивного элемента для упрощения проверки конца цикла. Часто указаны ограничения (например, что алгоритм вырезания комментариев, не понимает вложенные комментарии, и приводится пример того что получится в этом случае, и объяснено почему).

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

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

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




Комментарии (23):

  1. minm
    /#24364032 / +4

    Я всегда воспринимал эту книгу как пособие для школьного олимпиадного кружка по информатике. Если нужен серьезный справочник с глубокими основами - есть же классический учебник MIT "Алгоритмы" Кормена, Лейзерсона, Ривеста, Штайна.

    • nikolaysmartynov
      /#24364042

      пособие для школьного олимпиадного кружка по информатике

      А что именно там из школьной программы? Я понимаю, что гипербола - это такой художественный прием, но если серьезно, то какая часть студентов первого курса это поймет? Очень далеко не каждый соискатель на место разработчика расскажет, как хеш таблицы работают, а вы утверждаете, что сжатие данных в школе проходят. Не могли бы уточнить о какой школе речь?

      • iliazeus
        /#24364512

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

        • nikolaysmartynov
          /#24364642

          Посмотрите, например, задачки с некоторых предыдущих олимпиад.

          Спасибо, посмотрел. Задачи очень сильно выходящие за школьную программу - это финальный этап. Но и там область необходимых знаний ограничена и не требует, например, реализовывать разбор текста по грамматике. Что наверное логично.

          Вот для примера кусок оглавления:

          10. Сопоставление с образцом
          10.1. Простейший пример
          10.2. Повторения в образце - источник проблем
          10.3. Вспомогательные утверждения
          10.4. Алгоритм Кнута - Морриса - Пратта
          10.5. Алгоритм Бойера - Мура
          10.6. Алгоритм Рабина
          10.7. Более сложные образцы и автоматы
          10.8. Суффиксные деревья
          11. Анализ игр
          11.1. Примеры игр
          11.2. Цена игры
          11.3. Вычисление цены: полный обход
          11.4. Альфа-бета-процедура
          11.5. Ретроспективный анализ

          Какие задачи на каких олимпиадах требуют этих знаний и в какой школе их дают?

          • Drino
            /#24364876 / +1

            Какие задачи на каких олимпиадах требуют этих знаний и в какой школе их дают?

            В случае с алгоритмом Кнута-Морриса-Пратта, например:

            1. Задачи, сводящиеся к "эффективно найти все вхождения подстроки P в строку T".

            2. На каком-то этапе отбора на всероссийскую/международную олимпиаду школьников по информатике. Вот, например, задачка с красноречивым названием из материалов для подготовки к школьным олимпиадам по информатике.

            3. В той самой Летней Компьютерной Школе из соседнего комменатрия.

            Конкретно формальные грамматики не пользуются на олимпиадах популярностью из-за того, что это задачки "на реализацию", которые нужно не столько решать, сколько аккуратно писать для них код.

            • nikolaysmartynov
              /#24366096

              Благодарю за ссылки. По ним можно дойти до интересного документа, являющегося основанием всей этой деятельности:

              Правила выявления детей, проявивших выдающиеся способности, и сопровождения их дальнейшего развития (утв. постановлением Правительства РФ от 17 ноября 2015 г. N 1239)
              2. Выявление одаренных детей осуществляется ... посредством проведения олимпиад ...
              6. По итогам проведения мероприятия организатор ... направляет ... в веб-интерфейс государственного информационного ресурса о лицах, проявивших выдающиеся способности, предусмотренного пунктом 9 настоящих Правил, информацию об одаренных детях, являющихся победителями и призерами заключительного этапа мероприятий ...
              7. Информация ... направляется ... для формирования их портфолио и организации дальнейшей поддержки и сопровождения этих одаренных детей.
              11. Сопровождение дальнейшего развития одаренных детей ... в следующих формах:
              а) обеспечение индивидуальной работы с одаренными детьми по формированию и развитию их познавательных интересов, в том числе тьюторской и (или) тренерской поддержки;
              б) профессиональная ориентация одаренных детей посредством повышения их мотивации к трудовой деятельности по профессиям, специальностям, направлениям подготовки, востребованным на рынке труда;
              в) содействие в трудоустройстве после окончания обучения;
              г) психолого-педагогическое сопровождение одаренных детей;

              К сожалению, все это великолепие прошло мимо меня и я о нём даже не подозревал. У детей в школе чего-то такого тоже не замечал. Возможно, "выдающиеся" и "одаренные" - это поиск самородков в тысячах тонн породы. Я ни в коем случае не хочу умалять достижений олимпиадников. Я ими готов восхищаться и гордиться. Но собеседуя соискателей на вакансии разработчиков я вижу простых людей, которые окончили "простую школу", "простой институт" и имеют опыт предыдущей работы. Их бесполезно спрашивать про алгоритм Кнута-Морриса-Пратта. При этом они вполне справляются с решением задач в виде написания приложения, тестов и документации. На моей практике, тех, кто разбираются в структурах и алгоритмах, среди соискателей менее 10%.

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

              • Drino
                /#24367408

                При этом они вполне справляются с решением задач в виде написания приложения, тестов и документации

                Так это же хорошо! Олимпиадников - сотни, а разработчиков/тестировщиков и прочая-прочая - нужны десятки тысяч.

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

      • omxela
        /#24364536

        Влезу в разговор, извините. Речь идет о любой школе, где есть вменяемый преподаватель, который готов вести такой кружок. И найдётся несколько интересующихся ребят, готовых на этот кружок ходить. Дело это добровольное, поэтому там, в общем-то, не "проходят", а просто этим занимаются. Особенность прикладной дискретной математики, на мой взгляд, в том, что это, в сущности, игра в кубики. В той или иной форме эта дисциплина доступна не то, что в школе, а порою и в детском саду. А если кому-то она не даётся, то это не аргумент. В конце-концов, не все же должны этим заниматься. Есть и другие интересные вещи.

        • nikolaysmartynov
          /#24364710

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

          Ну я как человек когда-то преподававший информатику в школе могу сказать, что сильно повезет, если в классе есть хотя бы десяток ребят, у которых не ветер в голове, и еще сильнее повезет, если информатикой (а не химией, биологией, физикой, языком) заинтересуется хотя бы половина из них. Большая удача наскрести участников на школьную олимпиаду с реально ценными призами и подарками. В готовности школьника разбирать балансировку дерева после вставки я сильно сомневаюсь. В мотивации учителя факультативно это преподавать одному-двум ученикам тем более. Конечно, исключения бывают и среди первых, и среди вторых. Но это действительно исключения. Посмотрите, например, результаты по заключительным этапам ВсОШ по информатике по приведенной iliazeus ссылке.

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

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

          • eimrine
            /#24365360 / +1

            Да, есть дети, которые в 3 года говорят на нескольких языках, выступают на скрипке и умножают двузначные числа в уме. Означает ли это, что все остальные должны соответствовать их уровню (...)?
            Скорее, все остальные родители должны (сами себе должны, а не кому-то) соответствовать родителям этих детей. Вы же не зря упомянули именно скрипку именно в 3 года, это двойной намёк на книгу «послё трёх уже поздно». Почему бы в детском саду не поиграться с дискретной математикой, вместо сами знаете какой ерунды?

            • nikolaysmartynov
              /#24366138

              Почему бы в детском саду не поиграться с дискретной математикой, вместо сами знаете какой ерунды?

              Речь шла о книге, которую автор позиционирует как пособие для школьного образования и о моём недоумении подобной характеристикой. Считаю излишним агитировать за или против помощи своему ребенку в развитии. Однако, сомневаюсь в способности и, главное, мотивации большинства школьников и учителей ИВТ среднеобразовательных школ освоить и дать представленный в книге материал. К счастью это не отменяет тех самых выдающихся одаренных детей и их исключительных преподавателей, коим являлся сам автор. Надеюсь, усилия государства в этом направлении, изменят ситуацию. Буду рад ошибиться и узнать, что с 90-х и начала нулевых ситуация действительно поменялась.

          • omxela
            /#24365770

            Означает ли это, что все остальные должны соответствовать их уровню и школьный стандарт должен соответствовать бакалавриату?

            А кто говорит о "всех" или об изменении так называемого школьного стандарта? Вы спорите сами с собой. Речь идёт о том, что дети (возможно, в лице их родителей, но это бывает по-разному) должны иметь возможность влезть в это всё. Я тоже когда-то сам ходил на такие кружки, а потом вёл их время от времени. И не только с детьми, кстати. Да, на старте может быть 10 человек. На выходе - трое. Нет ничего чудеснее мотивированного ребёнка. Он способен очень на многое. Если в нужном возрасте попадёт в нужное (именно ему) место.

            • nikolaysmartynov
              /#24366196

              Речь идёт о том, что дети ... должны иметь возможность влезть в это всё.

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

        • Rad_66
          /#24369322 / +1

          Не смог удержаться )))

          Это так же далеко от Школы как МЁД от МЕЛА или мы о разных школах 1/1000

          у нас с этого года платный факультатив по матике только когда на него ходят одновременно троечники и отличники толку от него НОЛЬ пустая трата денег и времени)))

          а про общий уровень школы я вообще молчу

          видимо не там живем)

      • Drino
        /#24364818 / +1

        пособие для школьного олимпиадного кружка по информатике

        Аналогичного кружкам мехмата МГУ, упомянутым в тексте, только не по математике, а по информатике. Можно вспомнить, например, ЛКШ - это, конечно, не кружок, а летняя школа, но работают там со школьниками.

        А что именно там из школьной программы?

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

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

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

        • nikolaysmartynov
          /#24366272

          Но ведь автор не утверждает, что книжка по школьной программе.

          Нет, он говорит о том, что книга написана по материалам занятий программированием со школьниками. Я позволил себе усомниться в том, что это простые школьники.

          Речь может идти только об очень очень особой школе и очень очень особых школьниках. Например, таких, которые ходят на математический кружок мехмата МГУ, где математически доказывают выигрышную стратегию при игре в крестики-нолики. 90% материала выходят за рамки школьной программы по информатике. Да и некоторые задачи используют математический аппарат, который тоже в школьный стандарт не входит. Не стоит отметать эту книгу как что-то для маленьких и неразумных.

          Так каков же вывод? Книга для школьников (пусть и олимпиадников) и взрослому человеку читать её стыдно или поздно?

          Ну мне не стыдно. Я почерпнул для себя новое. Мне было интересно. Тем, кто уже давно не школьник, я, по прежнему, её рекомендую:

          Если базиса нет, то тут он дан. Если базис уже знаком, то для разминки и расширения кругозора.

          Если сравнивать с "Грокаем алгоритмы", то лучше уж прочитать "Программирование: теоремы и задачи". Да, наверное есть другие книги, где нет доказательства корректности и задач без решений и они будут более эффективны в плане затрат времени и полученного результата. Например,

          классический учебник MIT "Алгоритмы" Кормена, Лейзерсона, Ривеста, Штайна

          Для этого мы мнением и обмениваемся. Нет общепризнанного списка о том, что читать и в каком порядке. В соседней ветке с обзором "Грокаем алгоритмы" тоже рекомендовали каноничные тексты, но каждый рекомендовал свой набор. Я уже пополнил список того, что мне стоит прочесть. Если кто-то заинтересуется книгой А. Шеня или наоборот из моего описания или ваших комментариев поймет, что она ему не подходит и не потратит время зря - тоже хорошо.

          • Drino
            /#24367392

            Так каков же вывод? Книга для школьников (пусть и олимпиадников) и взрослому человеку читать её стыдно или поздно?

            Я такого не писал и не подразумевал - учиться никогда не поздно :)

            Моя позиция в том, что книжка написана очень доступным языком и, несмотря на пассаж в посте про "очень особенных детей", её вполне можно читать вместе с заинтересованным и освоившим программирование (или это уже делает его очень особенным?) ребёнком лет 11-16. Наравне с тем, чтобы дать ребёнку поиграть в Human Resource Machine.

            Для подготовки к алгоритмической секции её недостаточно (там выше был пассаж про О-нотацию), но для погружения в алгоритмы - книжка очень хорошая, потому что даёт достаточное количество практики, чтобы их "прочувствовать".

            Немного оффтоп - вообще в области программирования вещи "для школьников" часто оказываются хорошей точкой входа. Например, есть отличный курс Кириенко по основам программирования (на примере python) с довольно обширным набором задач для практической отработки навыков.

            Да, наверное есть другие книги, где нет доказательства корректности и
            задач без решений и они будут более эффективны в плане затрат времени и
            полученного результата. Например, классический учебник MIT "Алгоритмы" Кормена, Лейзерсона, Ривеста, Штайна

            Книжка Кормена как раз более фундаментальная и её ощутимо сложнее читать, если изначально не иметь какого-то представления о теме (которое как раз можно получить пройдя книжку Шеня).

            • nikolaysmartynov
              /#24368726 / +1

              там выше был пассаж про О-нотацию

              Да, автор не пишет O(nlogn), но для половины задач либо дано условие, либо дан анализ: "число операций пропорционально log n", "число шагов не должно превосходить ????1 log(a/b) + ????2 для некоторых констант ????1, ????2", "время работы остаётся порядка ????^2" и тому подобное. Возможно, это неканонично. Возможно, это понятнее, чем "сложность O(n^2)".

              В некоторых местах рассматриваются и затраты памяти. В некоторых местах рассматривается худший случай и в среднем.

        • middle
          /#24366574

          Я нашёл анкету примерно 2000-го года для студентов на практику в одну IT-контору. Вполне годится для теоретической части собеседования на миддла.

  2. playermet
    /#24366616 / +1

    Предыдущее издание книги можно, кстати, официально скачать с сайта издательства Московского Центра Непрерывного Математического Образования.

    Так и издание 2021-го года там рядом лежит.

    • nikolaysmartynov
      /#24368736

      Благодарю, исправил. В разделе "Свободно распространяемые издания" ссылка именно на предыдущее. Наверное, забыли обновить.

      • playermet
        /#24369516

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

        • Rad_66
          /#24372448

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

          но обучение по КНИГАМ для вхождения в профессию

          дело более чем спорное

          даже когда препод ЧИТАЕТ лекцию и то 70% зависит от таланта препода передать свои знания (а не его знаний как таковых) а уж потом от способностей студента,

          а самостоятельное обучение требует СУППЕР мотивации и кучи СВОБОДНОГО времени

          более-менее нормальная литература вся на английском

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

          в итоге получаем талмуд на 500 страниц в котором нужной инфы на 100 а их надо найти время все прочитать и еще что бы вкурить неплохо бы погуглить и далеко не факт что именно те методы нужны будут в конкретной задаче в

          в итоге масса потерянного времени и мало толка)

          не отрицаю пользы печатных изданий (хороших) но лишь как дополнение к самообразованию в виде справочника

          ловлю тапки)