Jautri ar Šķirošanu

Materiālu veidošana (katrai komandai)

Nepieciešamie materiāli

• Kartons vai celtniecības papīrs
• 1 liels marķieris
• Lente
• Lieli plastmasas rotaļu bloki
• Lielas kartona kastes

Dizains izaicinājums

Jūs esat daļa no inženieru komandas, kurai ir uzdevums kārtot objektus sarakstā, uzdodot konkrētus jautājumus, piemēram, salīdzinot divus objektus pēc to skaitliskās vērtības.

Kritēriji

• Objekti ar slēptu numuru veidos sarakstu.
• Jākārto saraksti, uzdodot virkni jautājumu.

Ierobežojumi

• Numuri ir redzami tikai “kontrolierim”.

1. Sadaliet klasi komandās pa 3-5.
2. Izdodiet darblapu Jautrība ar šķirošanu, ja vēlaties, lai studenti aizpildītu jautājumus darblapā. Pretējā gadījumā jūs varat veikt darbību bez darblapas.
3. Padomus un problēmu novēršanu skatiet sadaļā Fona jēdzieni.
4. Ir pamata kārtošana un pēc tam četras darbības. 2. un 3. darbība ir jāpabeidz kopā. 3. un 4. darbība ir jāpabeidz kopā. Tiek lēsts, ka katrs no tiem aizņem 90 minūtes.
5. Kopā ar klasi pārskatiet tālāk norādītos kārtošanas pamatnorādījumus un aiciniet studentus veikt kārtošanas pamatdarbību.
   Šķirošanas pamatnorādījumi:
   ● 1. solis: Studenti izvēlēsies 8 objektus, kas reprezentēs kārtojamo sarakstu. Viņi var izvēlēties jebko, kas atspoguļo viņu numuru sarakstu. Dažas saraksta idejas ir: a. Lieli plastmasas rotaļu bloki b. Lielas kartona kastes
   ● 2. solis: studenti izvēlas vienu personu komandā par “kontrolieri”.
   ● 3. solis: kontrolierim uz papīra jāizraksta nejauši skaitļi un jāpielīmē tie objektiem, lai tie netiktu paslēpti no pārējiem studentiem. Tikai kontrolierim vajadzētu tos redzēt.
   ● 4. solis: komanda tagad mēģinās kārtot sarakstu augošā secībā. Lai to izdarītu, studenti var darīt trīs lietas:
   a. Jautājiet kontrolierim: “Vai šis skaitlis ir lielāks par šo skaitli?” kas studentiem ļauj salīdzināt jebkurus divus skaitļus. Pārzinis var atbildēt tikai ar jā vai nē.
   b. Palūdziet kontrolierim nomainīt divus objektus. Pēc tam kontrolieris apmainīs objektus, pārliecinoties, ka uz tiem neatklāj skaitļus.
   c. Palūdziet kontrolierim pārvietot jebkuru objektu noteiktā pozīcijā, ti, “Pārvietot šo objektu trešajā pozīcijā” vai “Pārvietot šo objektu starp šiem diviem objektiem”.
   ● 5. solis: kontrolieris uzskaitīs uzdoto jautājumu “jā / nē” skaitu. Studentiem jācenšas kārtot skaitļus, vienlaikus saglabājot jautājumu skaitu līdz minimumam.
   ● 6. solis: Kad skolēniem šķiet, ka saraksts ir sakārtots, viņi lūgs kontrolierim atklāt numurus. Ja saraksts nav sakārtots, tad kontrolieris sajauc sarakstu un sāk no jauna.
