wstęp do informatyki i programowania (semestr zimowy 2014/15)

Celem tych zajęć jest zapoznanie studentów z podstawowymi zagadnieniami algorytmicznymi oraz nauka programowania w języku C++ z wykorzystaniem środowiska programistycznego 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.

Na konwersatorium będzie omawiany język programowania C++ na poziomie programowania strukturalnego i obiektowego oraz różne 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ść logicznego myślenia.

Terminarz

• wykład: środa 10-13 s.605 I.Mat. (Paweł Rzechonek)
• konwersatorium: wtorek 12-14 s.4 I.Inf. w tyg.nieparz. (Paweł Rzechonek)
• ćwiczenia:
  wtorek 12-14 s.4 I.Inf. w tyg.parzyst. (Paweł Rzechonek)
  środa 16-17 s.605 I.Mat. (Krzysztof Tabisz)
• laboratoria:
  środa 17-19 s.417 I.Mat. (Krzysztof Tabisz)
  środa 17-19 s.6 I.Inf. (Bartosz Rybicki)
  piątek 13-15 s.411 I.Mat. (Patryk Filipiak)
  piątek 13-15 s.6 I.Inf. (Paweł Rzechonek)

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 - algorytmy i struktury danych
• I LO w Tarnowie - algorytmy sortujące
• I LO w Tarnowie - binarne kodowanie liczb
• I LO w Tarnowie - bit w zastosowaniach
• I LO w Tarnowie - miejsca zerowe funkcji
• I LO w Tarnowie - całkowanie numeryczne
• 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ł laboratoium 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 50% 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ć 45% z wszystkich możliwych do uzyskania punktów; na ocenę bardzo dobrą trzeba będzie zdobyć 85% 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.

Laboratorium

8, 10 października 2014 r.

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.

15, 17 października 2014 r.

Napisz program, który wczyta dwie dodatnie liczby całkowite a następnie policzy i wypisze NWD dla tych liczb. Zaimplementuj algorytm Eulkidesa.

22, 24 października 2014 r.

Napisz program, który wczyta dodatnią liczbę rzeczywistą a następnie policzy i wypisze pierwiastek kwadratowy z tej liczby. Do policzenia pierwiastka użyj własnej funkcji, w której zaimplementujesz metodę babilońską. Zastanów się, jak określić liczbę iteracji w tej metodzie, aby wynik był w miarę dokładny. Na początku programu zrób deklarację funkcji obliczającej pierwiastek kwadratowy a jej definicję zrób na końcu.

29, 30 października 2014 r.

Napisz program, który wczyta współczynniki dwóch prostych w postaci ogólnej, czyli A₁x + B₁y + C₁ = 0 i A₂x + B₂y + C₂ = 0, a następnie wyliczy i wypisze współrzędne punktu przecięcia się tych prostych. Zastanów się, co zrobić w sytuacji, gdy proste się nie przecinają albo nakładaja się na siebie. Na początku programu zrób deklarację funkcji obliczającej punkt przecięcia się prostych a jej definicję zrób na końcu. W programie zadeklaruj i użyj struktur do zapamiętania współczynników prostej i współrzędnych punktu.

5, 7 listopada 2014 r.

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 kolejkę do określonego strumienia. Rzetelnie przetestuj działanie Twojej listy. Jak zachowa się metoda wstawiająca albo usuwająca, gdy zadana pozycja jest poza zasięgiem listy?

12, 14 listopada 2014 r.

Zaimplementuj strukturę danych, która będzie pamiętała ciąg wartości. Struktura ta ma pozwalać na szybki odczyt i zapis danych do określonych za pomocą indeksu pozycji w tym ciągu (zakładamy, że pierwszy element znajduje się zawsze na pozycji 0). Na ciągu tym chcemy także szybko 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 tego ciągu. Zaimplementuj więc tę strukturę na tablicy o określonym z góry rozmiarze. Rzetelnie przetestuj jej działanie. Czy umiesz dopisać do swojej implementacji operację szybkiego odwracania ciągu?

19, 21 listopada 2014 r.

