wstęp do informatyki i programowania (semestr zimowy 2015)

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.

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 i obiektowego oraz podstawowe elementy z biblioteki standardowej STL. Krótkie i proste przykłady powinny wspomóc naukę programowania w tym języku.

Informacje ogólne

Wymagane przygotowanie

• Dobra znajomość matematyki na poziomie szkoły średniej.

Terminarz

• wykład: wtorek 8-11 s.601 w IMat (Paweł Rzechonek)
• konwersatorium: wtorek 12-13 s.601 w IMat (Paweł Rzechonek)
• ćwiczenia:
  wtorek 11-12 s.601 w IMat (Paweł Rzechonek)
  środa 10-11 s.WS w IMat (Krzysztof Tabisz)
• laboratoria:
  środa 8-10 s.417 IMat (Krzysztof Tabisz)
  środa 16-18 s.6 IInf (Paweł Rzechonek)
  piątek 9-11 s.6 IInf (Bartosz Rybicki)

Literatura

Literatura podstawowa algorytmiczna:

• T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein: Wprowadzenie do algorytmów. Nowe wydanie. PWN, Warszawa 2012.
• L.Banachowski, K.Diks, W.Rytter: Algorytmy i struktury danych. Wydanie 5. WNT, Warszawa 2011.
• P.Wróblewski: Algorytmy, struktury danych i techniki programowania. Wydanie 4. Helion, Gliwice 2009.

Literatura uzupełniająca algorytmiczna:

• T.H.Cormen: Algorytmy bez tajemnic. Helion, Gliwice 2013.
• 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:

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

Literatura uzupełniająca programistyczna:

• 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.

Literatura elektroniczna programistyczna:

• 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

Zajęcia przedmiotowe

Zasady zaliczenia przedmiotu

Zaliczenie ćwiczeń

Ogólnie:

W semestrze będzie opublikowanych na tej stronie kilkanaście list z zadaniami teoretycznymi. Na ćwiczeniach Studenci mają prezentować rozwiązania tych zadań.

Obecności:

Obecność na ćwiczeniach jest obowiązkowa. Za każdą obecność na ćwiczeniach Student otrzymuje 1 punkt. Aby zaliczyć ćwiczenia Student musi uczestniczyć w co najmniej 60% zajęć.

Zadania:

Za prezentację podczas ćwiczeń poprawnego rozwiązania zadania z listy można uzyskać do 2 punktów (za zadanie trudniejsze do 3 punktów, za zadanie trudne do 4 punktów). W trakcie prezentacji rozwiązania trzeba się liczyć z pytamiami dotyczącymi zadania, na które Student powinien odpowiedzieć, jeśli dobrze rozumie treść zadania i sposób jego rozwiązania.

Oceny zaliczeniowe:

Aby Student zaliczył ćwiczenia na ocenę dostateczną potrzebuje do końca semestru zgromadzić co najmniej 15 punktów (liczba ćwiczeń plus 1, więc każdy co najmniej raz ma zaprezentować poprawne rozwiązanie zadania przy tablicy). Oceny wyższe będą wynikały z rankingu i oceny własnej Nauczyciela prowadzącego ćwiczenia.

Zaliczenie laboratorium

Ogólnie:

W semestrze będzie opublikowanych na tej stronie kilkanaście zadań programistycznych. Na laboratoriach Studenci mają programować określone zadania.

Obecności:

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

Zadania:

Za zaprogramowane zadanie z listy w trakcie laboratorium można uzyskać do 10 punktów. W trakcie prezentacji programu trzeba się liczyć z pytamiami dotyczącymi rozwiązania, na które Student powinien odpowiedzieć.

Oceny zaliczeniowe :

Aby Student zaliczył laboratorium na ocenę dostateczną potrzebuje do końca semestru zgromadzić co najmniej 60 punktów. Na ocenę bardzo dobrą Student potrzebuje zgromadzić 120 punktów. Oceny pośrednie pozostją w liniowej zależności od przedstawionych wymagań granicznych.

Kolokwia i egzaminy

Ogólnie:

W semestrze będą przeprowadzone 3 kolokwia oraz egzamin końcowy. Kolokwia i egzamin będą dotyczyły części teoretycznej omawianej na wykładzie.

Szczegóły:

Każde kolokwium i egzamin będzie się składać z dwóch części: części testowej i części zadaniowej. Część testowa będzie się składać z kilku/kilkunastu pytań otwartych, na które trzeba krótko i precyzyjnie odpowiedzieć. Część zadaniowa będzie polegała na rozwiązaniu zadania algorytmicznego (zadania będą podobne do tych z list ćwiczeniowych), czyli przedstawieniu idei rozwiązania, dokładnego opisu algorytmu, uzasadnienia jego poprawności i analizie złożoności obliczeniowej.

Zaliczenie:

Kolokwium/egzamin uznaje się za zaliczony, gdy Student uzyska co najmniej 40% punktów z części testowej oraz co najmniej 40% punktów z części zadaniowej.

Oceny:

Aby zaliczyć kolokwium/egzamin na ocenę dostateczną trzeba zdobyć 40% z wszystkich możliwych do uzyskania punktów; na ocenę bardzo dobrą trzeba będzie zdobyć 80% punktów; oceny pośrednie pozostają w liniowej zależności od przedstawionych wymagań granicznych.

Terminy:

Terminy kolokwiów będą ogłaszane na wykładzie co najmniej jeden tydzień wcześniej. Termin egzaminu zostanie ustalony w styczniu i ogłoszony na wykładzie co najmniej dwa tygodnie wcześniej. Wszystkie wymienione terminy będą też opublikowane na tej stronie (patrz na ogłoszenia).

Kolokwia:

W semestrze będą trzy kolokwia i nie będzie kolokwiów poprawkowych. Gdy Student zda wszystkie trzy kolokwia i będzie miał zaliczone ćwiczenia i laboratorium, to może ubiegać się na tej podstawie o zwolnienie z egzaminu. Ostateczną decycję w tej sprawie podejmę indywidualnie w stosunku do każdego Studenta pod koniec semestru.

Egzamin:

Student może przystąpić do egzaminu, gdy ma zaliczone ćwiczenia i laboratorium. Gdy Student nie zdał egzaminu albo był nieobecny na egzaminie, to może przystąpić do zdawania egzaminu poprawkowego. Będzie tylko jeden egzamin poprawkowy.

Wykład

6 października 2015 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].

13 października 2015 r. (rekurencja)

• pojęcie rekurencji
• obliczanie silni z wykorzystaniem rekurencji
• 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
• wyznaczanie n-tej liczby w ciągu Fibonacciego algorytmem rekurencyjnym, algorytmem liniowym oraz metodą macierzową

20 października 2015 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

27 października 2015 r. (odwrotna notacja polska)

• tablica
• stos
• kolejka
• implementacja stosu i kolejki na tablicy
• wyrażenia algebraiczne zapisane w NP Łukasiewicza
• wyrażenia algebraiczne zapisane w ONP
• obliczanie wyrażeń w postaci postfiksowej - wykorzystanie kolejki i stosu
• przekształcanie wyrażeń z postaci infiksowej do postfiksowej - algorytm Dijkstry

3 listopada 2015 r. (koszt zamortyzowany)

• tablicowa implementacja stosu i kolejki
• koszt zamortyzowany na przykładzie stosu z operacjami push, pop i multipop:
  • metoda sumaryczna
  • metoda księgowania
  • metoda potencjału
• tablica dynamiczna

10 listopada 2015 r. (dynamiczne struktury danych)