6. Pārskatiet 1. darbību - vienreizēja ievietošana Kārtīgi norādījumi kopā ar klasi un aiciniet studentus kārtot vienu ievietošanu.
   1. darbība - Norādījumi par vienu ievietošanu:
   ● 1. solis: izmantojot blokus vai lodziņus, izveidojiet sākotnējo sarakstu šādi: viens no numuriem jāizceļ, bet pārējie ir iepriekš jāsakārto augošā secībā. Tad izdalītais numurs jānovieto saraksta šķirotās daļas vienā galā. Komandai nevajadzētu redzēt skaitļus, bet tai jāzina, ka viss saraksts ir sakārtots, izņemot vienu numuru beigās, kas ir nevietā.
   
   ● 2. solis: Pēc tam studentiem jāievēro 4. solī sniegtie norādījumi, kas izklāstīti iepriekš esošajā pamata kārtošanā, un jāmēģina pilnībā kārtot sarakstu. To sauc par vienreizēju ievietošanu, un tas palīdz kā pamatelements citiem šķirošanas algoritmiem, piemēram, ievietošanas kārtošanai.
   ● 3. solis: Paskaidrojiet studentiem, ka, ja viņi varētu redzēt skaitļus, būtu acīmredzami, ka viņi var vienkārši ievietot 4 starp 3 un 5, un saraksts būtu pilnībā sakārtots. Tomēr tas nedarbojas datoros. Tāpēc studentiem jāsāk salīdzināt skaitļus un pēc tam pasūtīt mijmaiņas un / vai kustības. Šajā gadījumā studenti zina, ka viss saraksts ir augošā secībā, izņemot pēdējo numuru. Studentiem, protams, vajadzētu saprast, ka viņiem vienkārši jāidentificē pozīcija, kurā ievietot pēdējo nesakārtoto numuru. ŠEIT ievietojiet 6 PIEMĒRU ATTĒLUS
   Iepriekš redzamā diagrammu secība parāda, kam ideālā gadījumā būtu jānotiek klasē. Visas aktivitātes laikā studenti nezina sarakstā esošos skaitļus un vienkārši dod kontrolierim instrukciju kopu, lai salīdzinātu skaitļus.
   Šī aktivitāte studentus iepazīstina ar iterācijas jēdzienu. Iterācija ir solis inženiertehniskā projektēšanas procesā. Lai pareizi kārtotu skaitļus, studentiem ir jāveic atkārtojums.
7. Pārskatiet aktivitāti Nr. 2 - ievietošanas kārtība zemāk kopā ar klasi un aiciniet studentus veikt ievietošanas kārtojumu.
   2. darbība - ievietošanas kārtošanas instrukcijas:
   ● 1. solis: izmantojot blokus vai lodziņus, kārtojiet sarakstu nejauši.
   ● 2. solis: Studentiem tagad jācenšas to kārtot, izmantojot savas iepriekšējās zināšanas par vienreizēju ievietošanu.
   ● 3. solis: Studentiem problēma jāsadala atsevišķu ievietojumu sērijās. Atsevišķs skaitlis pats par sevi ir sakārtots saraksts. Piemēram, mēs varam teikt, ka viens skaitlis nejauši sakārtotā saraksta galējā kreisajā pusē ir sakārtots saraksts.
   ● 4. solis: Skolēniem tagad jāapsver šis 1 elementu sakārtotais saraksts un jāveic ievietošanas kārtošana, uzskatot otro elementu par vietas numuru vienā ievietošanā.
   ● 4. solis: Kad tas ir izdarīts, studentiem tagad ir sakārtots 2 elementu saraksts. Pēc tam procedūru atkārto, trešo elementu uzskatot par vietas numuru, lai iegūtu 3 elementu kārtoto sarakstu.
   ● 5. solis: Studenti turpina atkārtot šo atsevišķu ievietojumu secību, līdz beidzot tiek iegūts viss sakārtotais saraksts. Turpmākā diagrammu secība parāda, kas studentiem būtu ideāli jāmēģina. Ievērojiet, kā dzeltenā rūtiņa, kas apzīmē sarindoto saraksta daļu, laika gaitā pieaug. Ņemiet vērā, ka vienreizēja ievietošana tiek veikta atkārtoti, saraksta dzelteno daļu izmantojot kā sakārtoto sarakstu un nākamo elementu labajā pusē kā vietas numuru. Procedūra galu galā sakārtos visu sarakstu!
   ŠEIT ievietojiet 10 PIEMĒRU ATTĒLUS
