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

Вот кстати, хочется рассказать о неплохой книжке по алгоритмам и структурам данных – “Программирование: теоремы и задачи” А. Х. Шеня (свободно распространяется в электронном виде, на бумаге несколько раз издавалась МЦНМО). Вот все знают книжки, скажем, Кнута (но мало кто их читал), Кормена (тут ситуация немного получше), Дасгупты или Скиены – а я хочу сказать, что эта брошюрка (320 страниц, на фоне среднего “айтишного” учебника в тысячу-полторы – это ни о чем) по глубине изложенного материала не уступает как минимум двум последним.

Особенность книжки – в изложении материала. Это не столько учебник/справочник, сколько задачник, построенный по логике “системы задач на листочках”. Эта система применяется, скажем, во многих московских матшколах и состоит примерно в следующем – на каждую тему выдается список задач (”листочек” – обычно они помещаются на лист формата A4), часть задач может иметь и самостоятельную ценность (как полноценные теоремы; иногда содержательные утверждения разбиваются на несколько подряд идущих задач). Сложность задач возрастает, для перехода к последующим листочкам надо либо решить текущий целиком, либо решить большую часть задач (в этом случае листочки могут содержать и нерешаемые задачи). Часть задач может разбираться “у доски” (прежде всего что-то основополагающее), остальные предназначены для самостоятельного решения.

В общем, получился такой сборник задач по алгоритмам для старших школьников или студентов-младшекурсников, не отягощенный излишней сложностью (как тот же Кормен), но и не скатывающийся в сюсюкание, как Бхаргава. Использовать как справочник проблематично, а как набор задач для самостоятельного понимания этого всего – в самый раз. В непонятных местах можно дополнить книжкой Дасгупты или Скиены.

PS Издание 90-х годов сопровождалось совершенно шикарным текстом – “Не покупайте эту книгу!” (кликабельно):

dont-buy-this-book

