Сложеност - једноставно је

Грађевински материјали

Потребни материјали

• Картон за израду нумерисаних карата или неколико шпилова карата за играње (3 по ученику)
• Наградни предмети: Пиринач, мали слаткиши или други јефтини предмети. Узимајући као пример пиринач, потребно је око 25 кашика (ово је нешто мање од 400 г)

Припрема

Направите картице од картона или папира и нумеришите их редом почевши од 1. Потребне су три картице по ученику. Алтернативно се могу користити два или три шпила карата за игру, али се редослед карата мора објаснити ученицима.

Дизајн изазов

Ви сте инжењер који има изазов да анализира, развија и извршава алгоритме помоћу игара.

1. Поделите радни лист Цомплекити Ит'с Симпле. Разумевање странице „Раст секвенци“ од виталног је значаја за остатак лекције. Тестирајте разумевање материјала. Решење је приказано испод:
   

   Решење
   

   Локвањи 9 недеља. С обзиром да се број љиљана сваке недеље удвостручује, ако је у 9. недељи језеро преполовљено, потпуно се покрије након 10 недеља. Пример за шест недеља дат је у ресурсима за наставнике „Лопочи“.

   Раст низа који описује обухваћену површину је експоненцијалан.

   Колико могу да понесу?

   2Д површине расту квадратно са дужином страница, док 3Д ставке могу да расту кубично (тј. До моћи три). Стога је тежина коју костур може носити пропорционална под претпоставком да све стране линеарно расту, а кубни низ расте брже од квадратног.

   Повећање висине животиње може се постићи само стварањем костура те животиње од материјала који је тврђи и јачи него за мање животиње, или повећањем величине костију животиње. Због мале тежине мрава, његов костур (и мишићи) су довољно јаки да носе десет до педесет пута већу тежину од сопствене тежине, док то исто не важи за људе. Размислите о тежини зграде коју подупире стуб. Ако су горњи спратови претешки за камени стуб, он почиње да пуца и да се руши. За једноличан материјал, тежина коју може носити пропорционална је површини попречног пресека. Дакле, ако удвостручите све димензије зграде, његова тежина се повећава за 8 пута, капацитет стубова ће се повећати само четири пута.

   Ово се такође може илустровати разматрањем миша који пада низ окно лифта. Због своје мале тежине може преживјети, док веће животиње не би. (Пример према ТВ Корнер, Тхе Плеасурес оф Цоунтинг, Цамбридге Университи Пресс, 1996)

   Довршите секвенце

   Низови се настављају на следећи начин, са одговарајућим функцијама раста датим у загради:

   • 2, 2, 2, 2, 2, 2 (2)
   • 3, 6, 9, 12, 15, 18, 21 (3 кн)
   • 4, 9, 16, 25, 36, 49 ((н + 1) 2)
   • КСНУМКС, КСНУМКС, КСНУМКС, КСНУМКС, КСНУМКС, КСНУМКС, КСНУМКС
   • КСНУМКС, КСНУМКС, КСНУМКС, КСНУМКС, КСНУМКС, КСНУМКС, КСНУМКС

   Први низ расте споро (његова функција раста је само константа), док трећи низ расте најбрже (његова функција раста је квадратна). Четврта секвенца такође има функцију квадратног раста и стога расте истом брзином, али ће њене појединачне ставке увек бити ниже од оних у трећој секвенци.

    

   

2. Упознајте ученике са предметом играјући са њима Наградну игру, која је описана у ресурсима за наставнике „Групне игре“. Игра се састоји у томе што ученицима даје награде у облику малих предмета. Игра је овде објашњена са пиринчем као примером, али ради једнако добро и за друге мале награде. Пиринач се даје у рундама. Циљ игре је да се добије што је могуће више пиринча. Количина пиринча која се даје у свакој рунди одређена је једном од две стратегије награђивања:
   Опција КСНУМКС: Сваке рунде делиће се кашичица пиринча.
   Опција КСНУМКС: У првом кругу награда је само једно зрно пиринча. Затим се у сваком наредном кругу количина изданог пиринча удвостручи.
   • Нека сваки ученик изабере једну од стратегија награђивања и групише ученике према избору који су направили.
   • Свакој групи поделите награде круг по круг. Могли бисте именовати ученика у свакој групи који ће вам помоћи да избројите пиринач. Имајте на уму да пред крај тачан број зрна није важан.
   • Након прва четири круга, замолите ученике да упореде кумулативну награду. Учините исто након осам и дванаест рунди. Затим разговарајте са ученицима о исходу игре.
   • Студенти треба да интуитивно разумеју различите стопе раста. Ово се такође може повезати са повећањем рачунарске моћи савремених микропроцесора. Према Моореовом закону, број транзистора који се могу ставити на чип се удвостручује отприлике сваке две године. Од ученика се може тражити да размисле о последицама овог запажања и да ли је могуће да се овај раст настави много дуже.