8. Pārskatiet aktivitāti Nr. 3 - Divu sarakstu apvienošanas kārtošanas instrukcijas kopā ar klasi un aiciniet studentus veikt divu sarakstu apvienošanas kārtojumu.
   3. darbība - divu sarakstu apvienošanas kārtošanas instrukcijas:
   ● 1. solis: Sākotnējo sarakstu izveidojiet šādi: Sadaliet 8 objektus 2 sarakstos pa 4 objektiem, un abiem sarakstiem vajadzētu būt neatkarīgi sakārtotiem.
   ● 2. solis: Pēc tam saraksti jāievieto blakus, un studentiem tagad jāmēģina “sapludināt” abus sakārtotos sarakstus vienā sakārtotajā sarakstā, izpildot Basic Sort norādījumus.
   ● 3. solis: Šis kārtošana ir noderīgs sākumpunkts un pamatelements sarežģītākam algoritmam: apvienot kārtošanu. Tas arī prasa studentiem atsaukt atmiņā un atkārtoti izmantot savas zināšanas par vienreizēju ievietošanu.
   ● 4. solis: kreisajā pusē esošais saraksts ir sakārtots, lai jūs varētu uzskatīt 5. numuru par vietas numuru un sakārtot to kreisajā sarakstā. Tomēr studentiem ir kaut kas jāatklāj pašiem. Viņiem ir jāizmanto tas, ka arī labajā pusē esošais saraksts ir sakārtots, tāpēc nākamais ievietojamais skaitlis vienmēr ir lielāks nekā pēdējais ievietotais skaitlis.
   ● 5. solis: Kad skolēni vēlas sapludināt otro elementu labajā sarakstā kreisajā sarakstā, viņiem nav atkārtoti jāizpilda vienreizēja ievietošana no galējās kreisās puses, bet vienkārši jāsāk no punkta, kurā viņi ievietoja pēdējo elements.
   IEVĒROJIET 3 PIEMĒRU ATTĒLUS ŠEIT Ņemiet vērā, ka iepriekš norādītajā solī jūs nesākat visus jautājumus no dzeltenā saraksta sākuma, kas tika izdarīts ievietošanas kārtojumā. Tas ir tāpēc, ka mēs zinām, ka nākamais skaitlis, kas jāievieto dzeltenajā sarakstā, jau ir lielāks nekā pēdējais ievietotais skaitlis, jo rozā saraksts jau bija sakārtots. IEVĒROJIET 4 PIEMĒRU ATTĒLUS ŠEIT
9. Pārskatiet aktivitāti Nr. 4 - apvienojiet zemāk esošās kārtošanas instrukcijas ar klasi un aiciniet studentus kārtot ievietošanu.
   4. darbība - kārtošanas instrukciju apvienošana:
   ● 1. solis: nejauši iestatiet sarakstu. Studentiem jāmēģina kārtot sarakstu, izmantojot iepriekšējās zināšanas par divu sarakstu apvienošanu.
   ● 2. solis: sapludināšanas kārtojuma galvenā ideja ir sadalīšanas un iekarošanas princips. Tas ir viens no katra mūsdienu izsmalcinātā šķirošanas algoritma pamatjēdzieniem. Skolēniem katrs skaitlis būs jāuzskata par individuālu šķirotu 1. izmēra sarakstu.
   ● 3. solis: no turienes studenti mēģinās veikt zināmo divu sarakstu apvienošanu sarakstos. Tomēr no pirmā acu uzmetiena tas, ko studenti mēģinās, neatšķirsies no ievietošanas kārtojuma. Viņi vispirms sapludinās divus skaitļus un pēc tam trešo un pēc tam ceturto utt. Būtībā tas ir ievietošanas kārtojums.
   ● 4. solis: apvienošanas kārtība ir šāda:
   ○ No nejaušinātā saraksta katru skaitli uzskatiet par sakārtotu 1. izmēra sarakstu.
   ○ Tad izveidojiet blakus esošo sarakstu pārus un sapludiniet tos, lai tagad mums būtu 4 sakārtoti saraksti, katrs no tiem ir 2. izmērs.
   ○ Pēc tam vēlreiz izveidojiet sarakstu pārus un apvienojiet, lai iegūtu 2 sarakstus, katrs no tiem ir 4 izmēra.
   ○ Viena galīgā apvienošanās, un mēs iegūstam pilnu sakārtotu 8. izmēra sarakstu. Šī pieeja nodrošina, ka tiek atkārtoti samazināti katra atsevišķā skaitļa skaitļi, tāpēc tiek samazināts arī uzdotais jā / nē skaits.
10. Lai iegūtu vairāk satura par šo tēmu, skatiet sadaļu “Rakšana dziļāk”.

