Pagiging kumplikado - Ito ay Simple

Bumuo ng Mga Materyales

Mga Kinakailangan na Materyales

• Cardboard upang gumawa ng mga may bilang na card, o maraming mga deck ng paglalaro ng mga kard (3 bawat mag-aaral)
• Mga item sa gantimpala: bigas, maliit na kendi o iba pang mga item na murang gastos. Ang pagkuha ng bigas bilang isang halimbawa, tungkol sa 25 tablespoons ang kinakailangan (ito ay isang maliit na mas mababa sa 400g)

Paghahanda

Gumawa ng mga kard mula sa karton o papel at bilangin ang mga ito nang sunud-sunod simula sa 1. Tatlong card bawat estudyante ang kinakailangan. Bilang kahalili dalawa o tatlong deck ng paglalaro ng baraha ang maaaring magamit ngunit ang pagkakasunud-sunod ng mga kard ay kailangang ipaliwanag sa mga mag-aaral.

Disenyo Hamon

Ikaw ay isang inhinyero na binigyan ng hamon ng pag-aaral, pagbuo at pagpapatupad ng mga algorithm gamit ang mga laro.

1. Ipamahagi ang kumplikadong Ito ay worksheet. Ang pag-unawa sa pahina ng "Paglago ng mga Sequence" ay mahalaga para sa natitirang aralin. Subukan ang pag-unawa sa materyal. Ang solusyon ay ipinapakita sa ibaba:
   

   Solusyon
   

   Mga Lili ng Tubig 9 na linggo Dahil ang bilang ng mga liryo ay dumoble bawat linggo, kung sa 9 na linggo ang lawa ay natatakpan ng kalahati, ito ay ganap na natatakpan pagkatapos ng 10 linggo. Ang isang halimbawa sa loob ng anim na linggo ay ibinigay sa mapagkukunan ng guro na "Mga Water Lily."

   Ang paglago ng pagkakasunud-sunod na naglalarawan sa lugar na sakop ay exponential.

   Gaano karami ang madadala nila?

   Ang mga lugar sa ibabaw ng 2D ay lumalaki ng quadratically sa haba ng mga gilid, habang ang mga item ng 3D ay maaaring lumago cubically (ibig sabihin sa lakas ng tatlo). Samakatuwid, ang bigat na maaaring bitbitin ng isang balangkas ay proporsyonal na ipinapalagay na ang lahat ng panig ay lumalaki nang linear na isang kubiko na pagkakasunud-sunod ay lumalaki nang mas mabilis kaysa sa isang quadratic.

   Ang isang pagtaas sa taas ng hayop ay makakamit lamang sa pamamagitan ng paggawa ng balangkas ng hayop na iyon ng isang materyal na mas mahirap at mas malakas kaysa sa mga maliliit na hayop, o sa pamamagitan ng pagpapalaki ng laki ng mga buto ng hayop. Dahil sa maliit na bigat ng isang langgam, ang balangkas nito (at mga kalamnan) ay sapat na malakas upang magdala ng sampu hanggang limampung beses ang sarili nitong timbang, habang ang totoo ay hindi totoo para sa mga tao. Isipin ang tungkol sa bigat ng isang gusali na suportado ng isang haligi. Kung ang itaas na sahig ay masyadong mabigat para sa haligi ng bato, nagsisimula itong pumutok at gumuho. Para sa isang pare-parehong materyal, ang timbang na madala nito ay proporsyonal sa cross-sectional area. Kaya't kung doblehin mo ang lahat ng mga sukat ng gusali ng pagtaas ng timbang ng 8 beses, ang kapasidad ng mga haligi ay tataas lamang ng apat na beses.

   Maaari rin itong mailarawan sa pamamagitan ng pagsasaalang-alang sa isang mouse na nahuhulog sa isang baras ng elevator. Dahil sa kanyang maliit na bigat maaari itong mabuhay, habang ang mga malalaking hayop ay hindi. (Halimbawa halaw mula sa TW Körner, The Pleasures of Counting, Cambridge University Press, 1996)

   Kumpletuhin ang Mga Sequence

   Ang mga pagkakasunud-sunod ay nagpatuloy tulad ng sumusunod, na may kani-kanilang mga pagpapaandar na paglago na ibinigay sa panaklong:

   • 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

   Ang unang pagkakasunud-sunod ay lumalakas (ang pag-andar ng paglago nito ay isang pare-pareho lamang) habang ang pangatlong pagkakasunud-sunod ay lumalakas (ang pag-andar ng paglago ay parisukat). Ang pang-apat na pagkakasunud-sunod ay mayroon ding isang quadratic na pag-andar ng paglago at sa gayon ay lumalaki sa parehong rate, ngunit ang mga indibidwal na item ay palaging magiging mas mababa kaysa sa mga pangatlong pagkakasunud-sunod.

    

   

