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

Изградба на материјали

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

• Картон за правење нумерирани картички, или неколку палуби карти за играње (3 по ученик)
• Наградни предмети: Ориз, мали бонбони или други евтини производи. Земајќи го оризот како пример, потребни се околу 25 лажици (ова е малку помалку од 400гр)

Подготовка

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

Дизајн предизвик

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

1. Распределете го работниот лист „Комплексноста е едноставна“. Разбирањето на страницата „Раст на секвенци“ е од витално значење за остатокот од лекцијата. Тестирајте го разбирањето на материјалот. Решението е прикажано подолу:
   

   Решение
   

   Водни лилјани 9 недели. Бидејќи бројот на лилјани се удвојува секоја недела, ако во 9 недела езерцето е покриено на половина пат, тоа е целосно покриено по 10 недели. Пример за шест недели е даден во ресурсот на наставникот „Вода лилјани“.

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

   Колку можат да носат?

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

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

   Ова исто така може да се илустрира со разгледување на глувче кое паѓа од вратило на лифтот. Поради својата мала тежина може да преживее, додека поголемите животни не. (Пример адаптиран од TW Körner, The Pleasures of Counting, Cambridge University Press, 1996)

   Завршете ги секвенците

   Редоследот се продолжува на следниов начин, со соодветните функции за раст дадени во загради:

   • 2, 2, 2, 2, 2, 2 (2)
   • 3, 6, 9, 12, 15, 18, 21 (3 xn)
   • 4, 9, 16, 25, 36, 49 ((n + 1) 2)
   • 2, 5, 10, 17, 26, 37, 50
   • 64, 96, 112, 120, 124, 126, 127

   Првата секвенца расте најспоро (нејзината функција на раст е само константа) додека третата низа расте најбрзо (нејзината функција на раст е квадратна). Четвртата секвенца исто така има квадратна функција на раст и на тој начин расте со иста стапка, но нејзините поединечни ставки секогаш ќе бидат пониски од оние од третата секвенца.

    

   

2. Запознајте го предметот со учениците играјќи ја наградната игра со нив, која е опишана во ресурсот на наставникот „Групни игри“. Играта се состои од обезбедување награди, во форма на мали предмети, за учениците. Играта е објаснета овде со ориз како пример, но работи подеднакво добро за други мали награди. Оризот се дава во кругови. Целта на играта е да се добие што е можно повеќе ориз. Количината на ориз дадена во секој круг се одредува со една од двете стратегии за наградување:
   опција 1: Секој круг, ќе се дели една лажичка ориз.
   опција 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. Запознајте ги учениците со сортирање алгоритми следејќи ги упатствата на работниот лист за ученици „Сортирање алгоритми“, односно разделете ги картичките и ставете ги учениците во предложените големини на групата. Решението се појавува подолу:
   

   Решение

   Подредување меурчиња Ако палубата не е подредена, ќе има најмалку две последователни картички кои не се во правилен редослед. Алгоритмот на крајот ќе ги замени овие две картички. Затоа, ако нема повеќе картички што треба да се заменат, алгоритмот завршува и палубата е подредена. Bubble Sort има предност да се спроведе многу едноставно, но не е толку ефикасна како понапредните алгоритми за сортирање како што е спојување сортирање (види подолу). Комплексноста на време на работа на сортирање меур за n картички е квадратна, или O (n2).Побрзо сортирање алгоритми

   Додека сложеноста на времето на извршување на сортирање меурчиња е квадратна, постојат подобри методи. На пример, спојување сортирање има сложеност на времето на работа (O log n) за n картички. Интересна карактеристика на соединувањето е тоа што неговата структура овозможува да се паралелизира. Друг алгоритам со сложеност на времето на извршување O (n log n) кој често се користи при практикување брзо сортирање. Генерално функционира добро иако сложеноста на времето на работа е квадратна и затоа е полоша од онаа на соединување. Исто така, вообичаено е да се користат хибридни верзии на различни алгоритми за сортирање за да се прилагодат на специфични проблеми. За изведување на овие резултати видете TH Cormen et al., Вовед во алгоритми.

   За сортирање врз основа на споредување на одделни ставки, не постои метод со сложеност на времето во најлош случај подобар од O (n log n) кој не ги искористува паралелните операции како што е спојување различни купчиња картички во исто време. Ова е затоа што n картичките можат да се нарачаат на nn различни начини, и секоја споредба може да го намали половина од можните нарачки, што доведува до сложеност на O (log (nn)) = O (n log n).

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

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

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

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

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

