DISKREETTI MATEMATIIKKA Välikoe 2, syksy 2005
EI LASKIMIA!
EI MATKAPUHELIMIA!
1. Ovatko verkot
a) G1: •
??
??
??
? •
• •
G2: •
0000 0000
•KKKKK
•ppppp • b) D1:
•
•
•
22
• .. •
ll
•
qq•
•
RR OO
D2:
•MMMMM&&
•
??
•
•
&&
MM MM M •
ggOOOOOO
•
??
•
•
ggOOOOOO
isomorset? Perustele vastauksesi!
2. Muodosta kielen
L={x∈(a+b)∗ |kirjainten b määrä x:ssä on parillinen}
määräävä säännöllinen lauseke sekä sellainen deterministinen automaatti A ja kielioppi G, että L=L(A) ja L=L(G).
3. Olkoot fi,gi: N → R funktioita, i = 1, 2. Määrittele, mitä merkinnällä f1 ∈ O(g1) tarkoitetaan. Olkoon fi ∈ O(gi), i = 1, 2, ja n0 ∈ N sellainen vakio, että g1(n) ≥ g2(n) ≥ 0 aina, kun n ≥ n0. Osoita, että f1 +f2 ∈ O(g1).
4. Määrittele suuntaamattoman verkon G= (V, E, α) Hamiltonin sykli. Ol- koon solmujoukolla ositus V =V1∪V2. Oletetaan, että jos α(e) ={x, y}, niin joko x ∈ V1 ja y ∈ V2 tai x ∈ V2 ja y ∈ V1. Osoita, että jos |V| on pariton, niin verkossa Gei ole Hamiltonin sykliä.
