o przedmiocie

Wstęp do informatyki i programowania

Celem tych zajęć jest zapoznanie studentów z podstawowymi zagadnieniami algorytmicznymi oraz metodami ich skutecznego rozwiązywania za pomocą programów pisanych w języku C++ w środowisku programistycznym Code::Blocks a także w językach C# i F# na platformie .Net.

Na wykładzie prezentowanych będzie wiele różnorodych problemów obliczeniowych oraz skutecznych i efektywnych metod ich rozwiązywania. Omawiane będą podstawowe techniki konstuowania algorytmów i analizy ich złożoności obliczeniowej. Szczególny nacisk będzie położony na sposób w jaki dane są przechowywane w pamięci komputera, gdyż od organizacji danych bardzo często zależy czas działania programu rozwiązującego określone zadanie.

W ramach konwersatorium będzie omawiany język programowania C++ na poziomie programowania strukturalnego z elementami obiektowości oraz podstawowe elementy z biblioteki standardowej STL. Krótkie i proste przykłady powinny wspomóc naukę programowania w tym języku.

Wymagane przygotowanie

• Dobra znajomość matematyki na poziomie szkoły średniej.
• Umiejętność przeczytania dokumentacji technicznej w języku angielskim.

literatura

Literatura podstawowa algorytmiczna

• P.Wróblewski: Algorytmy, struktury danych i techniki programowania. Wydanie 4. Helion, Gliwice 2009.
• L.Banachowski, K.Diks, W.Rytter: Algorytmy i struktury danych. Wydanie 5. WNT, Warszawa 2011.
• T.H.Cormen: Algorytmy bez tajemnic. Helion, Gliwice 2013.

Literatura uzupełniająca algorytmiczna

• T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein: Wprowadzenie do algorytmów. Nowe wydanie. PWN, Warszawa 2012.
• S.Dasgupta, C.Papadimitriou, U.Vazirani: Algorytmy. PWN, Warszawa 2012.
• R.Sedgewick, K.Wayne: Algorytmy. Wydanie 4. Helion, Gliwice 2012.
• R.Neapolitan, K.Naimipour: Podstawy algorytmów z przykładami w C++. Helion, Gliwice 2004.
• N.Wirth: Algorytmy + struktury danych = programy. WNT, Warszawa 2004.
• A.V.Aho, J.E.Hopcroft, J.D.Ullman: Projektowanie i analiza algorytmów. Helion, Gliwice 2003.
• A.V.Aho, J.E.Hopcroft, J.D.Ullman: Algorytmy i struktury danych. Helion, Gliwice 2003.
• A.V.Aho, J.D.Ullman: Wykłady z informatyki z przykładami w języku C. Helion, Gliwice 2003.
• D.Knuth: Sztuka programowania (tom 1, 2, 3). WNT, Warszawa 2001.
• D.Harel: Rzecz o istocie informatyki. Algorytmika. WNT, Warszawa 2001.
• J.Bentley: Perełki oprogramowania. WNT, Warszawa 2001.
• J.Bentley: Więcej perełek oprogramowania.Wyznania programisty. WNT, Warszawa 2007.

Literatura elektroniczna algorytmiczna

• Uniwersytet Warszawski, MIM - algorytmy i struktury danych
• Uniwersytet Warszawski, MIM - zaawansowane algorytmy i struktury danych
• I LO w Tarnowie - binarne kodowanie liczb, algorytmy i struktury danych
• Wrocławski Portal Informatyczny

Literatura podstawowa programistyczna

C++

• S.Rao: C++. Dla każdego. Wydanie 7. Helion, Gliwice 2014.
• S.Prata: Język C++. Szkoła programowania. Wydanie 6. Helion, Gliwice 2013.
• K.Kuczmarski: Od zera do gier kodera. WNT, Warszawa 2004.
• J.Grębosz: Symfonia C++ (tom 1, 2, 3). Oficyna Kallimach, Kraków 2002.
• J.Grębosz: Pasja C++ (tom 1, 2). Oficyna Kallimach, Kraków 2003.

F#

• M.Mysior: Język F# w praktyce. Wydawnictwo EscapeMagazine.pl, Toruń 2012.

Literatura uzupełniająca programistyczna

C++

• B.Stroustrup: Język C++. Kompendium wiedzy. Wydanie 4. Helion, Gliwice 2014.
• N.M.Josuttis: C++. Biblioteka standardowa. Wydanie 2. Wydawnictwo Helion, Gliwice 2014.

F#