Компјутерот може да се користи за извршување на огромен број задачи што можат да ни помогнат во нашата работа. Понекогаш овие задачи се лесни за опишување со зборови, како што се „сортирајте го овој шпил карти“ или „најдете најбрз пат од Париз до Newујорк“. Сепак, за компјутер овие задачи може да бидат многу тешко да се решат. Внатрешно, компјутерот може само подобро да работи примитивни операции и само нивното правилно уредување решава проблем. Таквиот аранжман се нарекува ан алгоритамНа Бидејќи секоја примитивна операција трае некое време (неколку наносекунди во модерен компјутер), алгоритам бара одредена време на трчање со цел да ја заврши својата задача.

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

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

Алгоритмите треба да се споредат независно од примерот на проблемот (инаку најдобриот алгоритам е секогаш да се даде одговорот пресметан претходно.) Тука е корисен концептот за раст на низа: Може да се земе предвид големината на проблемот како параметар n во низа која е специфична за алгоритмот. Затоа, постојат различни алгоритми сложеност, што одговара на низата што ги опишува. Алгоритмите потоа се споредуваат со споредување на растот на секвенците. Затоа, алгоритам со квадратна сложеност е подобар од алгоритам со експоненцијална комплексност.

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

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

Широко познат пример за висока сложеност е проблемот со патувачкиот продавач (TSP). Во овој проблем, трговецот сака да работи во збир на градови. Тој сака да го најде најкраткиот можен пат помеѓу овие градови без да посети ниту еден град повеќе пати, и сака да се врати во својот почетен град на крајот од неговата маршрута. Ефикасно решавање на ова би било многу корисно за доделување правци за авиони, распоред на задачи на машини, па дури и производство на микропроцесори.

Додека сложеноста на TSP спречува ефикасно решавање на овие проблеми, за некои апликации, дури и може да биде пожелна висока сложеност. Кога се испраќа шифрирана порака, треба да биде многу тешко да се дојде до пренесените информации без да се знае некоја заедничка тајна. Во овој случај, енкрипцијата е дизајнирана на таков начин што декрипцијата има многу висока сложеност и со тоа се спречува прислушкувањето. Безбедната комуникација не би била можна без високата сложеност на декрипцијата. Овие примери и бројни други покажуваат дека познавањето на сложеноста на проблемот е многу корисно за пресметување и пошироко.

Интернет конекции

