Личный кабинет

Хабаровская школа программистов

Как учить программированию
Виталий Потопахин ( Пользователь )
Анна Владимировна подвигла меня на сообщение о наших планах. Примерно восемь лет назад, когда я впервые запустил проект "Интеллектуальные игры" я поставил перед тогдашним поколением школы две сверхзадачи: первая сделать самообучающуюся программу и вторую уйти от традиционной технологии построения таких программ (играющих против человека). Традиционная технология заключается в построении дерева перебора и поиска нужного варианта на основании некоторой оценки качества позиции в конце ветки. Форум у нас учительский, не все наверное знакомы с такими специальными вещами поэтому поясняю чуть более детально. Делается это так: строится дерево вариантов игры на некоторую глубину и для каждого варианта проигранного на эту глубину вычисляется оценочная функция представляющая собой способ получения некоторого числа. Чем данное число больше, тем позиция лучше. Принцип не сложный, но в деталях все совсем не так тривиально. Для большинства игр, построить сколько-нибудь глубокое дерево перебора не представляется возможным. Шахматы здесь даже не самая тяжелая игра. Надо учится отсекать ветви и это очень сложная вещь. Не менее сложной вещью является оценка. Возьмем для примера шахматы. Ясно, что ладья лучше пешки, но если ладья закрыта, а пешка находится на предпоследней горизонтали, то их качества меняются. Ладья в начале игры и ладья в конце игры это разные фигуры по своему качеству. В миттельшпиле конь может оказаться сильнее слона, но в эндшпиле если игра идет на разных флангах, то слон сильнее. Может быть возможно перечислить все возможные факторы, но что точно известно, так это то, что любая оценка упирается в субъективный фактор, в эксперта.
В общем так называемая обычная технология становится довольно таки сложной если мы возъмём любую реальную игру. Поэтому мы много лет копили информацию, и вырабатывали идеи создавая проекты игр на базе этой технологии. Большая часть результатов этой работы на www.lotos-khv.narod.ru
Сейчас объем наших коллективных знаний достиг критической массы, мы смогли выработать модель игры существенно отличающуюся от традиционных взглядов и сейчас желаем попытаться создать игру в которой не будет дерева перебора. Насколько мне известно удачных попыток такого рода пока не было. Планируем за два года создать программу игры в шахматы играющую в этой нашей модели в силу мастера.
В качестве инструментального средства выбран компонентный паскаль и среда БлэкБох. Мы правда в нашей школе начали осваивать эту среду только с осени 2006 года и знатоками себя не чувствуем, но как раз будет повод изучить это дело глубоко.
Михаил Густокашин ( Пользователь )
Несколько замечаний по разделу "Алгоритмы" (я уже начинал их излагать на первой странице, но потом прервался):
1) Алгоритм Йена работает не для "произвольного неориентированного графа", а для ациклического ориентированого графа. Поскольку для циклического графа он может работать неправильно (см. рис. на 1 странице), а ациклический неориентированный граф - это дерево, а в дереве может существовать только один путь, т.е. для неоринтированного графа. Для произвольного неориентированного графа алгоритм Йена ищет k-кратчайших простых цепей.
2) Все алгоритмы описаны без указания сложности и требований по памяти. Т.е. ни для одного алгоритма нет ни оценки сложности, ни оценки требуемой памяти. Если так подходить к описанию алгоритмов, то можно считать числа Фибоначчи через рекурсивную функцию (алгоритмически красиво) или использовать для хранения подмножества из 1000 натуральных чисел, каждое из которых не превышает 10^1000 на битовом массиве длиной 10^1000. Сложность-то O(1) получается! Практика показывает, что еще один критерий - реально измеренное время работы - достаточно важен. Алгоритмы с одной и той же асимптотической оценкой могут отличаться по производительности в сотни и тысячи раз.
3) Алгоритм Краскала. Там у Вас есть замечание о структурах данных. Вы утверждаете, что нет универсального метода хранения "компоненты связности". Я утверждаю, что есть - реализация системы непересекающихся множеств на основе стягивающихся корневых поддеревьев. Все языковые средства, которые она требуют - одномерный массив натуральных чисел, который есть в любом императивном языке. Сложность этого алгоритма не сильно больше линейной. Собственно, по Вашему описанию алгоритм Краскала можно реализовать либо неэффективно, либо никак.
4) Быстрая сортировка. Там путаница в терминах. Если L, R, M - левая граница, правая граница и средина ("левая", "правая", "барьер"), а A - сортируемый массив, то возникает путаница между L и A[L] и т.д. У меня такое впечатление сложилось, думаю у человека незнающего сложиться такое же мнение.

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

