Wyniki kolokwium poprawkowego

Nr indeksu Zadanie 1. Zadanie 2. Zadanie 3. Zadanie 4. Suma
277830 7 6.5 10 2 25.5
262767 7 7.5 7 1.5 23
305433 7 6.5 10 2 25.5
305139 0 3 9
12
305342 7 4.5 10
21.5
305759 0
4
4
276868 4 5.5 3
12.5

Rozwiązania zadań i kryteria oceny

Maksymalna liczba punktów za każde zadanie to 10.

Zadanie 1.

Program odwraca tablicę znaków. Dowód tego faktu najprościej przeprowadzić indukcyjnie (indukcja ze względu na n). Chcemy pokazać, że f(tab, n) odwraca kolejność pierwszych n elementów w tablicy tab. Dla n=1 sprawa jest oczywista. Teraz niech n > 1. Załóżmy, że n jest nieparzyste (dla parzystych n jest analogicznie i trochę prościej). Wówczas dla tablicy postaci: 
UvW
gdzie U i W to słowa długości (n-1)/2, po wykonaniu pętli for dostaniemy: 
WvU
Z założenia indukcyjnego, wywołania rekurencyjne odwrócą W i U, czyli otrzymamy 
WRxUR
Zapis WR oznacza odwrócenie słowa W. Tym sposobem pokazaliśmy, że słowo zostało odwrócone.

Zadanie 2.

Przykładowe rozwiązanie: 
int najdluzszy(int tab[], int n)
{
	int najdluzszy_fragment = 0;
	int aktualny = 0;
	
	for(int i=0; i<n; i++)
	{
		// aktualny to dlugosc najdluzszego fragmentu, ktory
		// konczy sie na pozycji i-1 (0 dla i = 0)

		// najdluzszy to najdluzszy fragment rownych elementow,
		// wsrod i pierwszych elementow tablicy
		if (i == 0 || tab[i] == tab[i-1])
			aktualny ++;
		else
			aktualny = 1;
		if (aktualny > najdluzszy_fragment)
			najdluzszy_fragment = aktualny;
	}
	return najdluzszy_fragment;
}
Operacją dominującą jest tu np. porównanie i == 0 albo sprawdzenie drugiego warunku w if w pętli. Pętla przebiega od i = 0 do n-1, zatem jest n operacji dominujących. W zadaniu chodziło o możliwie formalne uzasadnienie poprawności. Wszelkie opowiadania typu: "Przeglądamy tablicę i patrzymy czy bieżący element jest równy poprzedniemu. Jeśli tak, to zwiększamy długość aktualnego fragmentu." są zbędne - to mniej więcej widać po spojrzeniu na kod.

Należy do sprawy podejść nieco bardziej rzeczowo. W kodzie umieściłem dwa komentarze, przy czym warto zwrócić uwagę na parę spraw: Takie komentarze plus krótka uwaga, która mówi, że to właśnie z nich wynika poprawność podprogramu, są wystarczającym dowodem poprawności.

Ogólny przepis na uzasadnienie poprawności pętli jest więc następujący. Należy sformułować tzw. niezmienniki czyli zdania logiczne opisujące zmienne w programie, które zachodzą na samym początku każdego obrotu pętli oraz w momencie jej zakończenia. Z niezmiennika oraz faktu, że pętla się zakończyła, powinna wynikać poprawność pętli. Postanowiłem nie odejmować punktów, jeśli algorytm nie działał dla n = 0, jednak na przyszłość proszę pamiętać.

Zadanie 3.

Przy użyciu algorytmu HeapSort z wykładu w trakcie budowy kopca wykonywało się 12 porównań, zaś w fazie wyjmowania - 20 porównań. Niektórzy stosowali nieco inny sposób budowy kopca (np. przez UpHeap) i takie rozwiązania uznawałem za poprawne, o ile byłem w stanie dopasować ciąg zamian elementów do jakiegoś algorytmu, który omawialiśmy na zajęciach.

Zadanie 4.

Widzę dwa rozwiązania tego zadania. Zacznę od pierwszego, które jest krótkie, ale nieco trikowe. Załóżmy, że chcemy napisać program, który wypisze na ekran wszystkie jedno- i dwuelementowe podzbiory z tablicy liczb. Podzielmy tablicę na części rozmiaru f(n) oraz n - f(n). Każdy podzbiór albo jest w całości w jednej części (jedno wywołanie rekurencyjne), albo w całości w drugiej części (drugie wywołanie) albo ma po jednym elemencie w każdej z części (takich par jest f(n)(n-f(n))). Zatem algorytm z treści działa tak samo, jak przeglądanie wszystkich jedno- i dwuelementowych podzbiorów zbioru n-elementowego, czyli wykonuje n(n+1)/2 operacji wypisania.

Można też podejść do sprawy bardziej standardowo. Dla f(n) = 1 mamy T(n) = n-1 + T(n-1), czyli T(n) = O(n2). Podobnie, jeśli n jest potęgą dwójki dla f(n) = n/2 otrzymujemy: T(n) = n2/4 + 2T(n/2). Po rozwinięciu tej rekurencji wychodzi: 
T(n) = n2/4 + n2/8 + n2/16 + ...
czyli w sumie O(n2). Zgadujemy więc, że T(n) zawsze będzie rzędu n2. Żeby to pokazać, udowodnimy indukcyjnie, że T(n) ≤ n2. Bazę indukcji dostajemy natychmiast. Teraz krok indukcyjny: zakładamy, że nierówność jest spełniona dla 1, 2, ..., n-1. 
T(n) = f(n)(n-f(n)) + T(f(n)) + T(n-f(n)) ≤ (f(n))2 + f(n)(n-f(n)) + (n-f(n))2 ≤ (f(n) + n - f(n))2 = n2
Pierwsza nierówność to po prostu skorzystanie z założenia indukcyjnego. W drugiej, korzystam z nierówności a2 + ab + b2 ≤ (a+b)2. Ona przypomina wzór skróconego mnożenia, w którym po lewej stronie odjąłem ab. Ponieważ to ab było nieujemne, mamy nierówność.

Ograniczenie dolne można wyprodukować analogicznie, przy czym indukcyjnie pokazujemy T(n) ≥ n2/2.