Алгоритмика 3 ступень aka embedded systems aka робототехника
У меня была пара встреч с занимающимися школьной информатикой, и я с удивлением обнаружил: мои постинги про алгоритмику на основе робота LEGO Mindstorm NXT 2.0 понимаются полностью неправильно. Так что про ступень 3 (из http://ailev.livejournal.com/1022791.html) придётся написать подробней -- с явным прописыванием возможных непониманий.
1. Алгоритмикой я называю обучение программированию в объеме "структурного императивного программирования" причём без структур данных (кроме самых элементарных, вроде целых и плавающих). Это включает в себя умение ученика расписать какой-то регламент, инструкцию, план, последовательность вычислений и любые другие последовательности как-то группированных между собой действий, возможно с условным выполнением групп действий. Знание каких-то конкретных алгоритмов сортировки, нахождения пути на графе и т.д. (образовательная линия, предложенная Кнутом в его многотомнике) -- это уже специальное образование, хотя это именно алгоритмика (и для неё Кнут предлагает ассемблер, не блещущий богатством структур данных). Если добавить структуры данных, я бы предпочёл это называть информатикой (программа = алгоритм + структуры данных), что примерно соответствует computer science. Если обсуждать инженерные вопросы (требования, архитектура, тестирование, коллективная разработка и т.д.) -- то это я бы называл программированием aka программной инженерией.
2. Я считаю, что перед алгоритмикой-на-настоящем-роботе дитятко прошёл программирование-на-нарисованном-роботе. Вот главные отличия между ними:
-- исполнитель нарисованного робота ходит ровно на один шаг. Шаг в обратном направлении позволяет ему попасть точно в то же место. Настоящий робот может включить одно из двух колёс на какую-то мощность, после чего вы можете замерить нужное число градусов поворота этого колеса и справиться со временем на таймере. Нет понятия "шаг", для движения "вперёд" нужно задействовать два колеса, два колеса при одинаковых командах никогда не отрабатывают одинаково (и робот едет по кривой, а не прямой) и т.д.. То есть алгоритмика-на-нарисованном-роботе дискретна, а алгоритмика-на-настоящем-роботе аналогова, сводится к численным задачам, да ещё и привязана к реальному миру с его случайностями и нестабильностями.
-- алгоритмика-на-настоящем-роботе имеет целью продемонстрировать, как устроены embedded systems, и что такое "алгоритмы" на примере алгоритмов теории автоматического регулирования (а не "алгоритмы" как запись на алгоритмическом языке -- цель курса с нарисованным роботом).
-- Мы не управляем готовым роботом с его "пользовательской" системой команд ("вперёд", "направо"), а управляем эффекторами (левый мотор, правый мотор) и датчиками (таймер, угол поворота мотора, освещённость мата) и добиваемся нужного поведения. Если есть "пульт управления", то мы считаем, что это набор датчиков -- и программируем обработку снятой с них информации, а не получаем с этого пульта готовые команды управления роботом.
Я считаю, что идея иметь "настоящий робот", который программируется так же, как нарисованный (и вся "аналоговость" которого, работа с эффекторами и датчиками закрыты кодом в недрах КуМира, так что в Ершоле остаётся только исполнитель с командами "вперёд" (на шаг), "поворот на прямой угол" и т.д., плюс для "цифровости" делается специальное поле с контрастными клеточками и делаются прочие ухищрения того же сорта -- это вредная идея. Для обучения структурному программированию достаточно иметь нарисованного робота с дискретным поведением. Дорогая его эмуляция настоящим роботом -- это забивание гвоздя микроскопом, ничему не учит, ничего не демонстрирует, а только отрабатывает ложную идею, что с "настоящим роботом и настоящим полем" будет интересней. Нет, не будет интересней.
Как раз учить нужно "выходу в физику" и специфике этого выхода (точность, скорость, разбросы, поломки и т.д.), а не затушёвывать эту специфику. Ну, и после шага "познакомимся с основными операторами языка" дать шаг "попробуем запрограммировать какой-то алгоритм -- ПИД, и повлиять на реальный мир, а не пиксели на экране".
3. Алгоритмы, которые хотелось бы тут пройти -- это:
а) алгоритмы автоматического регулирования. Я подробно писал об этом тут: http://ailev.livejournal.com/971904.html (замечу, что там ставится вопрос "как научить программировать PID controller", но не даётся ответа на него. Но зато есть ссылки на литературу). Собственно, это "минимальный курс робототехники", тут можно было бы ставить точку. Робот с написанной и откалиброванной программой PID controller должен уметь выступить на соревновании скоростного прохождения трассы по нарисованной на мате линии (хотя "высший пилотаж" по этой теме -- это сделать что-то типа Segway). Ученик должен понимать каждую строчку его программы, уметь модифицировать эту программу для ситуации с линиями разной минимальной кривизны, разного диаметра колёс робота, покрытия разной скользкости.
б) алгоритмы пульта управления (remote controller). Робот должен хорошо проходить "слалом" между препятствиями, повинуясь сигналам от пульта дистанционного управления. Это не так-то просто (если вы не пользуетесь готовой программой пульта управления, типа http://androinica.com/2010/10/lego-launches-minddroid-a-remote-control-for-mindstorms-nxt/, а пытаетесь написать свою программу -- вам нужно как-то творчески пересчитать значения датчиков контроллера в команды для моторов робота, иначе вы не справитесь с управлением). Я бы считал, что нужно таки в качестве пульта управления использовать смартфон с Android (а не джойстик). Цель -- скоростное прохождение всяких "слаломов". Это просто дополнительное упражнение, ничего существенно нового по сравнению с предыдущим пунктом: кроме исполнителя "робот" появляется исполнитель "пульт" и добавочная математика примерно того же сорта, что и в (а).
в) теперь смартфон ставится на тележку робота и задействуется его веб-камера. Камера смотрит на пунктирную линию на мате. Задача: проехать по пунктирной линии (вместо сплошной линии, как в (а)). Для этого нужно распознавать пятна "пунктира", находить их "центры тяжести", строить прямые через эти "центры тяжести" и направлять робота по этим прямым -- используя пропорциональное управление. Это тоже традиционное соревнование в робототехнике, advanced level. Это существенно новое, это дополнительный материал: анализ сцен в растровой графике. Без него, конечно, можно обойтись -- но не хотелось бы.
4. Программы для 3а должны использовать исполнитель, который непосредственно работает с "железом" (датчиками и моторами) робота, минимально закрывая их от учеников. Вот как выглядит исполнитель "робот NXT" в RobotC -- http://www.robotc.net/support/nxt/media/code_listing/nxt.html. Что нужно сделать, чтобы иметь такой исполнитель на КуМире? Перевести на русский, но оставить суть. Никаких сложных команд типа "повернуть на 90 градусов": ученик должен, ежели ему нужно, сам написать программу "повернуть на X градусов с радиусом поворота Y сантиметров", используя только имеющиеся у робота эффекторы и способы управления ими, и датчики с предлагаемыми ими "родными" единицами измерения. Сама суть курса -- это чтобы ученики поняли, как делают все эти пересчёты из "содержательной постановки задачи" в "постановку задачи в терминах имеющегося железа", и почувствовали, как программа связана с физическим миром.
5. Конечно, системы программирования предоставляют разные удобства: кто-то требует счёта программы в компьютере и отработки команд по блютусу, кто-то готов загрузить программу в "кирпич" и позволить автономную работу робота вдали от компьютера. Кто-то даёт отладчик, кто-то не даёт. Алгоритм PID предъявляет требования к скорости работы программы, что может оказаться фатальным для медленных интерпретаторов.
6. Для 3b и 3c нет пока никаких намёток, как это делать, какие требования к железу, какие задачи можно было бы решать. Так что интересны любые предложения.
Теперь, надеюсь, никто не будет считать, что курс по освоению структурного программирования с нарисованным роботом и курс по алгоритмам для embedded systems -- это один и тот же курс, в котором нарисованный робот "просто заменяется" настоящим. Нет, это совсем-совсем другое, это про численную математику/алгоритмы и связь с "железными" системами. Эта ступенька с настоящим роботом Lego у меня вовсе не "начальное обучение языку программирования" (таких курсов по освоению операторов языка на примере программ управления роботом LEGO Mindstorm NXT полно в интернете, но я считаю, что на старте этого курса все эти операторы цикла, условные операторы и вспомогательные алгоритмы с параметрами ученики уже знают, и это знание просто используется, а не осваивается).
1. Алгоритмикой я называю обучение программированию в объеме "структурного императивного программирования" причём без структур данных (кроме самых элементарных, вроде целых и плавающих). Это включает в себя умение ученика расписать какой-то регламент, инструкцию, план, последовательность вычислений и любые другие последовательности как-то группированных между собой действий, возможно с условным выполнением групп действий. Знание каких-то конкретных алгоритмов сортировки, нахождения пути на графе и т.д. (образовательная линия, предложенная Кнутом в его многотомнике) -- это уже специальное образование, хотя это именно алгоритмика (и для неё Кнут предлагает ассемблер, не блещущий богатством структур данных). Если добавить структуры данных, я бы предпочёл это называть информатикой (программа = алгоритм + структуры данных), что примерно соответствует computer science. Если обсуждать инженерные вопросы (требования, архитектура, тестирование, коллективная разработка и т.д.) -- то это я бы называл программированием aka программной инженерией.
2. Я считаю, что перед алгоритмикой-на-настоящем-роботе дитятко прошёл программирование-на-нарисованном-роботе. Вот главные отличия между ними:
-- исполнитель нарисованного робота ходит ровно на один шаг. Шаг в обратном направлении позволяет ему попасть точно в то же место. Настоящий робот может включить одно из двух колёс на какую-то мощность, после чего вы можете замерить нужное число градусов поворота этого колеса и справиться со временем на таймере. Нет понятия "шаг", для движения "вперёд" нужно задействовать два колеса, два колеса при одинаковых командах никогда не отрабатывают одинаково (и робот едет по кривой, а не прямой) и т.д.. То есть алгоритмика-на-нарисованном-роботе дискретна, а алгоритмика-на-настоящем-роботе аналогова, сводится к численным задачам, да ещё и привязана к реальному миру с его случайностями и нестабильностями.
-- алгоритмика-на-настоящем-роботе имеет целью продемонстрировать, как устроены embedded systems, и что такое "алгоритмы" на примере алгоритмов теории автоматического регулирования (а не "алгоритмы" как запись на алгоритмическом языке -- цель курса с нарисованным роботом).
-- Мы не управляем готовым роботом с его "пользовательской" системой команд ("вперёд", "направо"), а управляем эффекторами (левый мотор, правый мотор) и датчиками (таймер, угол поворота мотора, освещённость мата) и добиваемся нужного поведения. Если есть "пульт управления", то мы считаем, что это набор датчиков -- и программируем обработку снятой с них информации, а не получаем с этого пульта готовые команды управления роботом.
Я считаю, что идея иметь "настоящий робот", который программируется так же, как нарисованный (и вся "аналоговость" которого, работа с эффекторами и датчиками закрыты кодом в недрах КуМира, так что в Ершоле остаётся только исполнитель с командами "вперёд" (на шаг), "поворот на прямой угол" и т.д., плюс для "цифровости" делается специальное поле с контрастными клеточками и делаются прочие ухищрения того же сорта -- это вредная идея. Для обучения структурному программированию достаточно иметь нарисованного робота с дискретным поведением. Дорогая его эмуляция настоящим роботом -- это забивание гвоздя микроскопом, ничему не учит, ничего не демонстрирует, а только отрабатывает ложную идею, что с "настоящим роботом и настоящим полем" будет интересней. Нет, не будет интересней.
Как раз учить нужно "выходу в физику" и специфике этого выхода (точность, скорость, разбросы, поломки и т.д.), а не затушёвывать эту специфику. Ну, и после шага "познакомимся с основными операторами языка" дать шаг "попробуем запрограммировать какой-то алгоритм -- ПИД, и повлиять на реальный мир, а не пиксели на экране".
3. Алгоритмы, которые хотелось бы тут пройти -- это:
а) алгоритмы автоматического регулирования. Я подробно писал об этом тут: http://ailev.livejournal.com/971904.html (замечу, что там ставится вопрос "как научить программировать PID controller", но не даётся ответа на него. Но зато есть ссылки на литературу). Собственно, это "минимальный курс робототехники", тут можно было бы ставить точку. Робот с написанной и откалиброванной программой PID controller должен уметь выступить на соревновании скоростного прохождения трассы по нарисованной на мате линии (хотя "высший пилотаж" по этой теме -- это сделать что-то типа Segway). Ученик должен понимать каждую строчку его программы, уметь модифицировать эту программу для ситуации с линиями разной минимальной кривизны, разного диаметра колёс робота, покрытия разной скользкости.
б) алгоритмы пульта управления (remote controller). Робот должен хорошо проходить "слалом" между препятствиями, повинуясь сигналам от пульта дистанционного управления. Это не так-то просто (если вы не пользуетесь готовой программой пульта управления, типа http://androinica.com/2010/10/lego-launches-minddroid-a-remote-control-for-mindstorms-nxt/, а пытаетесь написать свою программу -- вам нужно как-то творчески пересчитать значения датчиков контроллера в команды для моторов робота, иначе вы не справитесь с управлением). Я бы считал, что нужно таки в качестве пульта управления использовать смартфон с Android (а не джойстик). Цель -- скоростное прохождение всяких "слаломов". Это просто дополнительное упражнение, ничего существенно нового по сравнению с предыдущим пунктом: кроме исполнителя "робот" появляется исполнитель "пульт" и добавочная математика примерно того же сорта, что и в (а).
в) теперь смартфон ставится на тележку робота и задействуется его веб-камера. Камера смотрит на пунктирную линию на мате. Задача: проехать по пунктирной линии (вместо сплошной линии, как в (а)). Для этого нужно распознавать пятна "пунктира", находить их "центры тяжести", строить прямые через эти "центры тяжести" и направлять робота по этим прямым -- используя пропорциональное управление. Это тоже традиционное соревнование в робототехнике, advanced level. Это существенно новое, это дополнительный материал: анализ сцен в растровой графике. Без него, конечно, можно обойтись -- но не хотелось бы.
4. Программы для 3а должны использовать исполнитель, который непосредственно работает с "железом" (датчиками и моторами) робота, минимально закрывая их от учеников. Вот как выглядит исполнитель "робот NXT" в RobotC -- http://www.robotc.net/support/nxt/media/code_listing/nxt.html. Что нужно сделать, чтобы иметь такой исполнитель на КуМире? Перевести на русский, но оставить суть. Никаких сложных команд типа "повернуть на 90 градусов": ученик должен, ежели ему нужно, сам написать программу "повернуть на X градусов с радиусом поворота Y сантиметров", используя только имеющиеся у робота эффекторы и способы управления ими, и датчики с предлагаемыми ими "родными" единицами измерения. Сама суть курса -- это чтобы ученики поняли, как делают все эти пересчёты из "содержательной постановки задачи" в "постановку задачи в терминах имеющегося железа", и почувствовали, как программа связана с физическим миром.
5. Конечно, системы программирования предоставляют разные удобства: кто-то требует счёта программы в компьютере и отработки команд по блютусу, кто-то готов загрузить программу в "кирпич" и позволить автономную работу робота вдали от компьютера. Кто-то даёт отладчик, кто-то не даёт. Алгоритм PID предъявляет требования к скорости работы программы, что может оказаться фатальным для медленных интерпретаторов.
6. Для 3b и 3c нет пока никаких намёток, как это делать, какие требования к железу, какие задачи можно было бы решать. Так что интересны любые предложения.
Теперь, надеюсь, никто не будет считать, что курс по освоению структурного программирования с нарисованным роботом и курс по алгоритмам для embedded systems -- это один и тот же курс, в котором нарисованный робот "просто заменяется" настоящим. Нет, это совсем-совсем другое, это про численную математику/алгоритмы и связь с "железными" системами. Эта ступенька с настоящим роботом Lego у меня вовсе не "начальное обучение языку программирования" (таких курсов по освоению операторов языка на примере программ управления роботом LEGO Mindstorm NXT полно в интернете, но я считаю, что на старте этого курса все эти операторы цикла, условные операторы и вспомогательные алгоритмы с параметрами ученики уже знают, и это знание просто используется, а не осваивается).