Teorie vyčíslitelnosti a složitosti

UI/N1018

vyučován v zimním semestru | časová náročnost je 2 hodiny přednášek 2 hodiny cvičení týdně | lze za něj získat 6 kreditů

podmíněn předměty: Teorie jazyků a automatů II

přednáší doc. Ing. Petr Sosík Dr.
cvičení vede RNDR. Miroslav Langer Ph.D.

náročnost: rating_star_narocnostrating_star_narocnostrating_star_narocnost | užitečnost: rating_star_uzitecnostrating_star_uzitecnostrating_star_uzitecnost | zábavnost: rating_star_zabavnostrating_star_zabavnostrating_star_zabavnost

Průběh v jednotlivých letech

Popis bude doplněn co nejdříve.

Udělení zápočtu je podmíněno 75% účastí na cvičeních, získáním 50% možných bodů ze dvou písemek (v součtu)(v roce 2015 byl počet redukován na jednu písemku, šlo však o výjimečné okolnosti) a vypracováním projektu - Turingova stroje podle stanoveného zadání. To je přiděleno poté, co si studentem vytvoří účet v odpovídajícím kurzu na e-learningu, kde se také dozví jeho znění a kam bude nahrán výsledný projekt. Samotná zkouška pak probíhá písemnou formou a řada otázek (ne však všechny) je pojata ve stylu „napiš, vše co o daném tématu víš“.

Přínos předmětu

Text bude doplněn co nejdříve.

Materiály

základní

o kategorii

ikonka pdfskripta - základní19.ledna 2016, 20:06skripta - základní ke stažení849.02 KB
ikonka pdfskripta - Černá19.ledna 2016, 20:06skripta - Černá ke stažení3.83 MB
ikonka pdfskripta - Wiederman19.ledna 2016, 20:07skripta - Wiederman ke stažení510.69 KB
ikonka pdfmateriály ke cvičením19.ledna 2016, 20:07materiály ke cvičením ke stažení460.14 KB
ikonka zipsimulátor Turingova stroje20.ledna 2016, 16:05simulátor Turingova stroje ke stažení740.85 KB
ikonka pptDoplňující materiály4.února 2016, 13:26Doplňující materiály ke stažení1.37 MB

vytvořené

o kategorii

ikonka pdfvyřešené příklady ze skript ke cvičením19.ledna 2016, 20:34vyřešené příklady ze skript ke cvičením ke stažení480.56 KB
ikonka docxvyřešená 1. zápočtová písemka19.ledna 2016, 20:35vyřešená 1. zápočtová písemka ke stažení40.17 KB
ikonka docxvyřešená 2. zápočtová písemka19.ledna 2016, 20:36vyřešená 2. zápočtová písemka ke stažení38.09 KB
ikonka docxvyřešená zkoušková písemka19.ledna 2016, 20:37vyřešená zkoušková písemka ke stažení34.82 KB
ikonka docxvyřešená zkoušková písemka19.ledna 2016, 20:37vyřešená zkoušková písemka ke stažení117.69 KB

Projekty

o kategorii

ikonka zipsoubor Turingových strojů
rok: 2015-2016soubor Turingových strojů - náhled
vyučující: doc. Ing. Petr Sosík Dr.
popis:
zahranuje Turingovy stroje:
  • - přijímající jazyk L={a^i b^2i c^3i; i >= 0}
  • - přijímající jazyk L={w w^R w; kde w = {a,b}*}
  • - přijímající jazyk L={w w^R w^R; kde w = {a,b}*}
  • - počítající liché výskyty slova PIVO v textovém řetězci
  • - počítající logaritmus čísla v unární soustavě
  • - počítající podíl dvou čísel zadaných v dekadické soustavě
  • - počítající podíl dvou čísel zadaných v binární soustavě
  • - rozpoznávající mocniny dvou
  • - rozpoznávající násobky dvou
  • - počítající faktoriál
  • - počítající součet dvou čísel v unární soustavě
  • - počítající součin dvou čísel v unární soustavě
  • - přijímající jazyk 1^n = 1^i; i = 1 + 2 + ... + n
  • - přijímající jazyk 1^n = 1^i; i = 1^2 + 2^2 + ... + n^2
  • - přijímající jazyk 1^x = 1^y; y je celočíselná číst odmocniny z x
  • - přijímající jazyk L= 1^(x^4 - 4x + 3); x = 0,1,...
  • - přijímající jazyk L=1^y; y=2^x, x = 0,1,...
odkaz ke stažení:soubor Turingových strojů ke stažení
aktualizováno: 19.ledna 2016, 18:42