После неудачного (с точки зрения эффективности траты времени) погружения в "Грокаем алгоритмы" по совету Яндекс Практикум и решения нескольких задач в "Бесплатный курс: подготовка к собеседованиям" от того же Яндекса решил поискать литературу на тему разбора задач. Довольно много рекомендаций указывало на книгу "Программирование: теоремы и задачи" от Александра Шеня. Книгу можно, кстати, официально скачать с сайта издательства Московского Центра Непрерывного Математического Образования.
Сам автор характеризует книгу как справочник и задачник для преподавателя. Причем во введении и аннотации упоминает школу на порядок чаще университета. Да и формулировки многих задач намекают на школьную аудиторию. На этом стоит остановиться сразу. Речь может идти только об очень очень особой школе и очень очень особых школьниках. Например, таких, которые ходят на математический кружок мехмата МГУ, где математически доказывают выигрышную стратегию при игре в крестики-нолики. 90% материала выходят за рамки школьной программы по информатике. Да и некоторые задачи используют математический аппарат, который тоже в школьный стандарт не входит. Не стоит отметать эту книгу как что-то для маленьких и неразумных.
Напомню характеристику автора: справочник и задачник. Для справочника важны: удобство поиска, широта охвата, понятная формулировки задачи или проблемы, понятная формулировка решения, указание особенностей и ограничений. Рассмотрим подробнее:
Поиск: в принципе, предметный указатель в конце книги позволяет найти нужные вещи по ключевым словам. Но о какой-то каталогизации и систематизации алгоритмов и приемов речь не идет.
Охват: здесь описана классика вроде поиска, сортировки, структур данных (графы, стеки, хеш таблицы, деревья и т.п.), конечных автоматов; также тут описаны более редкие темы наподобие динамического программирования, теории игр, потоков (не в плане многозадачности, а в смысле сетей и пропускной способности), сжатия данных, синтаксического разбора. К сожалению, формат книги (320 небольших страниц) предопределяет небольшую глубину погружения в каждую из тем. По каждой теме автор дает введение и, на его взгляд, самое интересное. Здесь не найти всех сортировок, всех алгоритмов на графах, всех типов деревьев. Конечно, владеть тем, что описано - это уже немало. Но все-таки не формат справочника.
Формулировка задач: большинство задач сформулированы нейтрально и четко вроде "дан массив таких-то чисел, дано такое-то число, надо найти то-то". Во многих местах есть поясняющие примеры или пояснения. Однако, если мы говорим о классических справочниках вроде GoF, EIP и тому подобном, то все же такие формулировки не слишком удобны. Тем более, что найти нужную задачу сложно. У задач есть только номер и они никак не каталогизированы.
Разбор решений: решения приведены примерно для половины задач. В большинстве случаев это готовые программы на паскале. Иногда псевдокод, но не забывающий про начальные и граничные условия. Часть задач не предполагает написание программы и тогда в решении даётся текстовое объяснение. Сложные решения тоже снабжены объяснениями. Иногда тема разбита на несколько подзадач и полное решение строится постепенно. Стоит отметить, что задачи с решениями - это примерно половина книги. Есть главы, где только теория или алгоритм приводится только в виде общего описания. Я не отказался бы почитать реализацию поиска минимальной стоимости разрезания многоугольника или реализацию подсчета пропускной способности сети трубопроводов. Итого получается, что готовые решения приведены для четверти-трети материала. Иллюстраций маловато, а они были бы полезны для пояснения работы многих нетривиальных алгоритмов.
Особенности и ограничения: часто встречаются пометки, что если бы условия были немного другими, то можно было бы решить проще. Естественно указывается какими и как. Иногда встречаются хитрости вроде вставки фиктивного элемента для упрощения проверки конца цикла. Часто указаны ограничения (например, что алгоритм вырезания комментариев, не понимает вложенные комментарии, и приводится пример того что получится в этом случае, и объяснено почему).
Значительная часть места отводится под доказательство корректности программ, алгоритмов и предположений об их эффективности. С одной стороны "ничего непонятно, но очень интересно", а с другой, если бы речь шла именно о справочнике, то это место можно было бы использовать либо для более детального разбора решений (иногда приходится мысленно трассировать программу, чтобы понять, как она работает, а текстовое объяснение идеи алгоритма могло бы помочь), либо для того, чтобы привести решение там, где его в настоящий момент нет.
Про задачник: в первой части задач много и над ними интересно подумать, но часть глав больше про теорию, там задания, если и есть, то они на доказательство теорем и утверждений.
Резюмируя: читать разбор решений и поразмыслить, там, где решения не приведены, было интересно; интересно было читать про темы, которые более глубоко разобраны, чем в той же "Грокаем алгоритмы" (например, про динамическое программирование); интересно было ознакомиться (хоть и очень поверхностно) с новыми темами вроде теории игр и потоками. В целом книгу я бы к прочтению рекомендовал. Если базиса нет, то тут он дан. Если базис уже знаком, то для разминки и расширения кругозора.
Комментарии (23)
playermet
22.05.2022 18:53+1Предыдущее издание книги можно, кстати, официально скачать с сайта издательства Московского Центра Непрерывного Математического Образования.
Так и издание 2021-го года там рядом лежит.
nikolaysmartynov Автор
23.05.2022 12:03Благодарю, исправил. В разделе "Свободно распространяемые издания" ссылка именно на предыдущее. Наверное, забыли обновить.
playermet
23.05.2022 15:40Там на отдельной странице много книг этого автора перечислены (возможно даже все, я не знаю точно). Оттуда я ссылку и скопировал.
Rad_66
24.05.2022 11:27Пожалуй еще паять копеек вставлю по поводу печатных изданий (я далеко не программист)
но обучение по КНИГАМ для вхождения в профессию
дело более чем спорное
даже когда препод ЧИТАЕТ лекцию и то 70% зависит от таланта препода передать свои знания (а не его знаний как таковых) а уж потом от способностей студента,
а самостоятельное обучение требует СУППЕР мотивации и кучи СВОБОДНОГО времени
более-менее нормальная литература вся на английском
добавляем постоянные косяки перевода плюс отставание от реальных задач
в итоге получаем талмуд на 500 страниц в котором нужной инфы на 100 а их надо найти время все прочитать и еще что бы вкурить неплохо бы погуглить и далеко не факт что именно те методы нужны будут в конкретной задаче в
в итоге масса потерянного времени и мало толка)
не отрицаю пользы печатных изданий (хороших) но лишь как дополнение к самообразованию в виде справочника
ловлю тапки)
minm
Я всегда воспринимал эту книгу как пособие для школьного олимпиадного кружка по информатике. Если нужен серьезный справочник с глубокими основами - есть же классический учебник MIT "Алгоритмы" Кормена, Лейзерсона, Ривеста, Штайна.
nikolaysmartynov Автор
А что именно там из школьной программы? Я понимаю, что гипербола - это такой художественный прием, но если серьезно, то какая часть студентов первого курса это поймет? Очень далеко не каждый соискатель на место разработчика расскажет, как хеш таблицы работают, а вы утверждаете, что сжатие данных в школе проходят. Не могли бы уточнить о какой школе речь?
iliazeus
Уже довольно давно так сложилось, что школьные соревнования-олимпиады по программированию для старших классов имеют мало общего со школьной программой, а опираются, скорее, на программу примерно 1 курса по алгоритмам и структурам данных. Посмотрите, например, задачки с некоторых предыдущих олимпиад.
nikolaysmartynov Автор
Спасибо, посмотрел. Задачи очень сильно выходящие за школьную программу - это финальный этап. Но и там область необходимых знаний ограничена и не требует, например, реализовывать разбор текста по грамматике. Что наверное логично.
Вот для примера кусок оглавления:
Какие задачи на каких олимпиадах требуют этих знаний и в какой школе их дают?
Drino
В случае с алгоритмом Кнута-Морриса-Пратта, например:
Задачи, сводящиеся к "эффективно найти все вхождения подстроки P в строку T".
На каком-то этапе отбора на всероссийскую/международную олимпиаду школьников по информатике. Вот, например, задачка с красноречивым названием из материалов для подготовки к школьным олимпиадам по информатике.
В той самой Летней Компьютерной Школе из соседнего комменатрия.
Конкретно формальные грамматики не пользуются на олимпиадах популярностью из-за того, что это задачки "на реализацию", которые нужно не столько решать, сколько аккуратно писать для них код.
nikolaysmartynov Автор
Благодарю за ссылки. По ним можно дойти до интересного документа, являющегося основанием всей этой деятельности:
К сожалению, все это великолепие прошло мимо меня и я о нём даже не подозревал. У детей в школе чего-то такого тоже не замечал. Возможно, "выдающиеся" и "одаренные" - это поиск самородков в тысячах тонн породы. Я ни в коем случае не хочу умалять достижений олимпиадников. Я ими готов восхищаться и гордиться. Но собеседуя соискателей на вакансии разработчиков я вижу простых людей, которые окончили "простую школу", "простой институт" и имеют опыт предыдущей работы. Их бесполезно спрашивать про алгоритм Кнута-Морриса-Пратта. При этом они вполне справляются с решением задач в виде написания приложения, тестов и документации. На моей практике, тех, кто разбираются в структурах и алгоритмах, среди соискателей менее 10%.
Возвращаясь к тому, с чего всё началось: пособие для школьного олимпиадного кружка по информатике. Соглашаюсь. Каюсь: неверно истолковал как "в каждой школе это проходят".
Drino
Так это же хорошо! Олимпиадников - сотни, а разработчиков/тестировщиков и прочая-прочая - нужны десятки тысяч.
Проблема олимпиадников как раз в том, что они очень хорошо проходят все эти алгоритмические секции, потому что на них переобучены. А настоящая работа от алгоритмических секций значительно отличается.
omxela
Влезу в разговор, извините. Речь идет о любой школе, где есть вменяемый преподаватель, который готов вести такой кружок. И найдётся несколько интересующихся ребят, готовых на этот кружок ходить. Дело это добровольное, поэтому там, в общем-то, не "проходят", а просто этим занимаются. Особенность прикладной дискретной математики, на мой взгляд, в том, что это, в сущности, игра в кубики. В той или иной форме эта дисциплина доступна не то, что в школе, а порою и в детском саду. А если кому-то она не даётся, то это не аргумент. В конце-концов, не все же должны этим заниматься. Есть и другие интересные вещи.
nikolaysmartynov Автор
Ну я как человек когда-то преподававший информатику в школе могу сказать, что сильно повезет, если в классе есть хотя бы десяток ребят, у которых не ветер в голове, и еще сильнее повезет, если информатикой (а не химией, биологией, физикой, языком) заинтересуется хотя бы половина из них. Большая удача наскрести участников на школьную олимпиаду с реально ценными призами и подарками. В готовности школьника разбирать балансировку дерева после вставки я сильно сомневаюсь. В мотивации учителя факультативно это преподавать одному-двум ученикам тем более. Конечно, исключения бывают и среди первых, и среди вторых. Но это действительно исключения. Посмотрите, например, результаты по заключительным этапам ВсОШ по информатике по приведенной iliazeus ссылке.
Да, есть дети, которые в 3 года говорят на нескольких языках, выступают на скрипке и умножают двузначные числа в уме. Означает ли это, что все остальные должны соответствовать их уровню и школьный стандарт должен соответствовать бакалавриату? К сожалению, реальность такова, что далеко не каждый десятый и даже не двадцатый разработчик с опытом расскажет вам характеристики, как работает и как реализованы самые часто используемые контейнеры стандартной библиотеки ежедневно используемого им языка.
eimrine
nikolaysmartynov Автор
Речь шла о книге, которую автор позиционирует как пособие для школьного образования и о моём недоумении подобной характеристикой. Считаю излишним агитировать за или против помощи своему ребенку в развитии. Однако, сомневаюсь в способности и, главное, мотивации большинства школьников и учителей ИВТ среднеобразовательных школ освоить и дать представленный в книге материал. К счастью это не отменяет тех самых выдающихся одаренных детей и их исключительных преподавателей, коим являлся сам автор. Надеюсь, усилия государства в этом направлении, изменят ситуацию. Буду рад ошибиться и узнать, что с 90-х и начала нулевых ситуация действительно поменялась.
omxela
А кто говорит о "всех" или об изменении так называемого школьного стандарта? Вы спорите сами с собой. Речь идёт о том, что дети (возможно, в лице их родителей, но это бывает по-разному) должны иметь возможность влезть в это всё. Я тоже когда-то сам ходил на такие кружки, а потом вёл их время от времени. И не только с детьми, кстати. Да, на старте может быть 10 человек. На выходе - трое. Нет ничего чудеснее мотивированного ребёнка. Он способен очень на многое. Если в нужном возрасте попадёт в нужное (именно ему) место.
nikolaysmartynov Автор
Изначально речь шла о тезисе, что данная книга - школьное пособие. Автор не упоминает олимпиады в аннотации и введении (хотя в тексте некоторых задач дает примечание, что они были предложены на олимпиадах). В тоже время автор говорит об общеобразовательных школах. Именно это меня и удивило.
Rad_66
Не смог удержаться )))
Это так же далеко от Школы как МЁД от МЕЛА или мы о разных школах 1/1000
у нас с этого года платный факультатив по матике только когда на него ходят одновременно троечники и отличники толку от него НОЛЬ пустая трата денег и времени)))
а про общий уровень школы я вообще молчу
видимо не там живем)
Drino
Аналогичного кружкам мехмата МГУ, упомянутым в тексте, только не по математике, а по информатике. Можно вспомнить, например, ЛКШ - это, конечно, не кружок, а летняя школа, но работают там со школьниками.
Но ведь автор не утверждает, что книжка по школьной программе. В ней много задачек и не очень много теории, а изложение материала в основном идёт в виде разбора задач. Лишний формализм пропущен там, где его можно пропустить (книжка не вводит O-нотацию, например). Сравните с книжкой Кормена, написанной для студентов.
Первое издание книжки вышло в 1995 - школьникам в те времена приходилось писать на олимпиадах контейнеры, включая хеш-таблицы и различные вариации самобалансирующихся деревьев.
nikolaysmartynov Автор
Нет, он говорит о том, что книга написана по материалам занятий программированием со школьниками. Я позволил себе усомниться в том, что это простые школьники.
Так каков же вывод? Книга для школьников (пусть и олимпиадников) и взрослому человеку читать её стыдно или поздно?
Ну мне не стыдно. Я почерпнул для себя новое. Мне было интересно. Тем, кто уже давно не школьник, я, по прежнему, её рекомендую:
Если сравнивать с "Грокаем алгоритмы", то лучше уж прочитать "Программирование: теоремы и задачи". Да, наверное есть другие книги, где нет доказательства корректности и задач без решений и они будут более эффективны в плане затрат времени и полученного результата. Например,
Для этого мы мнением и обмениваемся. Нет общепризнанного списка о том, что читать и в каком порядке. В соседней ветке с обзором "Грокаем алгоритмы" тоже рекомендовали каноничные тексты, но каждый рекомендовал свой набор. Я уже пополнил список того, что мне стоит прочесть. Если кто-то заинтересуется книгой А. Шеня или наоборот из моего описания или ваших комментариев поймет, что она ему не подходит и не потратит время зря - тоже хорошо.
Drino
Я такого не писал и не подразумевал - учиться никогда не поздно :)
Моя позиция в том, что книжка написана очень доступным языком и, несмотря на пассаж в посте про "очень особенных детей", её вполне можно читать вместе с заинтересованным и освоившим программирование (или это уже делает его очень особенным?) ребёнком лет 11-16. Наравне с тем, чтобы дать ребёнку поиграть в Human Resource Machine.
Для подготовки к алгоритмической секции её недостаточно (там выше был пассаж про О-нотацию), но для погружения в алгоритмы - книжка очень хорошая, потому что даёт достаточное количество практики, чтобы их "прочувствовать".
Немного оффтоп - вообще в области программирования вещи "для школьников" часто оказываются хорошей точкой входа. Например, есть отличный курс Кириенко по основам программирования (на примере python) с довольно обширным набором задач для практической отработки навыков.
Книжка Кормена как раз более фундаментальная и её ощутимо сложнее читать, если изначально не иметь какого-то представления о теме (которое как раз можно получить пройдя книжку Шеня).
nikolaysmartynov Автор
Да, автор не пишет O(nlogn), но для половины задач либо дано условие, либо дан анализ: "число операций пропорционально log n", "число шагов не должно превосходить ????1 log(a/b) + ????2 для некоторых констант ????1, ????2", "время работы остаётся порядка ????^2" и тому подобное. Возможно, это неканонично. Возможно, это понятнее, чем "сложность O(n^2)".
В некоторых местах рассматриваются и затраты памяти. В некоторых местах рассматривается худший случай и в среднем.
middle
Я нашёл анкету примерно 2000-го года для студентов на практику в одну IT-контору. Вполне годится для теоретической части собеседования на миддла.