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

Урок 1. «Сортировка: упорядочение и классификация»

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

Как и многие практические информационные задачи, переходя в раздел научных проблем, сортировка заняла свое значимое место в теоретической информатике. Действительно, до тех пор пока мы сами наводим порядок на своем столе, никакая особая теория нам не нужна. Но как только мы сталкиваемся с огромным набором объектов, который не можем рассортировать сами, нам сразу же необходимо придумать какое-то конкретное правило, которое мы должны объяснить помощнику (или помощникам), чтобы выполнить поставленную задачу вместе. Если при этом мы выбираем в помощники компьютер, то задача изобретения правила сортировки дополнительно усложняется – ведь компьютер (в отличие от человека) выполняет четко определенный набор команд, всегда по определенным правилам. Примерно так в теоретической информатике появился раздел, посвященный различным алгоритмам сортировки. Алгоритмов сортировки существует несколько. Алгоритмы сортировки следует отличать от правила (способа) сортировки. Правило сортировки – это описание порядка, по которому мы должны сложить (разложить) объекты в наборе. Например: «Разложи все слова по частям речи и в каждой из групп расположи слова по алфавиту». Алгоритм сортировки – это инструкция, описывающая наши действия, которые приведут, в конечном счете, к выполнению описанного правила, то есть к наведению указанного порядка. По тому, для кого пишется алгоритм сортировки, можно разделить все алгоритмы на формальные и неформальные. Формальные алгоритмы пишут для формальных исполнителей, например компьютера. Такие алгоритмы должны быть составлены максимально четко и полно и должны использовать только те команды, которые доступны («понятны») исполнителю. Неформальные алгоритмы мы пишем для других людей (необязательно для сортировки). Такие алгоритмы могут быть не настолько полными, но они понятны для человека. На данном уроке мы в основном вводим необходимую лексику: сортировка, группировка, упорядочение. При этом группировкой мы будем называть такую сортировку, в процессе которой нужно получить группы (мешки или множества) объектов, то есть распределить объекты по группам. Обычно группировка производится по некоторому признаку.      Упорядочением мы будем называть такую сортировку, в процессе которой объекты нужно выстроить в последовательность. Также на этом листе определений мы знакомим ребят с примерами различных правил сортировки. С алгоритмами сортировки ребята познакомятся, работая с проектом «Сортировки».

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

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

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

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

Задача 1.  В этой задаче необходимо упорядочить слова – превратить множество слов в последовательность. На листе определений приведено правило словарного порядка для двух слов, поэтому формулировка данной задачи означает явно следующее – построить из слов последовательность так, чтобы из любых двух слов в последовательности раньше шло то, которое идет раньше в словарном порядке. Большинство ребят, наверняка, хорошо ориентируются в словарном порядке слов. Дети, которые изучали наш курс в начальной школе, решили довольно много подобных задач, помогать им, скорее всего, вообще не придется. Но если ваш класс изучает информатику с текущего года, то продумайте заранее, как вы будете помогать слабым учащимся. Из правила словарного порядка на листе определений становится ясно, что слова, первая буква которых идет в словаре раньше, будут идти раньше и в нашей последовательности. Поэтому для начала можно сгруппировать слова, ориентируясь только на первую букву. Если при этом в группе оказалось одно слово, то его можно сразу поставить в цепочку. Если нет – с этой группой надо работать, ориентируясь на вторую букву, и т. д. Например, просмотрим все слова и найдем все слова на «А». Такое слово одно – АИСТ. Напишем его в последовательность первым и пометим в наборе галочкой (чтобы больше его не просматривать). Далее ищем слова на «Б» (БУРЕВЕСТНИК), на «В» – ВОРОБЕЙ и т. д. Как видим, вплоть до буквы «И» в нашем наборе попадается не больше одного слова на одну букву, поэтому упорядочение идет достаточно легко. На букве «К» может возникнуть небольшой затор, поскольку в наборе есть 5 слов на «К». Здесь придется сравнивать слова, ориентируясь на вторую букву, а в одном случае – на третью. После буквы «К»  упорядочение можно закончить, ориентируясь на первую букву.

Ответ:

АИСТ

БУРЕВЕСТНИК

ВОРОБЕЙ

ГОРЛИЦА

ДЯТЕЛ

ЖУРАВЛЬ

ЗЯБЛИК

ИВОЛГА

КАЗАРКА

КАКАДУ

КИВИ

КЛЁСТ

КОРШУН

ЛАСТОЧКА

МАЛИНОВКА

НЕЯСЫТЬ

ОРЁЛ

ПЕТУХ

РЯБЧИК

