Računalništvo (FMF)/Vaje/1. kolokvij 2006-2007

Iz MaFiRaWiki


1. naloga

Ugotovi pravilnost naslednjih trditev.

(a) Jezik {a^nb^m: m,n \ge 1} je regularen

(b) Če je L1 regularen in L_1 \cup L_2 regularen, potem je tudi L2 regularen.

(/Rešitev 1. naloge)

2. naloga

Razpršeno matriko lahko v Mathematici predstavimo kot seznam {m,n,l}, kjer je seznam trojic {i,j,e}, e različen od 0. Trojica {i,j,e} pomeni, da se v i-ti vrstici in j-tem stolpcu matrike nahaja element e. V poljih, ki jih ni v seznamu l, so ničle. (Enaka predstavitev kot na vajah.)

(a) V Mathematici napiši funkcijo Transponiraj[M_], ki transponira razpršeno matriko M predstavljeno na zgornji način.

(b) Ugotovi, kaj vrne KajDelam[{5,7,{{1,3,"A"},{5,5,"G"},{3,7,"E"}}}], če je funkcija KajDelam definirana na naslednji način:

KajDelam[X_, {}] := X

KajDelam[X_, {t_, tr___}] := KajDelam[ReplacePart[X, Last[t], Take[t, 2]], {tr}]

KajDelam[M_] := KajDelam[Table[0, {M1}, {M2}], M3]

Kaj vrne funkcija KajDelam[M_] v splošnem, če je parameter M razpršena matrika predstavljena na zgornji način?

(/Rešitev 2. naloge)

3. naloga

Enostavnemu grafu G z vsaj tremi vozlišči pravimo škorpijon, če ima naslednjo lastnost: obstajajo tri posebna vozlišča a, b in c, za katere velja, da je vozlišče c povezano le z b, vozlišče b povezano le s c in z a, vozlišče a pa je povezano z vsemi ostalimi vozlišči grafa razen s c. Na spodnji sliki je primer takšnega grafa; pod sliko je njegova matrika sosednosti.

\begin{bmatrix} 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ \end{bmatrix}

Napiši algoritem, ki iz matrike sosednosti grafa G ugotovi, če je G škorpijon. Oceni njegovo časovno zahtevnost (v odvisnosti od števila vozlišč). Ta naj bo čimmanjša!

(/Rešitev 3. naloge)

4. naloga

Reši podnaloge.

(a) V MAX kopico po vrsti vstavljaj elemente:

5, 10, 21, 9, 8, 17, 13, 30, 19, 7, 6, 31.

Nato odstrani tri elemente. MAX kopico nariši po vsakem vstavljenem (odstranjenem) elementu.

(b) V MIN kopico po vrsti vstavljaj elemente: 5, 10, 21, 9, 8, 17, 13, 30, 19, 7, 6, 31.

Nato odstrani tri elemente. MIN kopico nariši po vsakem vstavljenem (odstranjenem) elementu.

(c) Ali je kopica uravnoteženo dvojiško drevo?

(/Rešitev 4. naloge)

Glej tudi

Osebna orodja