Nodarbību var veikt tikai 1 klases periodā vecākiem skolēniem. Tomēr, lai palīdzētu studentiem nejusties sasteigtiem un nodrošinātu studentu panākumus (īpaši jaunākiem skolēniem), sadaliet stundu divos periodos, dodot studentiem vairāk laika domāt par idejām, pārbaudīt idejas un pabeigt to noformējumu. Veiciet pārbaudi un pārskatu nākamajā klases periodā.

Padomi un problēmu novēršana

Visu vingrinājumu laikā studentiem jādod visas iespējas pašiem nākt klajā ar atbildēm. Spēles mērķis ir, lai studenti “izspēlējas” ar problēmu un paši redz, kas darbojas un kas ne. Šis uz atklājumiem balstītās mācīšanās veids ir ārkārtīgi efektīvs, lai attīstītu studentu augsta līmeņa kognitīvās spriešanas un problēmu risināšanas prasmes. Jāveicina arī diskusijas studentu vidū.

Attēlu un diagrammu zīmēšana var būt ļoti efektīva, sazinoties ar šo tēmu ar studentiem. Sadaļā Darbības instrukcijas sniegto grafiku var izmantot kā ceļvedi, kā izdarīt dažādus soļus. Studentus var arī mudināt zīmēt diagrammas, kas attēlo viņu piedāvātos algoritmus un risinājumus.

Ja studentiem ir grūtības sākt darbu, šeit ir daži padomi, kā panākt studentu pareizo ceļu:

• Mudiniet studentus apspriest veicamo uzdevumu. Biežāk studenti netīšām paši izdomā risinājumus, kad “skaļi domā” un pārrunā problēmu un / vai tās risinājumu ar vienaudžiem.
• Sāciet diskusiju, jautājot studentiem par viņu viedokļiem un mudinot studentus ar atšķirīgu viedokli iesaistīties aktīvās diskusijās.
• Piedāvājiet iespējamo risinājumu un pajautājiet studentiem, kas, viņuprāt, notiks, ja tas tiktu izmēģināts. Šāds jautājums, visticamāk, izraisīs jaunu domāšanas procesu studentu prātos un palīdzēs viņiem redzēt, kur viņi nokāpj no sliedēm. Pats jautājums varētu attiekties uz to, ko klase jau apsprieda, vai arī tā varētu būt pilnīgi jauna, bet ne vienmēr pareiza doma. Mērķis nav sniegt pareizu atbildi, bet mudināt studentus novērtēt iespējamos risinājumus un domāt un pamatot sevi.

Efektīvi izmantojiet komandu savstarpējās sacensības. Mēģiniet uzzināt korelāciju starp uzdoto jautājumu skaitu un laiku, kas vajadzīgs saraksta kārtošanai, un to, vai starp uzvarēšanu un mazāk jautājumu uzdošanu pastāv korelācija.

Interneta savienojumi

• Algoritmu animāciju šķirošana

Ieteicamais Reading

• Datorprogrammēšanas māksla, Donalda E. Knuta 3. sējums (ISBN: 0321751043)

Rakstīšanas aktivitāte

Datori parasti tērē aptuveni pilnu ceturtdaļu savas apstrādes jaudas dažādu datu kārtošanai. Piemēram, slimnīcā esošais dators var uzturēt ļoti lielu datu bāzi par visiem pacientiem, kuri kādreiz bijuši slimnīcā ārstēties pēdējo 5 gadu laikā. Dažādi cilvēki slimnīcā varētu vēlēties dažādus pacientu sarakstus. Persona, kas pārvalda slimnīcas finanses, varētu vēlēties pacientu sarakstu, kas sakārtots pēc viņu slimnīcas izmaksām. Pētnieks varētu vēlēties sarakstu, kas sakārtots pēc slimības, ar kuru viņi tika ārstēti. Administrators varētu vēlēties, lai sarakstu pasūtītu ārsts, kurš ārstēja pacientu. Ģenerējot šos sarakstus, datoram dati katru reizi būs jāsakārto no jauna atbilstoši lietotāja vajadzībām. Vai varat iedomāties kādu citu scenāriju, kurā šķirošana ir svarīga? Kādas ir šķiroto datu uzturēšanas priekšrocības salīdzinājumā ar nešķirotajiem datiem? Kādi ir iespējamie trūkumi?

Pielāgošana mācību programmas ietvariem

Piezīme: Šīs sērijas stundu plāni ir saskaņoti ar vienu vai vairākiem no šiem standartu kopumiem:  