• Сложеност зоолошка градина: (https://complexityzoo.uwaterloo.ca/Complexity_Zoo#sthash.1Gnn1E1Z.dpuf)
• P vs NP Проблем
• Законот на Мур
• Algorithm Analysis: (http://www.londoninternational.ac.uk/sites/default/files/computingsamples/co2226_vol2_ch1.pdf#sthash.1Gnn1E1Z.dpuf)
• Стандарди на ИТЕА за технолошка писменост
• Национални стандарди за научно образование: (http://www.nsta.org/publications/nses.aspx)
• Скалирање

Препорачано четиво

• Раст на секвенци и сортирање алгоритми: Вовед во алгоритми од Т.Х.Кормен и сор. (ISBN: 0070131511)
• Димензионална анализа: Задоволствата од броењето од TW Körner (ISBN: 0521568234)

Активност за пишување

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

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

Забелешка: Плановите за лекции во оваа серија се усогласени со еден или повеќе од следниве групи на стандарди:

• С. Стандарди за научно образование (http://www.nap.edu/catalog.php?record_id=4962)
• S. Научни стандарди за следната генерација (http://www.nextgenscience.org/)
• Стандарди за меѓународна технолошка асоцијација за технолошка писменост (http://www.iteea.org/TAA/PDFs/xstnd.pdf)
• S. Национален совет на наставници по математички принципи и стандарди за училишна математика (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 години)

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

• Расудување со равенки и нееднаквости
• Решавање равенки и нееднаквости во една променлива
• Математика.Содржина.HSA-REI.B.3Решавање линеарни равенки и нееднаквости во една променлива, вклучувајќи равенки со коефициенти претставени со букви.

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

• Градење функции
• Изградете функција која моделира врска помеѓу две количини
• Математика.Содржина.HSF-BF.A.2Напишете аритметички и геометриски секвенци и рекурзивно и со експлицитна формула, користете ги за моделирање ситуации и преведете помеѓу двете форми.
• Линеарни, квадратни и експоненцијални модели
• Конструирајте и споредувајте линеарни, квадратни и експоненцијални модели и решавајте проблеми
• Математика.Содржина.HSF-LE.A.1Разликувајте ситуации што можат да се моделираат со линеарни функции и со експоненцијални функции.
• Математика.Содржина.HSF-LE.A.1вПрепознајте ситуации во кои одредена количина расте или се распаѓа со постојана процентна стапка по единица интервал во однос на друга.

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

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

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

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

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

Стандарди за компјутерски науки CSTA K-12 одделение 6-9 (возраст од 11-14 години)

5. 2 Ниво 2: Компјутерски науки и заедница (L2)

• Компјутерско размислување (КТ)

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

• Соработка (CL)

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

• Компјутерска пракса и програмирање (CPP)

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

Стандарди за компјутерски науки CSTA K-12 одделение 9-12 (возраст од 14-18 години)

5.3 Ниво 3: Примена на концепти и креирање на реални решенија (L3)

5.3.A Компјутерски науки во современиот свет (MW)

• Компјутерско размислување (КТ)

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

5.3.B Концепти и практики за компјутерски науки (КП)

• Компјутерско размислување (КТ)

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, ___, ___

За првите три секвенци, исто така, пронајдете ја нивната соодветна функција за раст (во однос на n).

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

Кои секвенци растат најбрзо?

Игра за погодување бројки

Работете заедно со вашиот сосед. Еден од вас треба да размисли за број помеѓу 1 и 100. Не кажувајте му го тоа уште на вашиот партнер. Целта на вашиот партнер е да го погоди тој број во што е можно помалку обиди. Дозволено ви е да одговарате на прашања само со „да“ или „не“. Откако вашиот партнер ќе го најде точниот број, сменете ги улогите.

Метод на бисекција

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

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

Изборно: Најдете ја комплексноста

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

Ако сакате да дознаете повеќе за пронаоѓање на комплексноста, можете да ја погледнете книгата на TH Cormen et al., Вовед во алгоритми или на веб -страницата http://www.londoninternational.ac.uk/current_students/programme_resources/cis/pdfs /subject_guides/level_2/cis226_vol2/cis226_chap1.pdf

Сортирање алгоритми

Сега ќе разгледате неколку методи за сортирање. Вашиот наставник ќе ви даде картички и ќе научите два различни методи за сортирање.

За да го имитирате однесувањето на компјутерот, можете само да извршите одредени едноставни операции: Дозволено ви е да гледате две картички истовремено, да ги споредувате и да ги поместувате каде сакате, во зависност само од вредностите на двете картички. Ваквите операции може да вклучуваат замена на картички, вметнување на една картичка пред друга, итн. Се разбира, може да отворите и нови помошни купишта картички.

Сепак, не ви е дозволено само да ги погледнете сите картички, да ја запомните нивната вредност и веднаш да ги поставите во вистинската позиција.

Подредување меурчиња

Влезете во тричлени групи. Секоја група ќе добие по осум картички. Измешајте ги картичките и поставете ги картичките свртени надолу на масата.

Едноставен метод за сортирање е сортирање меурчиња. Применете ги следните чекори на вашите 8 картички:

1. Погледнете ги првите две картички и споредете ги
2. Заменете ги картичките (доколку е потребно), така што тие се во зголемен ред
3. Сега погледнете ја втората и третата картичка и заменете ги ако не се во зголемен ред
4. Продолжете така додека не стигнете до седмата и осмата карта. Заменете ги доколку е потребно
5. Сега повторете ги чекорите 1-4 додека не треба да правите повеќе трампа.

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

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

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

Факултативна: Влезете во групи од пет до десет и пронајдете свој метод за сортирање користејќи ги само дозволените операции како што е објаснето погоре. Можете ли да добиете нешто подобро од сортирање меурчиња? Зошто / зошто не?