2. Ipakilala ang paksa sa mga mag-aaral sa pamamagitan ng paglalaro ng Reward Game sa kanila, na inilalarawan sa mapagkukunan ng guro na "Mga Larong Pangkat." Ang laro ay binubuo ng pagbibigay ng mga gantimpala, sa anyo ng maliliit na item, sa mga mag-aaral. Ang laro ay ipinaliwanag dito sa bigas bilang isang halimbawa, ngunit gumagana itong pantay na rin para sa iba pang maliliit na gantimpala. Ang bigas ay ibinibigay nang paikot. Ang layunin ng laro ay upang makakuha ng mas maraming bigas hangga't maaari. Ang halaga ng bigas na ibinibigay sa bawat pag-ikot ay natutukoy ng isa sa dalawang diskarte sa gantimpala:
   Pagpipilian 1: Tuwing pag-ikot, isang kutsarita ng bigas ang makikitungo.
   Pagpipilian 2: Sa unang pag-ikot ang gantimpala ay isang solong butil lamang ng bigas. Pagkatapos, sa bawat sunud-sunod na pag-ikot, ang dami ng bigas na naibigay ay doble.
   • Hayaang pumili ang bawat mag-aaral ng isa sa mga diskarte sa gantimpala at ipangkat ang mga mag-aaral ayon sa napiling pagpipilian.
   • Makipagtulungan sa mga gantimpala sa bawat pangkat. Maaari kang magtalaga ng isang mag-aaral sa bawat pangkat na makakatulong sa pagbilang ng bigas. Tandaan na patungo sa dulo ng isang eksaktong bilang ng mga butil ay hindi mahalaga.
   • Matapos ang unang apat na pag-ikot, hilingin sa mga mag-aaral na ihambing ang pinagsama-samang gantimpala. Gawin ang pareho pagkatapos ng walo at labindalawang pag-ikot. Pagkatapos talakayin ang kinalabasan ng laro sa mga mag-aaral.
   • Ang mga mag-aaral ay dapat na makakuha ng isang madaling maunawaan sa iba't ibang mga rate ng paglago. Maaari rin itong maiugnay sa pagtaas ng lakas ng computing ng mga modernong microprocessor. Ayon sa Batas ni Moore, ang bilang ng mga transistor na maaaring mailagay sa isang maliit na tilad ay nagdoble ng humigit-kumulang bawat dalawang taon. Maaaring hilingin sa mga mag-aaral na mag-isip tungkol sa mga kahihinatnan ng pagmamasid na ito at kung posible na ang paglago na ito ay mas matagal pa.
