Компьютерное дополнение к курсу Информатика 6. 2017

Уроки 5–6. Проект «Сортировки»

Несколько слов о проектной работе

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

Курс поддерживает два важных, взаимодополняющих вида деятельности учащихся на уроке – учебную и проектную. Основная учебная деятельность осуществляется в рамках учебника, а проектная деятельность – при помощи тетради проектов (и приложения к ней). Соответственно, в рамках курса предполагается проведение уроков двух типов – обычных и проектных. Эти два типа уроков отличаются как целеполаганием, так и формами организации активности учащихся.

Основная учебная деятельность протекает всегда только в рамках явно введенных правил игры, материал вводится последовательно и систематически. В результате учащемуся всегда понятна учебная задача («что нужно сделать») и используемые учебные средства («с помощью чего это сделать»). Основная форма проведения такого урока – самостоятельная работа учащегося с учебником-тетрадью (на бумажном или электронном носителе), где учитель выступает в роли консультанта в сложных случаях и организатора общего обсуждения. Именно на обычных (не проектных) уроках в процессе решения задач на интуитивном уровне закладываются основы серьезного информатического и математического знания: научные понятия, свойства, методы и способы деятельности.

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

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

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

Наряду с практической задачей у каждого проекта существует некоторая методическая цель – то, ради чего мы с вами и проводим этот проект. Это может быть освоение метода или алгоритма теоретической информатики, применение полученных в курсе знаний к практическим задачам, выявление информационной природы  явлений окружающего мира и т. д. Проекты, которые выполняются в группе, также имеют целью развитие организаторских и коммуникативных навыков детей. Большинство проектов направлены на развитие самостоятельности, сообразительности, эрудированности ребят. И, наконец, практически все проекты преследуют мотивационную методическую цель. Они призваны заинтересовать ребят, вселить веру в собственные силы, мотивировать приобретение новых знаний.

Если практическую задачу для детей необходимо обязательно озвучивать, то методическую цель вслух детям описывать необязательно – при правильной организации проекта она достигается сама собой, без создания для этого специальной мотивации у детей. Однако при описании каждого проекта мы обязательно будем указывать не только практическую задачу, но и методическую цель. Это важно для вашей работы, чтобы правильно расставить акценты при проведении каждого проекта. Дело в том, что, в отличие от учебных задач, которые всегда имеют фиксированный объем, проектные задачи часто допускают всевозможные вариации и продолжения. Можно выполнить проект в минимальном объеме, а можно расширить его объем в ту или иную сторону. Минимальный объем проекта задается методической целью проекта, которую мы будем указывать. Максимальный  зависит от ваших предпочтений и интересов детей. При этом вы будете ставить и дополнительные методические цели, что вполне естественно.

Практическая цель проекта – сортировка набора объектов по некоторому правилу. На первом этапе проекта учащиеся работают с небольшими массивами объектов, на втором – с большим массивом объектов.

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

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

Тем не менее важно, чтобы деятельность в проекте была организована так, чтобы ребенок получил правильный опыт, относящийся к теме «Алгоритмы и исполнители». Для этого во время выполнения каждой практической задачи на сортировку объектов надо следить за выполнением следующих моментов:

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

·         Каждая сортировка (каждый вид сортировки) выполняется по своим правилам, которые включают: а) определенный набор возможных команд (доступных исполнителю); б) определенную последовательность этих команд.

·         Лучше, если каждая сортировка будет выполняться под контролем специально выбранных «контролеров». Они должны следить за правильностью выполнения сортировки и фиксировать все ошибки – нарушения алгоритма сортировки, выполнение недопустимых действий и т.д.

Все эти условия необходимы для понимания учащимися особенностей работы формального сортировщика в искусственной среде.

Материалы для проведения проекта: текст проекта, карточки со словами и числами. Всего в вашем распоряжении 23 карточки, на одной стороне которых – слова для разрезания (по 21 слову на карточке), а на другой – крупно напечатанные числа или слова. Для работы на втором этапе проекта вам также понадобится секундомер.

1 этап (первый урок).

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

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

Для проведения 1 этапа проекта вам понадобится один комплект раздаточного материала (приложения к тетради проектов). На первом этапе проекта ребятам предстоит работать с набором крупных чисел и слов.  Основная форма работы в этом проекте – групповая. Работа над проектом проходит в два этапа (рассчитана на два урока).