СОЛОВЕЙ

ТЕТЕРЕВ

УДОД

ФАЗАН

ЩЕГОЛ

Задача 2. В первом задании снова требуется упорядочить слова в словарном порядке. Все слова в наборе начинаются на букву «О», поэтому ориентируемся на вторую букву слов. Слов со второй «А» в наборе нет, а со второй «Б» есть – ОБВАЛ. Это слово и будет первым в цепочке, после него надо пропустить строчку. Дальше пишем слово со второй буквой «В» – ОВАЛ, и т .д. Надеемся, что с первым заданием проблем у ребят не возникнет. После того как все данные слова будут выстроены в цепочку, дети начинают вписывать в пустые строки свои слова так, чтобы словарный порядок сохранился. При этом каждое слово, кроме последнего, должно идти в словаре позже предыдущего и раньше следующего. Например, будем искать первое недостающее слово. Оно должно идти в словаре позже слова ОБВАЛ, но раньше – ОВАЛ. Ясно, что первая буква недостающего слова – «О». Можно подобрать слово со второй буквой «Б» – ОБГОН, ОБЛЕТ, ОБИДА, ОБРАЗ и т. д. –  или со второй буквой «В», но это несколько сложнее. Так дети продолжают работать вплоть до последнего пропуска, который заполнить несколько проще, ведь слово должно только идти в словарном порядке позже ОПЕРЕНИЕ. Продумайте заранее, какую помощь вы будете оказывать детям, которые не смогут заполнить один из пропусков. Здесь действительно есть сложные случаи: например, не всякому шестикласснику будет просто вставить слово между ОЛЕНЬ и ОМЛЕТ или ОМЛЕТ и ОНИ. Конечно, можно устроить общую проверку, в ходе которой дети будут предлагать свои варианты пропущенных слов и вписывать слова, которые не смогли придумать, но ребенок при этом будет достаточно пассивен. Нам кажется наиболее привлекательным вариант, когда ребенок ищет нужное слово в словаре. При этом дети повторят навыки работы со словарями и решат задачу все-таки самостоятельно. Но при таком варианте вам придется приготовить на урок хотя бы 5-6 словарей. Лучше всего, если это будут толковые словари, тогда ребенок сможет не просто найти подходящее слово, но и выяснить, что оно значит, если слово окажется незнакомым.

Вот один из вариантов подходящей цепочки (черным помечены данные слова):

ОБВАЛ

ОБУВЬ

ОВАЛ

ОВОЩ

ОГАРОК

ОГУРЕЦ

ОДИН

ОДИННАДЦАТЬ

ОКЕАН

ОКОЛО

ОЛЕНЬ

ОЛОВО

ОМЛЕТ

ОНА

ОНИ

ОПЕРА

ОПЕРЕНИЕ

ОШИБКА

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

Ответ: 12; 23; 89; 98; 123; 234; 987; 1234; 2345; 9876; 12345; 98765; 123456; 987654; 1234567.

Задача 4. Здесь требуется собрать одинаковые фигурки по группам. Наиболее простой способ не ошибиться – грамотно организовать перебор; этот метод следует предложить детям, которые запутались. Берем первый многоугольник на сетке – А  и ищем все многоугольники, равные ему. Записываем их имена вместе с А в первое множество, а сами фигурки аккуратно зачеркиваем карандашом, чтобы больше их не перебирать. Получаем первое множество: А; Г; И; Х. Теперь берем следующий многоугольник – Б и ищем все многоугольники, равные ему. Получаем второе множество многоугольников: Б; Ж; Р; Т. Третье множество: В; М; П; С. Четвёртое множество: Д; К; Л; Н; Ф. Все оставшиеся многоугольники оказываются равны между собой и составляют пятое множество: Е; З; О; У.

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

Задача 6. Необязательная. Учитывая общее количество ед. кв., если разрезать этот многоугольник на 4 одинаковых многоугольника, то их площадь в любом случае будет по 4 ½ ед. кв.  Поэтому решением будет разрезание прямоугольника вертикальной линией на два квадрата площадью по 9 ед. кв., а затем каждый из них – на два треугольника по диагонали.

Задача 7.  Нахождение объединения и пересечения множеств. Ответов на каждый вопрос  задачи может быть несколько.