3. I-play ang Pambansang Hulaan na Laro na ipinaliwanag sa mapagkukunan ng guro na "Mga Larong Pangkat." Ang solusyon para dito ay ipinapakita sa ibaba. Ang layunin ng laro ay hulaan ang isang numero na may ilang mga pagsubok hangga't maaari. Ang laro ay unang nilalaro kasama ng buong klase, at pagkatapos ay ilalagay ang mga mag-aaral sa mga pares upang siyasatin ang kanilang sariling mga diskarte upang malutas ang laro. Sabihin sa mga mag-aaral na tumayo. Mag-isip ng isang numero sa pagitan ng 1 at 50 at huwag sabihin ito sa mga mag-aaral. Pinapayagan silang magtanong lamang tulad ng "37 na ba?" o "20 na ba?" at maaari mo lamang sagutin ng "oo" o "hindi" hanggang sa makita nila ang tamang numero. Ang isang mag-aaral na nagtatanong ng isang katanungan na humahantong sa isang "hindi" sagot ay kailangang umupo at maaaring hindi na magtanong hanggang sa matapos ang laro. Tandaan na ang lahat ng mga mag-aaral ay maaaring nakaupo bago matapos ang laro. Sa kasong ito maaari kang magpasya na i-play muli ang laro at talakayin kung bakit hindi ito gumana at sa ganitong uri ng mga katanungan sa pinakamasamang kaso 50 pagsubok ang kinakailangan.
   
   Ang Paraan ng Bisection Ang isang pinakamainam na diskarte upang lapitan ang laro sa paghula ng numero ay ang paraan ng bisection: Magsimula sa pamamagitan ng pagtatanong ng "Ito ba (mahigpit) na higit sa 50?" Kung ang sagot ay "oo" magpatuloy sa "Mas malaki ba ito sa 75?", Kung hindi, tanungin ang "Mas malaki ba ito sa 25?" Magpatuloy sa ganitong paraan ng palaging pagtatanong para sa gitnang numero hanggang sa may natitirang isang pagpipilian lamang. Halimbawa:
   • (Ang bilang ay 54)
   • Mas malaki ba ito sa 50? Oo
   • Mas malaki ba ito sa 75? Hindi
   • Mas malaki ba ito sa 63? Hindi
   • Mas malaki ba ito sa 57? Hindi
   • Mas malaki ba ito sa 54? Hindi
   • Mas malaki ba ito sa 52? Oo
   • Mas malaki ba ito sa 53? Oo

   Kaya pagkatapos ng 7 mga katanungan malinaw na ang bilang ay dapat na 54. (May mga kaso kung saan 6 na katanungan lamang ang kinakailangan. Sa katunayan, ang average na bilang ng mga katanungan ay mag-log 100 = 6.64.)

   Ito ay isang pinakamainam na pamamaraan sapagkat sa bawat katanungan ang hanay ng mga posibleng numero ay nahahati sa dalawang tinatayang pantay na bahagi, na may isang naglalaman ng kinakailangang numero. Sa katunayan, para sa problemang ito, ang bawat pamamaraan na naghahati sa mga posibleng numero bawat katanungan ay pinakamainam. Ang isa pang solusyon ay ang magtanong ng mga katanungan tulad ng "Ang numero ba ay nahahati sa 2?"

   Opsyonal: Hanapin ang pagiging kumplikado

   Ang pagiging kumplikado ng pamamaraan ng bisection ay logarithmic, ibig sabihin, ng order O (log N). Ito ay isang bunga ng paghati sa mga posibleng numero sa bawat tanong. Kung pinapayagan ang lahat ng mga integer, walang paraan na maaaring malutas ang problema sa may takdang oras.

4. Ipakilala ang mga mag-aaral sa pag-uuri ng mga algorithm sa pamamagitan ng pagsunod sa mga tagubilin sa worksheet ng mag-aaral na "Pagsunud-sunurin ng Mga Algorithm," ibig sabihin, ibigay ang mga kard at ilagay ang mga mag-aaral sa mga iminungkahing laki ng pangkat. Lumilitaw ang solusyon sa ibaba:
   

   Solusyon

   Pag-uuri ng Bubble Kung ang deck ay hindi pinagsunod-sunod, magkakaroon ng hindi bababa sa dalawang magkakasunod na kard na wala sa tamang pagkakasunud-sunod. Sa kalaunan ay magpapalitan ang algorithm ng dalawang kard na ito. Samakatuwid, kung wala nang mga card na maipapalit, ang algorithm ay natatapos at ang deck ay pinagsunod-sunod. Ang Bbleble Sort ay may kalamangan na maging napaka-simple upang ipatupad, ngunit hindi ito kasing husay ng mas advanced na mga algorithm sa pag-uuri tulad ng pagsasama-sama ng uri (tingnan ang sa ibaba). Ang pagiging kumplikado ng oras ng run ng pag-uuri ng bubble para sa n cards ay parisukat, o O (n2).Mas Mabilis na Pag-uuri ng Mga Algorithm

   Habang ang pagiging kumplikado ng run time ng pag-uuri ng bubble ay parisukat, mas mahusay na mga pamamaraan na umiiral. Halimbawa merge sort ay may isang kumplikadong oras ng run ng O (n log n) para sa n cards. Ang isang kagiliw-giliw na tampok ng pagsasama-sama ng uri ay pinapayagan ng istraktura nito na maging parallelized. Ang isa pang algorithm na may kumplikadong oras ng run O (n log n) na madalas gamitin sa pagsasanay ng mabilis na uri. Sa pangkalahatan ay mahusay itong gumaganap kahit na ang pagiging kumplikado ng oras ng pagpapatakbo nito ay parisukat at sa gayon ay mas masahol kaysa sa pagsasama-sama ng uri. Karaniwan din na gumamit ng mga hybrid na bersyon ng iba't ibang mga pag-uuri ng mga algorithm upang umakma sa mga tukoy na problema. Para sa isang hango ng mga resulta na ito tingnan ang TH Cormen et al., Panimula sa Mga Algorithm.

   Para sa pag-uuri batay sa paghahambing ng mga indibidwal na item, walang pamamaraan na may pinakamasamang kaso na nagpapatakbo ng pagiging kumplikado ng oras na mas mahusay kaysa sa O (n log n) na hindi nagsasamantala sa mga parallel na operasyon tulad ng pagsasama ng iba't ibang mga stack ng mga kard nang sabay. Ito ay dahil ang mga n card ay maaaring mag-order sa iba't ibang paraan, at ang bawat paghahambing ay maaaring kalahati ng bilang ng mga posibleng pag-order, na humahantong sa isang pagiging kumplikado ng O (log (nn)) = O (n log n).