Общее обсуждение

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

Проект «Сортировки» или, по крайней мере, первый его этап лучше всего проводить по подгруппам. Тогда при общей работе по сортировке учащихся нужно выбрать 10 участников сортировки, 1-2 сортировщика и 1-2 контролера. Если работа идет всем классом, то участников сортировки все равно должно быть не больше 11 (по числу крупных карточек), сортировщиков 1-2, контролеров будет больше. Участникам сортировки нужно раздать и прикрепить на грудь крупные карточки с числами или словами. Эти учащиеся смогут видеть сортировку изнутри, потому что именно их и будут упорядочивать сортировщики, давая им команды, которые, в конце концов, приведут к нужному результату. Сортировщики будут давать участникам команды – некоторые заранее оговоренные допустимые действия. Можно договориться с участниками, что остальных команд они просто «не понимают», то есть если сортировщик дает недопустимую команду, то участники не делают ничего. Контролеры должны следить за соблюдением алгоритма сортировки – правильно ли сортировщик дает команды, не нарушает ли он последовательность действий, не дает ли недопустимых команд, правильно ли участники выполняют команды сортировщика. С контролерами надо договориться, как они будут реагировать на ошибки. Лучше всего исправлять ошибки по ходу сортировки и обращать на них внимание участников процесса (иначе ошибки будут повторяться).

В этом проекте мы занимаемся алгоритмами сортировки впервые, ведь на уроках мы говорили лишь о типе (правиле) сортировки. Действительно, если объектов немного, то способ, которым ребенок достигает результат (выполнение правила сортировки), ему не важен. Чаще всего при решении задач из учебника дети комбинируют несколько алгоритмов сортировки. Однако, если объектов много, а сортировку делает формальный исполнитель, то необходимо построить именно последовательность команд исполнителя – для него нельзя формулировать задачу как для человека: «расставь слова так, чтобы…». Поскольку сам тип сортировки (правило) и специфика объектов сортировки нам в этом проекте не важны (а важны только алгоритмы!), то вы можете сами выбрать и объекты, и правило. Мы, в свою очередь, предлагаем вам в качестве объектов числа  и слова. Числа можно упорядочивать по возрастанию или убыванию, слова – в прямом или обратном алфавитном порядке. Выбор стоит делать в зависимости от силы и подготовленности класса. Если класс изучал наш курс в начальной школе, то предпочтительно выполнять сортировку слов в порядке обратного словаря (это наиболее сложная задача). Возможно, вам покажется интересным на каждый новый алгоритм сортировки выбирать новые объекты и новое правило. Конечно, в ходе 1 этапа проекта сортировщиков, контролеров и участников надо иногда менять местами. Работа с каждым из первых четырех алгоритмов сортировки проходит по следующей схеме: вначале учитель дает краткое описание алгоритма, затем выбираются  участники, сортировщики, контролеры, участникам сортировки раздаются крупные карточки с числами или словами. Затем сортировщики начинают давать команды участникам, а контролеры – следить за процессом. После того как все учащиеся будут рассортированы, подводятся итоги, обсуждаются достоинства и недостатки данного алгоритма сортировки.

1. Сортировка с помощью прямого выбора

Описание алгоритма. Идея этого метода в том, чтобы строить последовательность по порядку – первый, второй, третий и т.д. То есть вначале нужно расположить все объекты перед собой и выбрать из них тот, который будет идти самым первым. Для этого придется прямо или косвенно сравнить его со всеми остальными объектами. После того как первый член последовательности будет найден, опять остается кучка объектов, среди которых мы ищем тот, который идет раньше всех остальных. Он будет вторым в нашей последовательности. Так мы будем продолжать, пока все объекты не закончатся.

Допустимые команды сортировщика участникам: встань первым, встань следующим после (имя ученика).

Описание хода работы. Вначале учитель знакомит детей с алгоритмом сортировки по порядку и распределяет роли. Особо стоит обратить внимание ребят на допустимые команды, лучше явно выписать их на доске. Затем участники сортировки встают в группу перед сортировщиком так, чтобы все карточки со словами (или числами) были ему хорошо видны. Лучше заранее договориться, как будет строиться последовательность детей, например: вдоль доски, от окна к двери, в затылок (или лицом к классу). После этого сортировщик начинает давать команды, а контролеры исправлять ошибки.

