Ctrl+K

2. Klasówka 2015/16 (14.01.2016)

2. Klasówka 2015/16 (14.01.2016)#

Zadanie 1 [2+3+5 = 10 punktów]#

Słowa kluczowe: grafy

Dla dodatniej liczby całkowitej n, kratownicą \(n \times n\) nazywamy graf o \(n^2\) wierzchołkach i \(2n(n-1)\) krawędziach, którego wierzchołki można poetykietować parami liczb (x,y), dla x=1,2, …, n i y=1,2, …, n, w taki sposób, że wierzchołek (x,y) jest połączony (sąsiaduje) z wierzchołkami: (x-1,y), (x+1,y), (x,y-1) oraz (x,y+1), o ile tylko sąsiad o takiej etykiecie istnieje. Oto przykład kratownicy 3x3:

Figure made with TikZ

  1. Policz ile jest różnych drzew BFS w kratownicy 3x3 o korzeniach w wierzchołkach stopnia 2.

  2. Policz ile jest różnych drzew DFS w kratownicy 3x3 o korzeniach w wierzchołkach stopnia 2.

  3. Przyjmijmy, że dana jest dodatnia liczba całkowita n oraz lista 2n(n-1) krawędzi pewnego grafu, którego wierzchołki poetykietowano liczbami całkowitymi od 1 do \(n^2\). Zaproponuj algorytm, który w czasie liniowym stwierdzi, czy dany graf jest kratownicą \(n \times n\).

Uwaga: dwa drzewa BFS (DFS) się różnią, jeśli istnieje wierzchołek o różnych ojcach w tych drzewach; na potrzeby tego zadania BFS-drzewo, to drzewo najkrótszych ścieżek prowadzących do korzenia.

Podpowiedź

  1. Warunek konieczny ale nie wystarczający: stopnie wierzchołków muszą odpowiadać wierzchołkom kraty (4 wierzchołki stopnia 2, 4(n-2) wierzchołków stopnia 3, \((n-1)\cdot(n-1)\) wierzchołków stopnia 4)

    • sprawdź czy stopnie wierzchołków są zgodne z powyższym warunkiem

    • zbuduj podgraf złożony tylko z wierzchołków stopnia 2 i 3 i sprawdź czy tworzy cykl długości 4(n-1)

    • wierzchołki stopnia 2 odpowiadają rogom, wierzchołki stopnia 3 odpowiadają bokom

    • nadaj wierzchołkom z cyklu współrzędne na kracie

    • nadawaj kolejnym wierszom wierzchołków współrzędne

    • gdy wszystkie wierzchołki otrzymały współrzędne na kracie, sprawdź czy krawędzie są zgodne z kształtem kraty.

Zadanie 2 [5+5 = 10 punktów]#

Słowa kluczowe: struktury danych; wzbogacanie

Niech A będzie skończonym, dynamicznie zmieniającym się ciągiem, którego elementami są liczby ze zbioru {-1,0,1}. Podciąg kolejnych elementów A nazwiemy dobrym, gdy jego suma jest równa zero. Podciąg jest super-dobry, gdy jest dobry i suma elementów w każdym jego prefiksie jest nieujemna.

Przykład: W ciągu A = [1,1,0,-1,0,0,1,-1,1,1,-1], podciąg -1,1,1,-1 jest dobry, ale nie super-dobry. Super-dobrym podciągiem jest na przykład 1,0,-1.

  1. Zaproponuj algorytm, który w czasie liniowym obliczy długość najdłuższego super-dobrego podciągu danego ciągu A.

  2. Zaproponuj strukturę danych, która pozwoli na wydajne wykonywanie następujących operacji na A:

    • Ini(A):: A := []; //wykonywana tylko raz, na początku

    • Wstaw(A,e,i):: wstaw nowy element e jako i-ty w A, \(1\le i \le |A|+1\);

    • Usuń(A,i):: usuń i-ty element z A, \(1\le i \le |A|\)

    • SuperDobry(A,i,j):: sprawdź, czy podciąg A[i..j] jest super-dobry, \(1\le i \le j \le |A|\);

W każdym zadaniu uzasadnij poprawność swoich rozwiązań i dokonaj analizy złożoności obliczeniowej zaproponowanych algorytmów.

Zawartość