• słownik i operacje słownikowe
• lista jako struktura sekwencyjna
• listy jednokierunkowe i dwukierunkowe
• listy cykliczne
• listy 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 k-arne
• drzewa binarne
• drzewa BST z porządkiem symetrycznym
• implementacja operacji słownikowych na drzewach BST
• slajdy z wykładu: ListyDrzewa.ppt

17, 24 listopada 2015 r. (grafy)

• pojęcie grafu
• reprezentacja grafu gęstego w postaci macierzy sąsiedztwa
• reprezentacja grafu rzadkiego w postaci list sąsiadów
• grafy eulerowskie
• grafy hamiltonowskie
• spójność grafu
• drzewa
• grafy skierowane
• grafy ważone
• minimalne drzewo rozpinające w grafie - algorytm Kruskala
• najkrótsze ścieżki w grafie - algorytm Dijkstry, algorytm Floyda-Warshalla
• slajdy z wykładu: Grafy.ppt

24 listopada 2015 r. (kolokwium I)

Ćwiczenia

6, 7 października 2015 r. (lista 1: schematy blokowe)

1. Narysuj schemat blokowy dla zadania wyznaczania znaku dla zadanej liczby (funkcja signum).
2. Narysuj schemat blokowy dla zadania rozwiązywania równania liniowego dla zadanych współczynników.
3. Narysuj schemat blokowy dla zadania obliczania sumy kolejnycyh liczb naturalnych od 1 do zadanej wartości k.
4. Narysuj schemat blokowy dla zadania obliczania silni dla zadanej wartości n.

13, 14 października 2015 r. (lista 2: szacowanie złożoności obliczeniowej algorytmów)

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 ≡:
   • (n+1)^0.5
   • 3·n²+5·n
   • 2ⁿ
   • 5·n+3
   • nⁿ⁺¹
   • n^0.1
   • log₂(5·n)
   • 2·n³+5
   • 3^2·n
   • √n
   • 4ⁿ⁺¹
   • log₃(n⁵)
   • (n+1)ⁿ
   • 3ⁿ⁺²
   • 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, 21 października 2015 r. (lista 3: rekurencja)

1. Jak za pomocą rekurencji wyrazić sumę kolejnych liczb całkowitych z zadanego zakresu od a do b, gdzie a≤b? Napisz w pseudokodzie funkcję rekurencyjną implementującą ten wzór. Jaka będzie złożoność obliczeniowa tej funkcji?
2. Jak za pomocą rekurencji wyrazić operację znajdowania wartości minimalnej dla zadanego skończonego ciągu liczbowego? 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ą interpreację 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.

27, 28 października 2015 r. (lista 4: liczby w zapisie binarnym)

1. Zapisz w postaci schematu blokowego algorytm generowania binarnej reprezentacji liczby naturalnej, zaczynając od najmniej znaczącego bitu.
2. Zapisz w postaci schematu blokowego algorytm generowania binarnej reprezentacji liczby rzeczywistej z przedziału (0, 1) z dokładnością do k miejsc po kropce dwójkowej.
3. Zapisz w postaci schematu blokowego algorytm inkrementacji (zwiększenia o 1) i algorytm dekrementacji (zmniejszenia o 1) zadanej liczby całkowitej zapisanej w postaci U2.
4. Zapisz w postaci schematu blokowego algorytm zmiany znaku w binarnej liczbie całkowitej zapisanej w postaci U2.
5. Jak wyrazić zmianę znaku w liczbie całkowitej zapisanej binarnie w postaci U2 za pomocą operacji negacji bitowej NOT oraz inkrementacji albo dekrementacji?
6. (trudniejsze) Zapisz w postaci schematu blokowego algorytm wyznaczania pierwszego zapalonego (ustawionego na 1) najmniej znaczącego bitu w binarnej liczbie całkowitej zapisanej w postaci U2.
7. (trudniejsze) Jak wyznaczyć pierwszy zapalony najmniej znaczący bit w binarnej liczbie całkowitej zapisanej w postaci U2 za pomocą operacji bitowych (AND, OR, XOR oraz przesunięć SHL i SHR) oraz inkrementacji i dekrementacji?
8. Zapisz następujące liczby dziesiętne postaci dwójkowej stosując kodowanie ZM, U1 i U2:
   1. 245
   2. 1968
   3. 57391
   4. -4286
9. Zapisz następujące liczby w postaci binarnej stałopozycyjnej z dokładnością do 6 bitów po kropce dwójkowej:
   1. 2/49
   2. 9+1/7
   3. -3/21
   4. -16-4/35
10. Zapisz następujące liczby w postaci binarnej zmiennopozycyjnej w obiekcie typu single zgodnie ze standardem IEEE-754:
    1. 1.5859375
    2. -0.046875
    3. 9.46875
    4. -19375.0
11. Wylicz, jaka jest najmniejsza i największa wartość dodatnia, którą można zapisać w notacji zmiennopozycyjnej w obiekcie typu double zgodnie ze standardem IEEE-754.

3, 4 listopada 2015 r. (lista 5: odwrotna notacja polska)

1. (trudniejsze) 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. (trudniejsze) Opracuj algorytm obliczania wartości wyrażenia zapisanego w postaci prefiksowej (notacja polska Łukasiewicza). Jakie struktury danych wykorzystujesz w swoim algorytmie? Czy Twój algorytm jest rekurencyjny czy iteracyjny?
3. 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)
4. (trudne) Opracuj algorytm przekształcania wyrażenia zapisanego w postaci postfiksowej (odwrotnej notacji polskiej) na postać infiksową (naturalną). Jakie struktury danych wykorzystujesz w swoim algorytmie? Czy Twój algorytm jest rekurencyjny czy iteracyjny?
5. Wylicz wartość zapisanych w notacji postfiksowej (odwrotna notacja polska) 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 /
6. Zapisz w notacji postfiksowej (odwrotna notacja polska) 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)

10, 11 listopada 2015 r. (lista 6: koszt zamortyzowany)

1. Rozważ k-bitowy licznik binarny. Wykaż, że złożoność czasowa ciągu n operacji increment() na tym liczniku jest liniowa O(n). Jaki będzie koszt czasowy wykonania pojedynczej operacji increment() w najgorszym przypadku? Pokaż, że zamortyzowany koszt czasowy wykonania jednej operacji na takiej strukturze będzie stały O(1) Zastosuj metodę księgowania albo kosztu sumarycznego.
2. (trudniejsze) Rozważ k-bitowy licznik binarny, przy czym licznik ten nie jest początkowo wyzerowany. Wykaż, że złożoność czasowa ciągu n operacji increment() na tym liczniku będzie liniowa O(n), gdy założymy, że n>k. Zastosuj metodę kosztu sumarycznego.
3. Rozważ k-bitowy licznik binarny z operacjami increment() i decrement(). Uzasadnij, że koszt czasowy wykonania ciągu n operacji na takim liczniku wynosi O(k·n). Podaj przykład takiego kosztownego ciągu operacji.
4. (trudniejsze) Rozważ tablicę dynamiczną, o początkowej pojemności równej 1. Na tablicy tej możemy wykonywać operacje odczytu i zapisu danych do zajętych komórek oraz operację push() dokładającą nowy element na koniec tablicy. Dokonaj zamortyzowanej analizy kosztu czasowego wykonania ciągu n operacji na takiej strukturze. Zastosuj metodę potencjału - jako funkcję potencjału przyjmij: 2·zajętość - pojemność.

17, 18 października 2015 r. (lista 7: kolejka i stos)