Поскольку сортировка по порядку является для детей совершенно естественным алгоритмом (именно им они чаще всего и пользуются при решении задач), то на нем долго останавливаться не стоит. Тем не менее стоит кратко обсудить недостатки этого способа, чтобы у детей возникла мотивация искать другие алгоритмы сортировки (лишенные этих недостатков).

2. Сортировка с помощью прямой вставки.

Описание алгоритма. Идея этого метода в том, что если у нас уже есть последовательность из нескольких слов, то следующие слова можно поочередно вставлять. При этом слово вставляется в цепочку после того, как в цепочке найдены его «соседи» – два соседних слова, одно из которых стоит по алфавиту раньше вставляемого слова, а другое – позже. При таком способе можно начинать строить цепочку с любого слова – берем из кучи слов любое и ставим в цепочку на любое место. Затем берем любое другое слово, смотрим, раньше оно по алфавиту, чем первое,  или позже, ставим его в цепочку выше или ниже. Затем берем третье слово и определяем его положение уже относительно двух первых слов и т.д., пока слова в кучке не кончатся.

Допустимые команды сортировщика: встань первым, встань следующим после (имя ученика), встань предыдущим перед (имя ученика).

Можно в число допустимых команд также включить команду «встань между (имя 1) и (имя 2). Но это не является необходимым, поскольку понятия «следующий» и «предыдущий», хорошо знакомые из нашего курса, однозначно определяют место элемента в последовательности.

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

3. Сортировка методом «всплывающего пузырька».

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

Допустимые команды сортировщика: (имя учащегося) поменяйся местами с предыдущим.

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

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

В конце, как обычно, следует обсудить достоинства и недостатки этого алгоритма сортировки. Наверное, дети сами скажут, что это довольно долгий способ, ведь в худшем случае может потребоваться много проходов по цепочке объектов.

4. Сортировка слиянием.

Описание алгоритма. Идея этого алгоритма в том, что необязательно сразу строить общую, длинную цепочку слов – можно вначале построить несколько более коротких упорядоченных цепочек, а затем соединить их в одну. Например, у нас есть 24 слова. Разделим их на 4 группы по 6 слов и в каждой группе слова упорядочим – получилось 4 упорядоченных последовательности слов. Чтобы построить из них общую последовательность, важно понять, что самое первое слово в общей цепочке будет обязательно находиться среди первых слов наших 4 цепочек. Значит, последовательности слов можно сложить в стопки так, чтобы всегда видеть только первые слова всех стопок – из них мы и будем выбирать сначала первое слово, затем второе и так дальше, пока все слова не кончатся.

Допустимые команды сортировщика при слиянии: встань первым, встань следующим.

Описание хода работы. Для отработки данного алгоритма в ходе групповой работы необходимо обязательно выбрать двух сортировщиков. Вначале учитель распределяет всех участников сортировки на две группы произвольно, число детей в каждой группе необязательно должно быть одинаковым. Затем каждый сортировщик упорядочивает свою группу любым способом из описанных выше (или комбинирует несколько способов). Процесс этой сортировки можно и не контролировать, но в конце контролеры обязательно должны проверить правильность расстановки слов (или чисел). В результате работы сортировщиков ребята в каждой группе должны быть выстроены в затылок так, чтобы можно было видеть карточки только первых ребят в колонне. Далее сортировщики переходят к процессу слияния упорядоченных последовательностей. Это наиболее важный этап данного алгоритма, поэтому его проведение должно тщательно контролироваться. В частности, должны выполняться следующие правила: а) в каждый момент сортировщик сравнивает ровно два слова (или числа) – слова, которые в этот момент оказываются первыми в своих последовательностях; б) итоговая последовательность строится по порядку – первый, второй и т.д. После того как учащиеся в двух группах закончатся, у нас появляется одна упорядоченная последовательность всех учащихся. Как обычно, стоит в конце обсудить достоинства и недостатки этого алгоритма. В числе достоинств обязательно стоит отметить то, что этот метод допускает групповое разделение труда. Это для нас важно, поскольку мы имеем возможность выполнять проектную задачу сообща.

