Недавно я прочитал цикл лекций для учителей информатики (по линии центра Вега). Лекции в основном про особенности олимпиад, которых могут не знать обычные учителя, и про то, как и чему, на мой взгляд, надо учить умных школьников.
На днях я написал во вКонтакте большой пост про проблемы на школьном этапе Всероссийской олимпиады школьников в Нижегородской области. В нем, в частности, была следующая фраза: «Нет никакого смысла гордиться тем, что вы победитель школьного или, допустим, призер районного этапа. Весь смысл школьного и районного этапов — отобрать участников областной олимпиады <…>, и соответственно участвовать в школьном и районном этапе имеет смысл либо с целью выйти на область <…>, или чисто в качестве тренировки, чтобы уже в будущем году выйти на область». В последовавшей дискуссии я более доформализовал и подробнее расписал, почему я так считаю, и здесь публикую еще более расширенный и отредактированный ответ.
Бывают задачи, в которых вам надо пройтись по какой-то одномерной структуре (массиву, строке), но при этом в определенных случаях вам может захотеться писать вложенные циклы — как правило, двигающие одну и ту же переменную.
Меня часто спрашивают, веду ли я индивидуальные занятия, индивидуальную подготовку к олимпиадам, aka занимаюсь ли я репетиторством. В целом, ответ — нет, не занимаюсь. По следующим причинам.
В теме про системы счисления люди очень частно используют термин «десятичная система счисления» не совсем правильно.
Последнее время я с несколькими учениками алгопрога обсуждал необходимость или не-необходимость различных оптимизаций в разных задачах. В последнем таком обсуждении я написал довольно развернутый ответ, который (в слегка отредактированном виде) публикую тут.
Hackers (and creative people in general) should never be bored or have to drudge at stupid repetitive work […] To behave like a hacker, you have to believe this enough to want to automate away the boring bits as much as possible[.]
Eric Steven Raymond, How To Become A Hacker
В этом посте я попробую описать, что обычно стоит ожидать на собеседованиях на позицию программиста (разработчика) в IT-компании, а также какое материалы с алгопрога и не только вам будут полезны. Пост в основном ориентирован на «студентов и старше», занимающихся на алгопроге, но и школьникам тоже будет полезно знать на будущее.
Каждое решение на алгопроге, которое успешно проходит все тесты, я просматриваю глазами и либо засчитываю, либо игнорирую. Если я засчитываю решение —значит, оно написано в целом нормально. Я могу к такому решению написать комментарий, но этот комментарий — он скорее «к сведению» ученика. А вот если я игнорирую решение, это значит, что решение надо переделать с учетом моего комментария. В этом посте я постараюсь описать общие принципы, которых я придерживаюсь при игнорировании решений.
Я добавил на алгопрог возможность просмотреть список пользователей с конкретной ачивкой (кликом по ачивке), и записал скринкаст про то, как я это делаю. Пишите комментарии, надо ли записывать подобного рода видео еще. Видео
Что делать толковым школьникам после окончания школы? Именно толковым в смысле программирования. Классический вариант — идти в университет, но последнее время все чаще становится популярной идея не идти в университет, а идти сразу работать, тем более что толковый школьник-программист действительно сразу после школы знает достаточно, чтобы начать работать и успешно зарабатывать деньги. В этом посте я опишу известные мне плюсы и минусы каждого варианта, и напишу мое личное мнение на этот счет.
Видеозапись рассказа про системы контроля версий с занятия 16 февраля. Видео
У языка программирования C++, а также у популярных IDE для этого языка, есть ряд особенностей, которые надо бы знать, чтобы эффективно писать на нем программы. В этом посте я постараюсь описать основные такие особенности, в первую очередь относящиеся к написанию небольших программ типа олимпиадных; возможно, в дальнейшем буду постепенно добавлять сюда что-нибудь. Сначала опишу особенности IDE, потому что они полезны даже тем, кто только начинает писать на C++, а потом особенности самого языка, которые нужны уже чуть более продвинутым школьникам.
Я давно хотел запостить список малоизвестных книг, статей и подобных материалов, которые были интересны мне и которые, я надеюсь, будут интересны многим людям с техническим складом ума, в том числе большинству моих друзей во вКонтакте и большинству учащихся на алгопроге. Я буду говорить про, скажем так, «художественную литературу», т.е. не специализированную литературу, допустим, по алгоритмам, а литературу для общего интереса (подробнее про это в следующих абзацах). Это, конечно, не имеет прямого отношения к тебе блога, и изначально я думал написать пост во вКонтакте, но решил, что в блог запостить это лучше, заодно в будущем я возможно буду этот список дополнять.
Алгопрог вам дает, в первую очередь, знания алгоритмов (ну и смежных тем). Но мало их знать, надо уметь их применять в реальной жизни, особенно если вы — школьник и хотите участвовать в олимпиадах. Если вы на начальных уровнях алгопрога (примерно до 3 уровня), то пока просто решайте алгопрог. Но добравшись до уровня 3 (или даже можно чуть раньше), начинайте более-менее регулярно тренироваться на задачах из реальной жизни — в первую очередь, конечно, решая раунды на codeforces, и прорешивая старые олимпиады.
Видеозапись рассказа про районную/городскую олимпиаду с занятия 8 декабря. Видео
Помимо олимпиад, есть еще один довольно широко распространенный вид «наукообразной» деятельности для школьников — это всевозможные «научные общества учащихся», «конференции», на которых школьники представляют свои «проекты». У меня такое очень двоякое отношение к таким мероприятиям; очень вкратце — проекты делать имеет смысл, участвовать в конференциях — в большинстве случаев вряд ли.
Видеозапись лекции про Far Manager с занятия 27 октября. Видео: Far Manager
Меня часто спрашивают, что нужно изучать школьнику, который планирует в будущем стать программистом. Еще чаще я сталкиваюсь с рассуждениями школьников в стиле «я хочу изучать C#, чтобы писать на нем игры». Недавно один школьник спросил меня, мол, мой курс на алгопроге — это больше подготовка к олимпиадам, или «обычный курс обучения программиста», по типу тех, которые более-менее активно рекламируются в интернете? Я тогда ему написал ответ, и ниже я публикую довольно расширенный вариант этого ответа, заодно отвечая и вообще на вопрос, что вообще нужно изучать школьнику, чтобы стать программистом.
Видеозапись лекции про командную строку и прочие способы взаимодействия программ с занятия 6 октября. Видео: командная строка и прочие способы взаимодействия программ
При решении задач на хеширование вам очень частно бывает надо уметь за $O(1)$ вычислять хеш любой подстроки заданной строки. Стандартный подход к таким задачам — давайте посчитаем хеши всех префиксов, а дальше будем с этим что-то делать…
В типичной олимпиадной задаче (и, соответственно, в типичной задаче на алгопроге) в условии четко оговариваются максимальные допустимые значения для переменных или другие ограничения на входные данные. Например, так:
…Тут, говорят, исполнилось 20 лет третьим «Героям», на «Медузе» прекрасный текст с воспоминаниями про них, и поэтому я решил все-таки записать одну историю, которую давно хотел записать, но все руки не доходили. История эта лишь очень косвенно относится к тематике этого блога, это просто история из серии «байки старого программиста», но, кажется, этой истории место скорее здесь, чем, например, на моей стене во вКонтакте.
Я рекомендую всем начинающим изучать питон. Но при этом я настоятельно не рекомендую использовать Jupyter notebook или подобные «среды разработки» (в кавычках, потому что на самом деле Jupyter вовсе не среда разработки). Попробую объяснить, почему.
Всем ученикам на алгопроге я всегда говорю: никогда не используйте вещественные числа, если без этого можно обойтись — из-за погрешностей, которые при этом всегда возникают. Подобные решения я сразу «игнорирую» (не засчитываю и требую от учеников их переделать).
Суть поста вкратце: я считаю, что на олимпиадах, целью которых (хотя бы отчасти) является выявление победителя, задачи должны быть составлены так, чтобы победитель не набрал максбалл — победитель должен скорее набирать процентов 70-80.
На алгопроге на начальных уровнях есть ряд задач, которые легко решаются стандартными функциями из стандартной библиотеки почти любого языка программирования — например, Максимум в массиве или Перевести символ в верхний регистр. Тем не менее, я всегда в этих задачах требую от учеников реализовать нужные действия вручную — в первом случае через цикл по массиву, во втором — работой с кодами символов. Недавно я доформализовал ответ на вопрос, почему я это требую.
И еще одно видео с другого мероприятия, на котором я недавно выступал — мастеркласса Women in big data. Видео: тестирование и отладка программ
Недавно я выступал на нижегородской C++ User Group с докладом про Undefined behavior. Сейчас огранизаторы мероприятия смонтировали видео и выложили на youtube. Настоятельно рекомендую посмотреть всем, кто более-менее неплохо знает C++.
…Недавно меня спросили, какой мой любимый язык программирования. Вообще, конечно, этот вопрос некорректный. Языки отличаются по очень многим вещам, и нет какого-то одного идеального языка, у каждого языка есть свои достинства и недостатки.
Пусть у вас есть небольшая программа, которая… не работает. Причем не просто как-то не работает, а у вас есть конкретный тест, конкретный пример, на котором она не работает. (Если у вас такого примера нет, то у меня есть отдельный текст про то, что делать в таком случае.) Как понять, что в программе не так, и как это исправить?
Довольно интересный вопрос — почему на олимпиадах по информатике традиционно дают задачи только на программирование (написание программ), при том, что в стандартной школьной программе программирование занимает лишь малую часть времени, и есть много других тем? Я попробую как-то ответить на этот вопрос. Все, что я излагаю ниже (да и выше тоже), конечно, является только моим личным мнением.
Очень часто наблюдаю, как многие школьники, да и не только школьники, начиная решать какую-то задачу, начинают сначала думать с разные мелких частных случаев, которые на самом деле никак не помогают в общем решении.
Пусть у вас есть простая задача — дан двумерный массив, надо посчитать и вывести на экран сумму каждой строки этого массива. Как вы будете это писать? Я бы это написал так:
В наше время (в отличие, например, от того, что было лет 15-20 назад) существует огромное количество разных олимпиад. Олимпиады проводят все кому не лень, и поэтому, к сожалению, качество проведения олимпиад часто сильно страдает.
Тестирование программы, или точнее проверка верности программы в широком смысле, начинается не когда вы уже написали программу. Вообще, тестировать можно и нужно даже идею, еще до того, как вы начали писать код — но сейчас я буду говорить именно про тестирование конкретного кода. Так вот, серьезно думать о тестировании и корректности кода надо еще когда вы этот код только пишете.
If you want proof, Harry, that you belong in Gryffindor, I suggest you look more closely at this.
Harry Potter and the Chamber of Secrets, by J.K. Rowling