1. Kolejkę można zaimplementować za pomocą dwóch stosów (do jednego stosu tylko wkładamy elementy a z drugiego tylko wyjmujemy). Pokaż, jak zaimplementować kolejkę, używając dwóch stosów.
   Wykaż, że złożoność czasowa ciągu n operacji enqueue() i dequeue() na takiej kolejce jest liniowa O(n). Jaki będzie koszt czasowy wykonania pojedynczej operacji dequeue() w najgorszym przypadku? Pokaż, że zamortyzowany koszt czasowy wykonania jednej operacji na takiej strukturze będzie stały O(1). Zastosuj metodę księgowania.
2. Pokaż, jak odwrócić kolejność elementów w kolejce. Oszacuj złożoność czasową i pamięciową wykonania takiej operacji.
   Możesz używać jako struktur pomocniczych tylko kolejek i stosów.
3. Pokaż, jak odwrócić kolejność elementów na stosie. Oszacuj złożoność czasową i pamięciową wykonania takiej operacji.
   Możesz używać jako struktur pomocniczych tylko kolejek i stosów.
4. (trudniejsze) Pokaż, jak odwrócić kolejność elementów w kolejce czy na stosie, przy założeniu, że mamy do czynienia z tablicową implementacją tych struktur.
   Odwrócenie kolejności elementów w tych strukturach należy wykonać w stałym czasie!

24, 25 listopada 2015 r. (lista 8: listy)

1. Zaimplementuj w pseudokodzie procedurę obliczającą długość listy jednokierunkowej. Napisz wersję iteracyjną i rekurencyjną tej procedury. Porównaj złożoność czasową i pamięciową obu procedur.
2. (trudniejsze) Zaimplementuj w pseudokodzie rekurencyjną procedurę usuwania zadanej wartości z listy jednokierunkowej. Napisz jedną wersją tej procedury dla przypadku, gdy należy usunąć pierwsze wystąpienie zadanej wartości, drugą wersję, gdy należy usunąć ostatnie wystąpienie oraz trzecią wersję dla przypadku, gdy należy usunąć wszystkie wystąpienia zadanej wartości.
3. (trudniejsze) Zaprojektuj algorytm odwracania listy jednokierunkowej złożonej z n węzłów. Metoda ta powinna działać w liniowym czasie O(n) i w stałej pamięci O(1). Przedstaw implementację tego algorytmu w pseudokodzie.
   Czy odwrócenie listy dwukierunkowej jest zadaniem prostszym czy trudniejszym?
4. (trudne) Rozważmy listę jednokierunkową bez wartownika. Może się tak zdarzyć, że wskaźnik na następnika w ostatnim węźle listy zamiast być pusty będzie wskazywał na jakiś węzeł w środku listy (może to być także pierwszy albo ostatni węzeł w tej liście). Wówczas na końcu tej lity powstanie cykl. Wymyśl metodę, która sprawdzi, czy zadana lista jest listą prostą czy listą z cyklem na końcu. Twój algorytm ma działać w liniowym czasie O(n) i w stałej pamięci O(1).
   Jak zmodyfikować przedstawiony algorytm, aby dodatkowo wyliczał on długość postałego cyklu (o ile taki cykl występuje na końcu listy) i długość całej listy. Twój algorytm po modyfikacji także ma działać w liniowym czasie O(n) i w stałej pamięci O(1).
5. Jak wstawić nowy element do posortowanej listy aby zachować uporządkowanie elementów? Możemy założyć, że lista jest dwukierunkowa. Opracuj odpowiedni algorytm i zapisz go w pseudokodzie.
6. Jak scalić dwie posortowane listy w jedną posortowaną listę? Możemy założyć, że lista jest dwukierunkowa. Opracuj odpowiedni algorytm i zapisz go w pseudokodzie.
7. (trudniejsze) Dana jest lista jednokierunkowa. Zaprojektuj algorytm, który wydzieli z tej listy podlistę z węzłami spełniającymi określony warunek (na przykład w liście przechowujemy liczby całkowite i należy wydzielić z niej podlistę z liczbami parzystymi). W wyniku mamy otrzymać dwie rozłączne listy. Napisz odpowiednią procedurę w pseudokodzie.

1, 2 grudnia 2015 r. (lista 9: drzewa BST)

1. Znajdź wszystkie drzewa binarne, których węzły tworzą ten sam ciąg, gdy wypisze się je w porządkach:
   1. preorder i inorder,
   2. preorder i postorder,
   3. inorder i postorder.
   Zakładamy, że żadne dwie wartości w takich drzewach nie powtarzają się.
2. Pokaż, jak za pomocą kolejki można wypisać zawartość drzewa binarnego poziomami (korzeń znajduje się na poziomie 0, synowie korzenia na poziomie 1, jego wnukowie na poziomie 2, itd).
3. (trudniejsze) Węzły pewnego drzewa binarnego zostały wypisane w porządku inorder i preorder. Pokaż, jak za pomocą stosów można odtworzyć strukturę drzewa, mając takie dwa ciągi danych. Zakładamy, że żadne dwie wartości w tym drzewie nie powtarzają się.
4. Wylicz, ile jest różnych drzew binarnych o n węzłach. Ułóż odpowiednie równanie rekurencyjne i przedstaw jego rozwiązanie (liczby Catalana). Udowodnij, że znalezione (w podręczniku lub w internecie) rozwiązanie tego równania jest prawdziwe (indukcja).
5. (trudniejsze) Budujemy n-elementowe drzewo BST wstawiając do niego w losowej kolejności liczby naturalne 1, 2, …, n. Zakładamy, że każdy ciąg wstawień (permutacja 1, 2, …, n) jest jednakowo prawdopodobny, oraz że n = 2^k-1.
   1. Jakie jest prawdopodobieństwo, że zbudowane drzewo będzie drzewem pełnym o wysokości krawędziowej k-1?
   2. Jakie jest prawdopodobieństwo, że zbudowane drzewo będzie listą, czyli drzewem o wysokości krawędziowej 2^k-2 (każdy węzeł oprócz jedynego liścia posiada tylko lewego albo prawego syna)?
6. (trudne) Przedstaw algorytm, który podzieli drzewo BST na dwa odrębne drzewa BST względem zadanej wartości klucza 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.
7. Napisz w pseudokodzie procedurę, które znajdzie element poprzedni (albo następny) co do wielkości względem zadanej wartości klucza x w drzewie BST.

8, 9 grudnia 2015 r. (lista 10: grafy)

1. Ile jest różnych nieizomorficznych grafów o 4 wierzchołkach? Narysuj je wszystkie.
2. Zbadaj, czy istnieje graf prosty 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
3. Wykaż, że w każdej grupie złożonej z 2 lub więcej osób są zawsze 2 osoby, które mają taką samą liczbę znajomych.
4. Pokaż,że istnieje taka grupa 5 osób, w której nie ma ani 3 osób znających się zawzajem, ani 3 osób takich, że żadna z nich nie zna dwóch pozostałych.
5. Wykaż, że istnieje dokładnie 2^n(n-1)/2 oznakowanych grafów prostych mających n wierzchołków. Ile z nich ma dokładnie m krawędzi?
6. Niech G będzie grafem mającym dokładnie n wierzchołków i m krawędzi. Ile wierzchołków i krawędzi będzie miał ten graf, gdy:
   1. usuniemy z niego jedną krawędź
   2. usuniemy z niego jeden wierzchołek wraz z incydentnymi z nim krawędziami
   3. usuniemy z niego jedną krawędź wraz z incydentnymi z nim wierzchołkami i krawędziami