Насчет Вашего отношения к олимпиадам. Не буду уподобляться отдельным невоспитанным товарищам, которые кидаются категоричными утверждениями, приводя в качестве доказательства ссылки на свой сайт. Поэтому просто выскажу свое мнение без попытки навязать его: олимпиадная задача хорошо иллюстрирует применение и модификацию того или иного алгоритма и очищена от "шелухи" в виде интерфейса и т.д. и т.п. Ведущие ВУЗы учитывают результаты олимпиад по информатике при поступлении и вряд-ли в приемных комиссиях сидят дураки, которые хотят набирать "натасканных" детей. Видимо, победа в олимпиаде хорошо характеризует человека, как способного обучаться на математическом факультете. В промышленности та же ситуация - корпорации спосируют олимпиады и приглашают на работу победителей - т.е. олимпиадники способны разрабатывать ПО, которое приносит корпорациям хорошую прибыль. Т.о. олимпиадники способны не только хорошо мыслить, но и применять свои знания на практике.
Естественно, нельзя научить всех олимпиадному программированию, т.к. некоторые не могут в стрессовой ситуации разрабатывать эффективные программы, но в спокойной ситуации, без спешки и нервов, могут сделать что-то приличное. Примерно то, что называется у Вас "большими проектами" я трактую как работу для научно-практической конференции школьников. У конференции, на мой взгляд, гораздо больше минусов - субъективность оценки, программирование уступает место умению устраивать "презентейшн", что к науке имеет крайне сомнительное отношение, ну и "шелуха" в виде интерфейсов и проч., которые есть чистое ремесло.

Остались еще кое-какие мысли - допишу завтра.
Виталий Потопахин ( Пользователь )
Добрый день Михаил. Читаю ваши сообщения в разных темах и у меня укрепляется мнение, что вы просто жаждете крови и поэтому ищите ошибок. Должен сказать, что "ошибки" которые вам удается обнаружить, это не более чем ваше субъективное восприятие.

Например вы цитируете меня: "Вы утверждаете, что нет универсального метода хранения "компоненты связности". Михаил цитировать надо буквально не изменяя текста. У меня фраза звучит по другому и смысл у неё другой.
Главное, я уже вроде пояснял, но если нет, то поясню. У меня цели отличные от ваших. Я ориентирован на не раскрученных детей, у которых только потенциал, каковой может быть раскроется а может быть и нет, эти дети плохо знают математику, не умеют читать математических текстов, не владеют терминологией. Мои попытки изложения это популяризация. А любая популяризация ведет к потере строгости.
Например, ваше замечание о типах графов для алгоритма Краскала вполне справедливо. Но вы попробуйте ввести понятие ациклический граф человеку, который термин граф пока отождествляет с картинкой. А вы от меня требуете асимтотических оценок и т.д.

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