• D.Syme, A.Granicz, A.Cisternino: F# 4.0 dla zaawansowanych. Wydanie 4. Wydawnictwo Helion, Gliwice 2017.

Literatura elektroniczna programistyczna

C++

• C++ (pl.wikibooks.org)
• C++11 (pl.wikipedia.org)
• C++ Language Tutorial (www.cplusplus.com)
• The C++ Tutorial (www.learncpp.com)
• C / C++ lecture notes, courses, tutorials, references, guides and online books (oopweb.com/CPP)
• C++11 Support in GCC (gcc.gnu.org)
• Ten C++11 Features Every C++ Developer Should Use (www.codeproject.com) by Marius Bancila
• The future of C++ (www.cprogramming.com) by Alex Allain

F#

• Try F#
• The F# Software Foundation
• F# for Data Science
• Visual F# Developer Center

wykład

Zasady zaliczenia przedmiotu

...

Spis wykładów

1. zadania obliczeniowe i algorytmy
2. liczby w zapisie binarnym
3. rekurencja
4. Odwrotna Notacja Polska
5. sortowanie
6. kolokwium I
7. sortowanie
8. listy
9. drzewa
10. kolokwium II
11. techniki rozwiązywania problemów optymalizacyjnych
12. wyrażenia regularne, gramatyki bezkontekstowe, automaty skończone
13. grafy
14. kolokwium III

Materiał omawiany na wykładach

4 października 2017 r: zadania obliczeniowe i algorytmy

• sprawy organizacyjne

• problem obliczeniowy i jego specyfikacja (dane wejściowe, wyniki, warunki dodatkowe) [pl.wikipedia.org], [edu.i-lo.tarnow.pl];
• algorytmy czyli metody rozwiązujące zadany problem obliczeniowy [pl.wikipedia.org];
• program jako zapis algorytmu w pseudokodzie oraz jego implementacja w konkretnym języku programowania [pl.wikipedia.org];
• złożoność obliczeniowa algorytmów (czasowa i pamięciowa) [pl.wikipedia.org];
• asymptotyka wykorzystywana do szacowania złożoności obliczeniowej algorytmów (notacja Ο, Ω i Θ) [pl.wikipedia.org].
• slajdy z wykładu: Efektywnosc.pdf

11 października 2017 r: liczby w zapisie binarnym

• bity i bajty i mnożniki binarne
• kodowanie informacji za pomocą bitów
• systemy liczbowe: dziesiętny i dwójkowy system liczbowy
• naturalny system dwójkowy
• przeliczanie liczb z systemu dziesiętnego na dwójkowy i w drugą stronę
• operacje arytmetyczne w systemie dwójkowym
• kodowanie liczb całkowitych ze znakiem: system ZM, U1 i U2
• dwójkowy system stałoprzecinkowy
• zaokrąglenia liczb w systemie dwójkowym
• arytmetyka stałopozycyjna
• arytmetyka zmiennopozycyjna: standard IEEE-754

18 października 2017 r: rekurencja

• pojęcie rekurencji
• obliczanie silni z wykorzystaniem rekurencji
• wyznaczanie n-tej liczby w ciągu Fibonacciego algorytmem rekurencyjnym oraz algorytmem liniowym
• potęgowanie poprzez wielokrotne mnożenie podstawy i algorytm szybkiego potęgowania
• oryginalny algorytm Euklidesa (z odejmowaniem) oraz zmodyfikowany przez Gabriela Lame w roku 1844 (zastosowanie operacji modulo) dla wyznaczenia NWD

25 października 2017 r: Odwrotna Notacja Polska

• tablica - podstawowa struktura danych
• tablica dynamiczna - dopasowuje się do rozmiaru danych
• stos - bufor LIFO
• kolejka - bufor FIFO
• implementacja stosu i kolejki na tablicy
• wyrażenia algebraiczne zapisane w NP Łukasiewicza
• wyrażenia algebraiczne zapisane w ONP
• obliczanie wyrażeń w postaci postfoksowej - wykorzystanie kolejki i stosu
• przekształcanie wyrażeń z postaci infiksowej do postfiksowej - algorytm Dijkstry (stacja rozrządowa)
• slajdy z wykładu: Bufory.pdf

8 listopada 2017 r: sortowanie

• problem sortowania
• sortowanie bąbelkowe
• sortowanie przez wstawianie
• sortowanie przez wybieranie
• sortowanie przez zliczanie
• wyszukiwanie binarne
• slajdy z wykładu: Porzadkowe.pdf

22 listopada 2017 r: kolokwium I