7. Wykaż, że graf dwudzielny o nieparzystej liczbie wierzchołków nie ma cyklu Hamiltona.
8. Wykaż, że graf prosty i jego dopełnienie nie mogą jednocześnie być niespójne.
9. Mostem w grafie spójnym nazywamy taką krawędź, że jej usunięcie rozspoi graf. Wykaż, że jeśli w grafie G każdy wierzchołek ma parzysty stopień, to w grafie G nie mam mostu.

15, 16 grudnia 2015 r. (lista 11: teoria informacji)

1. (łatwe) Dany jest zbiór n=2^m symboli S = {x₁,...,x_n}. Symbole te pojawiają się niezależnie w komunikatach z jednakowym prawdopodobieństwem P(x_i) = 2^-m dla i = 1,...,n. Jaka jest wartość informacji skojarzonej z pojedynczym symbolem z tego zbioru?
2. Dany jest zbiór n symboli S = {x₁,...,x_n}. Symbole te pojawiają się niezależnie w komunikatach z prawdopodobieństwami P(x_i) = 2^-i dla i = 1,...,n-1 oraz P(x_n) = 2^1-n. Ile informacji zawierają poszczególne symbole I(x_i) dla i = 1,...,n? Jaka jest entropia stowarzyszona z tym zbiorem symboli H(S)?
3. Dany jest zbiór 4 symboli S = {a, b, c, d}. Wyznacz entropię tego zbioru w przypadku następujących prawdopodobieństw:
   1. P(a) = P(b) = P(c) = P(d) = 1/4
   2. P(a) = 1/2, P(b) = 1/4, P(c) = P(d) = 1/8
   3. P(a) = 3/8, P(b) = P(c) = 1/4, P(d) = 1/8
   4. P(a) = 0.505, P(b) = 0.25, P(c) = 0.125, P(d) = 0.12
4. Informacja stowarzyszona ze zdarzeniem x_i występującym z prawdopodobieństwem p_i wyraża się wzorem I(x_i) = -log_k(p_i). Jaka powinna być podstawa logarytmu k, aby równanie to można było uznać za definicję bajtu? Odpowiedź uzasadnij.
5. Jaka ilość informacji jest zawarta w tablicy rejestracyjnej samochodu, która jest ciągiem 3 cyfr i następujących po nim 2 liter?
6. Jaka ilość informacji jest zawarta w ciągu kart pochodzących ze standartowej talii 52 kart?
7. Co to znaczy, że kod jest jednoznacznie dekodowalny? Sprawdź, czy następujące kody binarne są jednoznacznie dekodowalne:
   1. {0, 01, 11, 111}
   2. {0, 10, 110, 111}
   3. {1, 10, 110, 111}
   4. {1, 01, 001, 0001}
   Uzasadnij odpowiedzi.
8. Co to znaczy, że kod ma właściwość prefiksową? Sprawdź, czy następujące kody binarne są prefiksowe:
   1. {01, 001, 110, 111}
   2. {0, 10, 110, 111}
   3. {1, 00, 001, 110}
   4. {1, 0, 10, 01}
   Uzasadnij odpowiedzi.
9. (trudniejsze) Nierówność Krafta można stosować nie tylko do kodów binarnych lecz także do kodów o dowolnej liczbie liter r: Σ_i=1ⁿ (r^-l_i) ≤ 1. Jakie jest minimalne r, dla którego istnieje kod prefiksowy o długościach:
   1. {1, 1, 2, 2, 3, 3, 4, 4, 4}
   2. {1, 2, 2, 2, 2, 2, 2, 3, 3}
   3. {1, 3, 3, 3, 5, 5, 5, 7}
   4. {2, 2, 2, 2, 2, 2, 3, 3, 3, 3}
10. (trudne) Dla 3-literowego alfabetu źródłowego S = {a, b, c} i dla zbioru 2-literowych ciągów S₂ = {aa, ab, ac, ba, bb, bc, ca, cb, cc} wykaż, że H(S₂) = 2·H(S) przy założeniu, że źródło komunikatów generuje litery niezależnie od siebie. Uogólnij ten dowód na przypadek H(S_k) = k·H(S) dla dowolnego k.

22, 23 grudnia 2015 r. (lista 12: kompresja danych)

1. (trudne) Sformułuj najbardziej ogólny warunek, który zagwarantuje jednakową długość wszystkich słów kodowych wygenerowanych przez algorytm Huffmana. Uzasadnij, że jest on wystarczający.  
2. Pewne źródło danych generuje tekst złożony z liter alfabetu S = {a, b, c}. Prawdopodobieństwa odpowiadające poszczególnym literom wynoszą P = {0.8, 0.1, 0.1}. Wyznacz entropię H(S) tego źródła i porównaj ze średnią długością kodu wyznaczoną przez algorytm Huffmana dla liter alfabetu S. Czy średnią długością kodu jest wystarczająco bliska entropii H(S)?
3. (łatwe) Pewne źródło generuje 7-bitowe znaki z pewnego 128-literowego alfabetu: cztery z nich z ppb 1/16, dwanaście z ppb 1/48, czterdzieści osiem z ppb 1/192 i pozostałe sześćdziesiąt cztery z ppb 1/256. Gdyby znaki te miały kody wygenerowane za pomocą algorytmu Huffmana, to jaka byłaby średnia długość słowa kodowego?
4. (trudniejsze) Gdy prawdopodobieństwa występowania poszczególnych symboli znacznie się różnią, często stosuje się kodowanie nie pojedynczych symboli ale grup kilku znaków naraz - przyjmuje się, że prawdopodobieństwo wystąpienia danego ciągu jest iloczynem prawdopodobieństw występujących w nim symboli (zakładamy niezależność zdarzeń). Rozważmy więc źródło, które generuje cyfry z alfabetu S = {0, 1} z prawdopodobieństwami P(0) = 0.1 i P(1) = 0.9. Utwórz kod Huffmana dla tego źródła, w którym połączono m bitów w jeden symbol, dla m = 1, 2,... 8. Jakie są średnie długości słów kodowych dla poszczególnych wartości m? Jaka jest entropia tego źródła H(S)?
5. ...

5, 6 stycznia 2016 r. (lista 13: wyszukiwanie wzorca w tekście)

1. (łatwe) Rozważmy alfabet S = {a, b, c, d, e, f}, wzorzec P = "abecadabe" i tekst T = = "aababecabecadabecadabecafbabefababecadabecad". Ile dokładnie porównań wykona naiwny algorytm wyszukiwania wzorca P w tekście T i jaki wynik zwróci?
2. Załóżmy, że wszystkie symbole we wzorcu P są parami różne. Jak można w takim przypadku przyspieszyć działanie algorytmu Boyera-Moore'a? Jaka będzie wtedy jego złożoność czasowa?
3. Jeśli w algorytmie Boyera-Moore'a pamiętalibyśmy nie tylko ostanie, ale wszystkie wystąpienia każdego symbolu we wzorcu, to jak by to mogło przyspieszyć działanie tego algorytmu? Jak wtedy zmieniłaby się jego złożoność pamięciowa i czasowa?
4. (trudniejsze) Załóżmy, że wzorzec P może zawierać pewną liczbę wystąpień sumbolu uniwersalnego ∗, który pasuje do dowolnego ciągu (również do ciągu pustego); symbole uniwersalne nie mogą występować obok siebie we wzorcu, ani na początku ani na końcu wzorca. Podaj algorytm sprawdzania, czy taki wzorzec P występuje w tekście T, a jeśli tak, to podaj pierwsze wystąpienie tego wzorca w tekście (najbliższe przesunięcie i najmniejszą długość fragmentu tekstu, do którego ten wzorzec pasuje). Od czego będzie zależeć złożoność obliczeniowa tego algorytmu?
5. (łatwe) Narysuj diagram przejść automatu wyszukiwania wzorca P = ababbabbababbababbabb nad alfabetem Σ = {a, b}.
6. (łatwe) Skonstruuj automat wyszukiwania wzorca P = aabab i przetestuj jego działanie na tekście T = aaababaabaababaab.