Zdefiniuj strukturę węzła dla drzewa BST z operacjami wstawienia elementu do drzewa, wyszukiwania zadanej wartości, wypisania zawartości drzewa w porządkach in-order, pre-order i post-order oraz policzenia wszystkich elementów w drzewie. Jak zachowa się metoda wstawiająca, gdy zadana wartość już istnieje w drzewie?

Do drzewa BST z poprzedniego zadania dopisz operację wyznaczania i usuwania wartości minimalnej i maksymalnej oraz operację usuwania zadanej wartości z drzewa. Jak zachowa się metoda usuwająca, gdy zadanej wartości nie ma w drzewie?

Dodatkowo:

Do drzewa BST z poprzedniego zadania dopisz operację wyznaczania następnika i poprzednika w drzewie dla zadanej wartości. Jak zachowają się te metody, gdy zadanej wartości nie ma w drzewie?

Do drzewa BST z poprzedniego zadania dopisz funkcję drukująca strukturę drzewa. Wykorzystaj znaki ASCII do narysowania krawędzi (semigrafika). Na wydruku korzeń ma być przy lewej krawędzi; potomkowie każdego węzła są po jego prawej stronie. Śledząc wartości na wydruku z góry w dół powinniśmy odczytać wartości w drzewie od anjmniejszej do największej.

3, 5 grudnia 2014 r.

Napisz program, który wczyta dwa łańcuchy znakowe: tekst i zworzec, a następnie wyliczy i wypisze pozycje wszystkich wystąpień wzorca w tekście. Najpierw wyznacz wszystkie wystąpienia wzorca w tekście algorytmem naiwnym a potem algorytmem Byera-Moore'a.

Do gromadzenia liczb typu int (pozycje wystąpień wzorca w tekście) możesz użyć kontenera z biblioteki standardowej set<int>.

10, 12 grudnia 2014 r.

Napisz program, który wczyta dwa łańcuchy znakowe: tekst i zworzec, a następnie wyliczy i wypisze pozycje wszystkich wystąpień wzorca w tekście. Najpierw wyznacz wszystkie wystąpienia wzorca w tekście algorytmem naiwnym a potem algorytmem Karpa-Rabina.

17, 19 grudnia 2014 r.

Napisz program, który dla określonego tekstu (przeanalizuj I rozdział "Krzyżaków" H.Sienkiewicza) sporządzi statystykę występowania poszczególnych znaków, a potem na podstawie tej statystyki wygeneruje słowa kodowe dla poszczególnych znaków zgodnie z algorytmem Shanona-Fano.

Dodatkowo:

Spróbuj potem wygenerować słowa kodowe za pomocą algorytmu Shanona.

7, 9 stycznia 2015 r.

Napisz program, który dla określonego tekstu (przeanalizuj II rozdział "Krzyżaków" H.Sienkiewicza) sporządzi statystykę występowania poszczególnych znaków, a potem na podstawie tej statystyki wygeneruje drzewo kodowe Huffmana i na tej podstawie słowa kodowe dla poszczególnych znaków. Używając tego kodowania zapisz zakodowany tekst w pliku binarnym (wraz z informacjami pozwalającymi odtworzyć ten plik).

14, 16 stycznia 2015 r.

Napisz program, który dla określonego zbioru symboli i związanych z nimi prawdopodobieństw wyliczy informację bitową każdego z nich oraz entropię całego zbioru. Zakładamy, że pojawianie się symboli jest niezależne a ich prawdopodobieństwa sumują się do 1.

21, 23 stycznia 2015 r.

Zdefiniuj klasę reprezentująca graf gęsty w postaci macierzy sąsiadów. Następnie napisz program, który dla zadanego grafu sprawdzi, czy jest on spójny. Graf wczytaj z pliku tekstowego (najpierw liczbę wierzchołków, potem liczbę krawędzi a dalej krawędzie w postaci par wierzchołków). Do testowania spójności grafu wykorzystaj przeglądanie w głąb.

Ćwiczenia

7, 8 października 2014 r. (schematy blokowe)

