Comments 26
Я всегда воспринимал эту книгу как пособие для школьного олимпиадного кружка по информатике. Если нужен серьезный справочник с глубокими основами - есть же классический учебник MIT "Алгоритмы" Кормена, Лейзерсона, Ривеста, Штайна.
пособие для школьного олимпиадного кружка по информатике
А что именно там из школьной программы? Я понимаю, что гипербола - это такой художественный прием, но если серьезно, то какая часть студентов первого курса это поймет? Очень далеко не каждый соискатель на место разработчика расскажет, как хеш таблицы работают, а вы утверждаете, что сжатие данных в школе проходят. Не могли бы уточнить о какой школе речь?
Уже довольно давно так сложилось, что школьные соревнования-олимпиады по программированию для старших классов имеют мало общего со школьной программой, а опираются, скорее, на программу примерно 1 курса по алгоритмам и структурам данных. Посмотрите, например, задачки с некоторых предыдущих олимпиад.
Посмотрите, например, задачки с некоторых предыдущих олимпиад.
Спасибо, посмотрел. Задачи очень сильно выходящие за школьную программу - это финальный этап. Но и там область необходимых знаний ограничена и не требует, например, реализовывать разбор текста по грамматике. Что наверное логично.
Вот для примера кусок оглавления:
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. Ретроспективный анализКакие задачи на каких олимпиадах требуют этих знаний и в какой школе их дают?
Какие задачи на каких олимпиадах требуют этих знаний и в какой школе их дают?
В случае с алгоритмом Кнута-Морриса-Пратта, например:
Задачи, сводящиеся к "эффективно найти все вхождения подстроки P в строку T".
На каком-то этапе отбора на всероссийскую/международную олимпиаду школьников по информатике. Вот, например, задачка с красноречивым названием из материалов для подготовки к школьным олимпиадам по информатике.
В той самой Летней Компьютерной Школе из соседнего комменатрия.
Конкретно формальные грамматики не пользуются на олимпиадах популярностью из-за того, что это задачки "на реализацию", которые нужно не столько решать, сколько аккуратно писать для них код.
Благодарю за ссылки. По ним можно дойти до интересного документа, являющегося основанием всей этой деятельности:
Правила выявления детей, проявивших выдающиеся способности, и сопровождения их дальнейшего развития (утв. постановлением Правительства РФ от 17 ноября 2015 г. N 1239)
2. Выявление одаренных детей осуществляется ... посредством проведения олимпиад ...
6. По итогам проведения мероприятия организатор ... направляет ... в веб-интерфейс государственного информационного ресурса о лицах, проявивших выдающиеся способности, предусмотренного пунктом 9 настоящих Правил, информацию об одаренных детях, являющихся победителями и призерами заключительного этапа мероприятий ...
7. Информация ... направляется ... для формирования их портфолио и организации дальнейшей поддержки и сопровождения этих одаренных детей.
11. Сопровождение дальнейшего развития одаренных детей ... в следующих формах:
а) обеспечение индивидуальной работы с одаренными детьми по формированию и развитию их познавательных интересов, в том числе тьюторской и (или) тренерской поддержки;
б) профессиональная ориентация одаренных детей посредством повышения их мотивации к трудовой деятельности по профессиям, специальностям, направлениям подготовки, востребованным на рынке труда;
в) содействие в трудоустройстве после окончания обучения;
г) психолого-педагогическое сопровождение одаренных детей;
К сожалению, все это великолепие прошло мимо меня и я о нём даже не подозревал. У детей в школе чего-то такого тоже не замечал. Возможно, "выдающиеся" и "одаренные" - это поиск самородков в тысячах тонн породы. Я ни в коем случае не хочу умалять достижений олимпиадников. Я ими готов восхищаться и гордиться. Но собеседуя соискателей на вакансии разработчиков я вижу простых людей, которые окончили "простую школу", "простой институт" и имеют опыт предыдущей работы. Их бесполезно спрашивать про алгоритм Кнута-Морриса-Пратта. При этом они вполне справляются с решением задач в виде написания приложения, тестов и документации. На моей практике, тех, кто разбираются в структурах и алгоритмах, среди соискателей менее 10%.
Возвращаясь к тому, с чего всё началось: пособие для школьного олимпиадного кружка по информатике. Соглашаюсь. Каюсь: неверно истолковал как "в каждой школе это проходят".
При этом они вполне справляются с решением задач в виде написания приложения, тестов и документации
Так это же хорошо! Олимпиадников - сотни, а разработчиков/тестировщиков и прочая-прочая - нужны десятки тысяч.
Проблема олимпиадников как раз в том, что они очень хорошо проходят все эти алгоритмические секции, потому что на них переобучены. А настоящая работа от алгоритмических секций значительно отличается.
А настоящая работа от алгоритмических секций значительно отличается.
Бесспорно. В настоящей работе в основном не надо задействовать все те знания и хитрые алгоритмы. Однако ваше высказывание как бы намекает, что олимпиадники не справляются с обычной работой, потому что обучены чему-то другому.
Но тут я категорически не согласен. После двух недель переучивания, чтобы использовать нормальные имена переменных и функций, любой олимпиадник отлично справится с любой "обычной" работой. Потому что уметь писать программы — это необходимое условие чтобы быть олимпиадником. Это как тяжелоатлет сможет работать грузчиком.
Проблема олимпиадников — это плохой стиль (который при приходе в индустрию лечится за пару недель). И еще некоторым может стать скучно, но это не так часто происходит.
Однако ваше высказывание как бы намекает, что олимпиадники не справляются с обычной работой
Я имею в виду, что прохождение алгоритмической секции для олимпиадника не является маркером сопутствующих навыков разработчика.
Если человек потратил несколько тысяч часов жизни на программирование, то он скорее всего с лёгкостью напишет на своём рабочем языке, например, несложный обход графа. Если мы говорим об "обычном" разработчике, то к этой отметке он приходит с некоторым багажом из чтения чужого кода и организации процесса разработки.
Олимпиадник потратил несколько тысяч часов жизни на написание гораздо более сложных алгоритмов, чем обход графа, поэтому он тоже с лёгкостью его напишет. Но ему, возможно, придётся объяснять после найма про стиль, про тесты, про системы контроля версий и про цену поддержки кода.
Естественно, это лучше, чем кандидат, которому придётся объяснять про стиль, про тесты, про системы контроля версий, про цену поддержки кода и про программирование в целом. Олимпиадник без опыта работы - это джун с хорошим потенциалом, как бы звёздно он ни проходил алгоритмические секции.
Это как тяжелоатлет сможет работать грузчиком.
Конечно сможет, но я бы не доверил переезд свой переезд группе тяжелоатлетов выбранных по их рабочим весам. Обычно грузчики работают в команде и в их работе есть какое-то количество практик, позволяющих не повредить мебель/технику при перевозке. Подозреваю, что тяжелоатлет без опыта работы грузчиком об этом даже не задумается (пока не набьёт шишки).
Влезу в разговор, извините. Речь идет о любой школе, где есть вменяемый преподаватель, который готов вести такой кружок. И найдётся несколько интересующихся ребят, готовых на этот кружок ходить. Дело это добровольное, поэтому там, в общем-то, не "проходят", а просто этим занимаются. Особенность прикладной дискретной математики, на мой взгляд, в том, что это, в сущности, игра в кубики. В той или иной форме эта дисциплина доступна не то, что в школе, а порою и в детском саду. А если кому-то она не даётся, то это не аргумент. В конце-концов, не все же должны этим заниматься. Есть и другие интересные вещи.
Речь идет о любой школе, где есть вменяемый преподаватель, который готов вести такой кружок. И найдётся несколько интересующихся ребят, готовых на этот кружок ходить. Дело это добровольное, поэтому там, в общем-то, не "проходят", а просто этим занимаются
Ну я как человек когда-то преподававший информатику в школе могу сказать, что сильно повезет, если в классе есть хотя бы десяток ребят, у которых не ветер в голове, и еще сильнее повезет, если информатикой (а не химией, биологией, физикой, языком) заинтересуется хотя бы половина из них. Большая удача наскрести участников на школьную олимпиаду с реально ценными призами и подарками. В готовности школьника разбирать балансировку дерева после вставки я сильно сомневаюсь. В мотивации учителя факультативно это преподавать одному-двум ученикам тем более. Конечно, исключения бывают и среди первых, и среди вторых. Но это действительно исключения. Посмотрите, например, результаты по заключительным этапам ВсОШ по информатике по приведенной iliazeus ссылке.
Особенность прикладной дискретной математики, на мой взгляд, в том, что это, в сущности, игра в кубики. В той или иной форме эта дисциплина доступна не то, что в школе, а порою и в детском саду. А если кому-то она не даётся, то это не аргумент. В конце-концов, не все же должны этим заниматься.
Да, есть дети, которые в 3 года говорят на нескольких языках, выступают на скрипке и умножают двузначные числа в уме. Означает ли это, что все остальные должны соответствовать их уровню и школьный стандарт должен соответствовать бакалавриату? К сожалению, реальность такова, что далеко не каждый десятый и даже не двадцатый разработчик с опытом расскажет вам характеристики, как работает и как реализованы самые часто используемые контейнеры стандартной библиотеки ежедневно используемого им языка.
Да, есть дети, которые в 3 года говорят на нескольких языках, выступают на скрипке и умножают двузначные числа в уме. Означает ли это, что все остальные должны соответствовать их уровню (...)?Скорее, все остальные родители должны (сами себе должны, а не кому-то) соответствовать родителям этих детей. Вы же не зря упомянули именно скрипку именно в 3 года, это двойной намёк на книгу «послё трёх уже поздно». Почему бы в детском саду не поиграться с дискретной математикой, вместо сами знаете какой ерунды?
Почему бы в детском саду не поиграться с дискретной математикой, вместо сами знаете какой ерунды?
Речь шла о книге, которую автор позиционирует как пособие для школьного образования и о моём недоумении подобной характеристикой. Считаю излишним агитировать за или против помощи своему ребенку в развитии. Однако, сомневаюсь в способности и, главное, мотивации большинства школьников и учителей ИВТ среднеобразовательных школ освоить и дать представленный в книге материал. К счастью это не отменяет тех самых выдающихся одаренных детей и их исключительных преподавателей, коим являлся сам автор. Надеюсь, усилия государства в этом направлении, изменят ситуацию. Буду рад ошибиться и узнать, что с 90-х и начала нулевых ситуация действительно поменялась.
Означает ли это, что все остальные должны соответствовать их уровню и школьный стандарт должен соответствовать бакалавриату?
А кто говорит о "всех" или об изменении так называемого школьного стандарта? Вы спорите сами с собой. Речь идёт о том, что дети (возможно, в лице их родителей, но это бывает по-разному) должны иметь возможность влезть в это всё. Я тоже когда-то сам ходил на такие кружки, а потом вёл их время от времени. И не только с детьми, кстати. Да, на старте может быть 10 человек. На выходе - трое. Нет ничего чудеснее мотивированного ребёнка. Он способен очень на многое. Если в нужном возрасте попадёт в нужное (именно ему) место.
Речь идёт о том, что дети ... должны иметь возможность влезть в это всё.
Изначально речь шла о тезисе, что данная книга - школьное пособие. Автор не упоминает олимпиады в аннотации и введении (хотя в тексте некоторых задач дает примечание, что они были предложены на олимпиадах). В тоже время автор говорит об общеобразовательных школах. Именно это меня и удивило.
Не смог удержаться )))
Это так же далеко от Школы как МЁД от МЕЛА или мы о разных школах 1/1000
у нас с этого года платный факультатив по матике только когда на него ходят одновременно троечники и отличники толку от него НОЛЬ пустая трата денег и времени)))
а про общий уровень школы я вообще молчу
видимо не там живем)
пособие для школьного олимпиадного кружка по информатике
Аналогичного кружкам мехмата МГУ, упомянутым в тексте, только не по математике, а по информатике. Можно вспомнить, например, ЛКШ - это, конечно, не кружок, а летняя школа, но работают там со школьниками.
А что именно там из школьной программы?
Но ведь автор не утверждает, что книжка по школьной программе. В ней много задачек и не очень много теории, а изложение материала в основном идёт в виде разбора задач. Лишний формализм пропущен там, где его можно пропустить (книжка не вводит O-нотацию, например). Сравните с книжкой Кормена, написанной для студентов.
далеко не каждый соискатель на место разработчика расскажет, как хеш
таблицы работают, а вы утверждаете, что сжатие данных в школе проходят
Первое издание книжки вышло в 1995 - школьникам в те времена приходилось писать на олимпиадах контейнеры, включая хеш-таблицы и различные вариации самобалансирующихся деревьев.
Но ведь автор не утверждает, что книжка по школьной программе.
Нет, он говорит о том, что книга написана по материалам занятий программированием со школьниками. Я позволил себе усомниться в том, что это простые школьники.
Речь может идти только об очень очень особой школе и очень очень особых школьниках. Например, таких, которые ходят на математический кружок мехмата МГУ, где математически доказывают выигрышную стратегию при игре в крестики-нолики. 90% материала выходят за рамки школьной программы по информатике. Да и некоторые задачи используют математический аппарат, который тоже в школьный стандарт не входит. Не стоит отметать эту книгу как что-то для маленьких и неразумных.
Так каков же вывод? Книга для школьников (пусть и олимпиадников) и взрослому человеку читать её стыдно или поздно?
Ну мне не стыдно. Я почерпнул для себя новое. Мне было интересно. Тем, кто уже давно не школьник, я, по прежнему, её рекомендую:
Если базиса нет, то тут он дан. Если базис уже знаком, то для разминки и расширения кругозора.
Если сравнивать с "Грокаем алгоритмы", то лучше уж прочитать "Программирование: теоремы и задачи". Да, наверное есть другие книги, где нет доказательства корректности и задач без решений и они будут более эффективны в плане затрат времени и полученного результата. Например,
классический учебник MIT "Алгоритмы" Кормена, Лейзерсона, Ривеста, Штайна
Для этого мы мнением и обмениваемся. Нет общепризнанного списка о том, что читать и в каком порядке. В соседней ветке с обзором "Грокаем алгоритмы" тоже рекомендовали каноничные тексты, но каждый рекомендовал свой набор. Я уже пополнил список того, что мне стоит прочесть. Если кто-то заинтересуется книгой А. Шеня или наоборот из моего описания или ваших комментариев поймет, что она ему не подходит и не потратит время зря - тоже хорошо.
Так каков же вывод? Книга для школьников (пусть и олимпиадников) и взрослому человеку читать её стыдно или поздно?
Я такого не писал и не подразумевал - учиться никогда не поздно :)
Моя позиция в том, что книжка написана очень доступным языком и, несмотря на пассаж в посте про "очень особенных детей", её вполне можно читать вместе с заинтересованным и освоившим программирование (или это уже делает его очень особенным?) ребёнком лет 11-16. Наравне с тем, чтобы дать ребёнку поиграть в Human Resource Machine.
Для подготовки к алгоритмической секции её недостаточно (там выше был пассаж про О-нотацию), но для погружения в алгоритмы - книжка очень хорошая, потому что даёт достаточное количество практики, чтобы их "прочувствовать".
Немного оффтоп - вообще в области программирования вещи "для школьников" часто оказываются хорошей точкой входа. Например, есть отличный курс Кириенко по основам программирования (на примере python) с довольно обширным набором задач для практической отработки навыков.
Да, наверное есть другие книги, где нет доказательства корректности и
задач без решений и они будут более эффективны в плане затрат времени и
полученного результата. Например, классический учебник MIT "Алгоритмы" Кормена, Лейзерсона, Ривеста, Штайна
Книжка Кормена как раз более фундаментальная и её ощутимо сложнее читать, если изначально не иметь какого-то представления о теме (которое как раз можно получить пройдя книжку Шеня).
там выше был пассаж про О-нотацию
Да, автор не пишет O(nlogn), но для половины задач либо дано условие, либо дан анализ: "число операций пропорционально log n", "число шагов не должно превосходить 𝐶1 log(a/b) + 𝐶2 для некоторых констант 𝐶1, 𝐶2", "время работы остаётся порядка 𝑛^2" и тому подобное. Возможно, это неканонично. Возможно, это понятнее, чем "сложность O(n^2)".
В некоторых местах рассматриваются и затраты памяти. В некоторых местах рассматривается худший случай и в среднем.
Я нашёл анкету примерно 2000-го года для студентов на практику в одну IT-контору. Вполне годится для теоретической части собеседования на миддла.
Предыдущее издание книги можно, кстати, официально скачать с сайта издательства Московского Центра Непрерывного Математического Образования.
Так и издание 2021-го года там рядом лежит.
Благодарю, исправил. В разделе "Свободно распространяемые издания" ссылка именно на предыдущее. Наверное, забыли обновить.
Там на отдельной странице много книг этого автора перечислены (возможно даже все, я не знаю точно). Оттуда я ссылку и скопировал.
Пожалуй еще паять копеек вставлю по поводу печатных изданий (я далеко не программист)
но обучение по КНИГАМ для вхождения в профессию
дело более чем спорное
даже когда препод ЧИТАЕТ лекцию и то 70% зависит от таланта препода передать свои знания (а не его знаний как таковых) а уж потом от способностей студента,
а самостоятельное обучение требует СУППЕР мотивации и кучи СВОБОДНОГО времени
более-менее нормальная литература вся на английском
добавляем постоянные косяки перевода плюс отставание от реальных задач
в итоге получаем талмуд на 500 страниц в котором нужной инфы на 100 а их надо найти время все прочитать и еще что бы вкурить неплохо бы погуглить и далеко не факт что именно те методы нужны будут в конкретной задаче в
в итоге масса потерянного времени и мало толка)
не отрицаю пользы печатных изданий (хороших) но лишь как дополнение к самообразованию в виде справочника
ловлю тапки)
Программирование: теоремы и задачи