12, 13 stycznia 2016 r. (lista 14: automaty skończone)

1. Zaprojektuj automat skończony akceptujący słowa o nieparzystej długości. Alfabetem niech będzie zbiór wszystkich liter alfabetu angielskiego.
2. Zaprojektuj automat skończony akceptujący słowa kończące się na literę a. Alfabetem niech będzie zbiór wszystkich liter alfabetu angielskiego.
3. Zaprojektuj automat skończony akceptujący tylko słowa, w których nie ma obok siebie dwóch takich samych liter. Alfabetem niech będzie zbiór wszystkich liter alfabetu angielskiego.
4. Zaprojektuj automat skończony akceptujący tylko słowa złożone z powtórzeń takiej samej litery, na przykład bbb, a, ccccc. Alfabetem niech będzie zbiór liter {a, b, c}.
5. Zaprojektuj automat skończony akceptujący wszystkie słowa kończące się ciągiem abc. Alfabetem niech będzie zbiór liter {a, b, c}.
6. Zaprojektuj automat skończony akceptujący wszystkie słowa zawierające ciąg abc. Alfabetem niech będzie zbiór liter {a, b, c}.
7. Zaprojektuj automat skończony akceptujący wszystkie słowa niezawierające litery a. Alfabetem niech będzie zbiór liter {a, b, c}.
8. Zaprojektuj automat skończony akceptujący liczby podzielne przez 5. Alfabetem niech będzie zbiór wszystkich cyfr w systemie dziesiętnym.
9. Zaprojektuj automat skończony akceptujący liczby podzielne przez 3. Alfabetem niech będzie zbiór wszystkich cyfr w systemie dziesiętnym.
10. Zaprojektuj automat skończony akceptujący poprawnie zapisane liczby całkowite (bez zer wiodących na początku liczby i ze znakiem − dla liczb ujemnych) Alfabetem niech będzie zbiór wszystkich cyfr w systemie dziesiętnym oraz znak minusa.

19, 20 stycznia 2016 r. (lista 15: kryptografia)

1. ...

Konwersatorium

6 października 2015 r. (zmienne, stałe, wyrażenia)

• struktura programu w języku C/C++
• podstawowe typy danych
• literały dla typów podstawowych i łańcuchy znakowe
• deklarowanie zmiennych i inicjalizacja
• operacja przypisania
• operatory arytmetyczne, relacyjne i logiczne
• wyrażenia arytmetyczne i logiczne
• instrukcja warunkowa if

13 października 2015 r. (instrukcje sterujące)

• operatory inkrementacji i dekrementacji
• przypisania operacyjne
• instrukcja pętli while
• instrukcja pętli do-while
• instrukcja pętli for
• przerywanie pętli instrukcją break
• skracanie pętli instrukcją continue

20 października 2015 r. (funkcje)

• stałe
• referencje
• deklarowanie funkcji
• definiowanie funkcji
• wywołanie funkcji
• argunety funkcji przekazywane przez wartość i przez referencję
• zwracanie wyniku funkcji za pomocą instrukcji return
• funkcje rekurencyjne

27 października 2015 r. (wskaźniki)

• wskaźniki
• operator pobrania adresu &
• operator wyłuskania *
• arytmetyka wskaźników
• przekazywanie argumentów do funkcji za pomocą wskaźników
• tworzenie obiektów na stercie operatorem new
• usuwanie obiektów ze sterty operatorem delete

3 listopada 2015 r. (tablice)

• tablice jako zbiory danych
• ułożenie elementów tablicy w pamięci
• indeksowanie elementów tablicy
• deklarowanie i inicjalizacja tablicy
• tablice a wskaźniki
• tablice wielowymiarowe
• ciągi znaków typu const char*
• przekazywanie tablic do funkcji poprzez argumenty
• tworzenie tablic na stercie operatorem new[]
• usuwanie tablic ze sterty operatorem delete[]

10 listopada 2015 r. (struktury)

• struktura jako nowy typ danych
• pola w strukturze
• funkcje składowe w strukturze
• obiekty typu strukturowego
• dostęp do składowych w strukturze za pomocą . oraz ->
• konstruktor w strukturze
• wskaźnik this
• przeciążanie funkcji
• operatory new i delete dla struktur
• I filar programowania obiektowego - abstrakcja (modelowanie)

17 listopada 2015 r. (klasy)

• klasa jako nowy typ danych
• składowe publiczne i prywatne
• konstruktor domyślny
• konstruktor kopiujący
• przypisanie kopiujące
• destruktor
• pola stałe w klasie
• lista inicjalizacyjna w konstruktorze
• stałe funkcje składowe
• obiekty stałe
• II filar programowania obiektowego - hermetyzacja (ukrywanie implementacji)

24 listopada 2015 r. (składowe statyczne)

• składowe statyczne
• zewnętrzna definicja pól statycznych
• odwołania do statycznych funkcji składowych
• inicjalizacja pól statycznych
• wbudowane funkcje składowe w klasie

1 grudnia 2015 r. (funkcje zaprzyjaźnione)

• na czym polega przyjaźń w klasie
• deklaracja przyjaźni
• wykorzystanie przyjaźni
• zaprzyjaźnione operatory strumieniowe do pisania i czytania

8 grudnia 2015 r. (wyjątki)

• obsługa błędów poprzez zgłaszanie i łapanie wyjątków
• dopasowywanie wyjątków
• wyjątki w konstruktorach
• w destruktorach nie wolno zgłaszać wyjątków
• specyfikacja wyjątków
• wyjątki standardowe

15 grudnia 2015 r. (szablony funkcji)

• działanie szablonów w programach w C++
• definicja szablonu funkcji
• wygenerowanie funkcji szablonowej
• parametry szablonu funkcji
• definiowanie wyspecjalizowanych wersji szablonów funkcji
• dopasowanie w przypadku funkcji szablonowych
• szablony funkcji a przeladowanie
• szablon funkcji nie powinien korzystac ze zmiennych globalnych
• szablony zamiast makrodefinicji
• szablony definiujemy w części nagłówkowej

22 grudnia 2015 r. (szablony klas)

• definicja szablonu klasy
• wygenerowanie klasy szablonowej
• nazwa szablonu klasy
• parametry szablonu klasy
• dopasowanie w przypadku klasy szablonowej
• definiowanie wyspecjalizowanych wersji szablonów klas
• przyjaźń a szablony klas

12 stycznia 2016 r. (kolekcje STL)

19 stycznia 2016 r. (algorytmy z STL)

26 stycznia 2016 r. (funkcje narzędziowe z STL)

Laboratorium

Zadania laboratoryjne będzimy programować w języku C++, używając do tego celu zintegrowanego środowiska programistycznego Code::Blocks (jest to darmowy program do ściągnięcia ze strony www.codeblocks.org). Do pracy w domu warto pobrać wersję 13.12 razem ze stabilnym kompilatorem TDM-GCC ver. 4.7.1 - dla Windowsa będzie to plik codeblocks-13.12mingw-setup.exe.

Oprócz zadań programowanych na pracowni będą wystawiane zadania na themisie do zaprogramowania w domu. Themis to automatyczna sprawdzaczka zadań: zadania są przydzielane do grup i mają określony termin zakończenia.