• Kolokwium I odbędzie się w trakcie wykładu - rozpocznie się o godzinie 16:15 w sali 140 w IInf.
• Zakres materiału: reprezentacja liczb w komputerze, rekurencja, ONP.

29 listopada 2017 r: scalanie, podział, wyszukiwanie k-tego elementu, wyszukiwanie binarne

• technika dziel i zwyciężaj
• jednoczesne znajdowanie minimum i maksimum (algorytm rekurencyjny)
• problem scalania i sortowanie poprzez scalanie
• problem podziału i sortowanie szybkie (poprzez podział)
• technika redukcji jako odmiana dziel i zwyciężaj z jednym podproblemem
• wyszukiwanie k-tego elementu (algorytm Hoare'a)
• wyszukiwanie binarne (algorytm rekurencyjny)
• slajdy z wykładu: Porzadkowe.pdf

6 grudnia 2017 r: listy, drzewa

• zbiory i multizbiory dynamiczne
• słownik i operacje słownikowe
• lista jako struktura sekwencyjna
• lista jednokierunkowa i dwukierunkowa
• lista cykliczna
• lista z wartownikiem
• implementacja operacji słownikowych na listach uporządkowanych
• drzewo jako struktura hierarchiczna (rozgałęziona)
• drzewa jednokierunkowe i dwukierunkowe
• drzewa z wartownikiem
• implementacja drzew metodą "na lewo syn na prawo brat"
• drzewa binarne
• wysokość drzewa a głębokość liścia
• slajdy z wykładu: Listy.pdf, Drzewa.pdf

13 grudnia 2017 r: drzewa, kopce

• drzewa BST z porządkiem symetrycznym
• implementacja operacji słownikowych na drzewach BST
• rotacje w drzewach BST
• drzewa AVL - zrównoważone drzewa BST
• drzewa R-B - zrównoważone drzewa BST
• kolejka priorytetowa i operacje kolejkowe
• złączalne kolejki priorytetowe
• implementacja kolejki priorytetowej na drzewach lewicowych
• slajdy z wykładu: Drzewa.pdf, Kolejki.pdf

20 grudnia 2017 r: kolokwium II

• Kolokwium II odbędzie się w trakcie wykładu - rozpocznie się o godzinie 16:15 w sali 140 w IInf.
• Zakres materiału: problemy porządkowe, dynamiczne struktury danych (listy, drzewa, kopce).

3 stycznia 2018 r: techniki rozwiązywania zadań algorytmicznych

• metoda dziel i zwyciężaj: mnożenie długich liczb (algorytm Karacuby);
• metoda redukcji (odmiana dziel i zwyciężaj): znajdowanie miejsca zerowego funkcji (algorytm połowienia przedziałów);
• programowanie dynamiczne: najdłuższy wspólny podciąg (algorytm LCS);
• technika zachłanna: przydział wykładów do sali konferencyjnej, szeregowanie zadań do procesora.
• slajdy z wykładu: Techniki.pdf

10 stycznia 2018 r: wyrażenia regularne, automaty skończone

• ...

17 stycznia 2018 r: grafy

• ...
• slajdy z wykładu: Grafy.pdf

24 stycznia 2018 r: kolokwium III

• Kolokwium III odbędzie się w trakcie wykładu - rozpocznie się o godzinie 16:15 w sali 140 w IInf.
• Zakres materiału: kolejki priorytetowe (kopce lewicowe, kopce binarne), techniki rozwiązywania zadań algorytmicznych (dziel i zwyciężaj, programowanie dynamiczne, strategia zachłanna), wyrażenia regularne, automaty, gramatyki bezkontekstowe, grafy.

konwersatorium

Wyniki z kolokwiów i egzaminów

• kolokwium I (pdf)
• kolokwium II (pdf)
• kolokwium III (pdf)
• egzaminy (pdf)

ćwiczenia

Zasady zaliczenia przedmiotu

...

Spis zajęć ćwiczeniowych

1. algorytmy i ich złożoność
2. liczby w zapisie binarnym
3. rekurencja
4. ONP
5. sortowanie 1
6. sortowanie 2
7. sortowanie 3
8. dynamiczne struktury danych 1
9. dynamiczne struktury danych 2
10. słowniki i kolejki priorytetowe
11. techniki rozwiązywania problemów obliczeniowych

Zadania realizowane na ćwiczeniach

13 października 2017 r: algorytmy i ich złożoność (lista 1)

1. Zakładamy, że program rozwiązujący pewno zadanie potrzebuje f(n) mikrosekund (1 μs = 0.000001 s) dla danych rozmiaru n. Uzupełnij poniższą tabelę dla każdej funkcji f(n) i czasu t, wyliczając największy rozmiar danych n, dla których program wykona obliczenia w czasie t.

   f(n) mikrosekund	czas t
   	sekunda	minuta	godzina	dzień	miesiąc
   log(n)
   √n
   n
   n2
   2n

2. Dane są dwa algorytmy A i B, które rozwiązują ten sam problem P. Dla danych o rozmiarze n algorytm A działa w czasie f(n) a algorytm B w czasie g(n): Dla jakich wartości n bardziej opłaca się stosować algorytm A a dla jakich algorytm B?
   1.   f(n) = n³   oraz   g(n) = 100·n
   2.   f(n) = 10·n²   oraz   g(n) = 2ⁿ
   3.   f(n) = 10·n·log(n)   oraz   g(n) = n²
   Odpowiedź uzasadnij.
3. Przypomnij sobie definicję operatora Ο i uporządkuj poniższe funkcje ze względu na ich rząd wielkości, od asymptotycznie najwolniej rosnącej do asymptotycznie rosnącej najszybciej posługując się relacjami ⊆ i ≡:
   1.   (n+1)^0.5
   2.   3·n²+5·n
   3.   2ⁿ
   4.   5·n+3
   5.   nⁿ⁺¹
   6.   n^0.1
   7.   log₂(5·n)
   8.   2·n³+5
   9.   3^2·n
   10.   √n
   11.   4ⁿ⁺¹
   12.   log₃(n⁵)
   13.   (n+1)ⁿ
   14.   3ⁿ⁺²
   15.   2·n+7
   Przykład. Początek rozwiązania tego zadania wygląda następująco: Ο(log₂(n)) ≡ Ο(log₃(n⁵)) ⊆ Ο(n^0.1) ...
4. Korzystając z definicji operatorów Ο, Ω i Θ udowodnij, że:
   1.   10·n³ ∈ Ο(n⁵)
   2.   n+1 ∈ Ω(√n)
   3.   5·n²+7·n-3 ∈ Θ(n²)
   Wskazówka. Należy dobrać odpowiednie stałe w definicji i wykazać prawdziwość nierówności dla wszystich n większych od pewnej wartości.

20 października 2017 r: liczby w zapisie binarnym (lista 2)

1. Zapisz w postaci schematu blokowego:
   1. algorytm generowania binarnej reprezentacji liczby naturalnej, zaczynając od najmniej znaczącego bitu;
   2. algorytm inkrementacji (zwiększenia o 1) albo algorytm dekrementacji (zmniejszenia o 1) zadanej liczby całkowitej zapisanej w postaci U2;
   3. algorytm zmiany znaku w binarnej liczbie całkowitej zapisanej w postaci U2.
2. Zapisz następujące liczby całkowite w postaci dwójkowej stosując kodowanie ZM, U1 i U2:
   1.   -97
   2.   -341
   3.   -8952
   Uwaga. Użyj najmniejszej możliwej liczby bitów (wliczając w to bit znaku).
3. Zapisz następujące liczby w postaci binarnej stałopozycyjnej z dokładnością do 6 bitów po kropce dwójkowej stosując kodowanie U2:
   1.   ³/₄₉
   2.   ²¹¹/₂₅
   3.   -12 ⁴/₃₅
   Wskazówka. Wylicz 7 bitów po kropce dwójkowej i dopiero wtedy zaokrąglij wynik do 6 miejsc.
4. Zapisz następujące liczby w postaci binarnej zmiennopozycyjnej w obiekcie typu single (4 bajty) zgodnie ze standardem IEEE-754:
   1.   1.832482
   2.   -0.00735
   3.   -93573.0
   Uwaga. Wyznacz bit znaku, bity cechy (z uwzględnieniem BIAS) i mantysy (kodujemy tylko część ułamkową po normalizacji).
5. Wylicz, jaka jest najmniejsza i największa wartość dodatnia, którą można zapisać w notacji zmiennopozycyjnej w obiekcie typu double (8 bajtów) zgodnie ze standardem IEEE-754.

27 października 2017 r: rekurencja (lista 3)

1. Zapisz rekurencyjne wzory dla:
   1. ciągu arytmetycznego;
   2. ciągu geometrycznego.
   Napisz w pseudokodzie funkcje rekurencyjne implementujące te wzory. Jaka będzie złożoność obliczeniowa tych funkcji?
2. Jak za pomocą rekurencji wyrazić operację znajdowania wartości minimalnej dla zadanego skończonego ciągu liczbowego? Można przyjąć, że długość ciągu n jest parametrem funkcji. Napisz w pseudokodzie funkcję rekurencyjną implementującą ten wzór. Jaka będzie złożoność obliczeniowa tej funkcji?
3. Napisz rekurencyjną definicję dla współczynnika dwumianowego. Uzasadnij, skąd się wziął ten wzór. Napisz w pseudokodzie funkcję rekurencyjną implementującą ten wzór. Jaka będzie złożoność obliczeniowa tej funkcji? Postaraj się przekształcić wzór rekurencyjny dla współczynnika dwumianowego w taki sposób, aby po prawej stronie znajdował się tylko jeden współczynnik dwumianowy. Czy implementując ten wzór polepszy się złożoność obliczeniowa funkcji?
4. Napisz rekurencyjną definicję n-tej liczby Catalana. Jaką interpretację mają te liczby? Napisz w pseudokodzie funkcję rekurencyjną implementującą ten wzór.
5. Napisz rekurencyjną definicję dla funkcji Ackermanna. Wylicz kilka pierwszych wartości dla tej funkcji. Napisz w pseudokodzie funkcję rekurencyjną implementującą ten wzór.
6. [zadanie dodatkowe] Co oblicza rozszerzony algorytm Euklidesa? Wyjaśnij ideę jego działania i uzasadnij poprawność.

3 listopada 2017 r: ONP (lista 4)

1. Kolejka dwukierunkowa to struktura danych podobna do kolejki, pozwalająca jednak na wstawianie i usuwanie elementów na obu jej końcach. Jak zaimplementować taką strukturę na tablicy, aby wszystkie operacje wstawiania i usuwania działały w czasie stałym Ο(1)? Przedstaw ideę rozwiązania. Napisz w pseudokodzie wszystkie cztery procedury.
2. Znana jest tablicowa implementacja kolejki i stosu. Pokaż, jak zmodyfikować te implementacje, aby można było odwrócić kolejność elementów w tych buforach w stałym czasie Ο(1).
3. Zapisz w pseudokodzie algorytm obliczania wartości wyrażenia zapisanego w postaci ONP. Jakie struktury danych wykorzystujesz w swoim algorytmie? Czy Twój algorytm jest rekurencyjny czy iteracyjny?
4. Zapisz w pseudokodzie algorytm przekształcania wyrażenia zapisanego w postaci infiksowej (z funkcjami oprócz operatorów) na postać ONP. Jakie struktury danych wykorzystujesz w swoim algorytmie? Czy Twój algorytm jest rekurencyjny czy iteracyjny?
5. Zapisz w notacji prefiksowej (notacja polska Łukasiewicza) następujące wyrażenia (z uwzględnieniem priorytetów występujących tam operatorów):
   1. d / 4 * a / c * b
   2. 3 * x - y / 7 + z
   3. 1 + 2 * x ^ 2 ^ (y / 4 - 8)
6. Wylicz wartość zapisanych w notacji ONP następujących wyrażeń:
   1. 7 5 3 2 + / ^
   2. 2 8 ^ 4 / 6 +
   3. 3 2 17 13 - ^ * 7 5 + / 19 + 11 -
   4. 1 1 1 1 + * 1 1 + 1 + * 1 + 1 + *
   5. 3 2 1 + ^ 1 - 2 / 3 - 2 3 1 + * - 2 ^ 1 - 3 ^
   6. 10 16 14 - ^ 12 18 + - 26 + 28 22 - / 24 + 20 /
7. Zapisz w notacji ONP następujące wyrażenia:
   1. d / (4 * a / (c * b))
   2. 3 * (x - y) / (7 + z)
   3. (1 + 2 * x) ^ 2 ^ (y / 4 - 8)

17 listopada 2017 r: sortowanie (lista 5)

1. Dwa elementy w ciągu pozostają w inwersji, gdy nie pozostają w relacji ≤, czyli w ciągu A dla i<j mamy A_i>A_j. Uzasadnij, że algorytm sortowania bąbelkowego na ciągu n-elementowym wykona liniową liczbę zamian elementów Ο(n) (chociaż liczba porównań może być kwadratowa jeśli nie zastosujemy żadnej optymalizacji) w przypadku, gdy liczba inwersji związanych z każdym elementem jest stała Ο(1).
2. Transpozycja elementów w ciągu to zamiana miejscami tych elementów. W posortowanym n-elementowym ciągu dokonujemy losowej transpozycji. Jak zmodyfikować algorytm sortowania bąbelkowego, aby działał w liniowym czasie Ο(n) dla takich danych?
3. Uzasadnij, że algorytm sortowania przez wstawianie na ciągu n-elementowym wykona liniową liczbę porównań i zamian elementów Ο(n) (i będzie tym samym działał w liniowym czasie), gdy całkowita liczba inwersji w sortowanym ciągu jest liniowa Ο(n).
4. W posortowanym n-elementowym ciągu dokonujemy losowej transpozycji. Ile porównań elementów w średnim przypadku wykona algorytm sortowania przez wstawianie, gdy uruchomimy go na takim ciągu?
5. Algorytm pracujący na ciągu z danymi jest stabilny, gdy elementy o równej wartości będą występowały w takiej samej względnej kolejności po wykonaniu algorytmu, jaką miały w ciągu pierwotnym. Podaj przykład na to, że algorytm sortowania przez wybieranie nie jest stabilny.
6. Dokładnie oszacuj z góry i z dołu liczbę porównań i liczbę zamian wykonywanych przez algorytm sortowania przez wybieranie, jeśli uruchomimy go na ciągu n-elementowym.

1 grudnia 2017 r: sortowanie (lista 6)

1. W posortowanym n-elementowym ciągu dokonujemy losowej transpozycji dwóch różnych elementów. Ile porównań elementów w średnim przypadku wykona algorytm sortowania przez wstawianie, gdy uruchomimy go na takim ciągu?
2. Podaj przykład danych wejściowych, dla których algorytm sortowania przez wstawianie wykona:
   1. Ο(n) operacji;
   2. Ω(n²) operacji;
   3. Θ(n^1.5) operacji.
3. Posortowany n-elementowy ciąg został pocięty na √n kawałków, każdy o długości √n (zakładamy, że n jest kwadratem jakiejś liczby naturalnej). Kawałki te zostały potem losowo wymieszane ze sobą i znowu połączone w ciąg (każdy fragment pozostał jednak uporządkowany). Jak zaadoptować algorytm sortowania przez wybieranie do takich danych, aby działał on w czasie liniowym Ο(n). Zakładamy, że dane dostarczone do algorytmu znajdują się w tablicy.
4. Dany jest n-elementowy ciąg liczb całkowitych z zakresu od 0 do n²-1. Opisz algorytm sortowania, który dla takich danych będzie działał w czasie liniowym Ο(n).

8 grudnia 2017 r: sortowanie (lista 7)

1. W tablicy n-elementowej zapisane są dwa posortowane ciągi: pierwszy ciąg o długości m a za nim drugi ciąg o długości n-m. Opracuj algorytm scalania tych ciągów, który będzie korzystał z zewnętrznego bufora pomocniczego o rozmiarze min{m, n-m}. Zadbaj o to, aby opracowana metoda była stabilna i działała w miejscu. Opisz ideę działania algorytmu a potem zapisz go w pseudokodzie. Złożoność czasowa tego algorytmu powinna być liniowa Ο(n).
2. W tablicy n-elementowej zapisane są dwa posortowane ciągi: pierwszy ciąg o długości m a za nim drugi ciąg o długości n-m. Opracuj algorytm obliczania liczby inwersji występujących w tym ciągu. Opisz ideę działania algorytmu a potem zapisz go w pseudokodzie. Złożoność czasowa tego algorytmu powinna być liniowa Ο(n).
3. W tablicy n-elementowej zapisana jest jakaś permutacja. Opracuj algorytm obliczania liczby inwersji występujących w tej permutacji. Opisz ideę działania algorytmu a potem zapisz go w pseudokodzie. Złożoność czasowa tego algorytmu powinna być liniowo-logarytmiczna Ο(n·log n) dla danych rozmiaru n.
   Wskazówka: zaadoptuj sortowanie przez scalanie.
4. Jak zmodyfikować algorytm sortowania szybkiego, aby w każdym przypadku głębokość wywołań rekurencyjnych była nie większa niż log(n) dla danych rozmiaru n?
   Wskazówka: jedno z wywołań rekurencyjnych rozwiń w miejscu.
5. W n-elementowej tablicy A[0...n-1] zapisany jest rosnący ciąg liczb całkowitych (może on rozpoczynać się od liczby ujemnej a kończyć na dodatniej). Opracuj algorytm sprawdzania, czy w tym ciągu znajduje się chociaż jedna taka liczba x, że A[x] = x. Złożoność czasowa tego algorytmu powinna być lepsza niż liniowa o(n).

15 grudnia 2017 r: dynamiczne struktury danych (lista 8)

1. Rozważmy listę nieuporządkowaną z wartościami, które mogą się często powtarzać. Opracuj algorytm usuwania zadanej wartości z takiej listy:
   1. usuń pierwsze wystąpienie zadanej wartości na liście;
   2. wszystkie wystąpienia na zadanej wartości liście;
   3. usuń ostatnie wystąpienie zadanej wartości na liście;
   Opisz ideę rozwiązania każdego zadania. Zapisz swoje algorytmy w pseudokodzie.
2. Opracuj algorytm odwracania listy jednokierunkowej. Metoda ta powinna działać w miejscu w liniowym czasie. Zapisz swoje algorytmy w pseudokodzie.
   Czy odwrócenie listy dwukierunkowej jest zadaniem prostszym czy trudniejszym?
3. Jak wskazać w liście środkowy element? Opisz taki algorytm i zapisz go w pseudokodzie.
4. Może (ale nie musi) tak się zdarzyć, że w ostatnim węźle listy będziemy mieli odniesienie do jakiegoś węzeła w środku tej samej listy (może to być również pierwszy albo ostatni węzeł w tej liście). Wówczas na końcu takiej lity powstanie cykl. Wymyśl metodę, która sprawdzi, czy zadana lista jest listą prostą czy listą z cyklem na końcu. Opracuj algorytm, który rozwiązuje ten problem w liniowym czasie i zapisz go w pseudokodzie.
   Czy można zmodyfikować przedstawiony algorytm, aby dodatkowo wyliczał on długość całej listy?

22 grudnia 2017 r: dynamiczne struktury danych (lista 9)

1. Dane jest drzewo BST. Jak przekształcić to drzewo w posortowaną listę? Opisz algorytm i zapisz go w pseudokodzie.
2. Opracuj metodę, która pozwoli wyszukać w drzewie BST węzeł z zadaną wartością i potem za pomoca rotacji przesunąć ten węzeł do korzenia drzewa. Opisz taki algorytm i zapisz go w pseudokodzie.
3. Opracuj metodę, która pozwoli wyszukać w drzewie BST węzeł z natępnikiem zadanej wartości. Opisz taki algorytm i zapisz go w pseudokodzie.
4. Udowodnij, że wysokość drzewa czerwono-czarnego jest logarytmiczna w stosunku do liczby występujących w nim węzłów.
5. Opisz ideę łączenia ze sobą pary kopców lewicowych. Zapisz w pseudokodzie procedurę łączącą dwa kopce lewicowe.

słowniki i kolejki priorytetowe (lista 10)

1. Przedstaw algorytm, który podzieli drzewo BST na dwa odrębne drzewa BST względem zadanej wartości x. W jednym z wynikowych drzew mają się znaleźć wszystkie węzły pierwotnego BST z kluczami ≤x a w drugim z kluczami >x. Czas działania twojego algorytmu powinien być ograniczony przez głębokość węzła z wartością x w pierwotnym drzewie BST.
2. Opracuj algorytm i zapisz go w pseudokodzie, który znajdzie element poprzedni (albo następny) co do wielkości względem zadanej wartości klucza x w drzewie BST.
3. Zaprojektuj strukturę danych wykorzystującą kolejki priorytetowe, która będzie efektywnie realizowała operacje insert (wstawienie nowego elementu do zbioru) oraz extract-median (usunięcie ze zbioru elementu środkowego co do wielkości, czyli mediany). Operacje te powinny działać w czasie logarytmincznym względem rozmiaru danych. Opisz dokładnie działanie tych operacji i przeanalizuj złożoność obliczeniową każdej z nich.
4. Pokaż, jak za pomocą kolejki priorytetowej zaimplementować bufor FIFO albo LIFO.

wyrażenia regularne, gramatyki bezkontekstowe, automaty skończone (lista 11)

1. Napisz wyrażenie regularne, do którego dopasuje się:
   1. poprawnie zapisana godzina z dokładnością do minut albo sekund (na przykład 14:51, 00:15, 17:03:59);
   2. poprawnie zapisana data (na przykład 2016-12-20, 2017-01-04, 2018-02-28) przy założeniu, że nigdy nie wystąpi data 29 lutego w roku przestępnym;
   3. poprawnie zapisana liczba zmiennopozycyjna z kropką dziesiętną (na przykład 123.45, -0.987, 0.00001);
   4. poprawnie zapisany adres mailowy (na przykład abc123@interia.pl, def.ghi@gmail.com), w którym symbol kropki rodziela nie puste ciągi liter i cyfr rozpoczynające się od litery.
2. Zdefiniuj gramatykę bezkontekstową, która będzie definiowała języki zawierające:
   1. poprawnie rozstawione nawiasy;
   2. niepuste słowa zaczynające się tą samą literą co litera końcowa.
3. Niech dany będzie alfabet złożony z trzech liter Σ = {a, b, c}. Skonstruuj automat skończony akceptujący tylko słowa, które:
   1. mają nieparzystą długość;
   2. kończą się sufiksem baba;
   3. są niepuste i w których nie ma obok siebie dwóch takich samych liter;
   4. są niepustym ciągiem takich samych liter (na przykład bb, a, cccc).
4. Zaprojektuj automat skończony akceptujący liczby podzielne przez 3 zapisane w systemie dwójkowym.
5. Zaprojektuj automat skończony akceptujący liczby podzielne przez 9 zapisane w systemie dziesiętnym.

grafy (lista 12)

1. Zbadaj, czy istnieje graf o 6 wierzchołkach, których stopnie tworzą ciąg:
   1. (6, 2, 2, 2, 1, 1);
   2. (5, 3, 3, 3, 3, 1);
   3. (5, 4, 4, 3, 3, 2);
   4. (5, 5, 5, 5, 3, 3);
   5. (5, 5, 4, 3, 3, 2);
   6. (5, 5, 3, 3, 2, 2);
   Odpowiedź uzasadnij.
2. Wykaż, że w każdej grupie złożonej z więcej niż dwóch osób, zawsze są dwie osoby, które mają w tej grupie taką samą liczbę znajomych.
3. Wykaż, że w grupie sześciu osób zawsze znajdą się trzy takie, które albo znają się nawzajem, albo żadna z nich nie zna dwóch pozostałych.
4. Pokaż, że graf jest dwudzielny wtedy i tylko wtedy, gdy nie zawiera cyklu nieparzystej długości.
5. Niech G będzie grafem prostym z co najmniej dwoma wierzchołkami. Wykaż, że G zawiera dwa wierzchołki tego samego stopnia.
6. Niech G będzie grafem prostym, w którym każdy wierzchołek ma co najmniej r ≥ 2 sąsiadów. Wykaż, że G zawiera cykl o długości co najmniej r + 1.
7. Mostem w grafie spójnym nazywamy taką krawędź, której usunięcie spowoduje, że graf przestanie być spójny. Wykaż, że jeśli w grafie każdy wierzchołek ma parzysty stopień, to graf ten nie ma mostu.
8. Wykaż, że graf dwudzielny o nieparzystej liczbie wierzchołków nie ma cyklu Hamiltona.
9. Czy drzewo jest grafem dwudzielnym? Odpowiedź uzasadnij.

laboratorium

Zasady zaliczenia przedmiotu

Ogólnie:

W semestrze będzie opublikowanych na themisie i na tej stronie kilkanaście list z zadaniami programistycznymi. Część zadań będzie realizowana na laboratoriach a część będzie do zrealizowania w domu.

Obecności:

Obecność na laboratoriach jest obowiązkowa. Aby zaliczyć laboratorium Student musi uczestniczyć w co najmniej 60% zajęć.

Zadania programistyczne:

Za każde zaprogramowane zadanie w trakcie laboratorium można uzyskać do 4 punktów (za zadanie przesłane po zajęciach do 2 punktów). Za każde zaprogramowane zadanie domowe można uzyskać do 2 punktów (za zadanie przesłane po terminie do 1 punkta).

Plagiaty:

Zadań programistycznych nie wolno kopiować. Studentów, których złapię na wysyłaniu izomorficznych rozwiązań po raz pierwszy otrzymają po -20 punktów karnych. Druga próba kopiowania rozwiązań to -40 punktów karnych i notatka do Dziekana. Trzecia próba oszustwa zakończy się niezaliczeniem przedmiotu i wnioskiem do Wydziałowej Komisji Dyscyplinarnej. Uwaga: mam narzędzie do automatycznego sprawdzania podobieństw programów, aby skuteczniej wyszukiwać potencjalnych przestępców!

Oceny zaliczeniowe:

Aby zaliczyć laboratorium na ocenę dostateczną Student potrzebuje zgromadzić do końca semestru co najmniej 40% możliwych do zdobycia punktów. Na ocenę bardzo dobrą Student potrzebuje zgromadzić 80% możliwych do zdobycia punktów. Oceny pośrednie pozostaną w liniowej zależności od przedstawionych wymagań granicznych.

Zadania laboratoryjne

1. ...