3. Играјте игру погађања бројева објашњену у ресурсима за наставнике „Групне игре“. Рјешење за ово је приказано у наставку. Циљ игре је погодити број са што мање покушаја. Игра се прво игра са целим одељењем, а затим ће се ученици поделити у парове да истраже сопствене стратегије решавања игре. Реците ученицима да устану. Помислите на број између 1 и 50 и немојте то рећи ученицима. Сада им је дозвољено да постављају само питања попут „Је ли 37?“ или "Је ли 20?" и можете одговорити само са „да“ или „не“ док не пронађу тачан број. Ученик који постави питање које доводи до одговора „не“ мораће да седне и можда неће постављати више питања док се игра не заврши. Имајте на уму да сви ученици могу седети пре него што се игра заврши. У овом случају можете одлучити поново играти игру и разговарати о томе зашто није успјела те да је за ову врсту питања у најгорем случају потребно 50 покушаја.
   
   Метода прелома Оптимална стратегија за приступ игри погађања бројева је метода бисекције: Започните питањем "Је ли (строго) веће од 50?" Ако је одговор „да“, наставите са „Да ли је веће од 75?“, Ако не, питајте „Да ли је веће од 25?“ Наставите на овај начин увек тражећи средњи број док не остане само једна опција. На пример:
   • (Број је 54)
   • Да ли је већи од 50? да
   • Да ли је већи од 75? Не
   • Да ли је већи од 63? Не
   • Да ли је већи од 57? Не
   • Да ли је већи од 54? Не
   • Да ли је већи од 52? да
   • Да ли је већи од 53? да

   Дакле, након 7 питања јасно је да број мора бити 54. (Постоје случајеви у којима је потребно само 6 питања. У ствари, просечан број питања је лог 100 = 6.64.)

   Ово је оптимална метода јер се при сваком питању скуп могућих бројева дели на два приближно једнака дела, при чему један садржи тражени број. Заправо, за овај проблем је оптимална свака метода која преполовљује могуће бројеве по питању. Друго решење би било постављање питања попут „Да ли је број дељив са 2?“

   Опционално: Пронађите сложеност

   Сложеност методе бисекције је логаритамска, односно реда О (лог Н). То је посљедица преполовљења могућих бројева при сваком питању. Ако су дозвољени сви цели бројеви, онда ниједан метод не може решити проблем у коначном времену.

4. Упознајте ученике са алгоритмима за сортирање пратећи упутства на ученичком радном листу „Алгоритми сортирања“, тј. Поделите картице и уврстите ученике у предложене величине група. Решење се појављује испод:
   

   Решење

   Буббле Сорт Ако шпил није сортиран, бит ће најмање двије узастопне карте које нису у исправном редослиједу. Алгоритам ће на крају заменити ове две картице. Стога, ако нема више картица за замену, алгоритам се завршава и шпил се сортира. Сортирање мехурића има предност што је врло једноставно за имплементацију, али није тако ефикасно као напреднији алгоритми за сортирање, попут сортирања спајањем (види испод). Сложеност времена извођења сортирања облачића за н картица је квадратна или О (н2).Алгоритми бржег сортирања

   Иако је сложеност сортирања мехурића у времену извођења квадратна, постоје боље методе. На пример, сортирање спајањем има сложеност времена извођења О (н лог н) за н картица. Занимљива карактеристика сортирања спајањем је та што његова структура омогућава да се паралелизује. Још један алгоритам са сложеношћу времена извођења О (н лог н) који се често користи у увежбавању брзог сортирања. Генерално ради добро иако је сложеност времена извођења квадратна и самим тим лошија од оне код спајања. Такође је уобичајено користити хибридне верзије различитих алгоритама за сортирање за прилагођавање специфичним проблемима. За извођење ових резултата видети ТХ Цормен ет ал., Увод у алгоритме.

   За сортирање засновано на упоређивању појединачних ставки не постоји метода са сложеношћу у најгорем случају која је боља од О (н лог н) која не експлоатише паралелне операције, попут спајања различитих хрпа карата у исто време. То је зато што се н картица може наручити на нн различите начине, а свако поређење може преполовити број могућих наруџби, што доводи до сложености О (лог (нн)) = О (н лог н).