5. Сортировка через классификацию

Описание алгоритма. Как и в предыдущем алгоритме сортировки, здесь мы делим все слова на группы и упорядочиваем слова каждой группы. Однако здесь отличие состоит в том, чтобы делить слова на группы так, чтобы группы тоже оказывались упорядоченными между собой, то  есть все слова одной группы шли по алфавиту раньше слов другой группы. В таком случае после упорядочения слов в группах получившиеся цепочки не придется сливать, их можно будет просто сложить в стопку по порядку. Ясно, что при таком способе первоначально слова должны делиться на группы по первой букве (или по последней, если слова сортируются в обратном порядке). Этот алгоритм несложен для понимания детей, такой способ они часто использовали при решении задач из учебника. Поэтому если на уроке не хватит времени для отработки этого способа в ходе групповой работы – это не страшно. Вполне достаточно будет объяснить алгоритм, а дома предложить ребятам прочитать соответствующий текст на с. 5–6.

Допустимые команды сортировщика при группировке: встань в группу (номер).

Описание хода работы. Для работы по этому алгоритму нужно заранее приготовить 4 таблички для четырех групп: «Группа 1. А – Ж», «Группа 2. З – О», «Группа 3. П – Ц», «Группа 4. Ш – Я». Эти таблички нужно прикрепить к доске или стене на некотором расстоянии друг от друга. Лучше выбрать здесь 2-3 сортировщиков. Этот алгоритм несложный для понимания, поэтому при необходимости здесь можно обойтись без контролеров. После описания алгоритма учитель должен обязательно обратить внимание детей на допустимые команды и обсудить, как нужно их понимать. По команде «встань в группу 1» ребенок должен встать рядом с соответствующей табличкой.

Итак, вначале дети стоят в шеренге в затылок. Затем сортировщик отдает команды и распределяет детей на группы в зависимости от того, в какой отрезок попадет первая буква слова: если первая буква – Б, то учащийся встает в первую группу, а если П – то в третью. По ходу этой работы выясняется, что хотя алфавит мы разделили на примерно одинаковые отрезки, но слов в группах оказалось совсем не поровну: в первой группе 5 слов, во второй – 3 слова, в третьей – 2 слова, в четвертой – ни одного. Это важное наблюдение нам пригодится, когда мы будем обсуждать достоинства и недостатки данного алгоритма. После того как слова будут разделены на группы, каждый сортировщик выбирает по одной группе и упорядочивает в ней слова, пользуясь любым алгоритмом. Затем из трех последовательностей мы делаем одну, помещая последовательность второй группы после первой, а третьей – после второй.

Домашнее задание. После первого урока проекта в качестве домашнего задания детям следует предложить прочитать текст к проекту «Сортировка». Кроме того, нужно разрезать 2 комплекта раздаточного материала на отдельные страницы и раздать каждому учащемуся по две одинаковые страницы раздаточного материала. Каждую из двух страниц ребенок должен разрезать на карточки (21 штуку) и сложить в стопку в прямом или обратном алфавитном порядке  (в зависимости от того, как вы собираетесь сортировать слова на следующем этапе проекта). Каждую стопку слов стоит перевязать веревочкой, или завернуть в бумагу, или положить в маленький бумажный кармашек (чтобы слова не перепутались). Поручите детям также замерить время сортировки одного (первого) комплекта карточек. Это также необходимо для проведения второго этапа проекта.

2 этап (второй урок)

Практическая цель второго этапа – сортировка большого массива слов в обратном (или прямом) алфавитном порядке различными способами, силами всей группы, используя максимально эффективно силы каждого учащегося.

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

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

Для проведения второго этапа проекта вам понадобится: два комплекта разрезанных и упорядоченных наборов карточек из тетради проектов и один комплект разрезанных, но не упорядоченных наборов карточек. Также для измерения времени каждого этапа будет нужен секундомер. Кроме того, лучше заготовить набор крупных карточек с буквами русского алфавита (он понадобится для сортировки через группировку).

Общее обсуждение

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

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

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

 

I. Сортировка последовательным слиянием упорядоченных массивов.