1. Narysuj schemat blokowy dla zadania obliczania wartości bezwzględnej z zadanej liczby.
2. Narysuj schemat blokowy dla zadania obliczania znaku z zadanej liczby (jak w funkcji signum).
3. Narysuj schemat blokowy dla zadania obliczania równania liniowego dla zadanych współczynników.
4. Narysuj schemat blokowy dla zadania obliczania sumy kolejnycyh liczb naturalnych od 0 do zadanej wartości n.
5. Narysuj schemat blokowy dla zadania obliczania silni dla zadanej wartości n.

14, 15 października 2014 r. (problem wydawania reszty)

1. Rozważ problem wydawania reszty za pomocą określonych nominałów.
2. Napisz specyfikację dla takiego zadania.
3. Przedstaw ideę algorytmu wydającego resztę.
4. Zapisz ten algorytm w postaci schematu blokowego i w pseudokodzie.
5. Dla jakiego typu danych ten algorytm będzie działał optymalnie?

21, 22 października 2014 r. (kolejka i stos)

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. Pokaż, jak zaimplementować kolejkę, używając dwóch stosów. Oszacuj czas działania operacji na takiej kolejce.
   Pokaż także, jak zaimplementować stos za pomocą dwóch kolejek. Oszacuj czas działania operacji na takim stosie.
3. Pokaż, jak odwrócić kolejność elementów w kolejce. Pokaż także, jak odwrócić kolejność elementów na stosie.
   Możesz używać jako struktur pomocniczych tylko kolejek i stosów. Ile operacji w każdym przypadku będziesz musiał wykonać, aby odwrócić kolejność elementów w tych strukturach?
4. (trudniejsze) Pokaż, jak odwrócić kolejność elementów w kolejce i 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!

4, 5 listopada 2014 r. (listy)

1. Zaimplementuj w pseudokodzie procedurę obliczania długości listy jednokierunkowej. Napisz wersję iteracyjną i rekurencyjną tej procedury. Porównaj złożoność czasową i pamięciową obu procedur.
2. 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 oraz drugą wersję dla przypadku, gdy należy usunąć wszystkie wystąpienia zadanej wartości.
3. (trudniejsze) Zaprojektuj algorytm odwracania listy jednokierunkowej. Ma 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 o posortowanej listy dwukierunkowej z wartownikiem? Wstawienie należy tak wykonać, aby zewnętrzny wskaźnik na głowę listy nie wymagał aktualizacji. Napisz odpowiednią procedurę w pseudokodzie.
6. Dane są dwie posortowane listy jednokierunkowe. Zaprojektuj algorytm, który scali te listy w jedną posortowaną listę. Napisz odpowiednią procedurę w pseudokodzie.
7. Dana jest lista jednokierunkowa. Zaprojektuj algorytm, który wydzieli z tej listy podlistę z węzłami spełniającymi określony warunek. W wyniku mamy otrzymać dwie rozłączne listy. Napisz odpowiednią procedurę w pseudokodzie.

11, 12 listopada 2014 r. (złożoność zamortyzowana)

1. Kolejkę można zaimplementować za pomocą dwóch stosów (wcześniejsze zadanie). 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. 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.
3. 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.
4. 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.
5. (trudniejsze) Rozważ tablicę dynamiczną, o początkowej pojemności równej 1. Na tablicy tej możemy wykonywać operacje odczytu i zpisu 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ść.

