TÖL301G Formleg mál og reiknanleiki, haust 2016
Yfirlit yfir námskeið
Í námskeiðinu verður fjallað um ýmsar grunnhugmyndir í tölvunarfræði með það að markmiði að skilja betur hvers konar verkefni hægt sé að leysa með tölvum og hvaða eðlislægu takmarkani gilda um þær. Við sögu koma einföld líkön af reiknivélum eins og stöðuvélar, mállýsingar, staflavélar, reglulegar segðir og Turingvélar. Innbyrðis tengsl þessara líkana verða skoðuð auk þess sem fjallað verður um hagnýtingu þeirra við textaleit, í forritunarmálum og víðar. Leitað verður svara við því hvers vegna sum verkefni eru auðveld, önnur torleyst og enn önnur óleysanleg með því að skoða ákvarðanleika, yfirfærslur og flækjustigsflokkana P, NP auk NP-fullkominna verkefna.
Forkröfur: Nemandi þarf að hafa staðist próf í Stærðfræðimynstrum í tölvunarfræði (TÖL104G). Gerðar verða undanþágur fyrir nemendur sem hafa mjög sterkan grunn í stærðfræði auk nemenda sem hafa lokið B.Sc. gráðu í öðru fagi og eru að bæta við sig gráðu í tölvunarfræði.
Eftir að hafa lokið námskeiðinu á nemandi- að kunna skil á því hvernig flokka megi formleg mál með tilvísun til stöðuvéla og mállýsinga og geta formlega dregið af því ályktanir um helstu eiginleika þeirra.
- að geta rökstutt formlega hvers vegna sum reikniverkefni eru í eðli sínu flóknari en önnur og sum þeirra óleysanleg.
- að kunna skil á helstu líkönum fyrir reiknanleika, eðlislægum takmörkunum þeirra, og því hvernig herma megi eitt líkan með öðru.
Námsáætlun
Tölur innan sviga vísa til greina í kennslubók.
| Vika | |
| 1 | Kynning á námskeiði, mál (0.2) og löggengar stöðuvélar (1.1) |
| 2 | Brigðgengar stöðuvélar (1.2) |
| 3 | Reglulegar segðir (1.3) |
| 4 | Óregluleg mál og dælusetningin (1.4) |
| 5 | Samhengisfrjálsar mállýsingar (2.1) |
| 6 | Staflavélar (2.2) |
| 7 | Turingvélar og Church-Turing tilgátan (3.1 - 3.3) |
| 8 | Ákvarðanleiki (4.1, 4.2) |
| 9 | Yfirfærsla verkefna (5.1, 5.3) |
| 10 | Tímaflækja (7.1), flækjuflokkarnir P og NP (7.2, 7.3) |
| 11 | NP-fullkomin verkefni (7.4) |
| 12 | NP-fullkomin verkefni frh. (7.4, ítarefni) |
| 13 | Valin efni úr flækjufræði (10. kafli, ítarefni) |
| 14 | Samantekt námsefnis og umræður um próf |
Kennslubók:
Introduction to the Theory of Computation eftir Michael Sipser, 3. útgáfa, CENGAGE Learning, 2013. Bókin fæst í Bóksölu stúdenta.
Námstilhögun
Fyrirlestrar:- Þriðjudagar 15:50 - 18:10 í HT-104.
Í fyrirlestrum verða lögð fyrir stutt verkefni sem nemendur skila í lok tímans. Dæmatímar verða einu sinni í viku, tvisvar 40 mínútur í senn. Í tímunum verða lögð fyrir dæmi sem nemendur leysa með aðstoð kennara og skila í lok tímans. Nemendur mega vinna saman að lausn þessara verkefna. Þið veljið ykkur dæmahóp á Piazza (sjá neðar). Heimaverkefni verða lögð fyrir á þriðjudögum og á að skila þeim á þriðjudeginum viku síðar.
Aðalkennari:- Steinn Guðmundsson (steinng@hi.is). Aðsetur: Herbergi 212 í Tæknigarði (sími 525 4738).
Námsmat
Samanlögð einkunn tíu bestu heimaverkefna (af 13) gildir sem 30% af lokaeinkunn. Samanlögð einkunn 10 bestu dæmatímaverkefna (af 13) gildir 10% og lokapróf gildir 60%. Fyrirlestraverkefni (10 bestu af 13) gilda 10% til upphækkunar. Þó verður að ná einkunninni 5 á lokaprófinu einu sér, auk þess að ná þeirri einkunn samanlagt, til þess að standast námskeiðið.
Engin hjálpargögn eru heimiluð í prófinu. Það er ekki mætingarskylda í fyrirlestra eða dæmatíma en til að öðlast próftökurétt í námskeiðinu þarf nemandi að hafa skilað a.m.k. 3 heimaverkefnum í viku 8 og hlotið að lágmarki 4.0 í meðaleinkunn fyrir 3 bestu verkefnin. Þeir sem ekki uppfylla þetta skilyrði verða sjálfkrafa skráðir úr námskeiðinu í lok 8. viku.
Námskeiðsvefur
Kennarar setja tilkynningar og svara almennum fyrirspurnum um námskeiðið á vef sem kallast Piazza. Heimadæmi (og e.t.v. skýringar við þau), efni úr fyrirlestrum, ítarefni og lausnir á völdum dæmum fara líka á Piazza. Mikilvægt er því að skoða vefinn reglulega.
Nemendur skrái sig á piazza.com/hi.is/fall2016/tol301g. Fyrst þarf að velja ''Fall 2016'', haka við "Join as Student" í TOL 301G, smella á "Join Classes" og loks gefa upp HÍ tölvupóstfang (sendið póst á steinng@hi.is ef þið lendið í vandræðum með skráningu).
Samvinna nemenda og skil heimadæma
Nemendur eru hvattir til þess að ræða saman um námsefnið sín á milli, t.d. með því að hittast reglulega í 2ja - 4ra manna hópum. Þeir nemendur sem vinna að lausn heimadæma með öðrum þurfa alltaf að skrifa upp og skila inn sinni eigin lausn. Þeir þurfa ennfremur að tilgreina með hverjum var unnið að lausn verkefnisins.
Það er óheimilt að fá lausnir hjá öðrum, afrita lausnir eða láta aðra fá lausnina sína. Ef kennarar verða varir við afritaðar lausnir munu þeir lækka einkunn fyrir viðkomandi verkefni. Hikið ekki við að leita til aðalkennara ef þið eruð í vafa um hvað telst eðlileg samvinna og hvað ekki.
Lausnir á heimaverkefnum eiga að vera læsilegar og þær á að merkja nafni nemanda og númeri dæmahóps. Ekki verður tekið við illlæsilegum eða hroðvirknislega unnum lausnum og ekki er tekið við lausnum sem berast of seint.
Ef nemandi telur að mistök hafi verið gerð við yfirferð verkefnis getur hann beðið um endurmat á því. Í slíkum tilvikum þarf að skrifa stutta lýsingu á því hvað nemandinn telji vera rangt gert í yfirferð, hefta skýringuna við verkefnið og skila til dæmakennara. Frestur til að gera athugasemdir er ein vika frá því að að yfirförnu verkefni var skilað til baka.