1 этап. Предварительная подготовка. Поскольку на этом уроке детям предстоит выполнить довольно большой объем работы, чтобы все успеть, предлагаем вам сэкономить время за счет первого этапа сортировки слиянием. Конечно, упорядочение небольшого набора из 21 слова – для детей знакомая и простая задача. Поэтому мы рекомендовали вам на предыдущем уроке дать детям задание разрезать и упорядочить два одинаковых комплекта карточек (по 21 слову).  Кроме того, ребята дома должны были засечь время сортировки одного из комплектов. Поэтому перед началом работы стоит опросить ребят, кто сколько времени затратил на сортировку своего комплекта, и записать наибольшее время как первого этапа сортировки. Конечно, дети могут ошибиться при замерах или просто дома отвлечься от сортировки на разные дела. Поэтому результаты ребят стоит проверить. Это легко – замерьте свое время сортировки комплекта из 21 карточки, умножьте его на два, это будет время сортировки средним учеником. Если ваше время умножить на три, то это будет время сортировки медлительным и слабым учеником. Таким образом, время первого этапа (по опросу ребят) может быть меньше этого числа, но не должно быть существенно больше.

2 этап. Работа в небольших группах.

Итак, каждый из детей берет в руки один упорядоченный комплект из 21 слова. Теперь задача ребят – создать из нескольких упорядоченных стопок слов одну, где слова также будут идти в порядке обратного словаря. В начале этого этапа необходимо объединить ребят в группы по 3-4 человека (всего 3-4 группы) и поставить перед группами задачу. Перед началом работы следует обратить внимание детей на то, что проще всего сливать две упорядоченные последовательности слов. То есть можно в группах разбиться на пары и из каждых двух стопок слов образовать одну, а затем соединить две получившиеся более длинные последовательности слов. Если в группе 3 человека, то один из них в первом слиянии просто не участвует, а выступает в роли контролера. Подытожить эту работу желательно общим обсуждением, где еще раз прозвучат все правила, которыми пользовались дети при слиянии двух последовательностей слов в одну.

3 этап. Общее завершение поставленной задачи.

Завершающий этап сортировки начинается с короткого общего обсуждения – как следует провести окончательное слияние получившихся 3-4 длинных последовательностей слов. Используя опыт, полученный на предыдущем этапе выполнения проекта, ребята, скорее всего, сами предложат слить получившиеся последовательности попарно, а затем получившиеся последовательности слить еще раз. Чистое время выполнения этого этапа (без обсуждений) засекается, затем складывается со временем выполнения 1 и 2 этапов. Итак, вы получили время выполнения общей задачи – сортировки большого массива слов силами всех учащихся группы. Эту цифру надо обязательно где-то записать.

4 этап. Общее обсуждение.

По завершении выполнения поставленной задачи происходит общее обсуждение результатов. Скорее всего, всем учащимся будет ясно, что один человек затратил бы на эту работу гораздо больше времени. Интересно спросить их, почему это действительно так. Ответ очевиден – ведь работу, которую делал бы один, выполняли несколько человек, то есть в одно и то же время происходило в несколько раз больше действий, чем при индивидуальной работе. Действительно, если бы все действия, описанные выше, последовательно выполнял один человек – сначала упорядочил каждый из массивов, затем сливал парами и проч., то он потратил бы очень много времени. Можно предложить детям проверить эту гипотезу дома, упорядочив тот набор слов, который есть в его тетради проектов. Итак, секрет в одновременном выполнении нескольких операций как можно большим числом ребят, то есть работа должна быть параллельной. Тогда становится понятно, что затраченное в ходе выполнения задачи время можно ещё уменьшить, ведь только на первом этапе абсолютно все дети работали параллельно, а на последнем этапе работал, по сути, вообще только один ученик.

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

 

II. Сортировка параллельным слиянием упорядоченных массивов.

Для организации этой части проекта вам снова понадобятся упорядоченные стопки по 21 слову по числу ребят, участвующих в проекте. Поэтому мы вам советовали заранее заготовить еще один набор всех разрезанных карточек, упорядоченных в каждом наборе. Ясно, что за счет 1 этапа время сэкономить нельзя, ведь во время его выполнения все ребята и так работали параллельно. Поэтому мы начинаем сразу со слияния упорядоченных стопок (конечно, время 1 этапа мы при этом в конце должны прибавить).

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