Задача 8. Необязательная. Вы, наверное, уже догадались, что задачи о сортировке объектов по правилу существенно проще, чем задачи о выяснении этого правила. Данная задача вообще относится к разряду наиболее сложных, для ее решения необходимы: наблюдательность, с одной стороны, и  умение рассуждать и делать выводы – с другой. Поэтому стоит предложить ее наиболее сильным детям и лучше сделать это до того, как они решат задачу 11. Итак, при первом же взгляде на последовательность Ф становится ясно – слова упорядочены не в словарном порядке, ведь слово АВТОГОНКИ стоит последним, а слово КЛАССИКИ – первым. Вообще, видно, что порядок слов в последовательности Ф не имеет никакого отношения к порядку первых букв. Придя к такому выводу, кто-то из детей поймет, что надо анализировать буквы не с начала слова, а с конца. Это главный шаг в решении данной задачи. Итак, видим, что последние (и предпоследние) буквы всех слов одинаковы, значит, их можно не рассматривать. Как видим, слова с третьей с конца буквой И идут в цепочке Ф раньше, чем с третьей с конца Л. Это мы запомним и посмотрим, как упорядочены первые слова цепочки Ф (которые оканчиваются на «ИКИ»). Видим, что слово «КЛАССИКИ»  – первое, а «УСИКИ»  –  второе. Становится ясно, что упорядочены слова по пятой букве с конца, ведь дальше все буквы одинаковы, а во втором слове всего 5 букв. Так, сравнивая соседние слова попарно, дети постепенно формулируют правило расстановки слов в порядке обратного словаря, которое полностью приводится в задаче 11.

Задача 9. Необязательная. Это тоже задача непростая. Для ее решения необходимы  наблюдательность и умение обобщать. Действительно,  предупреждающие знаки имеют треугольную форму и выполнены в красно-бело-черном сочетании цветов. Запрещающие знаки имеют круглую форму и выполнены в красно-бело-черном сочетании цветов. Предписывающие знаки имеют круглую форму и выполнены в бело-синем сочетании цветов. Этой информации вполне достаточно, чтобы выполнить данное задание. Однако задачу можно решать и совершенно формально. Тем детям, которые совсем не знают с чего начать, посоветуйте найти в учебнике остальные задачи со знаками дорожного движения – 7, 35, 84. Тех детей, которые при этом не увидели никаких закономерностей,  попросите найти знаки, данные в этой задаче, в соответствующих задачах и так распределить знаки по группам. Возможно, в процессе этой работы дети сделают выводы о различии форм и цветов, а может и нет, но ясно, что непосредственный поиск всех знаков займет у ребенка довольно много времени.

Задача 10. Это несложная и по содержанию знакомая детям задача. Ее отличие от задачи 1 лишь в том, что надо упорядочить не русские, а английские слова и пользоваться, соответственно, английским алфавитом.

Задача 11. Здесь дети знакомятся с новым правилом упорядочения слов. Конечно, поначалу оно покажется детям непривычным и странным, однако именно так упорядочивают слова в некоторых словарях. Поскольку правило упорядочения для детей будет незнакомым, очень важно внимательно прочитать его и разобраться в нем. Если вы видите, что кто-то из детей совсем запутался, сравните вместе два слова с помощью этого правила. Например, возьмем УДАРЕНИЕ и ПЛЕЧО. Сравним последние буквы этих слов – Е и О. Они разные, значит, раньше стоит то слово, последняя буква которого в алфавите идет раньше. В алфавите буква Е идет раньше, чем О, значит, слово УДАРЕНИЕ в последовательности будет идти раньше. Теперь возьмите слова КВАСОК и ЧАСОК. Последние буквы у них одинаковые, значит, сравниваем предпоследние буквы. Они тоже одинаковые, значит, сравниваем третьи с конца буквы. Они одинаковые, как и четвертые с конца буквы. Первые по счету с конца различные буквы – пятые. В слове КВАСОК – буква В, в слове ЧАСОК – буква Ч. Буква В идет в алфавите раньше Ч, значит, слово КВАСОК будет идти в последовательности раньше. В процессе этого разговора  у ребенка формируется понимание того, что можно снова разделить слова на группы, но только не по первой, а по последней букве, и часть слов расставить в последовательности сразу. Так, в наборе есть лишь одно слово с последней буквой «А» - ОБЕЗЬЯНКА, оно и будет первым. Дальше перебираем последние буквы слов, сверяя их с алфавитным порядком. Следующим в цепочке будет слово УДАРЕНИЕ, затем – ДУТЫЙ. Затем находим три слова с последней «К». Здесь придется сравнивать предпоследние буквы, третьи с конца и т.д. Оставшиеся слова можно сравнить по последней букве.

Ответ:

ОБЕЗЬЯНКА

УДАРЕНИЕ

ДУТЫЙ

БАСОК

КВАСОК

ЧАСОК

ПЛЕЧО

КУПЛЕТ

ВОЗДУХ