Přikládám čtyři otázky z první části zkoušky.
Ve druhé části byl zadaný n-regulární hypergraf s m vrcholy takový, že každá dvojice hyperhran měla v průniku max. jeden vrchol a a) jsme chtěli najít validní obarvení takového hypergrafu a b) jsme chtěli všechny takové n-regulární hypergrafy na m vrcholech generovat. Měla se použít nějaká heuristika.
První část zkoušky:
Otázka 1)
Sestavte predikát termy/1, který postupně vrací termy složené z funktorů bin/2, un/1 a const/0. Výstupem bude tedy korektně sestavený term. Predikát by měl postupně vrátit všechna řešení, sice v libovolném pořadí, ovšem každé právě jednou.
termy(V).
V=const;
V=un(const);
V=bin(const,const);
V=un(un(const));
V=un(bin(const,const));
V=bin(un(const),un(const));
atd.
Otázka 2)
Multimnožinu lze specifikovat seznamem termů Prvek-Pocet. Sestavte predikát mensi/2, který porovná multimnožiny A a B následovně: mensi(A,B) je True právě tehdy, pokud v B existuje nějaký prvek, co není v A takový, že je větší než všechny prvky z A, které nejsou v B.
mensi([c-3,b-2,a-1],[d-1,b-3]) True
mensi([c-3,b-2,a-1],[c-1,b-3]) False
Otázka 3)
Navrhněte datový typ Graf a pro reprezentaci konečného neorientovaného grafu s vrcholy typu a.
Definujte funkci troj::Graf a -> Int, která k takovému grafu vrátí počet všech jeho trojúhelníků.
Otázka 4)
Dán datový typ
data Bag a = Item a | Items [Bag a]
a) Definujte funkci
fold :: (a->b) -> (->b) -> Bag a -> b
pro obecný průchod touto datovou strukturou (to (a->b) tam zastupuje počáteční hodnotu v normálním foldu)
b) Pomocí funkce fold definujte funkci
listy::Bag a -> [a]
která posbírá všechny hodnoty z položek Item ze všech úrovní zleva doprava
listy (Items [Item 1,Items [Item 2, Item 3], Items [Items [Item 4]]])
[1,2,3,4]
ŘEŠENÍ:
% abychom opravdu nagenerovali kazdy term, tak budeme postupne generovat vsechny termy velikosti 1, pak velikosti 2,3, atd.
termy(V) :- termy(V,1).
termy(V,N) :-
stejnevelke(V,N).
termy(V,N) :-
NN is N+1,
termy(V,NN).
%velikost 1 ma jen konstantni term
stejnevelke(const,1).
% pro velikost aspon dva generujeme termy s vnejsim funktorem un
stejnevelke(un(T),N) :-
N>1,
NN is N-1,
stejnevelke(T,NN).
% pro velikost aspon tri generujeme termy s vnejsim funktorem bin, vnitrni termy nabyvaji v souctu velikosti N-1
stejnevelke(bin(T1,T2),N) :-
N>2,
NN is N-2,
vsechnacislado(NN,Cisla),
member(M,Cisla),
O is N-1-M,
stejnevelke(T1,M),
stejnevelke(T2,O).
%vygeneruje seznam vsech cisel od 1 do N
vsechnacislado(1,[1]).
vsechnacislado(N,[N|List]) :-
N>1,
NN is N-1,
vsechnacislado(NN,List).
%nejprve spocitame rozdil seznamu, nasledne v obou rozdilech najdeme nejvetsi prvek a ty nakonec porovname
mensi(A,B) :-
rozdil(A,B,R1),
rozdil(B,A,R2),
nejvetsi(R1,MA),
nejvetsi(R2,MB),
MB@>MA.
%rozdil(+A,+B,-Res), rozdil obsahuje prvky, co jsou v A a ne v B (uz nepotrebujeme jejich pocty)
rozdil([], _, []).
%B neobsahuje prvni prvek z A, pridame ho tedy do vysledku
rozdil([K-_|T], B, [K|Res]) :-
\+ member(K-_, B),
rozdil(T,B,Res).
%B obsahuje prvni prvek z A, ale je ho tam mene -- stejne jako v predchozim pripade prvek pridame do vysledku
rozdil([K-APocet|T], B, [K|Res]) :-
member(K-BPocet, B),
APocet>BPocet,
rozdil(T,B,Res).
%B obsahuje prvni prvek z A a je ho tam aspon tolik, co v A
rozdil([K-APocet|T], B, Res) :-
member(K-BPocet, B),
APocet=<BPocet,
rozdil(T,B,Res).
% ze seznamu termu vybereme ten nejvetsi
nejvetsi([],0). %tady by se hodilo mit term, ktery je v @usporadani nejmensi; jestlize takovy neexistuje, porad by se to dalo pro neprazdne seznamy zachranit tim, ze rekurzi ukoncime na jednoprvkovych seznamech, tedy pridame nejvetsi([A],A).
nejvetsi([H|T], Res) :-
nejvetsi(T,Ress),
maximum(H,Ress,Res).
maximum(T1,T2,T1) :- T1 @>= T2.
maximum(T1,T2,T2) :- T1 @< T2.
data Graf a = G ([a], [(a,a)]) -- dvojice obsahuje seznam vrcholu typu a a pak seznam hran, kde kazda hrana je dvojice acek
troj :: Eq a => Graf a -> Int
troj g = troj' 1 1 1 g
troj' ::Eq a => Int -> Int -> Int -> Graf a -> Int -- dostane tri vrcholy (rsp. indexy do seznamu vrcholu) a vrati pocet trojuhelniku takovych, ze jejich tri vrcholy jsou v seznamu vrcholu grafu lexikograficky >= teto trojici (pro ty tri promenne plati nerovnosti u<=v<=w, specialne kazdy trojuhelnik zapocitame prave jednou)
troj' u' v' w' (G (vrcholy, hrany)) =
let
n=length vrcholy
u=last $ take u' vrcholy
v=last $ take v' vrcholy
w=last $ take w' vrcholy
tentotrojuhelnik = if ((obsahujehranu (u,v) hrany) && (obsahujehranu (w,v) hrany) && (obsahujehranu (u,w) hrany)) then 1 else 0 -- podivame se, zda stavajici vrcholy tvori trojuhelnik
in tentotrojuhelnik +
(if (u'==n)
then 0
else (
if (v'==n)
then (troj' (u'+1) (u'+1) (u'+1) (G (vrcholy, hrany)))
else (
if (w'==n)
then (troj' u' (v'+1) (v'+1) (G (vrcholy, hrany)))
else (troj' u' v' (w'+1) (G (vrcholy, hrany))))))
-- podle toho, ktere promenne jsou uz na konci se zeptame na trojici, ktera nasleduje lexikograficky za tou aktualni
obsahujehranu :: Eq a => (a,a) -> [(a,a)] -> Bool -- vrati, zda seznam obsahuje zadanou hranu
obsahujehranu e [] = False
obsahujehranu (u,v) ((x,y):r) = if ((u==x && v==y) || (u==y && v==x)) then True else (obsahujehranu (u,v) r)
data Bag a = Item a | Items [Bag a]
fold :: (a->b) -> (->b) -> Bag a -> b
fold f1 f2 (Item x) = f1 x -- v listu aplikujeme f1
fold f1 f2 (Items l) = f2 (map (fold f1 f2) l) -- ve vnitrnich vrcholech na syny rekurzivne mapujeme fold a vysledky skladame funkci f2
listy :: Bag a -> [a]
listy t = fold (\x -> [x]) (foldl (++) []) t -- v listech vyrobime singletonovy seznam, ve vnitrnich vrcholech spojujeme seznamy do kupy, foldl je klasicky fold pro seznamy
Zkouška 29.5.2017
Přednáška je věnována neprocedurálnímu programování. Většina semestru je věnována programování v jazyku Prolog, ve kterém studenti i ladí zápočtové programy. Informativně se studenti seznámí i s jazykem LISP a neprocedurálními částmi programovacích systémů.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 5
- Registrován: 25. 1. 2017 16:34
- Typ studia: Informatika Bc.
Zpět na „PRG005 Neprocedurální programování“
Přejít na
- Aktuální informace
- ↳ Studijní oddělení
- ↳ Knihovna
- ↳ Studentská komora Akademického senátu (SKAS)
- ↳ Volby na ak. rok 2013/2014
- Všichni
- ↳ Práce
- ↳ Klubovna
- ↳ Toto fórum
- ↳ Státní závěrečná zkouška
- ↳ Bakalářské SZZ
- ↳ Magisterské SZZ
- ↳ Info for foreign students
- ↳ Akce
- ↳ Fotbalový turnaj 2008
- Informatika ZS
- ↳ Výuka ZS 1. ročník
- ↳ DMI002 Diskrétní matematika
- ↳ 2007
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ MAI054 Matematická analýza I
- ↳ 2007
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ MAI057 Lineární algebra I
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ PRG030 Programování I
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ SWI120 Principy počítačů a operačních systémů
- ↳ SWI087 Principy počítačů
- ↳ Ostatní
- ↳ DMI051 Úvod do řešení problémů kombinatorických, mat. i jiných (IPS) II
- ↳ Výuka ZS 2. ročník
- ↳ MAI056 Matematická analýza III
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ OFY016 Fyzika pro nefyziky I - Svět kolem nás
- ↳ SWI089 Ochrana informace I
- ↳ SWI096 Internet
- ↳ TIN061 Algoritmy a datové struktury II
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ Ostatní
- ↳ Aplikační software
- ↳ NPRG035 Jazyk C# a platforma .NET
- ↳ NPRG041 Programování v C++
- ↳ AIL062 Výroková a predikátová logika
- ↳ 2007
- ↳ 2006
- ↳ 2005
- ↳ PGR013 Java
- ↳ MAI059 Pravděpodobnost a statistika
- ↳ Výuka ZS 3. ročník
- ↳ SWI099 Administrace Systemu Windows
- ↳ SWI015 Programování v Unixu
- ↳ SWI098 Principy překladačů
- ↳ 2006
- ↳ Ostatní
- ↳ DBI007 Organizace a zpracování dat I
- ↳ 2006
- ↳ MAI062 Algebra I
- ↳ PGR003 Počítačová grafika I
- ↳ SWI090 Počítačové sítě I
- ↳ Výuka ZS NMgr.
- ↳ TIN066 Datové struktury I
- ↳ TIN062 Složitost I
- ↳ TIN064 Vyčíslitelnost I
- ↳ MAI060 Pravděpodobnostní metody
- ↳ SWI004 Operační systémy
- ↳ SWI106 Administrace Unixu
- ↳ Ostatní
- ↳ NTIN090 Základy složitosti a vyčíslitelnosti
- ↳ OPT042 Programování s omezujícími podmínkami
- ↳ AIL002 Neuronové sítě
- ↳ AIL025 Evoluční algoritmy I
- ↳ AIL069 Umělá inteligence I
- ↳ NDBI001 Dotazovací jazyky I
- ↳ TIN070 Testování software
- ↳ NDBI027 Datové sklady a analytické metody pro Business Intelligence
- ↳ NDBI034 Vyhledávání multimediálního obsahu na webu
- ↳ NPRG023 Softwarový projekt
- Informatika LS
- ↳ Výuka LS 1. ročník
- ↳ MAI055 Matematická analýza II
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ MAI058 Lineární algebra II
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ PRG031 Programování II
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ TIN060 Algoritmy a datové struktury I
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ SWI095 Úvod do UNIXu
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ Ostatní
- ↳ Výuka LS 2. ročník
- ↳ SWI071 Ochrana informace II
- ↳ TIN071 Automaty a gramatiky
- ↳ PRG033 Ročníkový projekt - specifikace
- ↳ DMI011 Kombinatorika a grafy I
- ↳ DBI025 Databázové systémy
- ↳ Ostatní
- ↳ SWI036 Programování pro Windows I & II
- ↳ SWI096 Internet
- ↳ PRG005 Neprocedurální programování
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ NSWI143 Architektura počítačů
- ↳ Výuka LS 3. ročník
- ↳ Ostatní
- ↳ PGR004 Počítačová grafika II
- ↳ PRG036 Technologie XML
- ↳ SZZ026 Bakalářská práce
- ↳ PRG003 Metodika programování a filozofie programovacích jazyků
- ↳ MAI064 Matematické struktury
- ↳ MAI042 Numerická matematika
- ↳ SWI021 Počítačové sítě II
- ↳ SWI045 Rodina protokolů TCP/IP
- ↳ NPRG038 Pokročilé programování pro .NET
- ↳ Výuka LS NMgr.
- ↳ SWI109 Konstrukce překladačů
- ↳ NPRG042 Programování v paralelním prostředí
- ↳ SWI117 Technologie vývoje webových aplikací
- ↳ SWI026 Softwarové inženýrství
- ↳ MAI061 Metody matematické statistiky
- ↳ I1 Ostatní Teoretická informatika
- ↳ I2 Ostatní Softwarové systémy
- ↳ I3 Ostatní Matematická lingvistika
- ↳ I4 Ostatní Diskrétní modely a algoritmy
- ↳ AIL026 Evoluční algoritmy II
- ↳ AIL070 Umělá inteligence II
- ↳ NDBI010 Dokumentografické informační systémy
- ↳ NDBI023 Dobývání znalostí
- ↳ NDBI016 Transakce
- ↳ NDBI006 Dotazovací jazyky II
- ↳ NAIL029 Strojové učení
- Matematika
- ↳ Výuka LS 1. ročník
- ↳ Lineární algebra 2
- ↳ Programování 2
- ↳ Matematická analýza 1b
- ↳ Volitelné předměty
- ↳ Výuka LS 2. ročník
- ↳ Pravděpodobnost a statistika
- ↳ Teorie Míry a integrálu II
- ↳ Algebra II
- ↳ Matematická analýza 2b
- ↳ Ostatní
- ↳ Výuka LS 3. ročník
- ↳ Předměty numeriky
- ↳ Úvod do funcionální analýzy
- ↳ Funkcionální analýza I
- ↳ Vybrané partie z funkcionální analýzy
- ↳ Náhodné procesy 2
- ↳ Matematická statistika 2
- ↳ Teorie pravděpodobnosti 2
- ↳ Matematická ekonomie
- ↳ Ostatní
- ↳ LS - Předměty MMIB a pokročilé Algebry
- ↳ Všeobecná diskuse
- ↳ Počítačová algebra
- ↳ Teorie čísel a RSA
- ↳ Aplikovaná kryptografie II
- ↳ Standardy v kryptografii
- ↳ Kryptoanalytické útoky
- ↳ Aplikace bezpečnostních mechanismů
- ↳ Kvantové a DNA počítače
- ↳ Faktorizace velkých čísel
- ↳ Algebraická geometrie v kladné charakteristice
- ↳ Výuka ZS 1. ročník
- ↳ MAA001 Matematická analýza 1a
- ↳ PRM044 Programování I
- ↳ MAA079 Proseminář z kalkulu 1a
- ↳ DMA005 Diskrétní matematika
- ↳ ALG001 Lineární algebra a geometrie I
- ↳ Ostatní
- ↳ Volitelné předměty
- ↳ Výuka ZS 2. ročník
- ↳ MIB
- ↳ Matematická analýza 2a
- ↳ Teorie míry a integrálu
- ↳ Numerika
- ↳ Algebra
- ↳ Předměty finanční matematiky
- ↳ Ostatní
- ↳ Výuka ZS 3. ročník
- ↳ Matematická statistika
- ↳ Teorie pravděpodobnosti
- ↳ Náhodné procesy
- ↳ Optimalizace
- ↳ Předměty numeriky
- ↳ Předměty finanční matematiky
- ↳ Komplexní analýza
- ↳ Funcionální analýza
- ↳ Ostatní
- ↳ ZS - předměty MMIB a pokročilé Algebry
- ↳ Úvod do algebry
- ↳ Složitost pro kryptografii
- ↳ Samoopravné kódy
- ↳ Teoretická kryptografie
- ↳ Aplikovaná kryptografie I
- ↳ Datové a procesní modely
- ↳ Eliptické křivky
- ↳ Členění kryptografických standardů
- ↳ Kryptografické protokoly
- ↳ Úvod do teorie grup
- ↳ Právní aspekty zabezpečení dat
- ↳ Komutativní okruhy
- Fyzika ZS
- ↳ Výuka ZS 1. ročník
- ↳ OFY067 Fyzika v experimentech I
- ↳ MAF027 Lineární algebra I
- ↳ OFY021 Fyzika I (mechanika a molekulová fyzika)
- ↳ OFY056 Programování pro fyziky
- ↳ MAF033 Matematická analýza I
- Oborový mix aktuální
- ↳ Anglický jazyk
- ↳ Tělesná výchova
- ↳ Granty GAUK
- Odkazy
- ↳ Wiki
- ↳ SKAS
- ↳ Spolek Matfyzák
- Matematika Archiv
- ↳ Výuka LS 2006/2007 3. ročník
- ↳ Předměty numeriky
- ↳ Úvod do funcionální analýzy
- ↳ Náhodné procesy 2
- ↳ Matematická statistika 2
- ↳ Teorie pravděpodobnosti 2
- ↳ Matematická ekonomie
- ↳ Výuka LS 2006/2007 2. ročník
- ↳ Pravděpodobnost a statistika
- ↳ Teorie Míry a integrálu II
- ↳ Angličtina
- ↳ Algebra II
- ↳ Matematická analýza 2b
- ↳ Ostatní
- ↳ Výuka LS 2006/2007 1. ročník
- ↳ Volitelné předměty
- ↳ Lineární algebra 2
- ↳ Programování 2
- ↳ Matematická analýza 1b
- Zrušené předměty
- ↳ SWI087 Principy počítačů
- ↳ SWI120 Principy počítačů a operačních systémů
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ PRG029 Programování v C++
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ PRG032 Objektově orientované programování
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ SWI097 Základy operačních systémů
- ↳ NDBI003 Organizace a zpracování dat II
- Roztřídit (resty)
- ↳ Výuka ZS 2005/06 2. ročník
- ↳ Předměty informační bezpečnosti
- ↳ Předměty finanční matematiky
- ↳ Teorie míry a integrálu
- ↳ Numerika
- ↳ Algebra
- ↳ Analýza/kalkulus
- ↳ Matematika obecně
- ↳ Výuka LS 2005/06 2.ročník
- ↳ Základy matematického modelování
- ↳ Finanční management
- ↳ Úvod do optimalizace
- ↳ Numerika
- ↳ Kalkulus
- ↳ Angličtina
- ↳ Diferenciální geometrie
- ↳ Pravděpodobnost a statistika
- ↳ Teorie míry a integrálu II
- ↳ Algebra II
- ↳ Analýza 2b