Что касается ВУЗов. В приемных комиссиях сидят не дураки. Действительно человек умеющий побеждать на олимпиадах лучше того, который ничего не умеет. И это ВУЗы понимают. Но это плохой критерий. Он говорит о том, чо ВУЗы не особенно хотят возится. И кстати процесс приема это технология и система и дурость или умность отдельных людей здесь ничего не решает.
Михаил Густокашин ( Пользователь )
Крови мне вовсе не хочется, я выражаюсь очень корректно, без претензии на истину в последней инстанции и хочу как раз конструктивного диалога.
Насчет "популяризации" - это дело хорошее, я сам опускаю части описания алгоритмов, обычно это строгие доказательства алгоритмов, но про Йена у Вас написано, что он решает не ту задачу. Это дезинформация.
Кроме того, Вы говорили, что считаете учшим языком для описания алгоритма нечто паскалеподобное. Мне кажется, что лучше и приводить алгоритмы на Паскале (по крайней мере, быструю сортировку уж точно). Просто я по этому описанию ничего не понял, а "чистого" человека (который эту сортировку еще не знает) найти пока не удалось, а то бы на нем проверил.
Насчет "прямолинейных" алгоритмов - это Вы зря. На олимпиаде еще один критерий - время, потраченное на реализацию. Поэтому человек, пишущий кривые и длинные программы, ничего не успеет. Про незнакомые задачи отчасти верно, т.к. задач на олимпиадах дают с запасом, то человек сначала делает знакомое, а на незнакомое может вполне не остаться ни времени, ни сил. Но ожидать от школьника, что он за время олимпиады сам придумает алгоритм Дейкстры, не зная ни теории графов, ничего такого - тоже довольно опрометчиво. Если человек побеждает в олимпиаде, то это означает, что он способен аналитичски мыслить, применять полученные знания (ведь задачи формулируются далеко не как "реализуйте алгоритм Дейкстры", а нужно модифицировать, продумывать, оценивать. Ну и если человек хорошо готовился и ему все знакомо - это характеризует его как человека трудолюбивого и способного на долгий упорный труд. ВУЗы эти качества ценят и, в отличии от других предметов, победители олимпиад по информатике способны на созидательный труд в науке. Кстати, о системе. Систему можно замять, а можно активно поддерживать. Например, СПбГУ уже в открытую берет без экзаменов победителей командной и рассылает им спам, а МФТИ так ломается, что не поймешь что у них там за система приема. В МГУ все проще - пришел, приняли, не пришел - приглашать никто не будет. На сайте МГУ все написано. Собственно, в МГУ конкурс растет, а в МФТИ - падает. Может и не только из-за олимпиад, но общий подход иллюстрирует.

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

В общем-то, конечно, раскрывать потенциал детей - это хорошо, но лучше все-таки заниматься со способными. И представление о том, с кем я занимаюсь, у Вас, видимо, неправильное сложилось. Ко мне приходят люди из соседних домов, чьи-то там знакомые и соседи, младшие браться-сестры бывших учеников и т.д. И вовсе не все из физ-мат школ (хотя в Москве куда ни плюнь, везде физмат школа, а реально хороших не так уж много). И ничего, учаться и задачки решать и проекты сами делают, причем я об их проектах узнаю когда они уже и тему выбрали и что-то написали.
Виталий Потопахин ( Пользователь )
Михаил о том на кого вы расчитываете я сужу по вашим лекциям. Я их прочитал очень внимательно. Это хороший добросовестно сделанный материал, но не самодостаточный. Чтобы их читать надо знать достаточно много или читать что-то в процессе (это не в упрек, такой стиль вполне возможен). Но из этого я и делаю вывод о контингенте. Дети как правило не умеют комплексно пользоваться литературой и ожидают, что все будет понятно из курса, а в ваших лекциях кроме того, сложность растет очень быстро.

Кроме того ваша собственная фраза: "но лучше все-таки заниматься со способными" это вас характеризует как педагога. И еще "Детям, в отличии от нас, требуются быстрые результаты " вы идете за ними, а должно быть наоборот. Кроме того, эта фраза характеризует вас как знатока ученической психологии. ВЫ так уверены в своих психолого-педагогических знаниях?!

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

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

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

П.С.

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

Еще один П.С.

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

for i:=1 to n do
begin
тут текст зависящий только от параметра i строк 5
end;
for i:=1 to n do
begin
и тут текст зависящий только от параметра i строк 5 но чуть чуть другой. ПРичем переменные из этого цикла переменные предыдущего не используют.
end;

Задача была из международной олимпиады для которой поверьте очень тщательно разработанная система тестов. И их решение прошло все возможные тесты. И это было ожидаемо, так как время счета из-за этого ляпа существенно не повышается.
Но ведь это безграмотно.
Михаил Густокашин ( Пользователь )
Насчет конференций: есть такая конференция "Юниор", это даже скорее выставка-конференция, т.к. все доклады стендовые. Она является отборочным этапом ISEF и, насколько я знаю, диплом этой конференции имеет тот же статус, что и диплом олимпиады. Хотя здесь я не специалист, но вроде бы так. Так что этот путь тоже не заказан.
Про кусок текста: некрасиво, но скорее всего это возникло случайно. При наличии времни нормальные олимпиадники так не пишут, ну а если надо торопиться, то могут случайно забыть и так и оставить. Конечно, привыкание к промышленному стилю программирования идет болезненно, но быстро. Просто кроме олимпиад я не вижу такой области, где можно со смыслом дать широкий набор алгоритмов (я считаю, что в рамках годичной исследовательской работы широта охвата алгоритмов гораздо ниже, чем за год подготовки к олимпиадам). Собственно, ширина или глубина охвата уже зависит от конкретных учеников.
Еще одна проблема состоит в том, что московские детки очень хотят поступить в хороший ВУЗ и возникает проблема, что в 11 классе (когда мозги у детей уже хорошо работают) заниматься программированием им некогда - все время занимают подготовительные курсы, репетиторы и проч. Есть отдельные кадры, которые ходят на разные курсы чуть ли не с 8 класса. Так что еще один критерий для детей - поступление. Я лично считаю, что пусть лучше ученик не будет знать программирования в совершенстве и поступит в МГУ (там его научат), чем будет заниматься у меня интересным ему программированием и поступит в какую-нибудь шарагу, где деградирует и забудет то, что знал. Так что и с этим нужно считаться и это закрывает дверь преждевременной научной работе - конференции субъективнее и мест на них меньше, так что олимпиада - удачный способ совместить приятное с полезным для учеников.
Федор Ткачев ( Пользователь )
(Потопахин Виталий @ 22.05.2007, 16:33) <{POST_SNAPBACK}>
... ПЕдагогика очень странная наука.


И это еще мягко сказано :-)
Федор Ткачев ( Пользователь )
(Потопахин Виталий @ 22.05.2007, 16:33) <{POST_SNAPBACK}>
И их решение прошло все возможные тесты. И это было ожидаемо, так как время счета из-за этого ляпа существенно не повышается.
Но ведь это безграмотно.


Категорически не согласен. О безграмотности можно тут говорить только в каких-то конкретных случаях.

По-моему, часто такая оптимизация (а это оптимизация) усложняет понимание программы.

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

DIVIDE ET IMPERE.
Федор Ткачев ( Пользователь )
(Потопахин Виталий @ 22.05.2007, 03:29) <{POST_SNAPBACK}>
Он говорит о том, чо ВУЗы не особенно хотят возится.


Неверно. (Ну как еще сказать?)

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

Во-вторых, важно набирать по многим параметрам. Простые экзамены тоже не обо всем говорят ведь. На олимпиадников -- ограниченное число мест. Остальное (тоже ограниченное :-) -- на тех, кто прочно усвоил базовый материал (что очень немало).
Федор Ткачев ( Пользователь )
(Михаил Густокашин @ 22.05.2007, 11:10) <{POST_SNAPBACK}>
Крови мне вовсе не хочется, я выражаюсь очень корректно


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

footer logo © Образ–Центр, 2019. 12+