5. Опционално: Нека ученици прочитају ученичке изворе „Алгоритми“ у одељку „Позадински концепти“ да би упознали терминологију која се користи у рачунарству.
6. За више садржаја о теми, погледајте одељак „Дубље копање“.

Напредне опције

Напредни ученици могу написати упоредни есеј о различитим методама сортирања и критеријумима објашњења за преферирање једне методе над другом. Од напредних ученика се може тражити да изнесу аргументе о рачунској сложености разматраних алгоритама и зашто су перформансе алгоритама за поређење поређења фундаментално ограничене.

Лекција се може изводити за само 1 час за старије ученике. Међутим, да бисте ученицима помогли да се осећају пожуривано и да би им осигурали успех (посебно за млађе ученике), поделите наставу на два периода дајући ученицима више времена за мозгање, тестирање идеја и дораду њиховог дизајна. Спроведите тестирање и извештавање у наредном периоду наставе.

Шта је Алгоритам?

Рачунар се може користити за извршавање мноштва задатака који нам могу помоћи у раду. Понекад је ове задатке лако описати речима, попут „сортирај овај шпил карата“ или „пронађи најбржи пут од Париза до Њујорка“. Међутим, за рачунар ове задатке може бити веома тешко решити. Интерно, рачунар може само да ради боље примитивне операције и само њихов правилан распоред решава проблем. Такав аранжман назива се ан алгоритам. Пошто свака примитивна операција траје неко време (неколико наносекунди у савременом рачунару), алгоритам захтева одређену вредност време трајања како би завршио свој задатак.

Зашто су неки алгоритми бољи од других?

Сваки задатак захтева посебно осмишљен алгоритам који га може решити. Сортирање скупа картица не може се извршити помоћу алгоритма који је дизајниран да пронађе најкраћи пут између два града. Такође, прилично интуитивно, сортирање шпила од 200 карата траје дуже од сортирања само 52 карте (или у тривијалном случају, 2 карте). Стога време извођења зависи од проблема и његове величине (информатичари говоре о инстанца проблема).

Алгоритме треба упоређивати независно од инстанце проблема (иначе би најбољи алгоритам увек био да се одмах одмах да одговор који је претходно израчунат.) Овде је концепт раста низа користан: Величина проблема се може узети у обзир као параметар н у низу који је специфичан за алгоритам. Стога постоје различити алгоритми сложеност, што одговара низу који их описује. Алгоритми се затим упоређују поређењем раста секвенци. Стога је алгоритам квадратне сложености бољи од алгоритма експоненцијалне сложености.

Сложеност - корисно је

Ефикасност алгоритама је кључна за мноштво тренутних рачунарских апликација. Неке проблеме је тешко решити јер једини познати алгоритми који их решавају имају велику сложеност.

Опште познат пример велике сложености је проблем трговачког путника (ТСП). У овом проблему, трговац жели да послује у низу градова. Жели пронаћи најкраћи могући пут између ових градова, а да не посети ниједан град више пута, и жели да се врати у свој почетни град на крају свог итинерера. Ефикасно решавање овог проблема било би веома корисно за додељивање рута авионима, заказивање задатака на машинама, па чак и за производњу микропроцесора.

Иако сложеност ТСП -а спречава ефикасно решавање ових проблема, за неке апликације велика сложеност може чак бити пожељна. Када се шаље шифрована порука, требало би бити јако тешко доћи до пренете информације, а да се не зна нека заједничка тајна. У овом случају, шифровање је дизајнирано на такав начин да дешифровање има веома велику сложеност и на тај начин се спречава прислушкивање. Сигурна комуникација не би била могућа без велике сложености дешифровања. Ови примјери и бројни други показују да је познавање сложености проблема врло корисно за рачунање и шире.

Интернет Цоннецтионс