7, 9 października 2015 r. (instrukcja warunkowa)

1. Skompiluj i uruchom program w środowisku Code::Blocks, który wypisze komunikat powitalny.
2. Napisz program, który wczyta liczbę rzeczywistą a następnie policzy i wypisze wartość bezwzględną tej liczby.
3. Napisz program, który wczyta liczbę rzeczywistą a następnie policzy i wypisze wartość funkcji signum dla tej liczby (-1 dla liczby ujemnej, 0 dla zera, 1 dla liczby dodatniej).
4. Napisz program, który wczyta trzy liczby rzeczywiste reprezentujące współczynniki równania kwadratowego a następnie policzy i wypisze ile to równanie ma rozwiązań i jakie są te rozwiązania.

14, 16 października 2015 r. (instrukcje pętli)

1. Napisz program, który wczyta liczbę naturalną n a następnie wydrukuje na standardowym wyjściu kwadrat, używając tylko spacji i gwiazdek. Wszystkie boki kwadratu mają być równe i mają składać się z n gwiazdek.
   Na przykład dla n=5 program powinien wydrukować na ekranie następującą figurę:
   * * * * *
   *       *
   *       *
   *       *
   * * * * *
2. Napisz program, który wczyta liczbę naturalną n a następnie wydrukuje tabliczkę mnożenia o rozmiarach n×n.
   Zadbaj o to, aby tabliczka była wydrukowana w sposób estetyczny (szerokość każdej komórki ma być taka sama).
3. Napisz program, który wczyta dodatnią liczbę rzeczywistą a następnie policzy i wypisze pierwiastek kwadratowy z tej liczby. Do policzenia pierwiastka kwadratowego zastosuj metodę babilońską.
   Zastanów się, jak określić liczbę iteracji w tej metodzie, aby wynik był jak najbardziej dokładny (porównaj go z rezultatem funkcji sqrt() z biblioteki standardowej).

21, 23 października 2015 r. (rekurencja)

1. Napisz program, który wczyta liczbę naturalną n<20 a następnie policzy i wypisze wartość silni n! dla tej liczby. Zaimplementuj algorytm obliczania silni w wersji rekurencyjnej.
2. Napisz program, który wczyta dwie liczby naturalne x i y a następnie policzy i wypisze największy wspólny dzielnik NWD(x,y) dla tych liczb. Zaimplementuj poprawiony algorytm Eulkidesa w wersji rekurencyjnej.
3. Napisz program, który wczyta dwie liczby całkowite n i k takie, że 0≤k≤n≤100, a następnie policzy i wypisze wartość współczynnika dwumianowego (ⁿ_k) dla tych liczb. Zaimplementuj algorytm obliczający symbol Newtona w wersji rekurencyjnej.

28, 30 października 2015 r. (liczby w zapisie binarnym)

1. Napisz program, który wypisze w postaci tabelarycznej zestawienie widocznych znaków ASCII (od znaku spacji ' ' o kodzie 32 do znaku tyldy '∼' o kodzie 126) wraz z ich wartościami w postaci dziesiętnej, szesnastkowej i dwójkowej.
2. Napisz program, który wczyta liczbę naturalną w postaci binarnej (ciąg zer i jedynek) i wypisze ją w postaci dziesiętnej.
3. Napisz program, który wczyta liczbę całkowitą typu int i wypisze ją w postaci binarnej w systemie U2 (z bitem znaku).
4. Napisz program, który wczyta liczbę rzeczywistą typu double z przedziału (0, 1) i wypisze ją w postaci binarnej z dokładnością do 16 bitów.

4, 6 listopada 2015 r. (iteracja)

1. Napisz program, który wczyta liczbę naturalną >1 a następnie sprawdzi, czy taliczba jest pierwsza czy nie. Jeśli podana liczba będzie pierwsza, to należy wypisać tą samą liczbę a w przeciwnym przypadku najmniejszy podzielnik >1 dla tej liczby. W swoim programie iteracyjnie szykaj dzielników zadanej liczby.
2. Napisz program, który wczyta dwie liczby naturalne p i g takie, że p>g oraz p jest liczbą pierwszą, a następnie policzy i wypisze wartość g^-1 (czyli taką wartość, że g · g^-1 ≡ 1 mod p). Zaimplementuj rozszerzony algorytm Eulkidesa w wersji iteracyjnej.

11, 13 listopada 2015 r. (iteracja)

1. Napisz program, który wczyta ze standardowego wejścia liczbę naturalną a następnie wyliczy i wypisze na standardowe wyjście wszystkie jej dzielniki właściwe (każdy dzielnik w oddzielnej linii); na koniec program ma wypisać informację o tym, czy liczba ta jest doskonała czy nie.
   Wyjaśnienie. Dzielnikiem właściwym liczby nazywa się każdy jej dodatni dzielnik, który jest od niej różny. Liczba doskonała to liczba naturalna, która jest sumą wszystkich swoich dzielników właściwych.
2. Napisz program, który wczyta ze standardowego wejścia liczbę naturalną n a następnie wyliczy i wypisze na standardowe wyjście potęgę 2 najbliższą tej liczby ale nie większą od niej. Postaraj się aby złożoność czasowa Twojego algorytmu była lepsza od O(log n) i należała do O(log log n).

18, 20 listopada 2015 r. (tablice)

1. Napisz program, który wczyta ze standardowego wejścia liczbę naturalną n a potem n liczb rzeczywistych, umieszczając je w automatycznie utworzonej tablicy. Następnie program ma obliczyć i wypisać na standardowym wyjściu średnią arytmetyczną i odchylenie standardowe dla wczytanych danych.
   Uwaga. Do wyliczenia średniej arytmetycznej i odchylenia standardowego zdefiniuj osobne funkcje. Ich deklaracje umieść na początku programu źródłowego.
2. Napisz program, który wczyta ze standardowego wejścia parę liczb naturalnych n i k a potem wyliczy i wypisze wartość współczynnika dwumianowego (ⁿ_k). Współczynnik należy odczytać z trójkątnej tablicy z trójkątem Pascala zaalokowanej dynamicznie w pamięci i wypełnionej wiersz po wierszu, zgodnie ze wzorem:
   (ⁿ₀) = (ⁿ_n) = 1 dla n≥0
   (ⁿ_k) = (^n-1_k-1) + (^n-1_k) dla 0<k<n
   Uwaga. Zaalokuj w pamięci tylko taką tablicę jaka jest konieczna do odczytania zadanego współczynnika. Na końcu programu tablicę tą neleży usunąć z pamięci.

25, 27 listopada 2015 r. (struktury)

1. Zaprojektuj strukturę do pamiętania czasu w postaci godziny (0-23), minut (0-59) i sekund (0-59). Dopisz do tej struktury konstruktor inicjalizujący obiekt do przechowywania czasu poprawymi wartościami, metody odczytujące poszczególne składniki czasu oraz metodę drukującą czas do strumienia. Dodatkowo dopisz metodę dodająca do czasu zadaną liczbę godzin, minut i sekund.
   Napisz także program, który wczyta ze standardowego wejścia jakąś godzinę a potem liczbę sekund o ile tą godzinę przesunąć. Program ma zmodyfikować obiekt przechowujący czas o zadaną liczbę sekund oraz wypisać ten obiekt po zmodyfikowiu na standardowym wyjściu.
