Ctrl+K

Egzamin poprawkowy 2015/16 (18.02.2016)

Egzamin poprawkowy 2015/16 (18.02.2016)#

Zadanie 1 [20 punktów]#

Słowa kluczowe: grafy

W tym zadaniu rozważamy grafy, które można przedstawić na płaszczyźnie jako wielokąty wypukły zawierająca maksymalną liczbę nieprzecinających się przekątnych. Takie grafy nazywamy wielokątowymi. Wierzchołkom grafu wielokątowego odpowiadają wierzchołki wielokąta ponumerowane od 1 do n, zgodnie z kolejnością ich występowania na obwodzie. Krawędziom grafu odpowiada n boków i n-3 przekątnych wielokąta. Graf wielokątowy zadajemy przez liczbę n > 2 oraz ciąg 2n-3 par wierzchołków wyznaczających krawędzie grafu. Zakładamy ponadto, że z każdą krawędzią e dana jest całkowitoliczbowa waga w(e).

  1. [4 punkty] Jaka może być minimalna, a jaka maksymalna wysokość BFS-drzewa w wielokątowym grafie o 2016 wierzchołkach?

  2. [5 punktów] Jaka może być minimalna, a jaka maksymalna wysokość DFS-drzewa w wielokątowym grafie o 2016 wierzchołkach?

  3. [3 punkty] Rozważmy dowolny, spójny graf z parami różnymi wagami na krawędziach. Udowodnij, że dla każdego wierzchołka, krawędź o minimalnej wadze incydentna z tym wierzchołkiem należy do minimalnego drzewa rozpinającego.

  4. [8 punktów] Zaproponuj algorytm, który w czasie liniowym wyznacza minimalne drzewo rozpinające w grafie wielokątowym.

Zadanie 2 [10 punktów]#

Słowa kluczowe: sortowanie

Sortujemy ciągi zero-jedynkowe za pomocą operacji porównania \(\le\) (mniejsze lub równe).

  1. [5 punktów] Zaproponuj algorytm sortowania ciągu zero-jedynkowego o długości n, optymalny ze względu na porównania \(\le\) (interesuje nas dokładna, pesymistyczna liczba porównań). Udowodnij optymalność swojego algorytmu.

  2. [5 punktów] Zaproponuj stabilny algorytm sortowania ciągu zero-jedynkowego o długości n za pomocą n + o(n) porównań \(\le\).

Zadanie 3 [10 punktów]#

Słowa kluczowe: struktury danych, wzbogacanie

Zaproponuj strukturę danych, które na dynamicznie zmieniającym się ciągu liczbowym umożliwia wydajne wykonywanie następujących operacji:

  • Ini(\(\alpha\)):: \(\alpha\) := <> //utwórz pusty ciąg; operacja wykonywania tylko raz, na samym początku

  • Insert(\(\alpha\),a,k):: wstaw a jako k-ty element ciągu, \(1 \le k \le |\alpha|+1\)

  • Delete(\(\alpha\),a,k):: usuń k-ty element ciągu \(\alpha\), \(1 \le k \le |\alpha|\)

  • Sum(\(\alpha\),i,j):: podaj sumę elementów na pozycjach i, i+1,…, j, \(1 \le i \le j \le |\alpha|\)

  • Replace(\(\alpha\),i,j,a):: zamień każdy z elementów z pozycji i, i+1,…, j na a, \(1 \le i \le j \le |\alpha|\)

Zawartość