18, 19 listopada 2014 r. (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. 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.

2, 3 grudnia 2014 r. (wyszukiwanie wzorca w tekście)

1. 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?
2. 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?
3. (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). Jaka będzie złożoność czasowa i pamięciowa tego algorytmu?

9, 10 grudnia 2014 r. (wyszukiwanie wzorca w tekście)

1. (łatwe) Ile razy algorytm Karpa-Rabina spudłuje, szukając wzorca P = 26 w tekście T = 3141592653589793 nad alfabetem Σ = {0, 1, …, 9}, wykonując obliczania modulo q = 11?
2. Jak zmodernizować algorytm Karpa-Rabina, aby można go zastosować do problemu jednoczesnego szukania k zadanych wzorców?
3. (trudniejsze) Jak zmodernizować algorytm Karpa-Rabina, aby można go zastosować do problemu 2D szukania wzorca m×m w tekście n×n.
4. (łatwe) Skonstruuj automat skończony, który rozpoznaje:
   1. słowa nieparzystej długości;
   2. słowa, w których litera z∈Σ występuje dokładnie trzy razy;
   3. słowa, w których nie ma obok siebie dwóch takich samych liter;
   4. poprawnie zapisane liczby całkowite (bez zer wiodących na początku liczby i ze znakiem − dla liczb ujemnych).
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.
7. (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. W tekście T symbol uniwersalny ∗ w ogóle nie występuje. Pokaż, jak zbudować automat skończony dla takiego wzorca, który będzie znajdował wszystkie wystąpienia wzorca P w tekście T (początki poprawnych dopasowań) w czasie O(|T|).

16, 17 grudnia 2014 r. (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.

6, 7 stycznia 2015 r. (kodowanie)

1. ...

27, 28 stycznia 2015 r. (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.

Konwersatorium

7 października 2014 r.

• ...

21 października 2014 r.

• ...

4 listopada 2014 r.

• referencje
• stałe
• stałe wskaźniki i wskaźniki do stałych
• rekurencja
• rekurencyjna wersja funkcji silnia

Wykład

8 października 2014 r.

• sprawy organizacyjne
• binarna reprezentacja liczb całkowitych i zmiennopozycyjnych
• algorytm Euklidesa dla NWD

15 października 2014 r.

• elementarne struktury danych w C++
• wstęp do klas i obiektów w C++
• stos i kolejka i ich implementacja tablicowa

22 października 2014 r.

• złożoność czasowa i pamięciowa algorytmu
• asymptotyka i jej zastosowanie w szacowaniu złożoności obliczeniowej
• listy

29 października 2014 r.

• wyrażenia algebraiczne zapisane w Odwrotnej Notacji Polskiej
• obliczanie wyrażeń w postaci postfiksowej - wykorzystanie kolejki i stosu
• przekształcanie wyrażeń z postaci infiksowej do postfiksowej - algorytm Dijkstry
• koszt zamortyzowany - metoda sumaryczna

5 listopada 2014 r.

• koszt zamortyzowany - metoda księgowania
• koszt zamortyzowany - metoda potencjału
• licznik binarny
• tablica dynamiczna

12 listopada 2014 r.

• drzewa
• implementacja drzew metodą "na lewo syn na prawo brat"
• drzewa k-arne
• drzewa drzewa binarne
• drzewa BST z porządkiem symetrycznym
• implementacja operacji słownikowych w drzewach BST

19 listopada 2014 r.

• problem wyszukiwania wzorca w tekście
• naiwny algorytm wyszukiwania wzorca
• algorytm Boyera-Moore'a

26 listopada 2014 r.

• kolokwium I

3 grudnia 2014 r.

• algorytm Karpa-Rabina
• automaty skończone
• prefikso-sufiksy
• wyszukiwanie wzorca w tekście za pomocą automatów skończonych

10 grudnia 2014 r.

• teoria informacji
• informacja i entropia
• binarne kodowanie prefiksowe
• nierówność Krafta
• twierdzenie Shanona o kodowaniu dyskretnym

17 grudnia 2014 r.

• kodowanie Shanona
• kodowanie Shanona-Fano
• kodowanie Huffmana
• rozszerzone kodowanie Huffmana
• kodowanie za pomocą automatów skończonych

14 stycznia 2015 r.

• 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

21 stycznia 2015 r.

• kolokwium II

28 stycznia 2015 r.

• minimalne drzewo rozpinające w grafie - algorytm Kruskala
• kolejka priorytetowa zrealizowana na kopcu
• zbiory rozłączne zrealizowane na strukturze drzewiastej

4 lutego 2015 r.

• najkrótsze drogi w grafie ważonym - algorytm Dijkstry

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 LIFO? Jaka struktura danych implementuje LIFO?
7. Co to jest lista dwukierunkowa z wartownikiem?
8. Co to jest pełne drzewo binarne?
9. Na czym polega porządek symetryczny w drzewie BST?
10. 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. 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?
3. 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?

Kolokwium I: 26 listopada 2014 r.

...

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: 13 lutego 2015 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ą.

Instytut Informatyki