Забавление със сортирането
Този урок запознава учениците със сортирането, един от най -основните и фундаментални проблеми в компютърните науки. Учениците работят в екипи, за да открият алгоритми и да измислят начини за сортиране на числа.
- Наблюдавайте как може да има няколко начина за сортиране на числа и как някои начини са по -ефективни от други.
- Наблюдавайте как алгоритъмът е „процедура“ и не трябва да зависи от входа.
- Научете, че алгоритъмът трябва да бъде много ясен в инструкциите си.
Възрастови нива: 10-16
Строителни материали (за всеки екип)
Необходими материали
- Картон или строителна хартия
- 1 Голям маркер
- лента
- Големи пластмасови игрални блокове
- Големи картонени кутии
Design Challenge
Вие сте част от екип инженери, на които е дадено предизвикателството да сортира обекти в списък чрез задаване на конкретни въпроси, като например сравняване на два обекта по тяхната числова стойност.
Критерии
- Обектите със скрит номер ще формират списъка.
- Трябва да сортирате списъци, като зададете поредица от въпроси.
Ограничения
- Номерата са видими само за „контролера“.
- Разбийте класа на екипи от 3-5.
- Раздайте работния лист „Забавление със сортиране“, ако искате учениците да попълнят въпросите в работния лист. В противен случай можете да извършвате дейността без работния лист.
- Вижте раздела „Основни концепции“ за съвети и отстраняване на проблеми.
- Има основно сортиране и след това четири дейности. Дейности № 2 и № 3 трябва да бъдат завършени заедно. И, Дейност № 3 и № 4 трябва да бъдат завършени заедно. Очаква се всеки от тях да отнеме 90 минути.
- Прегледайте по -долу Основните инструкции за сортиране с класа и накарайте учениците да извършат основната дейност по сортиране.
Основни инструкции за сортиране:
● Стъпка 1: Учениците ще изберат 8 обекта, които да представят списъка за сортиране. Те могат да изберат всичко, което да представлява техния списък с числа. Някои идеи за списъка са: а. Големи пластмасови игрални блокове b. Големи картонени кутии
● Стъпка 2: Учениците избират един човек от екипа за „контролер“.
● Стъпка 3: Контролерът трябва да напише произволни числа на лист хартия и да ги залепи с обектите, така че да са скрити от другите ученици. Само контролерът трябва да може да ги вижда.
● Стъпка 4: Сега екипът ще се опита да сортира списъка във възходящ ред. За да направят това, учениците могат да направят следните три неща:
а. Попитайте контролера „Това число по -голямо ли е от това число?“ което позволява на учениците да сравняват всякакви две числа. Администраторът може да отговори само с да или не.
б. Помолете контролера да размени всички два обекта. След това контролерът ще размени обектите, като внимава да не разкрива числата върху тях.
° С. Помолете контролера да премести всеки обект в определена позиция, т.е. „Преместете този обект на трета позиция“ или „Преместете този обект между тези два обекта“.
● Стъпка 5: Контролерът ще отчита броя на зададените въпроси „да/не“. Учениците трябва да се опитат да сортират числата, като същевременно сведат броя на въпросите до минимум.
● Стъпка 6: След като учениците почувстват, че списъкът е сортиран, те ще помолят контролера да разкрие числата. Ако списъкът не е сортиран, тогава контролерът разбърква списъка и започва отначало. - Прегледайте дейност № 1 - Инструкции за сортиране на единично вмъкване по -долу с класа и накарайте учениците да направят сортиране за единично вмъкване.
Дейност #1 - Инструкции за сортиране на единично вмъкване:
● Стъпка 1: Използвайки блокове или кутии, настройте първоначалния списък, както следва: едно от числата трябва да бъде отделено, а останалите да бъдат предварително подредени във възходящ ред. След това отделеният номер трябва да бъде поставен в единия край на сортираната част от списъка. Екипът не трябва да вижда числата, но трябва да знае, че целият списък е сортиран, с изключение на едно число в края, което не е на място.
● Стъпка 2: След това учениците трябва да следват инструкциите в Стъпка #4, описани в Основното сортиране по -горе, и да се опитат да сортират напълно списъка. Това се нарича единично вмъкване и помага като основен градивен елемент за други алгоритми за сортиране като сортиране на вмъкване.
● Стъпка 3: Обяснете на учениците, че ако могат да видят числата, би било очевидно, че те могат просто да поставят 4 между 3 и 5 и списъкът ще бъде напълно сортиран. Това обаче не е начинът, по който работят компютрите. Следователно учениците трябва да започнат със сравняване на числата и след това да поръчват суапове и/или ходове. В този случай учениците знаят, че целият списък е във възходящ ред, с изключение на последния номер. Учениците естествено трябва да осъзнаят, че просто трябва да идентифицират позицията, в която да вмъкнат последното неподредено число. ВМЕСТИТЕ 6 ПРИМЕРНИ ИЗОБРАЖЕНИЯ ТУК
Горната последователност от диаграми показва какво в идеалния случай трябва да се случи в класната стая. По време на дейността учениците не са наясно с числата в списъка и просто дават набор от инструкции на контролера за сравняване на числата.
Тази дейност запознава учениците с концепцията за итерация. Итерацията е стъпка в процеса на инженерно проектиране. Учениците трябва да повтарят отново и отново, за да сортират правилно числата. - Прегледайте дейност № 2 - Инструкции за сортиране на вмъкване по -долу с класа и накарайте учениците да направят сортиране за вмъкване.
Дейност #2 - Инструкции за сортиране на вмъкване:
● Стъпка #1: С помощта на блокове или кутии подредете списъка на случаен принцип.
● Стъпка #2: Учениците сега трябва да се опитат да го сортират, използвайки предишните си познания за единично вмъкване.
● Стъпка #3: Учениците трябва да разбият проблема на поредица от единични вмъквания. Самотен номер сам по себе си е сортиран списък. Например, можем да кажем, че единичното число в крайния ляв ъгъл на произволно подредения списък е сортиран списък.
● Стъпка #4: Сега учениците трябва да разгледат този сортиран списък с 1 елемент и да направят сортиране за вмъкване, третиращо втория елемент като номер на място в единичното вмъкване.
● Стъпка #4: След като приключат, учениците вече имат сортиран списък с 2 елемента. След това процедурата се повтаря, третирайки третия елемент като номер на място, така че да получим сортиран списък от 3 елемента.
● Стъпка #5: Учениците продължават да повтарят тази последователност от единични вмъквания, докато накрая получат целия сортиран списък. Следващата последователност от диаграми показва какво учениците трябва да опитат в идеалния случай. Забележете как жълтото поле, което обозначава сортираната част от списъка, расте с течение на времето. Обърнете внимание, че единичното вмъкване се извършва многократно, като се използва жълтата част на списъка като сортиран списък, а следващият елемент вдясно като номер на място. Процедурата в крайна сметка ще сортира целия списък!
ВМЕСТИТЕ 10 ПРИМЕРНИ ИЗОБРАЖЕНИЯ ТУК - Прегледайте дейност № 3-Инструкции за сортиране на два списъка по-долу с класа и накарайте учениците да направят сортиране за обединяване на два списъка.
Дейност #3-Инструкции за сортиране на обединяване в два списъка:
● Стъпка #1: Настройте първоначалния списък, както следва: Разделете 8 -те обекта на 2 списъка по 4 обекта, като двата списъка трябва да бъдат сортирани независимо.
● Стъпка 2: След това списъците трябва да се поставят един до друг и учениците сега трябва да се опитат да „обединят“ двата сортирани списъка в един сортиран списък, като следват инструкциите от Основното сортиране.
● Стъпка #3: Това сортиране е полезна отправна точка и градивен елемент за по -сложен алгоритъм: Сортиране за сливане. Това също изисква учениците да си припомнят и използват повторно знанията си за единично вмъкване.
● Стъпка #4: Списъкът вляво е сортиран, така че можете да третирате 5-то число като номер на място и да го сортирате в левия списък. Има обаче нещо, което учениците трябва да открият сами. Те трябва да се възползват от факта, че списъкът вдясно също е сортиран, така че следващото число, което трябва да бъде вмъкнато, винаги е по -голямо от последното вмъкнато число.
● Стъпка #5: Когато учениците искат да обединят втория елемент от десния списък в левия списък, те не трябва да изпълняват повторно единично вмъкване от крайния ляв край, а просто започват от точката, в която са вмъкнали последния елемент.
ВМЕСТЕТЕ 3 ПРИМЕРНИ ИЗОБРАЖЕНИЯ ТУК Обърнете внимание, че в горната стъпка не започвате въпросите отначало от жълтия списък, което е направено в Сортиране на вмъкване. Това е така, защото знаем, че следващото число, което трябва да бъде вмъкнато в жълтия списък, вече е по -голямо от последното, тъй като розовият списък вече е сортиран. - Прегледайте дейност № 4 - Обединете инструкциите за сортиране по -долу с класа и накарайте учениците да направят сортиране за вмъкване.
Дейност #4 - Инструкции за сортиране на обединяване:
● Стъпка #1: Настройте списъка на случаен принцип. Учениците трябва да се опитат да сортират списъка, като използват предишните си познания за сливане на два листа.
● Стъпка 2: Основната идея зад Merge Sort е принципът на разделяй и владей. Това е една от основните концепции зад всеки съвременен сложен алгоритъм за сортиране. Учениците ще трябва да разглеждат всеки номер като отделен сортиран списък с размер 1.
● Стъпка #3: Оттам учениците ще се опитат да извършат известното сливане на два списъка в списъците. На пръв поглед обаче това, което учениците ще опитат, няма да се различава много от Insertion Sort. Те първо ще обединят две числа, а след това трето, а след това четвърто и т.н. Това по същество е сортиране на вмъкване.
● Стъпка #4: Трикът за обединяване на сортиране е следният:
○ От рандомизирания списък третирайте всеки номер като сортиран списък с размер 1.
○ След това оформете двойки съседни списъци и ги обединете, така че сега имаме 4 сортирани списъка, всеки с размер 2.
○ След това отново оформете двойки списъци и ги обединете, за да получите 2 списъка, всеки с размер 4.
○ Едно последно сливане и получаваме пълен сортиран списък с размер 8. Този подход гарантира, че итерациите за всеки отделен номер са сведени до минимум, така че броят на зададените въпроси „да/не“ също е сведен до минимум. - За повече съдържание по темата вижте раздела „Копаене по -дълбоко“.
Модификация на времето
Урокът може да бъде направен само за 1 клас за по -големите ученици. Въпреки това, за да помогнете на учениците да не се чувстват прибързани и да осигурят успех на учениците (особено за по -малките ученици), разделете урока на два периода, като дадете на учениците повече време за мозъчна атака, тестване на идеи и финализиране на техния дизайн. Проведете тестването и разбора през следващия учебен период.
Съвети и отстраняване на неизправности
По време на упражненията на учениците трябва да се дава всяка възможност да измислят отговорите сами. Целта на играта е учениците да „поиграят“ с проблема и сами да видят кое работи и кое не. Тази форма на учене, основано на открития, е изключително ефективна при развиването на познавателните умения и умения за решаване на проблеми на високо ниво. Дискусиите сред учениците също трябва да се насърчават.
Рисуването на картини и диаграми може да бъде много ефективно при съобщаването на тази конкретна тема на учениците. Графиките, предоставени в раздела с инструкции за дейност, могат да се използват като ръководство за това как да нарисувате различните стъпки. Учениците също могат да бъдат насърчавани да рисуват диаграми, изобразяващи предложените им алгоритми и решения.
Ако студентите изпитват затруднения при започване, ето няколко съвета как да насочите учениците към правилния път:
- Насърчете учениците да обсъдят задачата. По -често учениците по невнимание сами ще измислят решения, когато „мислят на глас“ и обсъждат проблема и/или неговото решение с връстниците си.
- Започнете дискусията бързо, като попитате учениците за техните гледни точки и насърчете учениците с различни гледни точки да се включат в активни дискусии.
- Предложете потенциално решение и попитайте учениците какво мислят, че би се случило, ако се опита. Такъв въпрос най -вероятно ще предизвика нов мисловен процес в съзнанието на учениците и ще им помогне да видят къде са се отклонили от релсите. Самият въпрос може да се отнася до това, което класът вече обсъжда, или може да е изцяло нова, но не непременно правилна мисъл. Целта не е да се даде правилен отговор, а да се насърчат учениците да оценят възможните решения и да мислят и разсъждават сами.
Използвайте ефективно междуотборните състезания ефективно. Опитайте се да установите връзка между броя на зададените въпроси и времето, необходимо за сортиране на списъка, и дали е имало връзка между спечелването и задаването на по -малко въпроси.
Интернет връзки
Препоръчителна четене
- Изкуство на компютърното програмиране, том 3 от Доналд Е. Кнут (ISBN: 0321751043)
Писателска дейност
Компютрите обикновено харчат около една четвърт от своята процесорна мощ за сортиране на различни данни. Като пример компютър в болница може да поддържа много голяма база данни за всички пациенти, които някога са били на лечение в болницата през последните 5 години. Различните хора в болницата може да искат различни списъци с пациенти. Човек, управляващ болничните финанси, може да иска списък с пациенти, подредени според техните болнични такси. Изследователят може да иска списък, подреден по болестта, за която е лекуван. Администраторът може да иска списък, поръчан от лекаря, който лекува пациента. Докато генерира тези списъци, компютърът ще трябва да сортира данните отново всеки път според нуждите на потребителя. Можете ли да се сетите за друг сценарий, при който сортирането е важно? Какви предимства има поддържането на сортирани данни пред несортирани данни? Какви са възможните недостатъци?
Привеждане в съответствие с учебните програми
Забележка: Плановете за уроци от тази поредица са съобразени с един или повече от следните набори от стандарти:
- Стандарти за научно образование в САЩ (http://www.nap.edu/catalog.php?record_id=4962)
- Научни стандарти на САЩ от следващо поколение (http://www.nextgenscience.org/)
- Стандарти на Международната асоциация по технологично образование за технологична грамотност (http://www.iteea.org/TAA/PDFs/xstnd.pdf)
- Принципите и стандартите за училищна математика на Националния съвет на учителите по математика на САЩ (http://www.nctm.org/standards/content.aspx?id=16909)
- Американски общи основни държавни стандарти за математика (http://www.corestandards.org/Math)
- Асоциация на учителите по компютърни науки K-12 Стандарти за компютърни науки (http://csta.acm.org/Curriculum/sub/K12Standards.html)
Национални стандарти за научно образование К-4 клас (на възраст 4-9)
СЪДЪРЖАНИЕ СТАНДАРТ А: Науката като запитване
В резултат на дейностите всички ученици трябва да се развиват
- Способности, необходими за извършване на научни изследвания
СЪДЪРЖАНИЕ СТАНДАРТ Б: Физически науки
В резултат на дейностите всички ученици трябва да развият разбиране за
- Свойства на предмети и материали
СЪДЪРЖАНИЕ СТАНДАРТ Д: Наука и технологии
В резултат на дейностите всички ученици трябва да се развиват
- Способности за технологичен дизайн
- Разбиране за науката и технологиите
СЪДЪРЖАНИЕ СТАНДАРТ F: Наука в лична и социална перспектива
В резултат на дейностите всички ученици трябва да развият разбиране за
- Видове ресурси
- Наука и технологии в местните предизвикателства
СЪДЪРЖАНИЕ СТАНДАРТ G: История и природа на науката
В резултат на дейностите всички ученици трябва да развият разбиране за
- Науката като човешко начинание
Национални стандарти за научно образование 5-8 клас (на възраст 10-14)
СЪДЪРЖАНИЕ СТАНДАРТ А: Науката като запитване
В резултат на дейностите всички ученици трябва да се развиват
- Способности, необходими за извършване на научни изследвания
- Разбиране за научното изследване
СЪДЪРЖАНИЕ СТАНДАРТ Б: Физически науки
В резултат на своите дейности всички ученици трябва да развият разбиране за
- Свойства и промени на свойствата в материята
СЪДЪРЖАНИЕ СТАНДАРТ Д: Наука и технологии
В резултат на дейности в 5-8 клас всички ученици трябва да се развиват
- Способности за технологичен дизайн
- Разбиране за науката и технологиите
Национални стандарти за научно образование 5-8 клас (на възраст 10-14) (продължение)
СЪДЪРЖАНИЕ СТАНДАРТ F: Наука в лична и социална перспектива
В резултат на дейностите всички ученици трябва да развият разбиране за
- Рискове и ползи
- Наука и технологии в обществото
Принципи и стандарти за училищна математика (на възраст 6 - 18)
Измерване
- разбират измеримите атрибути на обектите и мерните единици, системи и процеси.
- прилагат подходящи техники, инструменти и формули за определяне на измерванията.
Решаване на проблеми
- изграждане на нови математически знания чрез решаване на проблеми.
- решаване на проблеми, които възникват в математиката и в други контексти.
- прилагат и адаптират различни подходящи стратегии за решаване на проблеми.
- наблюдавайте и обмисляйте процеса на решаване на математически проблеми.
Връзки
- разпознават и прилагат математиката в контексти извън математиката.
Представителство
- създаване и използване на представи за организиране, записване и предаване на математически идеи.
- избирайте, прилагайте и превеждайте между математически представи за решаване на проблеми.
Стандарти за технологична грамотност - всички възрасти
Природата на технологиите
- Стандарт 1: Студентите ще развият разбиране за характеристиките и обхвата на технологията.
- Стандарт 3: Студентите ще развият разбиране за връзките между технологиите и връзките между технологиите и други области на обучение.
Технология и общество
- Стандарт 4: Студентите ще развият разбиране за културните, социалните, икономическите и политическите ефекти на технологиите.
- Стандарт 6: Учениците ще развият разбиране за ролята на обществото в развитието и използването на технологиите.
Дизайн
- Стандарт 9: Студентите ще развият разбиране за инженерния дизайн.
Стандарти за технологична грамотност - всички възрасти (продължение)
Способности за един технологичен свят
- Стандарт 13: Учениците ще развият способности за оценка на въздействието на продуктите и системите.
Проектираният свят
- Стандарт 14: Студентите ще развият разбиране и ще могат да избират и използват медицински технологии.
- Стандарт 19: Студентите ще развият разбиране и ще могат да избират и използват производствени технологии.
Сесия 1 - Сортиране на вмъкване
Това е групово упражнение. Преди да започнете, моля, сформирайте група от 3-5 ученици.
Единично вмъкване
Начертайте 8 карти, всяка с различен номер. Нека един ученик от вашата група да бъде контролер, а другите трябва да играят заедно. Само контролерът има право да вижда номерата.
Контролерът трябва да настрои картите за единично вмъкване, а другите трябва да играят, за да сортират списъка. Направете това поне 5 пъти и попълнете таблицата по -долу.
Кръгъл | Брой зададени да/не въпроси | Какъв беше неуместният номер? |
1 | ||
2 | ||
3 | ||
4 | ||
5 |
Въз основа на информацията, която сте въвели по -горе, отговорете на следните въпроси:
- Какъв е средният брой въпроси, зададени в един кръг?
______________________
- Да предположим, че трябва да попълните горната таблица за 5000 единични вмъквания. Коя според вас би била възможно най -голямата стойност във втората колона (Броят на зададените въпроси за да/не)?
______________________
- Да предположим, че сте работили със списък от 10 числа вместо 8. Какъв би бил вашият отговор на въпрос 2 в този случай?
______________________
- Можете ли сега да свържете размера на списъка с броя на зададените въпроси в най -лошия случай? Дайте много кратък отговор за това как мислите размера на списъка и въпросите, зададени в най -лошия случай (Не забравяйте, че колкото по -малък е броят на въпросите, толкова по -добре. Така че, когато казваме „най -лошия случай“, имаме предвид възможно най -големия брой на зададените въпроси)
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
Сортиране по вмъкване
Сега, със същите тези карти, играйте играта Сортиране на вмъкване. Не забравяйте да започнете с напълно случаен списък.
Направете Insertion Sort поне 5 пъти и попълнете таблицата по -долу. Контролерът трябва да води запис на третата колона, преди да започне сортирането, и да я разкрие, след като списъкът е сортиран.
Кръгъл | Брой зададени да/не въпроси | Какъв беше началният списък? |
1 | ||
2 | ||
3 | ||
4 | ||
5 |
Въз основа на информацията, която сте въвели по -горе, отговорете на следните въпроси:
- Какъв е средният брой въпроси, зададени в един кръг?
______________________
- Сигурно сте осъзнали, че сортирането на вмъкване е само поредица от единични вмъквания. Дайте много кратък отговор за това как бихте свързали броя на единичните вмъквания с размера на списъка за сортиране.
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
- Запомнете отговора си на въпрос 2 от упражнението за единично вмъкване. Използвайте този отговор, за да изчислите броя на въпросите, които ще трябва да зададете в Сортиране на вмъкване в „най -лошия случай“. Покажете стъпките си.
Окончателен отговор: __________________
- Срещнете се с друга група в мач за сортиране, за да видите кой може да сортира по-бързо произволен списък. В интерес на справедливостта ще има по един контролер от всеки екип. Правилата на играта трябва да се спазват стриктно, но можете да използвате всяка процедура, която искате.
Брой въпроси, които сте задали: _______________________
Брой въпроси, които опонентът ви е задал: _______________________
Спечели ли? _______________________
Сесия 2 - Сортиране на обединяване
Това е групово упражнение. Преди да започнете, моля, сформирайте група от 3-5 ученици.
Обединяване с два списъка
Начертайте 8 карти, всяка с различен номер. Нека един ученик от вашата група да бъде контролер, а другите трябва да играят заедно. Само контролерът има право да вижда номерата.
Контролерът трябва да настрои картите за сливане с два списъка, а другите трябва да играят, за да сортират списъка. Направете това поне 5 пъти и попълнете таблицата по -долу.
Кръгъл | Брой зададени да/не въпроси | Какъв беше началният списък? |
1 | ||
2 | ||
3 | ||
4 | ||
5 |
Въз основа на информацията, която сте въвели по -горе, отговорете на следните въпроси:
- Какъв е средният брой въпроси, зададени в един кръг?
______________________
- Да предположим, че трябва да попълните горната таблица за 5000 сливания с два списъка. Коя според вас би била възможно най -голямата стойност във втората колона (Броят на зададените въпроси с да/не)?
______________________
- Да предположим, че сте работили със списък от 10 числа вместо 8. Какъв би бил вашият отговор на въпрос 2 в този случай?
______________________
- Сега се върнете и вижте отговорите, които сте дали за упражнението за единично вмъкване. Какви прилики виждате? Какви разлики? Как се различават числата? Различават ли се малко или много? Запишете вашите мисли по този въпрос.
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
Сливане на сортиране
Сега, със същите тези карти, играйте играта Merge Sort. Не забравяйте да започнете с напълно случаен списък.
Направете Merge Sort поне 5 пъти и попълнете таблицата по -долу. Контролерът трябва да води запис на третата колона, преди да започне сортирането, и да я разкрие, след като списъкът е сортиран.
Кръгъл | Брой зададени да/не въпроси | Какъв беше началният списък? |
1 | ||
2 | ||
3 | ||
4 | ||
5 |
Въз основа на информацията, която сте въвели по -горе, отговорете на следните въпроси:
- Какъв е средният брой въпроси, зададени в един кръг?
______________________
- Сигурно сте осъзнали, че Merge Sort е само поредица от сливания с два списъка. Колко сливания с два списъка сте направили, за да обедините Сортирайте списъка с 8 номера?
______________________
- Запомнете отговора си на Въпрос 2 от упражнението Обединяване на два списъка. Използвайте този отговор, за да изчислите броя на въпросите, които ще трябва да зададете в Merge Sort в „най -лошия случай“. Покажете стъпките си.
Окончателен отговор: __________________
- Срещнете се с друга група в мач за сортиране, за да видите кой може да сортира по-бързо произволен списък. В интерес на справедливостта ще има по един контролер от всеки екип. Правилата на играта трябва да се спазват стриктно, но можете да използвате всяка процедура, която искате.
Брой въпроси, които сте задали: _______________________
Брой въпроси, които опонентът ви е задал: _______________________
Спечели ли? _______________________