Stærðfræðimynstur í tölvunarfræði

Vikublað 12

Í næstu viku verður farið í ýmis reiknilíkön úr kafla 11.

Hér að neðan eru 5 skiladæmi sem þið eigið að skila í hólf dæmatímakennara ykkar fyrir hádegi mánudaginn 21. nóvember. Munið að merkja skilin ykkar með númeri dæmahóps og nafni dæmatímakennara. Auk þess eru nokkur dæmi í viðbót sem þið ættuð að nota til að æfa ykkur og fullvissa ykkur um að þið skiljið efni. Farið verður í einhver af þeim í dæmatímunum eftir því sem tími vinnst til.

Skiladæmi 11

1. Dæmi 38 í kafla 8.3 á bls. 565 í kennslubók.
   [Þýðing: Ákvarðið hvort gefin pör af netum séu einsmóta. Sýnið fram á einmótun með falli eða gefið góðan rökstuðning fyrir því að netin séu ekki einsmóta. ]

2. [Próf 2004] Gefið er netið hér að neðan: Á hve marga vegu má merkja hnútana með bókstöfunum a, b, c, d og e þannig að netin séu einsmóta (e. isomorphic), en ekki sama netið? Með öðrum orðum, hversu mörg ólík merkt net eru sammóta netinu að ofan? Útskýrið hvernig þið reiknið út töluna.

3. Dæmi 36 í kafla 8.5 á bls. 590 í kennslubók. Hvað með Hamilton veg?
   [Þýðing: Ákvarðið hvort gefið net hafi Hamilton hring. Ef það hefur Hamilton hring sýnið hann. Ef það hefur ekki Hamilton hring rökstyðjið þá að slíkur hringur er ekki í netinu. ]

4. Dæmi 16 í aukadæmum fyrir kafla 8 á bls. 626 í kennslubók.
   [Þýðing: Yfirgnæfumengi hnúta í einföldu neti er mengi hnúta þannig að sérhver annar hnútur hefur stiku yfir í a.m.k. einn hnút í þessu mengi. Yfirgnæfumengi með minnsta fjölda hnúta er kallað minnsta yfirgnæfumengi. Finnið minnsta yfirgnæfumengi í netinu á myndinni. ]

5. Dæmi 18 í kafla 9.1 á bls. 643 í kennslubók.
   [Þýðing: Hve marga hnúta hefur fullt 5-undar tré með 100 innri hnúta? ]

Skilið þessum dæmum fyrir hádegi mánudaginn 21. nóvember.

Úr kafla 8.4:

5, 9, 25, 31, 35.

Úr kafla 8.5:

3, 7, 11, 33, 45.

Úr kafla 9.1:

3, 11, 21, 27.

Munið að dæmin að ofan eru æfingadæmi og að þið græðið mest á því að reyna að leysa þau sjálf (en ekki að horfa á einhvern annan leysa þau!). Feitletruðu dæmin eru "athyglisverðari" en hin og líklegra að farið verði í þau í dæmatímunum.