• Комплексни зоолошки врт: (хттпс://цомплекитизоо.уватерлоо.ца/Цомплекити_Зоо#стхасх.1Гнн1Е1З.дпуф)
• П вс НП Проблем
• Моореов закон
• Algorithm Analysis: (http://www.londoninternational.ac.uk/sites/default/files/computingsamples/co2226_vol2_ch1.pdf#sthash.1Gnn1E1Z.dpuf)
• ИТЕА стандарди за технолошку писменост
• Национални стандарди научног образовања: (хттп://ввв.нста.орг/публицатионс/нсес.аспк)
• Скалирање

Рецоммендед Реадинг

• Раст низова и алгоритми за сортирање: Увод у алгоритме ТХ Цормен ет ал. (ИСБН: 0070131511)
• Димензиона анализа: ужитци бројања, ТВ Корнер (ИСБН: 0521568234)

Писање активности

Упоредите различите методе сортирања и објасните зашто бисте радије једни над другима. Напишите кратак текст о важности рачунске сложености у криптографији.

Усклађивање са оквирним програмима

Белешка: Планови лекција у овој серији усклађени су са једним или више следећих скупова стандарда:

• С. Стандарди научног образовања (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)
• Удружење наставника информатике К-12 Стандарди рачунарске науке (http://csta.acm.org/Curriculum/sub/K12Standards.html)

Принципи и стандарди за школску математику

Алгебра Стандард

Као резултат активности, сви ученици би требало да се развијају

• Разумети обрасце, односе и функције.
• Користите математичке моделе за представљање и разумевање квантитативних односа.

Стандард за решавање проблема

Као резултат активности, сви ученици би требало да се развијају

• Примените и прилагодите низ одговарајућих стратегија за решавање проблема.
• Пратите и размишљајте о процесу решавања математичких проблема.

Заједнички основни државни стандарди за математику од 9 до 12 разреда (од 14 до 18 година)

Алгебра Стандард

• Образложење једначинама и неједнакостима
• Решите једначине и неједначине у једној променљивој
• Матх.Цонтент.ХСА-РЕИ.Б.3Решите линеарне једначине и неједначине у једној променљивој, укључујући једначине са коефицијентима представљеним словима.

Функције стандард

• Функције зграде
• Изградите функцију која моделира однос између две величине
• Матх.Цонтент.ХСФ-БФ.А.2Напишите аритметичке и геометријске секвенце и рекурзивно и са експлицитном формулом, користите их за моделирање ситуација и преводите између два облика.
• Линеарни, квадратни и експоненцијални модели
• Конструишите и упоредите линеарне, квадратне и експоненцијалне моделе и решите проблеме
• Матх.Цонтент.ХСФ-ЛЕ.А.1Разликовати ситуације које се могу моделовати линеарним функцијама и експоненцијалним функцијама.
• Матх.Цонтент.ХСФ-ЛЕ.А.1цПрепознајте ситуације у којима количина расте или пропада константном процентуалном стопом по интервалу јединице у односу на другу.

 Стандарди за технолошку писменост - сва доба

         Природа технологије

• Стандард 1: Студенти ће развити разумевање карактеристика и домета технологије.
• Стандард 2: Студенти ће развити разумевање основних концепата технологије.
• Стандард 3: Студенти ће развити разумевање односа између технологија и веза између технологије и других поља студија.

Дизајнирани свет

• Стандард 17: Студенти ће развити разумевање и моћи ће да бирају и користе информационе и комуникационе технологије.

ЦСТА К-12 Стандарди рачунарске науке, разреди 6-9 (узраст 11-14)

5. 2 Ниво 2: Рачунарске науке и заједница (Л2)

• Рачунарско размишљање (ЦТ)

3. Дефинишите алгоритам као низ упутстава које рачунар може да обради.
4. Процените начине на које се различити алгоритми могу користити за решавање истог проблема.
5. Одглумите алгоритме претраживања и сортирања.
6. Користите визуелне приказе стања проблема, структура и података (нпр. Графиконе, графиконе, мрежне дијаграме, дијаграме тока).
7. Интеракција са моделима и симулацијама специфичним за садржај (нпр. Екосистеми, епидемије, молекуларна динамика) ради подршке учењу и истраживању.

• Сарадња (ЦЛ)

3. Сарађујте са вршњацима, стручњацима и другима користећи заједничке праксе попут програмирања у пару, рада у пројектним тимовима и учешћа у активностима групног активног учења.
4. Изложите диспозиције неопходне за сарадњу: пружање корисних повратних информација, интегрисање повратних информација, разумевање и прихватање вишеструких перспектива, социјализација.

• Рачунарска пракса и програмирање (ЦПП)

4. Показати разумевање алгоритама и њихове практичне примене.

ЦСТА К-12 Стандарди рачунарске науке, разреди 9-12 (узраст 14-18)

5.3 Ниво 3: Примена концепата и стварање стварних решења (Л3)

КСНУМКС.А Рачунарске науке у савременом свету (МВ)

• Рачунарско размишљање (ЦТ)

3. Објасните како су низ, одабир, понављање и рекурзија градивни блокови алгоритама.
4. Користите моделирање и симулацију за представљање и разумевање природних феномена.

КСНУМКС.Б Концепти и праксе рачунарских наука (ЦП)

• Рачунарско размишљање (ЦТ)

5. Користите анализу података за боље разумевање сложених природних и људских система.

9. Анализирајте податке и идентификујте обрасце кроз моделирање и симулацију.

Раст секвенци

 Локвањи

На језерцу постоји један локвањ. Сваке недеље се број локвања удвостручи. Језерце је након 10 недеља потпуно прекривено локвањима. После колико недеља је само половина језера прекривена локвањима? Објасните своје резоновање.

Колико могу да понесу?

Тежина коју скелет може да носи пропорционална је његовој површини попречног пресека. Тежина животиње пропорционална је њеној запремини. Зашто мислите да мрав може да носи десет до педесет пута већу тежину, док човек тешко може да носи сопствену тежину? (Савет: Упоредите раст површине и запремине.)

Довршите секвенце

Пронађите следећа два елемента у сваком од следећих низова.

• 2, 2, 2, 2, ___, ___
• 3, 6, 9, 12, 15, ___, ___
• 4, 9, 16, 25, ___, ___
• 2, 5, 10, 17, 26, ___, ___
• 64, 96, 112, 120, 124, ___, ___

За прве три секвенце такође пронађите њихову одговарајућу функцију раста (у смислу н).

Који низ расте најспорије?

Које секвенце најбрже расту?

Игра погађања броја

Радите заједно са комшијом. Неко од вас мора смислити број између 1 и 100. Немојте то још рећи свом партнеру. Циљ вашег партнера је да погоди тај број у што је могуће мање покушаја. На питања је дозвољено само да одговорите са „да“ или „не“. Када ваш партнер пронађе тачан број, замените улоге.

Метода прелома

Дозвољено вам је само да постављате питања попут „Да ли је број већи од 20?“ или „Да ли је број већи од 54?“ Која је најбоља стратегија коју можете пронаћи у овом случају? Колико покушаја вам је потребно у најгорем случају?

Објасните у неколико речи зашто је ваш метод оптималан.

Опционално: Пронађите сложеност

Можете ли пронаћи низ који описује колико је питања потребно у најгорем случају ако су дозвољени бројеви од 1 до Н? Одговор је најбоље изражен великим-О записом. (Савет: Пробајте логаритам.) Шта се дешава ако су дозвољени сви цели бројеви?

Ако желите да сазнате више о проналажењу сложености, можете погледати књигу ТХ Цормен ет ал., Увод у алгоритме или на веб локацији хттп://ввв.лондонинтернатионал.ац.ук/цуррент_студентс/программе_ресоурцес/цис/пдфс /субјецт_гуидес/левел_2/цис226_вол2/цис226_цхап1.пдф

Алгоритми сортирања

Сада ћете погледати неколико метода сортирања. Ваш учитељ ће вам дати картице, а ви ћете научити две различите методе сортирања.

Да бисте опонашали понашање рачунара, можете само да извршите одређене једноставне операције: Дозвољено вам је да гледате две карте одједном, упоредите их и премештате где год желите, у зависности само од вредности две картице. Такве операције могу укључивати замену картица, уметање једне картице пре друге итд. Наравно, можете отворити и нове помоћне гомиле картица.

Међутим, није вам дозвољено само да погледате све карте, запамтите њихову вредност и одмах их поставите на право место.

Буббле Сорт

Уђите у три групе. Свака група ће добити осам карата. Измешајте карте и положите их на сто са лицем надоле.

Једноставан начин сортирања је сортирање по мехурићима. Примените следеће кораке на својих 8 картица:

1. Погледајте прве две карте и упоредите их
2. Замените картице (ако је потребно) тако да буду у све већем редоследу
3. Сада погледајте другу и трећу картицу и замените их ако нису у све већем редоследу
4. Наставите тако док не дођете до седме и осме карте. Замените их ако је потребно
5. Сада понављајте кораке 1-4 све док не будете морали више да мењате.

Првих неколико замена приказано је на слици десно. Прве две карте је потребно заменити, у средини су карте већ у

исправан редослед и потребно је заменити „8“ и „3“ поново.

Након завршетка, окрените све картице и проверите да ли су сортиране. Објасните у неколико речи зашто ова метода функционише.

Опционо: Уђите у групе од пет до десет и пронађите сопствени метод сортирања користећи само дозвољене операције како је горе објашњено. Може ли бити боље од сортирања мехура? Зашто Зашто не?