2. Zaprojektuj strukturę do pamiętania współrzędnych punktu na płaszczyźnie. Zdefiniuj w tej strukturze konstruktor bezparametrowy i konstruktor z wartościami współrzędnych punktu, metody odczytujące poszczególne współrzędne oraz metodę drukującą punkt do strumienia. Dodatkowo dopisz metodę dodającą do punktu zadany wektor i zwracającą nowy punkt.
   Napisz także program, który wczyta ze standardowego wejścia współrzędne jakiegoś punktu a potem wektor, o który ten punkt należy przesunąć. Program ma wyznaczyć punkt po przesunięciu o zadany wektor i wypisać go na standardowym wyjściu.

2, 4 grudnia 2015 r. (klasy)

1. Zaprojektuj klasę reprezentującą stos liczb całkowitych. Zaimplementuj stos w tej klasie na tablicy. Klasa ta powinna posiadać konstuktor określający pojemność stosu, konstruktor domyślny (pojemność stosu ma być wtedy równa 256), destruktor oraz konstruktor kopiujący i przypisanie kopiujące. Funkcjonalność stosu to minimum wstawianie na stos, ściąganie ze stosu i sprawdzanie ile elementów jest na stosie.
   class stack {
       int c; // capacity
       int n; // size of the stack
       double *arr; // array of doubles
   public:
       stack();
       stack(int cp);
       stack(const stack &st);
       stack& operator=(const stack &st);
       ˜stack();
   public:
       void push(double x);
       double pop();
       double top() const;
       int capacity() const { return c; }
       int size() const { return n; }
       bool empty() const { return n == 0; }
       bool full() const { return n == c; }
   };
   Napisz także program, który rzetelnie przetestuje działanie Twojego stosu - przetestuj wszystkie opweracje wykonywane na stosie.

9, 11 grudnia 2015 r. (zaprzyjaźnione operatory strumieniowe)

1. Do klasy reprezentującej stos z poprzedniego tygodnia dopisz zaprzyjaźnione operatory do dopisania do stosu danych ze strumienia i do zapisania zawartości stosu do strumienia. Napisz także program, który rzetelnie przetestuje działanie Twoich zaprzyjaźnionych operatorów strumieniowych dla stosu.

16, 18 grudnia 2015 r.

1. Zdefiniuj strukturę węzła dla listy jednokierunkowej z operacjami wstawienia elementu na zadaną pzycję oraz usunięcia elementu z zadanej pozycji. Dopisz jeszcze funkcję, która wypisze listę do określonego strumienia. Rzetelnie przetestuj działanie Twojej listy.
   Gdy zadana pozycja w funkcji wstawiającej albo usuwającej element jest poza zasięgiem listy, wówczas zgłoś wyjątek out_of_range.
2. Na liście tej chcemy także wykonywać operacje dokładania nowych elementów na początku i na końcu oraz usuwania elementów z początku i z końca listy.
3. Do pisz do listy rekurencyjne metody obliczania długości listy, sprawdzania czy znajduje sie na niej określona wartość (ewentualnie ile jest takich wartości) oraz wyznaczające indeks pierwszego i ostatniego wystąpienia zadanej wartości.
4. Opakuj homogeniczną strukturę listy obiektem zarządzającym działaniami na liście.

5, 8 stycznia 2016 r.

Kolokwia i egzaminy

Przykładowe zadania jakie mogą się znaleźć na kolokwium I

Część testowa. Odpowiedz krótko ale precyzyjnie na poniższe pytania. Przy odpowiedziach do pytań powinny się znajdować obliczenia albo uzasadnienia. Za poprawne odpowiedzi do wszystkich pytań można łącznie otrzymać do 10 punktów.

1. Przypomnij definicję operatora Ω(g(n)), wyznaczającego klasę wszystkich funkcji ograniczonych asymptotycznie z dołu przez g(n). Następnie podaj przykład funkcji f(n), która należy do Ω(n²) ale nie należy do Θ(n²). Pokaż z definicji, że f(n) należy do Ω(n²).
2. Narysuj schemat blokowy dla zadania obliczania silni.
3. Jak wykorzystać algorytm Euklidesa do znajdowania NWW?
4. Przypomnij rekurencyjną definicję funkcji obliczającej n-ty wyraz ciągu Fibonacciego. Ile wywołań tej funkcji zostanie zrobionych dla argumentu o wartości 4?
5. Zapisz w notacji postfiksowej wyrażenie (1+sin(n/8+2^k+1*3-1))/2.
6. Co to jest bufor LIFO? Jaka struktura danych implementuje bufor LIFO?
7. Co to jest lista dwukierunkowa?
8. Co to jest lista z wartownikiem?
9. Co to jest pełne drzewo binarne?
10. Na czym polega porządek symetryczny w drzewie BST?
11. Ile różnych drzew BST można zbudować, umieszczając w nim trzy różne wartości? Narysuj te drzewa dla wartości: 1, 2, 3.

Część zadaniowa. Wybierz jedno z poniższych zadań i zaprezentuj jego rozwiązanie. Za poprawne rozwiązanie zadania można otrzymać do 10 punktów.

1. Rozważ k-bitowy licznik binarny. Licznik ten jest tablicą bitów, która reprezentuje zapis binarny wartości licznika. Napisz w pseudokodzie implementację operacji increment(), która zwiększa wartość licznika o 1. Wykaż, że złożoność czasowa ciągu n operacji increment() na tym liczniku jest liniowa O(n). Zastosuj metodę księgowania. Jaki będzie koszt czasowy wykonania pojedynczej operacji increment() w najgorszym przypadku? Jaki będzie zamortyzowany koszt czasowy wykonania pojedynczej operacji increment()? Odpowiedzi uzasadnij.
2. 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.
3. W k-elementowej tablicy jest zapisana binarnie liczba całkowita w systemie U2 (w każdej komórce jest zapisany jeden bit 0 albo 1). Opisz algorytm zmiany znaku w tej liczbie. Jaka jest złożoność czasowa i pamięciowa przedstawionego algorytmu?
4. Opisz algorytm, który usunie co drugi element z podanej listy jednokierunkowej. Napisz w pseudokodzie procedurę, która realizuje ten algorytm. Jaka jest jego złożoność czasowa i pamięciowa?
5. Opisz algorytm, który znajdzie element następny co do wielkości względem zadanej wartości x w drzewie BST (należy więc wyznaczyć najmniejszą wartość spośród większych od x w tym drzewie). Napisz w pseudokodzie procedurę, która realizuje ten algorytm. Jaka jest jego złożoność czasowa i pamięciowa?

Przykładowe zadania jakie mogą się znaleźć na kolokwium II

Część testowa. Odpowiedz krótko ale precyzyjnie na poniższe pytania. Przy odpowiedziach do pytań powinny się znajdować obliczenia albo uzasadnienia. Za poprawne odpowiedzi do wszystkich pytań można łącznie otrzymać do 10 punktów.