Например, у нас в группе имеется 15 человек. Чтобы число стопок было четным, возьмем 16 стопок. Для их слияния по парам нам понадобится 8 человек. Значит, после слияния у нас получится 8 стопок, и для их слияния понадобится 4 человека. На следующем этапе для слияния 4 стопок нужно 2 человека и на завершающем – 1 человек. Таким образом, для реализации параллельной работы учащиеся должны быть расположены в классе по следующей схеме (см. рисунок). Изображенное на рисунке дерево можно перестроить для любого числа учащихся, удалив (или добавив) пары вершин с соответствующих уровней.

Работу можно организовать так. На столах выложены в ряд все упорядоченные стопки слов. Перед ними выстраивается в два раза меньшее, чем число стопок, число учащихся. За ними выстраиваются в 2 раза меньшее число учащихся так, чтобы им было удобно брать слова у двоих впереди стоящих учеников. Далее в соответствии со схемой выстраиваются оставшиеся ученики. Правила взаимодействия могут быть такими. Вначале каждый из учеников, перед которыми лежат стопки со словами, выбирает из двух верхних слов то, которое идет раньше в обратном словаре, и передает его ученику, следующему за ним. Тот, в свою очередь, из двух слов, переданных ему, выбирает то, которое идет раньше в обратном словаре, и передает его следующему, а следующий, в свою очередь, передает одно слово ученику, собирающему общую стопку всех слов. Дальше работа идет по той же схеме, но с условием, чтобы никому из учащихся не приходилось одновременно работать с более чем двумя словами, иначе со временем возникнет неразбериха. Поэтому желательно договориться, чтобы каждый учащийся первого ряда передавал свои слова следующему не тогда, когда ему захочется, а тогда, когда тот попросит. Это произойдет в тот момент, когда будет передано предыдущее слово, полученное от этого ученика, то есть у него на парте освободится место с той стороны.

Перед тем как засекать время этого этапа, лучше предварительно проверить, как работают ребята по описанной выше схеме, то есть сначала просто потренироваться на небольших наборах слов. Например, можно выдать ученикам первого ряда по 2 стопки из 3-4 слов и посмотреть, все ли ребята поняли принцип взаимодействия. Возможно, кого-то из ребят придется подвинуть, кому-то еще раз объяснить принятые договоренности.

После этого начинается работа на исходных наборах слов. Время этой работы засекается, складывается со временем проведения 1 этапа сортировки (индивидуального).

Общее обсуждение. По завершении выполнения задачи следует сравнить время сортировки первым и вторым способом. Вообще, во втором случае сортировка должна закончиться быстрее. Стоит еще раз спросить ребят, за счет чего это произошло. Ясно, что достоинством второго способа является одновременное участие всех ребят в сортировке и за счет этого ускорение процесса в целом. Хорошо бы на заключительном этапе работы обсудить с ребятами и недостатки второго способа. К числу таких недостатков следует отнести неравномерное распределение нагрузки на учащихся, расположенных на разных уровнях сортировки. Действительно, учащимся второго уровня дерева сортировки, чтобы выполнить свою часть работы, приходится упорядочивать всего 42 слова, выполняя при этом 41 попарное сравнение. В то же время корневому ученику, к которому стекаются все слова, придется выполнить сравнений на одно меньше, чем общее число слов. То есть корневой ученик выполняет гораздо больший объем работы.

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

 

III. Сортировка через классификацию

Этап предварительной подготовки. Перед началом работы у каждого учащегося должен быть набор из 21 неупорядоченного слова. Кроме того, лучше заготовить крупные карточки с буквами русского алфавита.

1 этап. Классификация слов

На первом этапе каждый учащийся получает набор из 21 неупорядоченного слова. Он должен разложить слова своего набора по группам по последней букве – в одну группу складываются все слова, заканчивающиеся на А, в другую – на Б и т.д. Задача учителя – организовать эту работу так, чтобы ребятам было легко подойти к каждой группе слов. Для этого можно на каждую парту поставить по 2 коробки или таблички с буквами, чтобы ребята спокойно могли перемещаться по классу, не мешая друг другу.

2 этап. Упорядочение слов в группах

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

Общее обсуждение

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