• ASV zinātnes izglītības standarti (http://www.nap.edu/catalog.php?record_id=4962)
• ASV nākamās paaudzes zinātnes standarti (http://www.nextgenscience.org/) 
• Starptautiskās tehnoloģiju izglītības asociācijas tehnoloģiskās pratības standarti (http://www.iteea.org/TAA/PDFs/xstnd.pdf)
• ASV Nacionālās matemātikas skolotāju skolu matemātikas principu un standartu padome (http://www.nctm.org/standards/content.aspx?id=16909)
• ASV matemātikas kopējie pamatstandarti (http://www.corestandards.org/Math)
• Datorzinātņu skolotāju asociācijas K-12 datorzinātņu standarti (http://csta.acm.org/Curriculum/sub/K12Standards.html)

Nacionālie zinātnes izglītības standarti K-4 pakāpe (no 4 līdz 9 gadiem)

SATURA A STANDARTS: Zinātne kā izmeklēšana

Aktivitāšu rezultātā visiem studentiem vajadzētu attīstīties

• Zinātniskās izpētes veikšanai nepieciešamās spējas 

SATURA B STANDARTS: Fiziskā zinātne

Aktivitāšu rezultātā visiem studentiem būtu jāattīsta izpratne par

• Objektu un materiālu īpašības 

E SATURA STANDARTS: Zinātne un tehnoloģija 

Aktivitāšu rezultātā visiem studentiem vajadzētu attīstīties

• Tehnoloģiskā dizaina spējas 
• Izpratne par zinātni un tehnoloģiju 

F SATURA STANDARTS: Zinātne personīgajā un sociālajā perspektīvā

Aktivitāšu rezultātā visiem studentiem būtu jāattīsta izpratne par

• Resursu veidi 
• Zinātne un tehnoloģija vietējos izaicinājumos 

G SATURA STANDARTS: Zinātnes vēsture un daba

Aktivitāšu rezultātā visiem studentiem būtu jāattīsta izpratne par

• Zinātne kā cilvēka centieni 

Nacionālie zinātnes izglītības standarti 5. – 8. Klase (vecumā no 10 līdz 14 gadiem)

SATURA A STANDARTS: Zinātne kā izmeklēšana

Aktivitāšu rezultātā visiem studentiem vajadzētu attīstīties

• Zinātniskās izpētes veikšanai nepieciešamās spējas 
• Izpratne par zinātnisko izpēti 

SATURA B STANDARTS: Fiziskā zinātne

Viņu aktivitāšu rezultātā visiem studentiem būtu jāattīsta izpratne par

• Matērijas īpašības un īpašību izmaiņas 

E SATURA STANDARTS: Zinātne un tehnoloģija

5.-8.klašu aktivitāšu rezultātā visiem skolēniem vajadzētu attīstīties

• Tehnoloģiskā dizaina spējas 
• Izpratne par zinātni un tehnoloģiju 

Nacionālie zinātnes izglītības standarti 5. – 8. Klase (vecumā no 10 līdz 14 gadiem) (turpinājums)

F SATURA STANDARTS: Zinātne personīgajā un sociālajā perspektīvā

Aktivitāšu rezultātā visiem studentiem būtu jāattīsta izpratne par

• Riski un ieguvumi 
• Zinātne un tehnoloģija sabiedrībā 

Skolas matemātikas principi un standarti (vecumā no 6 līdz 18 gadiem)

mērīšana

• saprast objektu izmērāmos atribūtus, mērvienības, sistēmas un procesus. 
• mērījumu noteikšanai jāpiemēro piemērotas metodes, rīki un formulas. 

Problēmu risināšana

• veidot jaunas matemātikas zināšanas, izmantojot problēmu risināšanu.
• atrisināt problēmas, kas rodas matemātikā un citos kontekstos.
• pielietot un pielāgot dažādas piemērotas stratēģijas problēmu risināšanai. 
• uzraudzīt un pārdomāt matemātisko problēmu risināšanas procesu. 

savienojumi

• atpazīt un pielietot matemātiku kontekstos ārpus matemātikas.

Pārstāvība

• izveidojiet un izmantojiet attēlojumus matemātisko ideju organizēšanai, reģistrēšanai un saziņai. 
• atlasīt, pielietot un tulkot starp matemātiskiem attēlojumiem, lai atrisinātu problēmas. 

Tehnoloģiskās pratības standarti - visos vecumos

Tehnoloģijas daba

• 1. standarts: Studenti attīstīs izpratni par tehnoloģiju īpašībām un apjomu.
• 3. standarts: Studenti attīstīs izpratni par sakarībām starp tehnoloģijām un saiknēm starp tehnoloģijām un citām studiju jomām.

Tehnoloģija un sabiedrība

• 4. standarts: Studenti attīstīs izpratni par tehnoloģiju kultūras, sociālo, ekonomisko un politisko ietekmi.
• 6. standarts: Studenti attīstīs izpratni par sabiedrības lomu tehnoloģiju attīstībā un izmantošanā.

Dizains

• 9. standarts: Studenti attīstīs izpratni par inženiertehnisko dizainu.

Tehnoloģiskās pratības standarti - visu vecumu (turpinājums)

Tehnoloģiskās pasaules spējas

• 13. standarts: Studenti attīstīs spējas novērtēt produktu un sistēmu ietekmi.

Projektētā pasaule

• 14. standarts: Studenti attīstīs izpratni par medicīnas tehnoloģijām un varēs tās izvēlēties un izmantot.
• 19. standarts: Studenti attīstīs izpratni un spēs izvēlēties un izmantot ražošanas tehnoloģijas.

1. sesija - ievietošanas kārtošana

Tas ir grupas vingrinājums. Pirms sākat, lūdzu, izveidojiet 3-5 studentu grupu.

Viena ievietošana

Izveidojiet 8 kārtis, katrai ar atšķirīgu numuru. Lai viens jūsu grupas students būtu kontrolieris, un pārējiem jāspēlē līdzi. Tikai kontrolierim ir atļauts redzēt numurus.

Kontrolierim ir jāiestata kartes vienreizējai ievietošanai, un pārējām jāspēlē, lai kārtotu sarakstu. Dariet to vismaz 5 reizes un aizpildiet zemāk esošo tabulu.

Pamatojoties uz iepriekš ievadīto informāciju, atbildiet uz šādiem jautājumiem:

1. Cik vidēji vienā kārtā tiek uzdoti jautājumi?

______________________

2. Pieņemsim, ka jums bija jāaizpilda iepriekš redzamā tabula par 5000 atsevišķiem ievietojumiem. Kāda, jūsuprāt, būtu lielākā iespējamā vērtība otrajā ailē (jā / nē uzdoto jautājumu skaits)?

______________________

3. Pieņemsim, ka jūs strādājāt ar 10 numuru sarakstu, nevis 8. Kāda būtu jūsu atbilde uz otro jautājumu tādā gadījumā?

______________________

4. Vai tagad varat saistīt saraksta lielumu ar sliktākajā gadījumā uzdoto jautājumu skaitu? Sniedziet ļoti īsu atbildi par to, kā jūs domājat saraksta lielumu un sliktākajā gadījumā uzdotajiem jautājumiem (atcerieties, jo mazāks jautājumu skaits, jo labāk. Tātad, sakot “sliktākais gadījums”, mēs domājam pēc iespējas lielāku skaitu no uzdotajiem jautājumiem)

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

Ievietošanas kārtojums

Tagad ar šīm pašām kartēm spēlējiet spēli Insertion Sort. Atcerieties sākt ar pilnīgi nejaušu sarakstu.

Veiciet ievietošanu Kārtot vismaz 5 reizes un aizpildiet zemāk esošo tabulu. Pirms kārtošanas kontrolierim jāreģistrē trešā kolonna un pēc saraksta sakārtošanas tā jāatklāj.

Pamatojoties uz iepriekš ievadīto informāciju, atbildiet uz šādiem jautājumiem:

1. Cik vidēji vienā kārtā tiek uzdoti jautājumi?

______________________

2. Jums noteikti jāsaprot, ka ievietošanas kārtojums ir tikai atsevišķu ievietojumu sērija. Sniedziet ļoti īsu atbildi par to, kā jūs saistītu atsevišķu ievietojumu skaitu ar kārtojamā saraksta lielumu.

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

3. Atcerieties savu atbildi uz 2. jautājumu, izmantojot uzdevumu Vienreizēja ievietošana. Izmantojiet šo atbildi, lai aprēķinātu to jautājumu skaitu, kas “sliktākajā gadījumā” būtu jāuzdod sadaļā Ievietošanas kārtošana. Parādiet savas darbības.

Galīgā atbilde: __________________

4. Šķiršanas mačā dodieties aci pret aci ar citu grupu, lai redzētu, kurš var ātrāk kārtot nejaušinātu sarakstu. Taisnīguma labad no katras komandas būs viens kontrolieris. Būtu stingri jāievēro spēles noteikumi, taču jūs varat izmantot jebkuru vēlamo procedūru.

Uzdoto jautājumu skaits: _______________________

Jautājumu skaits, ko jūsu pretinieks uzdeva: _______________________

Vai tu uzvarēji? _______________________

2. sesija - apvienot šķirošanu

Tas ir grupas vingrinājums. Pirms sākat, lūdzu, izveidojiet 3-5 studentu grupu.

Divu sarakstu apvienošana

Izveidojiet 8 kārtis, katrai ar atšķirīgu numuru. Lai viens jūsu grupas students būtu kontrolieris, un pārējiem jāspēlē līdzi. Tikai kontrolierim ir atļauts redzēt numurus.

Kontrolierim jāiestata kartes divu saraksta apvienošanai, bet pārējām jāspēlē, lai kārtotu sarakstu. Dariet to vismaz 5 reizes un aizpildiet zemāk esošo tabulu.

Pamatojoties uz iepriekš ievadīto informāciju, atbildiet uz šādiem jautājumiem:

1. Cik vidēji vienā kārtā tiek uzdoti jautājumi?

______________________

2. Pieņemsim, ka jums bija jāaizpilda iepriekš redzamā tabula par 5000 divu sarakstu apvienošanu. Kāda, jūsuprāt, būtu lielākā iespējamā vērtība otrajā kolonnā (jā / nē uzdoto jautājumu skaits)?

______________________

3. Pieņemsim, ka jūs strādājāt ar 10 numuru sarakstu, nevis 8. Kāda būtu jūsu atbilde uz otro jautājumu tādā gadījumā?

______________________

4. Tagad atgriezieties un apskatiet atbildes, ko sniedzāt par vingrinājumu Vienreizēja ievietošana. Kādas līdzības jūs redzat? Kādas atšķirības? Kā skaitļi atšķiras? Vai tie nedaudz atšķiras, vai arī tie daudz atšķiras? Pierakstiet savas domas par to.

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

__________________________________________________________________

Apvienot Kārtot

Tagad ar tām pašām kartēm spēlējiet sapludināšanas kārtojumu. Atcerieties sākt ar pilnīgi nejaušu sarakstu.

Veiciet sapludināšanu Kārtot vismaz 5 reizes un aizpildiet zemāk esošo tabulu. Pirms kārtošanas kontrolierim jāreģistrē trešā kolonna un pēc saraksta sakārtošanas tā jāatklāj.

Pamatojoties uz iepriekš ievadīto informāciju, atbildiet uz šādiem jautājumiem:

1. Cik vidēji vienā kārtā tiek uzdoti jautājumi?

______________________

2. Jums noteikti jāsaprot, ka sapludināšanas kārtojums ir tikai divu sarakstu apvienošanos sērija. Cik divu sarakstu apvienošanās jūs veicāt, lai sapludinātu Kārtot 8 skaitļu sarakstu?

______________________

3. Atcerieties savu atbildi uz 2. jautājumu, izmantojot vingrinājumu Divu sarakstu apvienošana. Izmantojiet šo atbildi, lai aprēķinātu to jautājumu skaitu, kas “sliktākajā gadījumā” būtu jāuzdod Merge Sort. Parādiet savas darbības.

Galīgā atbilde: __________________

4. Šķiršanas mačā dodieties aci pret aci ar citu grupu, lai redzētu, kurš var ātrāk kārtot nejaušinātu sarakstu. Taisnīguma labad no katras komandas būs viens kontrolieris. Būtu stingri jāievēro spēles noteikumi, taču jūs varat izmantot jebkuru vēlamo procedūru.

Uzdoto jautājumu skaits: _______________________

Jautājumu skaits, ko jūsu pretinieks uzdeva: _______________________

Vai tu uzvarēji? _______________________

Nodarbības plāna tulkošana

[valodas mainītājs]