1. Skonstruuj automat skończony, który rozpoznaje słowa o długości podzielnej przez 3.
2. Ile razy algorytm Karpa-Rabina spudłuje, szukając wzorca P = 84 w tekście T = 271828182845904523536 nad alfabetem Σ = {0, 1, …, 9}, wykonując obliczania modulo q = 13?
3. Dany jest zbiór 5 symboli S = {a, b, c, d, e}. Wyznacz entropię tego zbioru w przypadku następujących prawdopodobieństw: P(a) = P(b) = P(c) = 1/4 i P(d) = P(e) = 1/8.
4. Jaka ilość informacji jest zawarta w numerze dowodu osobistego, który jest ciągiem 3 liter i następujących po nim 6 cyfr? Zapisz wzór i oszacuj najlepiej jak potrafisz licząc w bitach.
5. Czy kod binarny {00, 01, 11, 110, 111} jest jednoznacznie dekodowalny? Odpowedź uzasadnij.
6. Czy kod binarny {00, 011, 101, 1110} jest prefiksowy? Odpowedź uzasadnij.
7. Korzystając z nierówności Krafta wyznacz minimalną liczbę symboli kodowych potrzebnych do stworzenia kodu prefiksowego o długościach {1, 1, 2, 2, 3, 3}.
8. Pewne źródło generuje symbole z alfabetu Σ = {a, b, c} z prawdopodobieństwami P(a)=0.3, P(b)=0.2 i P(c)=0.5. Jaka będzie średnia długość binarnego słowa kodowego dla tego alfabetu, jeśli kodowanie tych symboli zostanie wyznaczone algorytmem Shannona? Wykonaj niezbędne obliczenia.
9. Pewne źródło generuje symbole z alfabetu Σ = {a, b, c, d, e, f} z prawdopodobieństwami P(a)=0.29, P(e)=0.23, P(d)=0.17, P(b)=0.13, P(c)=0.11 i P(f)=0.07. Wyznacz kody binarne dla symboli z tego alfabetu za pomocą algorytmu Shannona-Fano. Wykonaj niezbędne obliczenia.
10. Pewne źródło generuje symbole z alfabetu Σ = {a, b, c, d, e, f, g, h, i} z prawdopodobieństwami P(a)=0.3, P(e)=0.2, P(i)=0.15, P(b)=0.1, P(c)=0.1, P(d)=0.05, P(g)=0.05, P(h)=0.03 i P(f)=0.02. Narysuj drzewo kodowe Huffmana dla symboli z tego alfabetu. Wykonaj niezbędne obliczenia.

Część zadaniowa. Wybierz jedno z poniższych zadań i zaprezentuj jego rozwiązanie. Za poprawne rozwiązanie zadania można otrzymać do 10 punktów.

1. Załóżmy, że wzorzec P może zawierać pewną liczbę wystąpień symbolu uniwersalnego ◊, który pasuje do dowolnego znaku; Podaj algorytm wyszukiwania wszystkich wystąpień takiego wzorca P w tekście T, który będzie modyfikacją algorytmu Karpa-Rabina. Jaka będzie złożoność czasowa i pamięciowa tego algorytmu?
2. Wyszukanie w łańcuchu s maksymalnego prefikso-sufiksu sprowadza się do znalezienia najdłuższego prefiksu, który jednocześnie jest sufiksem łańcucha s. Opisz algorytm budowy tablicy prefikso-sufiksów dla zadanego wzorca P (w tablicy tej wyliczamy długości maksymalnych prefikso-sufiksów dla kolejnych prefiksów wzorca). Następnie opisz jak wykorzystać tą tablicę do budowy automatu skończonego rozpoznającego wzorzec P.
3. Zmodyfikuj algorytm Huffmana, aby można było za jego pomocą wygenerować kody trynarne (mamy do dyspozycji trzy znaki 0, 1 i 2, a nie tylko dwa 0 i 1 jak w przypadku kodów binarnych). Węzły w powstałym drzewie kodowym będą mogły mieć wtedy trzech potomków. Rozważ osobno przypadek nieparzystej i parzystej liczby symboli do zakodowania.

Egzamin podstawowy: 11 lutego 2016 r.

...

Uzupełnienie przykładowych zadań jakie mogą się znaleźć na egzaminie

Część testowa. Odpowiedz krótko ale precyzyjnie na poniższe pytania. Przy odpowiedziach do pytań powinny się znajdować obliczenia albo uzasadnienia.

1. Jaka może być maksymalna ilość krawędzi w grafie prostym n-wierzchołkowym?
2. Jaka może być minimalna ilość krawędzi w spójnym grafie prostym n-wierzchołkowym?
3. Co to znaczy, że graf jest spójny?
4. Czym jest składowa spójności w grafie?
5. Co to jest graf ważony?
6. Co to jest cykl Hamiltona w grafie? Podaj przykład grafu z cyklem Hamiltona.
7. Co to jest cykl Eulera w grafie? Podaj przykład grafu z cyklem Eulera.
8. Jaki jest warunek konieczny i wystarczający aby w grafie prostym istniał cykl Eulera?
9. Ile pamięci potrzeba na zapamiętanie grafu w postaci macierzy sąsiedztwa?
10. Ile czasu potrzeba na wyznaczenie stopnia zadanego wierzchołka w grafie, jeśli jest on zapamiętany w postaci list sąsiadów?
11. Ile krawędzi zawiera graf prosty n-wierzchołkowy, który jest drzewem?
12. Jaką strukturę danych wykorzystuje się do przeglądania grafu wszerz?
13. Co to jest drzewo rozpinające grafu?
14. Na czym polega relaksacja w algorytmie Dijkstry?
15. Jaka będzie złożoność czasowa algorytmu Dijkstry znajdującego minimalne ścieżki w grafie ważonym, gdy wykorzystamy w nim kolejkę priorytetową zaimplementowaną w postaci kopca?
16. Jaka będzie złożoność czasowa algorytmu Kruskala wyznaczania minimalnego drzewa rozpinającego w grafie, gdy wykorzystamy w nim drzewiastą strukturę dla zbiorów rozłącznych ze zrównoważonym łączeniem?
17. Na czym polega porządek kopcowy w drzewie?
18. Ile czasu zajmuje usunięcie elementu maksymalnego z kopca n-elementowego? Co ma zasadniczy wpływ na ten czas?
19. Jaka jest wysokość kopca n-elementowego?
20. Jeśli kopiec n-elementowy umieścimy w tablicy, to jaki będzie indeks lewego i prawego syna i-tego elementu?
21. Na czym polega przesiewanie elementu w górę w kopcu? Kiedy takie przesiewanie się stosuje?
22. Ile pamięci zajmuje drzewiasta struktura dla zbiorów rozłącznych, gdy liczba wszystkich elementów wynosi n?
23. Na czym polega zrównoważone łącznie w drzewiastej strukturze dla zbiorów rozłącznych?
24. Jaki jest czas wykonania operacji find(x) w strukturze drzewiastej ze zbalansowanym łączeniem dla zbiorów rozłącznych?
25. Jaki jest czas wykonania operacji union(x, y) w strukturze drzewiastej ze zbalansowanym łączeniem dla zbiorów rozłącznych, gdy x i y są reprezentantami zbiorów?

Część zadaniowa. Wybierz dwa z poniższych zadań i zaprezentuj ich rozwiązania.

1. Dany jest graf prosty n-wierzchołkowy, w którym stopień każdego wierzchołka jest ≥n/2. Zaprojektuj algorytm wyznaczania w tym grafie cyklu Hamiltona. Przedstaw ideę rozwiązania. Zapisz ten algorytm w speudokodzie. Oszacuj jego złożoność obliczeniową.
2. Jak zmodyfikować algorytm Dijkstry, aby wyznaczał najkrótszą ścieżkę pomiędzy parą zadanych wierzchołków? Przedstaw ideę rozwiązania. Zapisz ten algorytm w speudokodzie. Oszacuj jego złożoność obliczeniową.
3. Opracuj strukturę danych dla zbioru dynamicznego z efektywnymi operacjami wstawiania elementu do zbioru insert(x) i usuwania ze zbioru k-tego co dowielkości extract-kth(). Zakłądamy, że k jest z góry ustaloną liczbą. Opisz oglną ideę budowy tekiej struktury. Zapisz w speudokodzie wspomniane operacje. Oszacuj ich złożoność obliczeniową.

Ranking

Instytut Informatyki