5. Opsyonal: Ipabasa sa mga mag-aaral ang mapagkukunan ng mag-aaral na "Mga Algorithm" sa Seksyon ng "Mga Konsepto sa Background" upang makilala ang mga terminolohiya na ginamit sa Computer Science.
6. Para sa higit pang nilalaman sa paksa, tingnan ang seksyong "Digging Deeper".

Mga Advanced na Pagpipilian

Ang mga advanced na mag-aaral ay maaaring sumulat ng isang mapaghahambing na sanaysay sa iba't ibang mga pamamaraan ng pag-uuri at ang paliwanag na pamantayan para mas gusto ang isang pamamaraan kaysa sa iba. Ang mga advanced na mag-aaral ay maaaring hilingin na magbigay ng mga argumento ng pagiging kumplikado ng computational ng mga isinasaalang-alang na mga algorithm at kung bakit ang pagganap ng mga algorithm ng pag-uuri ng uri ay limitado sa panimula.

Ang aralin ay maaaring gawin sa kasing liit ng 1 panahon ng klase para sa mga matatandang mag-aaral. Gayunpaman, upang matulungan ang mga mag-aaral mula sa pakiramdam na nagmamadali at upang matiyak ang tagumpay ng mag-aaral (lalo na para sa mga mas batang mag-aaral), hatiin ang aralin sa dalawang panahon na nagbibigay sa mga mag-aaral ng mas maraming oras upang mag-utak, subukan ang mga ideya at tapusin ang kanilang disenyo. Isagawa ang pagsubok at debrief sa susunod na panahon ng klase.

Ano ang isang Algorithm?

Maaaring magamit ang isang computer upang magsagawa ng maraming gawain na makakatulong sa atin sa ating trabaho. Minsan ang mga gawaing ito ay madaling ilarawan sa mga salita, tulad ng "pag-uri-uriin ang deck ng mga kard", o "hanapin ang pinakamabilis na paraan mula sa Paris patungong New York". Gayunpaman, para sa isang computer ang mga gawaing ito ay maaaring napakahirap lutasin. Sa panloob ay maaari lamang magsagawa ang isang computer primitive na operasyon at ang kanilang wastong pag-aayos lamang ang naglulutas ng isang problema. Ang ganitong pag-aayos ay tinatawag na an algorithm. Dahil ang bawat primitive na operasyon ay tumatagal ng ilang oras (ilang nanoseconds sa isang modernong computer), ang isang algorithm ay nangangailangan ng isang tiyak takbo ng oras upang matapos ang gawain nito.

Bakit Mas Mabuti ang Ilang Algorithm kaysa sa Iba?

Ang bawat gawain ay nangangailangan ng isang espesyal na dinisenyo algorithm na maaaring malutas ito. Ang pag-aayos ng isang hanay ng mga kard ay hindi maaaring gawin sa isang algorithm na idinisenyo upang mahanap ang pinakamaikling landas sa pagitan ng dalawang lungsod. Gayundin, medyo intuitively, ang pag-uuri ng isang deck ng 200 cards ay mas matagal kaysa sa pag-uuri lamang ng 52 card (o sa walang kuwenta na kaso, 2 card). Samakatuwid ang oras ng pagtakbo ay nakasalalay sa problema at sa laki nito (pinag-uusapan ng mga siyentista sa computer ang a halimbawa ng problema).

Ang mga algorithm ay dapat na ihambing nang nakapag-iisa ng halimbawa ng problema (kung hindi man ang pinakamahusay na algorithm ay palaging ibibigay agad ang sagot na kinakalkula bago.) Dito kapaki-pakinabang ang konsepto ng paglaki ng isang pagkakasunud-sunod: bilang parameter n sa isang pagkakasunud-sunod na tukoy sa algorithm. Samakatuwid mayroong mga algorithm ng iba't ibang kaguluhan, na naaayon sa pagkakasunud-sunod na naglalarawan sa kanila. Ang mga algorithm ay inihambing sa pamamagitan ng paghahambing ng paglago ng mga pagkakasunud-sunod. Samakatuwid ang isang algorithm ng quadratic na pagiging kumplikado ay mas mahusay kaysa sa isang algorithm ng pagiging kumplikado ng exponential.

Pagiging kumplikado - Kapaki-pakinabang

Ang kahusayan ng mga algorithm ay mahalaga para sa isang napakaraming mga kasalukuyang aplikasyon ng computing. Ang ilang mga problema ay napakahirap malutas dahil ang tanging kilalang mga algorithm na nalulutas ang mga ito ay may napakataas na pagiging kumplikado.

Ang isang malawak na kilalang halimbawa ng mataas na pagiging kumplikado ay ang naglalakbay na problema sa salesman (TSP). Sa problemang ito, nais ng isang negosyante na magnegosyo sa isang hanay ng mga lungsod. Nais niyang hanapin ang pinakamaikling posibleng ruta sa pagitan ng mga lungsod na ito nang hindi bumibisita sa anumang lungsod nang higit sa isang beses, at nais niyang bumalik sa kanyang panimulang lungsod sa pagtatapos ng kanyang itinerary. Ang paglutas nito nang mahusay ay magiging napaka kapaki-pakinabang para sa pagtatalaga ng mga ruta para sa mga eroplano, pag-iiskedyul ng mga gawain sa mga makina at kahit na ang paggawa ng mga microprocessor.

Habang ang pagiging kumplikado ng TSP ay pumipigil sa isang mahusay na solusyon sa mga problemang ito, para sa ilang mga application, ang mataas na pagiging kumplikado ay maaaring maging kanais-nais. Kapag ang isang naka-encrypt na mensahe ay ipinadala, dapat na napakahirap makakuha ng naihatid na impormasyon nang hindi nalalaman ang ilang nakabahaging lihim. Sa kasong ito, ang pag-encrypt ay dinisenyo sa isang paraan na ang decryption ay may isang napakataas na pagiging kumplikado at sa gayon ay maiwasan ang eavesdropping. Ang ligtas na komunikasyon ay hindi posible kung wala ang mataas na pagiging kumplikado ng decryption. Ang mga halimbawang ito at maraming iba pa ay nagpapakita na ang pag-alam sa pagiging kumplikado ng isang problema ay lubhang kapaki-pakinabang para sa computing at higit pa.

Mga Koneksyon sa Internet

• Masalimuot na Zoo: (https://complexityzoo.uwaterloo.ca/Complexity_Zoo#sthash.1Gnn1E1Z.dpuf)
• P vs NP Problema
• Batas ni Moore
• Algorithm Analysis: (http://www.londoninternational.ac.uk/sites/default/files/computingsamples/co2226_vol2_ch1.pdf#sthash.1Gnn1E1Z.dpuf)
• Mga Pamantayan sa ITEA para sa Teknikal na Pagbasa
• Mga Pamantayan sa Edukasyon sa Pambansang Agham: (http://www.nsta.org/publications/nses.aspx)
• Scaling

Inirerekumendang Reading

• Paglago ng mga Sequence at Pag-uuri ng Mga Algorithm: Panimula sa Mga Algorithm ni TH Cormen et al. (ISBN: 0070131511)
• Dimensyon ng Pagsusuri: Ang Mga kasiyahan sa Pagbibilang ng TW Körner (ISBN: 0521568234)

Gawain sa Pagsulat

Paghambingin ang iba't ibang mga pamamaraan ng pag-uuri at ipaliwanag kung bakit mas gugustuhin mo ang isa kaysa sa isa pa. Sumulat ng isang maikling teksto sa kahalagahan ng pagiging kumplikado ng computational sa cryptography.

Pagkahanay sa Mga Framework ng Kurikulum

tandaan: Ang mga plano sa aralin sa seryeng ito ay nakahanay sa isa o higit pa sa mga sumusunod na hanay ng mga pamantayan:

• S. Mga Pamantayan sa Edukasyon sa Agham (http://www.nap.edu/catalog.php?record_id=4962)
• S. Susunod na Mga Pamantayan sa Agham na Henerasyon (http://www.nextgenscience.org/)
• Mga Pamantayan sa International Technology Education Association para sa Teknikal na Pagbasa (http://www.iteea.org/TAA/PDFs/xstnd.pdf)
• S. Pambansang Konseho ng Mga Guro ng Mga Prinsipyo at Pamantayan ng Matematika para sa Matematika sa Paaralan (http://www.nctm.org/standards/content.aspx?id=16909)
• S. Karaniwang Mga Pamantayang Pangunahing Estado para sa Matematika (http://www.corestandards.org/Math)
• Mga Pamantayan sa Agham ng Guro sa Computer K-12 Mga Pamantayan sa Agham ng Computer (http://csta.acm.org/Curriculum/sub/K12Standards.html)

Mga Prinsipyo at Pamantayan para sa Matematika sa Paaralan

Pamantayan sa Algebra

Bilang resulta ng mga aktibidad, lahat ng mag-aaral ay dapat na bumuo

• Maunawaan ang mga pattern, ugnayan, at pag-andar.
• Gumamit ng mga modelo ng matematika upang kumatawan at maunawaan ang mga ugnayan sa dami.

Pamantayan sa Paglutas ng problema

Bilang resulta ng mga aktibidad, lahat ng mag-aaral ay dapat na bumuo

• Ilapat at iakma ang iba't ibang mga naaangkop na diskarte upang malutas ang mga problema.
• Subaybayan at pagnilayan ang proseso ng paglutas ng problema sa matematika.

Mga Karaniwang Core na Pamantayan sa Estado para sa Matematika Baitang 9-12 (edad 14 - 18)

Pamantayan sa Algebra

• Nangangatuwiran sa Mga Equation at Inequalities
• Malutas ang mga equation at inequalities sa isang variable
• Matematika.Kontento.HSA-REI.B.3Malutas ang mga linear equation at inequalities sa isang variable, kasama ang mga equation na may mga coefficients na kinakatawan ng mga titik.

Pag-andar pamantayan

• Mga pagpapaandar sa gusali
• Bumuo ng isang pagpapaandar na nagmomodelo ng isang ugnayan sa pagitan ng dalawang dami
• Matematika.Kontento.HSF-BF.A.2Sumulat ng mga pagkakasunud-sunod ng aritmetika at geometriko na parehong recursively at may isang malinaw na pormula, gamitin ang mga ito upang i-modelo ang mga sitwasyon, at isalin sa pagitan ng dalawang anyo.
• Mga modelo ng Linear, Quadratic, at exponential
• Bumuo at ihambing ang mga linear, quadratic, at exponential na mga modelo at lutasin ang mga problema
• Matematika.Kontento.HSF-LE.A.1Makilala ang pagitan ng mga sitwasyon na maaaring ma-modelo sa mga linear function at may exponential function.
• Matematika.Kontento.HSF-LE.A.1cKilalanin ang mga sitwasyon kung saan lumalaki o nabubulok ang isang dami ng isang pare-pareho na porsyento ng rate bawat agwat ng yunit na may kaugnayan sa iba pa.

 Mga Pamantayan para sa Teknikal na Pagbasa at Pagsulat - Lahat ng Edad

         Ang Kalikasan ng Teknolohiya

• Pamantayan 1: Ang mga mag-aaral ay bubuo ng pag-unawa sa mga katangian at saklaw ng teknolohiya.
• Pamantayan 2: Ang mga mag-aaral ay bubuo ng pag-unawa sa pangunahing mga konsepto ng teknolohiya.
• Pamantayan 3: Ang mga mag-aaral ay bubuo ng pag-unawa sa mga ugnayan sa mga teknolohiya at mga koneksyon sa pagitan ng teknolohiya at iba pang larangan ng pag-aaral.

Ang Dinisenyo na Daigdig

• Pamantayan 17: Ang mga mag-aaral ay bubuo ng isang pag-unawa sa at magagawang pumili at gumamit ng mga teknolohiya ng impormasyon at komunikasyon.

Mga Pamantayan sa Science sa Computer ng CSTA K-12 Grades 6-9 (edad 11-14)

5. 2 Antas 2: Computer Science and Community (L2)

• Computational Thinking (CT)

3. Tukuyin ang isang algorithm bilang isang pagkakasunud-sunod ng mga tagubilin na maaaring maproseso ng isang computer.
4. Suriin ang mga paraan na maaaring magamit ang iba't ibang mga algorithm upang malutas ang parehong problema.
5. Isadula ang paghahanap at pag-uuri ng mga algorithm.
6. Gumamit ng mga visual na representasyon ng mga estado ng problema, istraktura, at data (hal. Mga grap, tsart, network diagram, flowchart).
7. Makipag-ugnay sa mga modelo at simulation na tukoy sa nilalaman (hal., Mga ecosystem, epidemya, dynamic na molekular) upang suportahan ang pag-aaral at pagsasaliksik.

• Pakikipagtulungan (CL)

3. Makipagtulungan sa mga kapantay, dalubhasa, at iba pa na gumagamit ng mga kasanayan sa pakikipagtulungan tulad ng pares ng programa, pagtatrabaho sa mga pangkat ng proyekto, at pakikilahok sa mga aktibong aktibidad sa pag-aaral ng pangkat.
4. Kinakailangan ang mga disposisyon ng pag-exhibit para sa pakikipagtulungan: pagbibigay ng kapaki-pakinabang na puna, pagsasama ng puna, pag-unawa at pagtanggap ng maraming pananaw, pakikisalamuha.

• Pagsasanay sa Computing at Programming (CPP)

4. Ipakita ang isang pag-unawa sa mga algorithm at ang kanilang praktikal na aplikasyon.

Mga Pamantayan sa Science sa Computer ng CSTA K-12 Grades 9-12 (edad 14-18)

5.3 Antas 3: Paglalapat ng Mga Konsepto at Paglikha ng Mga Solusyon na Totoong Mundo (L3)

5.3.A Computer Science sa Modern World (MW)

• Computational Thinking (CT)

3. Ipaliwanag kung paano ang pagkakasunud-sunod, pagpili, pag-ulit, at recursion ay nagtatayo ng mga bloke ng mga algorithm.
4. Gumamit ng pagmomodelo at simulation upang kumatawan at maunawaan ang natural phenomena.

5.3.B Mga Konsepto at Kasanayan sa Computer Science (CP)

• Computational Thinking (CT)

5. Gumamit ng pagtatasa ng data upang mapahusay ang pag-unawa sa mga kumplikadong natural at sistemang pantao.

9. Pag-aralan ang data at kilalanin ang mga pattern sa pamamagitan ng pagmomodelo at simulation.

Ang Paglago ng mga Sequence

 Mga Lili ng Tubig

Sa isang pond mayroong isang solong water lily. Tuwing linggo ang bilang ng mga water lily sa pond ay doble. Ang pond ay ganap na natatakpan ng mga water lily pagkatapos ng 10 linggo. Matapos kung gaano karaming mga linggo ang kalahati lamang ng pond na natatakpan ng mga water lily? Ipaliwanag ang iyong pangangatuwiran.

Gaano karami ang madadala nila?

Ang bigat na maaaring bitbitin ng isang balangkas ay proporsyonal sa cross-sectional area nito. Ang bigat ng isang hayop ay proporsyonal sa dami nito. Bakit sa palagay mo ang isang langgam ay maaaring magdala ng sampu hanggang limampung beses sa sarili nitong timbang habang ang isang tao ay mahirap na magdala ng sarili nitong timbang? (Pahiwatig: Ihambing ang paglaki ng isang lugar at isang dami.)

Kumpletuhin ang Mga Sequence

Hanapin ang susunod na dalawang elemento sa bawat isa sa mga sumusunod na pagkakasunud-sunod.

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

Para sa unang tatlong pagkakasunud-sunod, hanapin din ang kani-kanilang pag-andar ng paglaki (sa mga tuntunin ng n).

Aling pagkakasunud-sunod ang lumalakas?

Aling mga pagkakasunud-sunod ang pinakamabilis na lumalaki?

Isang Larong Hulaan ng Laro

Makipagtulungan sa iyong kapwa. Ang isa sa iyo ay kailangang mag-isip ng isang numero sa pagitan ng 1 at 100. Huwag pa itong sabihin sa iyong kapareha. Ang layunin ng iyong kapareha ay hulaan ang bilang na iyon sa ilang mga pagsubok hangga't maaari. Pinapayagan ka lamang na sagutin ang mga tanong ng "oo" o "hindi". Kapag natagpuan ng iyong kasosyo ang tamang numero, lumipat ng mga tungkulin.

Ang Paraan ng Bisection

Pinapayagan kang magtanong tulad ng "Mas malaki ba ang bilang sa 20?" o "Mas malaki ba ang bilang sa 54?" Ano ang pinakamahusay na diskarte na mahahanap mo sa kasong ito? Ilan sa mga pagsubok ang kailangan mo sa pinakamasamang kaso?

Ipaliwanag sa ilang mga salita kung bakit ang iyong pamamaraan ay pinakamainam.

Opsyonal: Hanapin ang pagiging kumplikado

Mahahanap mo ba ang isang pagkakasunud-sunod na naglalarawan kung gaano karaming mga katanungan ang kinakailangan sa pinakamasamang kaso kung pinapayagan ang mga numero mula 1 hanggang N? Ang sagot ay pinakamahusay na ipinahayag sa big-O notasyon. (Pahiwatig: Subukan ang logarithm.) Ano ang mangyayari kung pinapayagan ang lahat ng mga integer?

Kung nais mong malaman ang tungkol sa paghahanap ng pagiging kumplikado, maaari mong tingnan ang libro ni TH Cormen et al., Panimula sa Mga Algorithm o sa website http://www.londoninternational.ac.uk/current_students/programme_resource/cis/pdfs /subject_guides/level_2/cis226_vol2/cis226_chap1.pdf

Pag-uuri ng Mga Algorithm

Titingnan mo ngayon ang ilang mga pamamaraan ng pag-uuri. Bibigyan ka ng iyong guro ng mga kard at matututunan mo ang dalawang magkakaibang pamamaraan ng pag-uuri.

Upang gayahin ang pag-uugali ng isang computer, maaari ka lamang magsagawa ng ilang mga simpleng operasyon: Pinapayagan kang tumingin ng dalawang card nang paisa-isa, ihambing ang mga ito at ilipat ang mga ito saan mo man gusto, nakasalalay lamang sa mga halaga ng dalawang kard. Ang mga nasabing pagpapatakbo ay maaaring magsama ng pagpapalit ng mga kard, paglalagay ng isang card bago ang isa pa, atbp Siyempre, maaari mo ring buksan ang mga bagong auxiliary stack ng mga kard.

Gayunpaman, hindi ka pinapayagan na tingnan lamang ang lahat ng mga kard, alalahanin ang kanilang halaga at agad na ilagay ang mga ito sa tamang posisyon.

Pag-uuri ng Bubble

Kumuha ng mga pangkat ng tatlo. Ang bawat pangkat ay makakakuha ng walong card. I-shuffle ang mga card at ilagay ang mga kard sa mesa.

Ang isang simpleng pamamaraan para sa pag-uuri ay pag-uuri ng bubble. Ilapat ang mga sumusunod na hakbang sa iyong 8 card:

1. Tingnan ang unang dalawang kard at ihambing ang mga ito
2. Ipagpalit ang mga kard (kung kinakailangan) upang ang mga ito ay nasa pagtaas ng pagkakasunud-sunod
3. Ngayon tingnan ang pangalawa at pangatlong card at palitan ang mga ito kung wala sila sa pagtaas ng pagkakasunud-sunod
4. Magpatuloy na gawin ito hanggang sa maabot mo ang ikapito at ikawalong card. Ipagpalit ang mga ito kung kinakailangan
5. Ngayon ulitin ang mga hakbang 1-4 hanggang sa hindi mo na kailangang gumawa ng anumang mga swap.

Ang unang ilang mga swap ay inilalarawan sa figure sa kanan. Ang unang dalawang kard ay kailangang palitan, sa gitna ang mga kard ay nasa

wastong pagkakasunud-sunod at ang "8" at ang "3" ay kailangang palitan muli.

Pagkatapos makumpleto, i-turn over ang lahat ng mga card at suriin kung sila ay pinagsunod-sunod. Ipaliwanag sa ilang mga salita kung bakit gumagana ang pamamaraang ito.

Opsyonal: Kumuha ng mga pangkat ng lima hanggang sampu at hanapin ang iyong sariling pamamaraan ng pag-uuri gamit ang pinapayagan lamang na mga operasyon tulad ng ipinaliwanag sa itaas. Maaari kang makakuha ng anumang mas mahusay kaysa sa uri ng bubble? Bakit bakit Hindi?