14 комментариев

  1. Pavel Ivanov пишет:

    Вот только работает такое только на учащихся этих самых матшкол, просто потому, что им накопленный интеллектуальный капитал позволяет эти задачи без томиков с теорией решать. Если же самого Шеня брать, то он банально не умеет объяснять на понижение уровня в принципе. Как лектор – очень сбивчивый и непосоедовательный, посему любит с талантливыми школьниками работать, которые его с полуслова понимают.

    • Pavel Ivanov пишет:

      Это я к “а как набор задач для самостоятельного понимания этого всего – в самый раз”, собственно.

    • Необходимая теория для простых вещей там разбирается, а дальше – ну как получится. “Самоучителей” по всему этому делу не написал толком никто.

      • Pavel Ivanov пишет:

        В обычных условиях среднестатистический ученик стопарнётся на нетиповых задачах. Чушь выше сложность и нетиповая ситуация – приехали, тупик. По поводу самоучителя – я думаю, это вряд ли возможно универсально сделать. Ещё Сократ в Диалогах Платона говорил, что учебники делают вид, что они умные, а задай им вопрос глубже – они говорят тебе одно и то же. Без живого педагога и качественно-выстроенных отношений с учениками не обойтись поэтому, а школы, отбирающие себе учеников, могут априори это себе позволить. А вот утверждение, что по этому задачнику можно самому обучиться – это проклятие знания, скорее. Когда ты лет 15 – 20 в теме – тебе всё очевидно и легко. А стоит дать этот задачник полному нубу – сразу окажется, что там дофига непростых вещей. Ну и по библиографии – он на Вирта, Гасфилда и Ахо ссылается. Для среднестатистического школьника или просто человека, не видевшего cs никогда – это неподъёмная литература, её давать как есть нельзя, подводки нужны.

        • > Ну и по библиографии – он на Вирта, Гасфилда и Ахо ссылается. Для среднестатистического школьника или просто человека, не видевшего cs никогда – это неподъёмная литература, её давать как есть нельзя, подводки нужны.

          Так это и есть “подводки”, что вот не только эта брошюрка рассказывает про алгоритмы, а есть еще вот такие книжки.

      • Pavel Ivanov пишет:

        “Давно хотел обсудить эту тему. Большинство из нас в первую очередь использует собственный опыт и считает его универсальным. Я начал программировать лет эдак в 9, с BASIC РК для Апогей БК-01. Мой основной сценарий был такой: а) разобрался с основными конструкциями и синтаксисом в первом приближении; б) перепечетал из книжки (это был Ч. Косневски и ещё одна книжечка, «Персональный компьютер в играх и задачах», кажется, так) код, запустил, порадовался, что работает, начал его модифицировать и с ним всячески играться. Спустя несколько лет, с появлением нормального компьютера, начал осваивать Pascal и C. Самостоятельно. Я не помню у себя никаких особенных мучений по поводу изучения синтаксиса ни на одном из этих этапов. И я, естественно, считаю, что у всех так. Ну, право дело, неужели трудно запомнить, что в вызове функций нужна круглая скобка, а не квадратная, что любая открытая скобка должна закрыться на том же уровне вложенности, что блоки кода выделяются фигурными скобками, что строки нужно писать в двойных кавычках, что имена переменных не должны содержать пробелов, что сравнение — это двойное равно, а не одинарное, что… Параллельно с моим программистским самообразованием то тут то там (преимущественно в школе) появлялись всякие «исполнители» («Пока на западе свободно — шаг на запад»), которые я всегда считал чем-то вроде детской игрушки. Мне не было интересно их программировать. Виртуальный робот в виртуальном мире, который только и может, что ходить по лабиринтам? Пфф. Give me the real thing, dude! Когда я узнал про Scratch, уже во вполне взрослом возрасте, я подумал — да кому нужна эта штука, мышкой из блоков программы собирать, когда можно нормальный язык выучтить за неделю? Хрень какая-то. И, думаю, в школе я бы к нему так же бы относился. А потом я совсем вырос и стал преподавать программирование. Взрослым людям, но не имеющим никакого программистского бэкграунда. И тут выяснились три вещи: а) 80% вопросов на лекциях (я заставляю на лекциях перенабирать тот код, который я показываю, у себя, и сразу же его воспроизводить) — «почему у меня не работает? потому что здесь должна быть кавычка не круглая, а квадратная, это же индексация списка, а не вызов функции — а, ну да»; б) алгоритмические конструкции типа циклов и условий, понятие переменной, простейшие структуры данных типа списка и т.д. — это сложно. Это чертовски сложно. Чёрт, да вообще понять, что программа выполняется строчка за строчкой, и что про каждую строчку можно очень аккуратно понять, что на ней делается — это сложно. Потому что реально under the hood куча каких-то абстракций, которые мне понятны уже 20 лет, а люди о них впервые слышат. Что такое «булевский тип»? Как это 2 > 1 == True? Что это вообще значит? Это объективно трудно. в) А ещё сложнее — это понять, что для того, чтобы компьютер проверил, являются ли все числа в списке чётными, нужно — у-у-у… С чего вообще начать? Это делается с помощью if, да? Я написал с циклом, но программа не работает, почему? А потому, что она у вас проверяет первый элемент и если он чётный, то сразу говорит да. Вот, видите, у вас тут return стоит. Гм-м-м, а как же надо тогда?… Ну вот представьте себе, я сейчас вам буду зачитывать список — по одному числу, ваша задача — ответить на вопрос, являются ли все числа в этом списке чётными. Поехали. Два. Да! Три. Ой. Вот. Ладно, я ещё подумаю. И вот после нескольких лет такой работы я чего-то призадумался — может, ладно, пусть этот ваш Scratch в школе будет, а? Хоть со скобками там проблем нет. А с другой стороны, может, лучше сразу пусть привыкают к тому, что компьютер — безжалостная железяка, и любая опечатка приведёт к тому, что программа не будет работать как надо? Итог. Мне кажется, что главное — это мотивация. Надо, чтобы было интересно. Если объективно борьба с синтаксисом убивает мотивацию — возможно, действительно стоит отложить борьбу с синтаксисом на потом?” (c) Не помню уже, откуда.

        • > Мне кажется, что главное — это мотивация. Надо, чтобы было интересно. Если объективно борьба с синтаксисом убивает мотивацию

          А пускай убивает. Если даже говорить о “школьном” уровне – та же физика или математика в разы сложнее.

          • Pavel Ivanov пишет:

            Я это к тому, что надо это студентам именно объяснять в теории сначала, чтобы они понимали, что значит if, что это оператор, что дальше происходит, если это интерпретатор или компилятор.

            Не все такие гениальные, как ты, многим нужно видение мира :)

            • Ну дык, есть один-единственный метод это объяснить – выполнить несколько десятков конструкций с if “ручками”, на бумаге или на доске (”Ну вот представьте себе, я сейчас вам буду зачитывать список — по одному числу, ваша задача — ответить на вопрос, являются ли все числа в этом списке чётными”). Но это “убивает мотивацию” похлеще всего остального.

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

  2. Никой пишет:

    Шура, скажи, вот мне 33. Образование техническое. Учился что в школе что в вышке на 3-4. Работаю на фулл тайм проектировщиком. В среднем зарплата норм. Но есть два желания
    1 либо работать удаленно
    2 свалить в сша на работу любую
    Как известно первая и вторая цели пересекаются с профессией программиста.
    Как можно себя проверить, с чего начать чтобы понять смогу я работать по этой теме или нет.
    Какую технологию попробовать освоить с самого начала?
    Хочу заметить, что большую часть твоих технических постов я не понимаю;(

    • Ну я так скажу – начать с того, что прочитать вот эту статью Норвига:

      https://norvig.com/21-days.html

      Понять, что на овладение профессией уйдет 10 000 часов/10 лет/что-то в таком духе.

      Если не отпугнуло – пройти курс на http://pythontutor.ru (это по мотивам курса Дениса Кириенко для семиклассников). Если зашло нормально – то дальше стандартно – выучить 2-3 языка программирования (ну, скажем, тот же Python, Java, C), понять, что из этих трех ближе, прочитать пару книжек по алгоритмам и структурам данных (”для работяг” – это Skiena, для студентов – Дасгупта), дальше заниматься уже более практической работой (ну скажем, с Java – попробовать программировать под Android, с питоном – Django и веб-приложения, C – либо попробовать влиться в большой опенсорсный проект, либо всякие там микроконтроллеры пощупать).

    • Pavel Ivanov пишет:

      Можно ещё http://hexlet.io попробовать. Там норм ребята работают, не как в Geekbrains.

Ответить

Или воспользуйтесь входом по OpenID: