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

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: piątek 11-14 s.601 w IMat (Paweł Rzechonek)
• konwersatorium: piątek 10-11 s.601 w IMat (Paweł Rzechonek)
• ćwiczenia:
  środa 9-10 s.4 w IInf (Paweł Rzechonek)
  środa 11-12 s.603 w IMat (Paweł Schmidt)
• laboratoria:
  środa 10-12 s.6 IInf (Paweł Rzechonek)
  środa 12-13 s.6 IInf (Paweł Schmidt)
  środa 16-18 s.416 IMat (Krzysztof Tabisz)

Literatura

Literatura podstawowa algorytmiczna:

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

Literatura uzupełniająca algorytmiczna:

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

Literatura elektroniczna algorytmiczna:

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

Literatura podstawowa programistyczna:

C++

• S.Rao: C++. Dla każdego. Wydanie 7. Helion, Gliwice 2014.
• 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.
• K.Kuczmarski: Od zera do gier kodera. WNT, Warszawa 2004.

F#

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

Literatura uzupełniająca programistyczna:

C++

• B.Stroustrup: Język C++. Kompendium wiedzy. Wydanie 4. Helion, Gliwice 2014.
• N.M.Josuttis: C++. Biblioteka standardowa. Wydanie 2. Wydawnictwo Helion, Gliwice 2014.
• S.Prata: Język C++. Szkoła programowania. Wydanie 6. Helion, Gliwice 2014.

Literatura elektroniczna programistyczna:

C++

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

F#

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

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 algorytmiczne albo 1 punkt za rozwiązanie podpunktu w zadaniu obliczeniowym. 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.

Kartkówki:

Na niektórych ćwiczeniach będą robione zapowiedziane wcześniej kartkówki. Za poprawne rozwiązanie zadania na kartkówce można uzyskać 1 punkt.

Oceny zaliczeniowe:

Aby zaliczyć ćwiczenia na ocenę dostateczną Student potrzebuje do końca semestru zgromadzić co najmniej tyle punktów ile było w semestrze ćwiczeń plus liczba kartkówek na ćwiczeniach plus 2 (poprawne rozwiązanie jakiegoś zadania algorytmicznego lub poprawne rozwiązanie dwóch podpunktów w jakichś zadaniach obliczeniowych). 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 zaprogramowanie zadań 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ć.

Zadania domowe na themisie:

Z tygodnia na tydzień będę ogłaszał na themisie po trzy zadania do samodzielnego zaprogramowania w domu. Za każde zaliczone zadanie będzie można otrzymać po 1 punkcie, więc za komplet rozwiązań można uzyskać do 3 punktów. Wszystkie zadania będę również porównywał między sobą, aby wykluczyć kopiowanie rozwiązań!

Oceny zaliczeniowe :

Aby Student zaliczył laboratorium na ocenę dostateczną potrzebuje do końca semestru zgromadzić co najmniej 50% możliwych do zdobycia punktów (czyli około 75 punktów) 40% możliwych do zdobycia punktów (czyli około 60 punktów). Na ocenę bardzo dobrą Student potrzebuje zgromadzić 90% możliwych do zdobycia punktów (czyli około 145 punktów) 80% możliwych do zdobycia punktów (czyli około 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 zaliczy 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

7 października 2016 r: liczby w zapisie binarnym

• sprawy organizacyjne

• 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
• zaokrąglenia liczb w systemie dwójkowym
• arytmetyka stałopozycyjna
• arytmetyka zmiennopozycyjna: standard IEEE-754

14 października 2016 r: zadania obliczeniowe i algorytmy

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

21 października 2016 r: rekurencja

• pojęcie rekurencji
• obliczanie silni z wykorzystaniem rekurencji
• potęgowanie poprzez wielokrotne mnożenie podstawy w porównaniu z algorytmem 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ą

28 października 2016 r: odwrotna notacja polska

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

4 listopada 2016 r: sortowanie

• problem sortowania
• sortowanie bąbelkowe
• sortowanie przez wstawianie
• sortowanie przez wybieranie

18 listopada 2016 r: dziel i zwyciężaj

• technika dziel i zwyciężaj
• jednoczesne znajdowanie minimum i maksimum (algorytm rekurencyjny)
• problem scalania i sortowanie poprzez scalanie
• problem podziału i sortowanie szybkie (poprzez podział)

25 listopada 2016 r: redukcja

• mnożenie długich liczb - algorytm Karacuby
• technika redukcji jako odmiana dziel i zwyciężaj z jednym podproblemem
• wyszukiwanie binarne (algorytm rekurencyjny)

2 grudnia 2016 r: programowanie dynamiczne

• problemy optymalizacyjne
• technika programowania dynamicznego
• najdłuższy wspólny podciąg

16 grudnia 2016 r: automaty skończone

• BNF
• EBNF
• diagramy syntaktyczne
• automaty skończone
• deterministyczne automaty skończone
• wyrażenia regularne

13 stycznia 2017 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
• drzewa AVL - zrównoważone drzewa BST
• drzewa R-B - zrównoważone drzewa BST
• slajdy z wykładu: Listy.pptx, Drzewa.pptx

20 stycznia 2017 r: kolejki priorytetowe, zbiory rozłączne

• kolejka priorytetowa i operacje kolejkowe
• złączalne kolejki priorytetowe
• zbiory rozłączne
• slajdy z wykładu: Kolejki.pptx, Zbiory.pptx

27 stycznia 2017 r: grafy

• pojęcie grafu
• graf prosty
• podgraf
• ścieżki i cykle w grafie
• grafy spójne
• spójne składowe grafu
• drzewa
• macierzowa reprezentacja grafów gęstych
• listowa reprezentacja grafów rzadkich
• cykl Eulera i grafy eulerowskie
• cykl Hamiltona i grafy hamiltonowskie
• przeglądanie grafu wszerz
• przeglądanie grafu w głąb
• grafy skierowane
• silnie spójne składowe grafu skierowanego
• grafy ważone
• slajdy z wykładu: Grafy.pptx

3 lutego 2017 r: grafy

• minimalne drzewo rozpinające w grafie - algorytm Kruskala
• najkrótsze ścieżki w grafie - algorytm Dijkstry
• najkrótsze ścieżki w grafie - algorytm Bellmana-Forda
• najkrótsze ścieżki w grafie - algorytm Floyda-Warshalla
• kolorowanie grafów
• grafy planarne
• kolorowanie grafów planarnych
• slajdy z wykładu: Grafy.pptx

Ćwiczenia

12 października 2016 r: liczby w zapisie binarnym (lista 1)

1. Zapisz następujące liczby dziesiętne postaci dwójkowej stosując kodowanie ZM, U1 i U2:
   1. 245
   2. -117
   3. 1968
   4. -2740
   5. 57391
   6. -54286
   Uwaga. Użyj najmniejszej możliwej liczby bitów (wliczając w to bit znaku).
2. Zapisz następujące liczby w postaci binarnej stałopozycyjnej z dokładnością do 6 bitów po kropce dwójkowej stosując kodowanie U2:
   1. ²/₄₉
   2. 9¹/₇
   3. ¹²⁴/₁₅
   4. -³/₂₁
   5. -16⁴/₃₅
   6. -²⁵/₉
   Wskazówka. Wylicz 7 bitów po kropce dwójkowej i dopiero wtedy zaokrąglij wynik do 6 miejsc.
3. Zapisz następujące liczby w postaci binarnej zmiennopozycyjnej w obiekcie typu single (4 bajty) zgodnie ze standardem IEEE-754:
   1. 1.5859375
   2. -0.046875
   3. 9.46875
   4. -19375.0
   Uwaga. Wyznacz bit znaku, bity cechy (z uwzględnieniem BIAS) i mantysy (kodujemy tylko część ułamkową po normalizacji).
4. 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.

19 października 2016 r: algorytmy i ich złożoność (lista 2)

1. Zapisz w postaci schematu blokowego:
   1. algorytm generowania binarnej reprezentacji liczby naturalnej, zaczynając od najmniej znaczącego bitu;
   2. algorytm inkrementacji (zwiększenia o 1) i algorytm dekrementacji (zmniejszenia o 1) zadanej liczby całkowitej zapisanej w postaci U2;
   3. algorytm zmiany znaku w binarnej liczbie całkowitej zapisanej w postaci U2;
   4. algorytm generowania binarnej reprezentacji liczby rzeczywistej z przedziału (0, 1) z dokładnością do k miejsc po kropce dwójkowej.
2. Jak wyliczyć zmianę znaku w liczbie całkowitej zapisanej binarnie w postaci U2 za pomocą operacji negacji bitowej NOT oraz inkrementacji albo dekrementacji? Odpowiedź uzasadnij.
3. Jak wyznaczyć pierwszy zapalony najmniej znaczący bit w binarnej liczbie całkowitej zapisanej w postaci U2 za pomocą operacji bitowych AND, OR, XOR i przesunięć SHL, SHR oraz inkrementacji i dekrementacji? Odpowiedź uzasadnij.
4. 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

5. 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.
6. Przypomnij sobie definicję operatora Ο i uporządkuj poniższe funkcje ze względu na ich rząd wielkości, od asymptotycznie najwolniej rosnącej do asymptotycznie rosnącej najszybciej posługując się relacjami ⊆ i ≡:
   1. (n+1)^0.5
   2. 3·n²+5·n
   3. 2ⁿ
   4. 5·n+3
   5. nⁿ⁺¹
   6. n^0.1
   7. log₂(5·n)
   8. 2·n³+5
   9. 3^2·n
   10. √n
   11. 4ⁿ⁺¹
   12. log₃(n⁵)
   13. (n+1)ⁿ
   14. 3ⁿ⁺²
   15. 2·n+7
   Przykład. Początek rozwiązania tego zadania wygląda następująco: Ο(log₂(n)) ≡ Ο(log₃(n⁵)) ⊆ Ο(n^0.1) ...
7. 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.

26 października 2016 r: rekurencja (lista 3)

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? Można przyjąć, że długość ciągu n jest globalnie znana albo że jest parametrem funkcji. Napisz w pseudokodzie funkcję rekurencyjną implementującą ten wzór. Jaka będzie złożoność obliczeniowa tej funkcji?
3. Napisz rekurencyjną definicję dla współczynnika dwumianowego. Uzasadnij, skąd się wziął ten wzór. Napisz w pseudokodzie funkcję rekurencyjną implementującą ten wzór. Jaka będzie złożoność obliczeniowa tej funkcji? Postaraj się przekształcić wzór rekurencyjny dla współczynnika dwumianowego w taki sposób, aby po prawej stronie znajdował się tylko jeden współczynnik dwumianowy. Czy implementując ten wzór polepszy się złożoność obliczeniowa funkcji?
4. Napisz rekurencyjną definicję n-tej liczby Catalana. Jaką interpretację mają te liczby? Napisz w pseudokodzie funkcję rekurencyjną implementującą ten wzór.
5. Napisz rekurencyjną definicję dla funkcji Ackermanna. Wylicz kilka pierwszych wartości dla tej funkcji. Napisz w pseudokodzie funkcję rekurencyjną implementującą ten wzór.

9 listopada 2016 r: stos, kolejka i ONP (lista 4)

1. Kolejka dwukierunkowa to struktura danych podobna do kolejki, pozwalająca jednak na wstawianie i usuwanie elementów na obu jej końcach. Jak zaimplementować taką strukturę na tablicy, aby wszystkie operacje wstawiania i usuwania działały w czasie stałym Ο(1)? Przedstaw ideę rozwiązania. Napisz w pseudokodzie wszystkie cztery procedury.
2. Dana jest tablicowa implementacja kolejki. Pokaż, jak zmodyfikować tą implementację, aby można było odwrócić kolejność elementów w kolejce w stałym czasie Ο(1).
3. Dana jest tablicowa implementacja stosu. Pokaż, jak zmodyfikować tą implementację, aby można było odwrócić kolejność elementów na stosie w stałym czasie Ο(1).
4. 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?
5. Zapisz w notacji prefiksowej (notacja polska Łukasiewicza) następujące wyrażenia (z uwzględnieniem priorytetów występujących tam operatorów):
   1. d / 4 * a / c * b
   2. 3 * x - y / 7 + z
   3. 1 + 2 * x ^ 2 ^ (y / 4 - 8)
6. Opracuj algorytm przekształcania wyrażeń zapisanych 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?
7. 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 /
8. 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)

16 listopada 2016 r: sortowanie (lista 5)

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

23 listopada 2016 r: dziel i zwyciężaj (lista 6)

1. Dane są dwie liczby zespolone x = (a + b·i) oraz y = (c + d·i). Iloczyn tych liczb to x·y = ((ac-bd) + (ad+bc)·i). Jak wykorzystać technikę dziel i zwyciężaj do obliczenia iloczynu liczb zespolonych w taki sposób, aby wykonać nie 4 a tylko 3 mnożenia?
2. W tablicy n-elementowej zapisane są dwa posortowane ciągi: pierwszy ciąg o długości m a za nim drugi ciąg o długości n-m. Opracuj algorytm scalania tych ciągów, który będzie korzystał z zewnętrznego bufora pomocniczego o rozmiarze min{m, n-m}. Zadbaj o to, aby opracowana metoda była stabilna i działała w miejscu. Opisz ideę działania algorytmu a potem zapisz go w pseudokodzie. Złożoność czasowa tego algorytmu powinna być liniowa Ο(n).
3. W przedstawionej na wykładzie rekurencyjnej wersji algorytmu sortowania przez scalanie dane wejściowe o rozmiarze n były dzielone na dwie części w proporcjach 1:1 (dokładne rozmiary po podziale to odpowiednio ⌈ⁿ/₂⌉ oraz ⌊ⁿ/₂⌋). Jak zmieni się złożoność czasowa tego algorytmu, gdy dane wejściowe będą dzielone na dwie części w proporcjach 1:k dla pewnej ustalonej wartości k (dokładne rozmiary po takim podziale to odpowiednio ⌈ⁿ/_k+1⌉ oraz ⌊^k·n/_k+1⌋)?
4. Jak wykorzystać algorytm sortowania przez scalanie do policzenia wszystkich inwersji w zadanym ciągu liczbowym?
5. Często mamy do czynienia z danymi, których wartości się powtarzają. Pokaż, jak zmodyfikować algorytm podziału Lomuta, aby podzielił dane zapisane w n-elementowej tablicy względem piwota p na trzy części: elementy <p, elementy =p i elementy >p.
6. Niech dana będzie n-elementowa nieuporządkowana tablica A z liczbami oraz dwa piwoty p i q, takie że min(A)≤p≤q≤max(A). Pokaż, jak zmodyfikować algorytm podziału Lomuta, aby dokonywał trójpodziału na elementy <p, elementy ∈[p,q] i elementy >q.
7. Jak zmodyfikować algorytm sortowania szybkiego, aby w każdym przypadku głębokość wywołań rekurencyjnych była nie większa niż log(n) dla danych rozmiaru n? Wskazówka: jedno z wywołań rekurencyjnych rozwiń w miejscu.

30 listopada 2016 r: metoda redukcji (lista 7)

1. Zmodyfikuj algorytm Karatsuby (dziel i zwyciężaj) mnożenia długich liczb w taki sposób, aby liczba była dzielona na trzy części zamiast na dwie. Ile mnożeń krótszych liczb musisz wtedy wykonać? Jaka jest złożoność czasowa twojego algorytmu?
   Wskazówka: asymptotyczny czas działania algorytmu z podziałem na trzy części powinien być lepszy niż z podziałem na dwie części.
2. Dane są dwie posortowane n-elementowe tablice liczb oraz liczba całkowita k z zakresu 1 ≤ k ≤ 2n. Opisz algorytm znajdowania k-tej co do wielkości liczby spośród liczb zapisanych w obu tablicach. Czas działania twojego algorytmu powinien być rzędu O(log n).
   Wskazówka: wykorzystaj w swoim rozwiązaniu technikę redukcji do mniejszego podproblemu.
3. Dana jest posortowane n-elementowa tablica liczb, pewna wartość x oraz liczba naturalna k ≤ n. Opracuj efektywny algorytm znajdowania w tej tablicy k liczb najbliższych liczbie x.
4. Dana jest funkcja f(x) ciągła na przedziale zadanym [a, b]. Wiemy też, że f(a) < 0 oraz f(b) > 0. Opracuj efektywny algorytm znajdowania miejsca zerowego tej funkcji należącego do przedziału [a, b] z dokładnością do pewnego ustalonego ε > 0.

7 grudnia 2016 r: programowanie dynamiczne (lista 8)

1. Przedstaw w pseudokodzie rekurencyjny algorytm obliczający n-tą liczbę Fibonacciego, który wykorzystuje n-elementową tablicę do spamiętywania raz obliczonych wyników (aby nie wykonywać wielokrotnie tych samych obliczeń).
2. Udowodnij, że rekurencyjna procedura obliczająca współczynnik dwumianowy (ⁿ_k) będzie w sumie wywoływana 2·(ⁿ_k) - 1 razy.
3. Pokaż, jak obliczyć współczynnik dwumianowy (ⁿ_k) używając tablicy pomocniczej B[0...k] oraz kilku dodatkowych komórek pamięci. Następnie pokaż, jak rozwiązać to zadanie używając jeszcze mniejszej tablicy pomocniczej B[0...min{k, n-k}] oraz kilku dodatkowych komórek pamięci.
4. Pokaż, jak zrekonstruować największy wspólny podciąg LCS dla zadanych ciągów wejściowych X i Y tylko na podtawie tablicy z długościami LCS dla wszystkich par prefiksów tych ciągów (tablica taka jest tworzona w trakcie działania klasycznego algorytmu rozwiązującego zadanie LCS). Twój algorytm powinien działać w czasie O(m + n), gdzie m = |X| i n = |Y|.

14 grudnia 2016 r: programowanie dynamiczne (lista 9)

1. Dany jest nieuporządkowany ciąg n liczb. Przedstaw algorytm obliczający długość najdłuższego podciągu rosnącego w zadanym ciągu. Oszacuj złożoność czasową i pamięciową opisanego algorytmu.
   Wskazówka: policz dla każdego elementu w tym ciągu, jaka jest maksymalna długość podciągu rosnącego kończącego się na tym elemencie.
2. Dany jest nieuporządkowany ciąg n liczb. Przedstaw algorytm wyznaczający najdłuższy podciąg rosnący w zadanym ciągu. Złożoność czasowa opisanego algorytmu powinna należeć do O(n·log(n)) a pamięciowa do O(n).
   Wskazówka 1: policz dla każdego elementu w tym ciągu, jaka jest maksymalnad ługość podciągu rosnącego kończącego się na tym elemencie oraz który element jest poprzednikiem bieżącego.
   Wskazówka 2: zastosuj wyszukiwanie binarne do znalezienia elementu poprzedzającego bieżący element.
3. Koszt pomnożenia macierzy o rozmiarze a×b przez macierz o rozmiarze b×c wynosi a·b·c mnożeń i a·(b-1)·c dodawań, co sprowadza się do ogólnego kosztu Θ(a·b·c) mierzonego liczbą operacji arytmetycznych. Wiemy też, że mnożenie kilku macierzy jest łączne, więc możemy dowolnie ponawiasować iloczyn ciągu macierzy.
   Dany jest ciąg n macierzy M₁, M₂, ..., M_n o rozmiarach odpowiednio k₀×k₁, k₁×k₂, ..., k_n-1×k_n. Należy optymalnie wymnożyć te macierze, czyli pomnożyć je w takiej kolejności, aby wykonać jak najmniej operacji arytmetycznych. Przedstaw algorytm rozwiązujący to zadanie i oszacuj jego złożoność obliczeniową.
   Wskazówka: wyznacz, które mnożenie będzie wykonane jako ostatnie w rozwiązaniu optymalnym.
4. Triangulacja to podział wielokąta zwykłego na sumę nienakładających się na siebie trójkątów, których wierzchołkami mogą być tylko wierzchołki danego wielokąta.
   Danych jest n punktów na płaszczyźnie P₁, P₂, ..., P_n, które są kolejnymi wierzchołkami wielokąta wypukłego. Należy optymalnie striangulować ten wielokąt, czyli tak podzielić go na trójkąty, aby suma długości wszystkich krawędzi, które dzielą dany wielokąt na trójkąty była jak najmniejsza. Przedstaw algorytm rozwiązujący to zadanie i oszacuj jego złożoność obliczeniową.
   Wskazówka: można rozpocząć od boku wyznaczonego przez punkty P₁ i P_n i wyznaczyć trzeci wierzchołek tworzący z nimi trójkąt należący do rozwiązania optymalnego.

4, 11 stycznia 2017 r: automaty skończone (lista 10, 11)

1. Napisz w notacji BNF a potem w notacji EBNF formuły definiujące:
   1. identyfikator (ciąg alfanumeryczny rozpoczynający się od litery);
   2. liczbę rzeczywistą w notacji naukowej, taką jak literał zmiennopozycyjny w języku C++ (liczba rzeczywista z opcjonalną częścią ułamkową po kropce dziesiętnej, potem litera 'e' albo 'E' a po niej wykładnik w postaci liczby całkowitej);
   3. deklarację zmiennych całkowitoliczbowych w uproszczonym języku C++ (nazwa typu a po nim lista zmiennych odseparowanych przecinkami; zmienne mogą być zainicjalizowane tylko prostymi literałami; deklarację kończy średnik);
   4. wyrażenie logiczne (operandami w takim wyrażeniu mogą być zmienne logiczne albo literały 'true' czy 'false'; operatory logiczne to koniunkcja 'and' albo ∧, alternatywa 'or' albo ∨, negacja 'not' albo ¬, implikacja 'impl' albo ⇒, równoważność 'equiv' albo ⇔; w wyrażeniach logicznych można także używać nawiasów).
2. Narysuj diagramy syntaktyczne dla:
   1. liczby całkowitej;
   2. liczby rzeczywistej z opcjonalną częścią ułamkową po kropce dziesiętnej;
   3. deklaracji napisu takiego jak literał napisowy w języku C++ (ciąg liter w cudzysłowach; wewnątrz cudzysłowów mogą się znaleźć znaki specjalne rozpoczynające się od odwróconego ukośnika);
   4. definicji struktury w uproszczonym języku C++ (we wnętrzu struktury mogą być umieszczone tylko deklaracje pól całkowitych, rzeczywistych, boolowskich i znakowych oraz tablice wymienionych typów).
3. Niech dany będzie alfabet złożony z trzech liter Σ = {a, b, c}. Skonstruuj automat skończony akceptujący tylko słowa, które:
   1. mają nieparzystą długość;
   2. kończą się sufiksem baba;
   3. są niepuste i w których nie ma obok siebie dwóch takich samych liter;
   4. są niepustym ciągiem takich samych liter (na przykład bb, a, cccc).
4. Zaprojektuj automat skończony akceptujący liczby podzielne przez 6 zapisane w systemie dwójkowym.
5. Zaprojektuj automat skończony akceptujący liczby podzielne przez 9 zapisane w systemie dziesiętnym.
6. Zaprojektuj automat skończony akceptujący poprawnie zapisane w systemie dziesiętnym nieujemne liczby całkowite (bez zer wiodących na początku, za wyjątkiem liczby zero).
7. Napisz wyrażenie regularne, do którego dopasuje się:
   1. poprawnie zapisana godzina z dokładnością do minut albo sekund (na przykład 14:51, 00:15, 17:03:59);
   2. poprawnie zapisana data (na przykład 2016-12-20, 2017-01-04, 2018-02-28) przy założeniu, że nigdy nie wystąpi data 29 lutego w roku przestępnym;
   3. poprawnie zapisana liczba zmiennopozycyjna z kropką dziesiętną (na przykład 123.45, -0.987, 0.00001);
   4. poprawnie zapisany adres mailowy (na przykład abc@interia.pl, def.gh@gmail.com, kl-mn@onet.pl).

 

8. Napisz wyrażenie regularne, do którego dopasuje się poprawnie zapisany polski adres (bez adresata): ulica/plac, numer domu, kod pocztowy i miejscowość z najbliższą pocztą.
   Przykład: pl. Przestronny 17 m. 3, 56-789 Wrocław.
9. Zaprojektuj automat skończony akceptujący poprawnie zapisany skrótowy liczebnik porządkowy w języku angielskim.
   Przykłady: 21-st, 402-nd, 1003-rd, 111-th.
10. Narysuj diagram syntaktyczny dla wyrażenia arytmetycznego zapisanego w języku C++.
    Przykłady: (123 + x) * 0.7, -sin(alfa + pi / 2) * cos(alfa - beta).
11. Napisz w notacji BNF a potem w notacji EBNF formuły definiujące spis treści w jakiejś książce.

18, 25 stycznia 2017 r: listy, drzewa, kolejki priorytetowe, zbiory rozłączne (lista 12, 13)

1. Opracuj algorytm obliczający długość zadanej listy jednokierunkowej. Napisz napisz w pseudokodzie wersję iteracyjną i rekurencyjną tej procedury. Porównaj złożoność czasową i pamięciową obu procedur.
2. Rozważmy listę nieuporządkowaną z wartościami, które często się powtarzają na tej liście. Opracuj algorytm usuwania zadanej wartości z listy jednokierunkowej:
   1. usuń pierwsze wystąpienie zadanej wartości na liście;
   2. wszystkie wystąpienia na zadanej wartości liście;
   3. usuń ostatnie wystąpienie zadanej wartości na liście;
3. Opracuj algorytm odwracania listy jednokierunkowej. 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. 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. 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.
8. 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ę.
9. 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).
10. 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).
11. 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)?
12. 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.
13. Opracuj algorytm i zapisz go w pseudokodzie, który znajdzie element poprzedni (albo następny) co do wielkości względem zadanej wartości klucza x w drzewie BST.

 

14. Wykaż, że odwrotnie posortowana tablica jest kopcem.
15. Zaprojektuj strukturę danych wykorzystującą kopce, która będzie efektywnie realizowała operacje insert (wstawienie nowego elementu do zbioru) oraz extract-median (usunięcie ze zbioru elementu środkowego co do wielkości, czyli mediany). Operacje te powinny działać w czasie logarytmincznym względem rozmiaru danych. Opisz dokładnie działanie tych operacji i przeanalizuj złożoność obliczeniową każdej z nich.
16. Zaprojektuj strukturę danych, która będzie efektywnie realizowała operacje insert (wstawienie nowego elementu do zbioru) oraz extract-min (usunięcie ze zbioru elementu minimalnego) oraz extract-max (usunięcie ze zbioru elementu maksymalnego). Operacje te powinny działać w czasie logarytmincznym względem rozmiaru danych. Opisz dokładnie działanie tych operacji i przeanalizuj złożoność obliczeniową każdej z nich.
17. Pokaż, jak za pomocą kolejki priorytetowej zaimplementować zwykłą kolejkę FIFO albo zwykły stos LIFO.
18. Wykaż, że w drzewie dwumianowym B_k stopnia k, które zawiera 2^k węzłów, długość ścieżki od korzenia do dowolnego węzła w tym drzewie jest nie większa niż k.
19. Jak włożyć drzewo dwumianowe B_k stopnia k do tablicy 2^k-elementowej? Twoje rozwiązanie powinno pozwalać na łatwe łączenie dwóch drzew dwumianowych. Napisz wzory pozwalające ustalić na podstawie indeksu w~tablicy numer poziomu, na którym węzeł się znajduje, jego stopień oraz indeksy ojca, brata i kolejnych synów.
20. Napisz w pseudokodzie implementację operacji meld łączącej dwa kopce dwumianowe.
21. Dane jest drzewo dwumianowe B_k stopnia k, które zawiera 2^k węzłów. W drzewie tym jest zachowany porządek kopcowy z elementem minimalnym w korzeniu. Następnie zmieniamy w dowolnym wybranym węźle pamiętaną w nim wartość. Porządek kopcowy może więc zostać zaburzony. Jeśli zmienimy wartość na mniejszą, to zwykłe sianie w górę przywróci ten porządek w O(log n) krokach, a więc w akceptowalnym czasie. Jeśli natomiast zmienimy wartość na większą, to przywrócenie porządku kopcowwego poprzez proste sianie w dół będzie działać istotnie dłużej (O(log² n) kroków). Opracuj metodę, która po zmianie wartości na większą we wskazanym elemencie przywróci porządek kopcowy w czasie O(log n).
22. Dana jest rodzina n jednoelementowych zbiorów rozłącznych. Zbiory te będziemy pamiętali w postaci drzewiastej ze zbalansowanym łączeniem. Skonstruuj ciąg n-1 operacji union, by w ich wyniku powstał jeden zbiór reprezentowany przez n-elementowe drzewo o wysokości ≤log(n).
23. Zbiory rozłączne pamiętamy w postaci drzewiastej ze zbalansowanym łączeniem. Napisz w pseudokodzie implementację operacji union z wykorzystaniem parametru rank w węźle, który jest reprezentantem zbioru.
24. Zbiory rozłączne pamiętamy w postaci drzewiastej ze zbalansowanym łączeniem i kompresją ścieżek przy wyszukiwaniu. Napisz w pseudokodzie implementację rekurencyjną a potem iteracyjną operacji find, która znajduje reprezentanta zbioru i dokonuje kompresji ścieżki, która prowadziła od zadanego węzła do korzenia drzewa.

1 lutego 2017 r: grafy (lista 14)

1. Rozważmy graf prosty. Stopień wierzchołka w grafie to liczba incydentnych z nim krawędzi. Wykaż, że suma stopni wszystkich wierzchołków jest liczbą parzystą.
2. Udowodnij, że w grafie spójnym każde dwie najdłuższe ścieżki mają wspólny wierzchołek.
3. Dopełnieniem grafu prostego G = (V, E) nazywamy graf G' = (V, E') złożony ze wszystkich krawędzi, których nie ma w G, czyli E' = {(u, v) : (u, v) ∉ E}. Udowodnij, że przynajmniej jeden sposród grafów G, G' jest spójny.
   Wskazówka: Załóż, że G nie jest spójny (możesz przyjąć, że ma dokładnie dwie składowe spójności) i pokaż wtedy, że G' jest spójny.
4. W przedziale pociągu siedzi sześć osób. Pokaż, że wśród nich znajdą się trzy osoby, które albo znają się nawzajem, albo żadna z nich nie zna dwóch pozostałych.

Konwersatorium

7 października 2016 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
• operatory inkrementacji i dekrementacji
• wyrażenia arytmetyczne
• operatory relacyjne i logiczne
• wyrażenia logiczne
• instrukcja warunkowa if

14 października 2016 r: instrukcje sterujące

• operatory bitowe
• wyrażenia bitowe
• 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
• instrukcja wyboru switch-case

21 października 2016 r: funkcje

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

28 października 2016 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*
• argumenty wywołania programu
• przekazywanie tablic do funkcji poprzez argumenty
• tworzenie tablic na stercie operatorem new[]
• usuwanie tablic ze sterty operatorem delete[]

4 listopada 2016 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

18 listopada 2016 r: struktury

• referencja
• referencja jako argument funkcji
• tworzenie tablic na stercie operatorem new[]
• usuwanie tablic ze sterty operatorem delete[]
• definicja struktury struct
• pola w strukturze
• zmienne strukturowe
• operator . (kropka) realizujący dostęp do składowych w strukturze
• inicjalizacja struktury za pomocą listy inicjalizującej
• inicjalizacja struktury za pomocą konstruktora
• zapisanie struktury do strumieniea za pomocą operatora <<

25 listopada 2016 r: kolokwium I

2 grudnia 2016 r: klasy

• I filar programowania obiektowego - abstrakcja (modelowanie)
• klasa jako nowy typ danych
• pola i funkcje skłądowe w klasie
• dostęp do składowych w klasie za pomocą . oraz ->
• konstruktory
• wskaźnik this
• 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

16 grudnia 2016 r: operatory

• II filar programowania obiektowego - hermetyzacja (ukrywanie implementacji)
• składowe publiczne i prywatne
• deklaracja i definicja składowych statycznych
• odwołania do składowych statycznych
• funkcje zaprzyjaźnione z klasą
• operatory składowe
• operatory zaprzyjaźnione
• operatory strumieniowe

5 stycznia 2017 r: kolokwium II

13 stycznia 2017 r: wprowadzenie do F#

20 stycznia 2017 r: wprowadzenie do F#

27 stycznia 2017 r: kolokwium III

3 lutego 2017 r: przygotowanie do egzaminu

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ę 16.01 z kompilatorem gcc 5.4.0 - dla Windowsa będzie to plik codeblocks-16.01mingw-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ą dla wszystkich i mają określony termin zakończenia. Uwaga, hasło wejściowe to: wip2016.

12 października 2016 r: instrukcja warunkowa

1. Skompiluj i uruchom program w środowisku Code::Blocks, który wypisze kilka parametrów biomedycznych dotyczących Twojej osoby (wiek, wzrost, waga, kolor oczu, itp). Parametry te zdefiniuj jako stałe w swoim programie.
2. Napisz program, który wczyta liczbę rzeczywistą t a następnie policzy i wypisze wartość funkcji ((1-t²)(1-k²t²))^-1/₂ dla tej liczby. Parametr k zdefiniuj w programie jako stałą należącą do zbioru (0, 1).
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ą wartości tego rozwiązania.
5. Zrób zadanie ABS wystawione na themisie w zbiorze zadań o nazwie "laboratorium 1".

Zadanie domowe polega na zrealizowaniu trzech zadań wystawionych na themisie w zbiorze zadań o nazwie "zadanie domowe 1": CPP100, CPP106, SUMSUB.

19 października 2016 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).

Zadanie domowe polega na zrealizowaniu trzech zadań wystawionych na themisie w zbiorze zadań o nazwie "zadanie domowe 2": CPP102, CPP107, CS.

26 października 2016 r: rekurencja

1. 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 oraz iteracyjnej.
2. 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.
3. Napisz program, który wczyta liczbę naturalną n<20 a następnie policzy i wypisze wartość n-tej liczby Catalana. Zaimplementuj algorytm obliczania liczby Catalana w wersji rekurencyjnej.
4. Napisz program, który wczyta dwie małe liczby naturalne m i n a następnie policzy i wypisze wartość funkcji Ackermanna A(m, n). Zaimplementuj algorytm obliczania funkcji Ackermanna w wersji rekurencyjnej.

Zadanie domowe polega na zrealizowaniu trzech zadań wystawionych na themisie w zbiorze zadań o nazwie "zadanie domowe 3": BIN, CPP108, KKGCD.

2 listopada 2016 r: tablice

Zadanie domowe polega na zrealizowaniu trzech zadań wystawionych na themisie w zbiorze zadań o nazwie "zadanie domowe 4": CPP104, CPP129, KNOKURS7.

9 listopada 2016 r: tablice

1. Napisz program, który wczyta ze standardowego wejścia liczbę naturalną n a potem n liczb całkowitych, umieszczając je w automatycznie utworzonej tablicy (na stosie); na koniec program ma wczytać liczbę naturalną k < n Następnie program ma wyznaczyć i wypisać na standardowym wyjściu k najmniejszych wartości spośród n wczytanych do tablicy.
   Uwaga. Liczby wypisane jako wynik nie muszą być wypisane w takiej kolejności jak były wczytywane.
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 (na stercie) 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.

Zadanie domowe polega na zrealizowaniu trzech zadań wystawionych na themisie w zbiorze zadań o nazwie "zadanie domowe 5": CPP126, CTABLES6, CTABLES9.

16 listopada 2016 r: sortowanie

1. Napisz program, który wczyta ze standardowego wejścia liczbę naturalną n a potem utworzy denamicznie na stercie n-elementową tablicę dla liczb całkowitych i wpisze do niej losowe liczby z zakresu od 100 do 999. Program ma wypisać zawartość całej tablicy, następnie posortować ją algorytmem sortowania przez wstawianie i na końcu znowu wypisać zawartość tablicy po posortowaniu.
   Uwaga 1. Zdefiniuj osobną funkcję do sortowania tablicy.
   Uwaga 2. Na końcu zwolnik pamięć przydzieloną na stercie dla tablicy z danymi.
2. Napisz program, który wczyta ze standardowego wejścia liczbę naturalną n a potem utworzy denamicznie na stercie n-elementową tablicę dla liczb całkowitych i wpisze do niej kolejne liczby naturalne od 0 do n-1. Program ma dokonać losowej permutacji komórek w tablicy i na końcu wypisać jej zawartość.
   Zadbaj o to, by każda permutacja była wybierana z (prawie) takim samym prawdopodobieństwem.
   Uwaga 1. Zdefiniuj osobną funkcję do spermutowania danych w tablicy.
   Uwaga 2. Na końcu zwolnik pamięć przydzieloną na stercie dla tablicy z danymi.
3. Napisz program, który wczyta ze standardowego wejścia liczbę naturalną n a potem n liczb całkowitych, umieszczając je w utworzonej dynamicznie na stercie n-elementowej tablicy. Program ma wypisać zawartość całej tablicy, następnie posortować ją algorytmem sortowania bąbelkowego i na końcu znowu wypisać zawartość tablicy po posortowaniu.
   Zadbaj o to, by algorytm wykonywał na przemiennie przesiewanie w górę i w dół tablicy oraz aby zakończył działanie wcześniej, gdy tablica zostanie posortowana (zliczaj liczbę wykonywanych zamian w każdym przesiewaniu i sprawdzaj czy wynosi 0).
   Uwaga 1. Zdefiniuj osobną funkcję do sortowania tablicy.
   Uwaga 2. Na końcu zwolnik pamięć przydzieloną na stercie dla tablicy z danymi.

Zadanie domowe polega na zrealizowaniu jednego zadania wystawionego na themisie w zbiorze zadań o nazwie "zadanie domowe 6": PER.

23 listopada 2016 r: ONP

1. Napisz program, który oblicz wartość wyrażenia zapisanego w postaci ONP. Wyrażenie odczytuj sekwencyjnie ze standardowego wejścia (aż do napotkania końca danych ^Z). Wyrażenie może zawierać tylko liczby rzeczywiste oraz 2-argumentowe operatory dodawania (+), odejmowania (-), mnożenia (*) i dzielenia(/).
   Uwaga 1. Wykorzystaj w swoich obliczeniach stos liczb rzeczywistych zaimplementowany na rozsądnie dużej tablicy.
   Uwaga 2. Zakładamy, że wyrażenie ONP jest zapisane prawidłowo.

Zadanie domowe polega na zrealizowaniu dwóch zadań wystawionych na themisie w zbiorze zadań o nazwie "zadanie domowe 7": BINSRCH, INWERSJE.

30 listopada 2016 r: dziel i zwyciężaj

1. Napisz program, który wczyta ze standardowego wejścia liczbę naturalną n a potem utworzy denamicznie na stercie n-elementową tablicę dla liczb całkowitych i wpisze do niej losowe liczby z zakresu od 0 do 2³⁰-1. Program ma wypisać zawartość całej tablicy, następnie posortować ją algorytmem sortowania szybkiego i na końcu znowu wypisać zawartość tablicy po posortowaniu. Zaimplementuj algorytm sortowania szykiego w sposób rekurencyjny. Jako metodę podziału zaimplementuj algorytm Lomuta z modyfikacją polegającą na ustawieniu na granicy podziału piwota.
   Uwaga 1. Zdefiniuj osobną funkcję rekurencyjną do sortowania szybkiego tablicy oraz osobną funkcję dokonująca podziału względem losowo wybranego elementu.
   Uwaga 2. Na końcu zwolnij pamięć przydzieloną na stercie dla tablicy z danymi.

Zadanie domowe polega na zrealizowaniu dwóch zadań wystawionych na themisie w zbiorze zadań o nazwie "zadanie domowe 8": HANOICHK, STO2.

7 grudnia 2016 r: programowanie dynamiczne

1. Zadanie jest na themisie: CZEKOLADA (laboratorium 8).

14 grudnia 2016 r: programowanie dynamiczne

1. Wybierz jedno z zadań na themisie: TRIAN albo MAXNDSUB (laboratorium 9).

4 stycznia 2017 r: programowanie w F#

1. Podstawowe typy danych w F#.
2. Wyrażenia i przypisania.
3. Funkcje i rekurencja.

11 stycznia 2017 r: programowanie w F#

1. Listy i operacje na listach.
2. Dopasowanie do wzorca.
3. Przetwarzanie list.

18 stycznia 2017 r: programowanie w F#

1. Unie.
2. Definiowanie i przetwarzanie drzew.

25 stycznia 2017 r: programowanie w F#

1. Rekordy.
2. ...

1 lutego 2017 r: programowanie w F#

1. Przetwarzanie sekwencyjne.
2. ...

Kolokwia i egzaminy

Kolokwium I

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 góry przez g(n).
2. Przypomnij definicję operatora Ω(g(n)), wyznaczającego klasę wszystkich funkcji ograniczonych asymptotycznie z dołu przez g(n).
3. Podaj przykład funkcji f(n), która należy do Ο(10ⁿ) ale nie należy do Θ(10ⁿ).
4. Podaj przykład funkcji f(n), która należy do Ω(n²) ale nie należy do Θ(n²).
5. Algorytm A wykonuje n² kroków obliczeniowych a algorytm B 100·n kroków rozwiązując pewien problem dla danych rozmiaru n. Dla jakich rozmiarów danch bardziej opłaca się stosować algorytm A a dla jakich algorytm B?
6. Uporządkuj klasy funkcji wyznaczone operatorem O za pomocą relacji ≡ i ⊂: O(log₃(n²)), O(2²ⁿ), O(log₁₀(5n+1)), O(4ⁿ⁺²), O(2^log(n)+1).
7. Korzystając z definicji pokaż, że log(n³) ∈ Ο(log(n)).
8. Korzystając z definicji pokaż, że n·log(n) ∈ Ω(n).
9. Zapisz liczbę dziesiętną -99 w postaci binarnej na ośmiu bitach używając systemu kodowania U2.
10. Zapisz liczbę dziesiętną -33 w postaci binarnej na ośmiu bitach używając kodowania ZM, U1 i U2.
11. Zapisz liczbę wymierną 93⁵/₁₇ w postaci binarnej w systemie stałopozycyjnym z dokładnością do 6 miejsc po kropce dwójkowej.
12. Wyznacz binarną wartość cechy i mantysy dla liczby 9.46875 po znormalizowaniu.
13. Narysuj schemat blokowy dla zadania obliczania funkcji signum(x).
14. Narysuj schemat blokowy dla zadania iteracyjnego obliczania silni n!.
15. Narysuj schemat blokowy dla zadania wypisania wszystkich pierwiastków równania kwadratowego.
16. Narysuj schemat blokowy dla zadania zwiększenia o 1 liczby n-bitowej zapisanej w systemie U2.
17. Narysuj schemat blokowy dla zadania zmiany znaku na przeciwny liczby n-bitowej zapisanej w systemie U2.
18. Napisz rekurencyjną definicję dla funkcji silnia n!.
19. Napisz rekurencyjną definicję dla współczynnika dwumianowego (ⁿ_k).
20. Napisz rekurencyjną definicję dla funkcji Ackermanna Ack(m, n).
21. Przypomnij rekurencyjną definicję funkcji obliczającej n-ty wyraz ciągu Fibonacciego. Ile wywołań tej funkcji zostanie zrobionych dla argumentu o wartości 5?
22. Przypomnij rekurencyjną definicję funkcji obliczającej n-tą liczbę Catalana. Ile wywołań tej funkcji zostanie zrobionych dla argumentu o wartości 4?
23. Jak zmodyfikować algorytm szybkiego potęgowania aby działał dla liczb zapisanych w systemie dziesiętnym?
24. Jak wykorzystać algorytm Euklidesa do znajdowania NWW?
25. Jak wykorzystać algorytm Euklidesa do znajdowania NWD dla trzech liczb?
26. Jak działa bufor LIFO? Jakie operacje przeprowadza się na takim buforze? Jaka struktura danych implementuje bufor LIFO?
27. Jak działa bufor FIFO? Jakie operacje przeprowadza się na takim buforze? Jaka struktura danych implementuje bufor FIFO?
28. Zapisz w notacji prefiksowej wyrażenie infiksowe 1/x+2*(x^2)-z^(y/4-8).
29. Zapisz w notacji postfiksowej wyrażenie infiksowe cos(1+sin(n/8+2^k+1*3-1))/2.
30. Oblicz wartość wyrażenia zapisanego w postaci ONP: 10 16 14 - ^ 12 18 + - 26 + 28 22 - / 24 + 20 /.

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

1. W n-elementowej tablicy zapisana jest binarnie liczba całkowita w systemie U2 (w każdej komórce jest zapisany jeden bit 0 albo 1). Opisz algorytm zwiększenia o 1 zapisanej tam liczby. Uzasadnij poprawność swojego rozwiązania. Jaka jest złożoność czasowa i pamięciowa przedstawionego algorytmu?
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. Opisz algorytm Dijkstry zamiany wyrażenia arytmetycznego zapisanego w postaci infiksowej z nawiasami na beznawiasową postać postfiksową ONP (algorytm ten jest czasem nazywany stacją rozrządową). Jakich struktur danych używa ten algorytm? Jaka jest jego złożoność obliczeniowa (czasowa i pamięciowa)?

Zadania z kolokwium I z dnia 25 listopada 2016 r.

Kolokwium II

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. Co to znaczy, że algorytm jest stabilny?
2. Co to znaczy, że algorytm działa w miejscu?
3. Jaki problem rozwiązuje algorytm wyszukiwania binarnego?
4. Jaka jest złożoność czasowa algorytmu wyszukiwania binarnego?
5. Ile porównań musi zrobić algorytm wyszukiwania zadanej wartości w nieuporządkowanym ciągu? Odpowiedź uzasadnij.
6. Na czym polega problem sortowania?
7. Czy sortowanie bąbelkowe jest stabilne? Odpowiedź uzasadnij.
8. Czy sortowanie bąbelkowe działa w miejscu? Odpowiedź uzasadnij.
9. Jaka jest złożoność czasowa sortowania bąbelkowego?
10. Ile zamian elementów wykona algorytm sortowania bąbelkowego w najgorszym przypadku? Odpowiedź uzasadnij.
11. Czy sortowanie przez wstawianie jest stabilne? Odpowiedź uzasadnij.
12. Czy sortowanie przez wstawianie działa w miejscu? Odpowiedź uzasadnij.
13. Jaka jest złożoność czasowa sortowania przez wstawianie?
14. Ile porównań elementów wykona algorytm sortowania przez wstawianie, jeśli uruchomimy go na posortowanym ciągu? Odpowiedź uzasadnij.
15. Ile porównań elementów wykona algorytm sortowania przez wstawianie, jeśli uruchomimy go na odwrotnie posortowanym ciągu? Odpowiedź uzasadnij.
16. Czy sortowanie przez wybieranie jest stabilne? Odpowiedź uzasadnij.
17. Czy sortowanie przez wybieranie działa w miejscu? Odpowiedź uzasadnij.
18. Jaka jest złożoność czasowa sortowania przez wybieranie?
19. Ile zamian elementów wykona algorytm sortowania przez wybieranie w najgorszym przypadku? Odpowiedź uzasadnij.
20. Na czy polega problem scalania?
21. Czy algorytm scalania jest stabilny? Odpowiedź uzasadnij.
22. Czy algorytm scalania działa w miejscu? Odpowiedź uzasadnij.
23. Jaka jest złożoność czasowa algorytmu scalania? odpowiedź uzasadnij.
24. Jaka jest złożoność czasowa algorytmu sortowania przez scalanie?
25. Od czego zależy stabilność algorytmu sortowania przez scalanie?
26. Na czy polega problem podziału?
27. Czy algorytm podziału Lomuta jest stabilny? Odpowiedź uzasadnij.
28. Czy algorytm podziału Lomuta działa w miejscu? Odpowiedź uzasadnij.
29. Jaka jest złożoność czasowa podziału Lomuta? odpowiedź uzasadnij.
30. Jaka jest złożoność czasowa algorytmu sortowania szybkiego (przez podział) w najgorszym przypadku?
31. Jaka jest złożoność czasowa algorytmu sortowania szybkiego (przez podział) w oczekiwanym przypadku?
32. Od czego zależy stabilność algorytmu sortowania szybkiego (przez podział)?
33. Na czy polega problem znajdowania k-tego elementu?
34. Jakie zadanie rozwiązuje algorytm Hoare'a?
35. Jaka jest złożoność czasowa algorytmu Hoare'a w najgorszym przypadku?
36. Jaka jest złożoność czasowa algorytmu Hoare'a w oczekiwanym przypadku?
37. Czy algorytm Hoare'a jest stabilny? Odpowiedź uzasadnij.
38. Jakie warunki musi spełniać problem, aby można go było rozwiązać techniką dziel i zwyciężaj?
39. Na czym polega metoda rozwiązywania problemów techniką redukcji?
40. Jakie warunki musi spełniać problem, aby do jego rozwiązania warto było użyć programowania dynamicznego?
41. Jaką grupę problemów zaliczamy do problemów optymalizacyjnych?
42. Jakie zadanie rozwiązuje algorytm Karacuby?
43. Jaki jest czas działania algorytmu Karacuby?
44. Jakią techniką rozwiązuje się zadanie mnożenia długich liczb?
45. Na czym polega problem triangulacji wielokąta wypukłego?
46. Jakią techniką rozwiązuje się zadanie triangulacji wielokąta wypukłego?
47. Jakia jest złożoność pamięciowa i czasowa algorytmu rozwiązującego zadanie triangulacji wielokąta wypukłego?
48. Sformułuj zależność rekurencyjną pozwalającą efektywnie znajdować najkrótszą triangulację wielokąta wypukłego.
49. Na czym polega problem LCS?
50. Jakią techniką rozwiązuje się zadanie znajdowania najdłuższego wspólnego podciągu?
51. Jakia jest złożoność pamięciowa i czasowa algorytmu rozwiązującego zadanie LCS?
52. Sformułuj zależność rekurencyjną pozwalającą efektywnie znajdować najdłuższy wspólny podciąg dla pary zadanych ciągów.
53. Na czym polega problem znajdowania najdłuższego podciągu rosnącego w zadanym ciągu?
54. Jakią techniką rozwiązuje się zadanie znajdowania najdłuższego podciągu rosnącego?
55. Jakia jest złożoność pamięciowa i czasowa algorytmu rozwiązującego zadanie LIS?
56. Sformułuj zależność rekurencyjną pozwalającą efektywnie znajdować najdłuższy podciąg roznący dla zadanego ciągu.
57. Na czym polega problem mnożenia ciągu macierzy?
58. Jakią techniką rozwiązuje się zadanie mnożenia ciągu macierzy?
59. Jakia jest złożoność pamięciowa i czasowa algorytmu rozwiązującego zadanie mnożenia ciągu macierzy?
60. Sformułuj zależność rekurencyjną pozwalającą efektywnie wymnożyć ciąg macierzy.

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

1. Algorytm scalania zaprezentowany na wykładzie zużywa dużo pamięci O(n) na tablice pomocnicze. Zaprojektuj w oparciu technikę dziel i zwyciężaj algorym scalania, który będzie zużywał pamięć tylko na wywołania rekurencyjne. Przedstaw ideę rozwiązania. Napisz w pseudokodzie swój algorytm. Oszacuj jego złożoność obliczeniową (czasową i pamięciową).
2. Dane są dwa uporządkowane ciągi liczb, pierwszy n-elementowy i drugi m-elementowy, a także liczba naturalna 0≤k<n+m. Należy wyznaczyć k-ty co do wielkości element spośród danych z obu ciągów (taki, który stałby na pozycji k-tej po scaleniu). Zaprojektuj w oparciu technikę redukcji algorym rozwiązujący ten problem, który będzie działał w czasie logarytmincznym O(n+m). Przedstaw ideę rozwiązania. Napisz w pseudokodzie swój algorytm. Oszacuj jego złożoność obliczeniową (czasową i pamięciową).
   Wskazówka: porównaj środkowe elementy tych ciągów.
3. Algorytm podziału Lomuta czy Sedgewicka nie jest stabilny. Zaprojektuj w oparciu technikę dziel i zwyciężaj algorym podziału, który będzie działał stabilnie. Przedstaw ideę rozwiązania. Napisz w pseudokodzie swój algorytm. Oszacuj jego złożoność obliczeniową (czasową i pamięciową).
4. Jak zmodyfikować algorytm sortowania szybkiego, aby w każdym przypadku głębokość wywołań rekurencyjnych była nie większa niż log(n) dla danych rozmiaru n? Przedstaw ideę rozwiązania. Napisz w pseudokodzie swój algorytm. Oszacuj jego złożoność obliczeniową (czasową i pamięciową).
   Wskazówka: jedno z wywołań rekurencyjnych rozwiń w miejscu.
5. Dany jest nieuporządkowany ciąg n liter. Należy wyznaczyć najdłuższy palindrom w tym ciągu. Przedstaw ideę rozwiązania. Napisz w pseudokodzie swój algorytm. Oszacuj jego złożoność obliczeniową (czasową i pamięciową).
   Wskazówka: znajdź zależność ostetecznego rozwiązania od rozwiązań mniejszych podzadań.
6. Dany jest nieuporządkowany ciąg n liczb. Należy wyznaczyć najdłuższy podciąg rosnący w tym ciągu. Przedstaw ideę rozwiązania. Napisz w pseudokodzie swój algorytm. Oszacuj jego złożoność obliczeniową (czasową i pamięciową).
   Wskazówka: znajdź zależność ostetecznego rozwiązania od rozwiązań mniejszych podzadań.

Zadania z kolokwium II z dnia 5 stycznia 2017 r.

Kolokwium III

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

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. Napisz w notacji BNF formuły definiujące palindrom zbudowany nad alfabetem Σ = {a, b}.
2. Skonstuuj diagram syntaktyczny dla napisu reprezentującego liczbę naturalną (z zerem włącznie) zapisaną w systemie dwójkowym; liczba różna od zera ma być zapisana bez zer wiodących.
3. Skonstruuj automat skończony akceptujący tylko niepuste słowa zbudowane nad alfabetem Σ = {a, b, c}, których długość jest podzielna przez 3.
4. Skonstruuj automat skończony akceptujący tylko niepuste słowa zbudowane nad alfabetem Σ = {a, b, c}, w których nie sąsiadują ze sobą takie same litery (słowa nie zawierają podsłów aa ani bb ani cc).
5. Napisz wyrażenie regularne, do którego dopasuje się poprawnie zapisana godzina z dokładnością do minut albo sekund (na przykład 14:51, 00:15, 17:03:59); godziny, minuty i ewentualnie sekundy zapisujemy zawsze w formie dwucyfrowej.
6. Wymień i opisz trzy podstawowe operacje słownikowe.
7. Wymień i opisz dwie podstawowe operacje kolejkowe w kolejkach priorytetowych.
8. Wymień i opisz trzy podstawowe operacje kolejkowe w złączalnych kolejkach priorytetowych.
9. Wymień i opisz dwie podstawowe operacje wykonywane na zbiorach rozłącznych.
10. Przy jakim poziomie zapełnienia (procentowo) zostanie powiększona tablica dynamiczna?
11. Przy jakim poziomie zapełnienia (procentowo) zostanie pomniejszona tablica dynamiczna?
12. Co to jest głowa w liście?
13. Co to jest wartownik w liście i gdzie on jest zlokalizowany?
14. Czym się różni lista jednokierunkowa od dwukierunkowej?
15. Co to znaczy, że lista jest cykliczna?
16. Co to jest korzeń w drzewie?
17. Czym są liście w drzewie?
18. Co to jest drzewo binarne?
19. Co to jest binarne drzewo pełne?
20. Co to jest binarne drzewo zupełne?
21. Co to jest binarne drzewo regularne?
22. Ile węzłów zawiera binarne drzewo pełne o wysokości 4?
23. Jaka jest najmniejsza liczba węzłów w binarnym drzewie zupełnym o wysokości 5?
24. Jaka jest maksymalna i minimalna wysokość drzewa binarnego zawierającego 5 węzłów?
25. Jaka jest maksymalna wysokość regularnego drzewa binarnego zawierającego 7 węzłów?
26. Na czym polega porządek symetryczny w drzewie BST?
27. Co to znaczy, że drzewie jest zachowany porządek kopcowy?
28. Podaj warunek zbalansowania w drzewie AVL.
29. Podaj warunek zbalansowania w drzewie czerwono-czarnym.
30. Ile czasu zajmuje wstawienie nowego elementu do drzewa BST w najgorszym przypadku?
31. Ile czasu zajmuje usunięcie elementu z drzewa AVL w najgorszym przypadku?
32. Ile czasu zajmuje wyszukanie elementu w drzewie czerwono-czarnym w najgorszym przypadku?
33. Na czym polega rotacja w lewo/prawo w drzewie BST? Zrób rysunek poglądowy.
34. Ile czasu zajmuje wstawienie nowego elementu do kopca n-elementowego?
35. Ile czasu zajmuje usunięcie elementu maksymalnego z kopca n-elementowego?
36. Jaka jest wysokość kopca n-elementowego?
37. Jaka jest złożoność czasowa budowy kopca od góry?
38. Jaka jest złożoność czasowa budowy kopca od dołu?
39. Jaka jest złożoność czasowa sortowania kopcowego?
40. Czy sortowanie kopcowe działa w miejscu? Odpowiedź uzasadnij.
41. Czy sortowanie kopcowe jest stabilne? Odpowiedź uzasadnij.
42. Jaki jest czas usunięcia elementu maksymalnego z n-elementowej kolejki priorytetowej zbudowanej na liście nieuporządkowanej?
43. Jaki jest czas wstawienia nowego elementu do n-elementowej kolejki priorytetowej zbudowanej na liście uporządkowanej?
44. Podaj definicję drzewa dwumianowego.
45. Ile jest węzłów na poziomie 2 w drzewie dwumianowym B₆?
46. Ile jest węzłów w drzewie dwumianowym B₇?
47. Co robi operacja meld na drzewach dwumianowych?
48. Z ilu drzew dwumianowych będzie się składał kopiec dwumianowy o 23 węzłach?
49. Jaka jest złożoność czasowa operacji usunięcia elementu minimalnego z kopca dwumianowego?
50. Co jest wynikiem opracji find na zbiorach rozłącznych?
51. Czym są parametry opracji union na zbiorach rozłącznych?
52. Na czym polega zbalansowane łączenie zbiorów w listowej reprezentacji zbiorów rozłącznych?
53. Na czym polega zbalansowane łączenie zbiorów w drzewiastej reprezentacji zbiorów rozłącznych?
54. Na czym polega kompresja ścieżki przy wyszukiwaniu reprezentanta zbioru w drzewiastej reprezentacji zbiorów rozłącznych?
55. Jaka jest złożoność czasowa operacji find w listowej reprezentacji zbiorów rozłącznych?
56. Jaka jest złożoność czasowa operacji union w listowej reprezentacji zbiorów rozłącznych ze zbalansowanym łączeniem zbiorów?
57. Jaka jest złożoność czasowa wykonania ciągu m operacji union i find w listowej reprezentacji zbiorów rozłącznych ze zbalansowanym łączeniem zbiorów?
58. Jaka jest złożoność czasowa operacji union w drzewiastej reprezentacji zbiorów rozłącznych?
59. Jaka jest złożoność czasowa operacji find w drzewiastej reprezentacji zbiorów rozłącznych ze zbalansowanym łączeniem?
60. Jaka jest złożoność czasowa wykonania ciągu m operacji union i find w drzewiastej reprezentacji zbiorów rozłącznych ze zbalansowanym łączeniem?

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

1. 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. Zaprojektuj algorym, który sprawdzi, czy zadana lista jest listą prostą czy listą z cyklem na końcu. Napisz w pseudokodzie swój algorytm. Twój algorytm ma działać w liniowym czasie O(n) i w stałej pamięci O(1).
   Wskazówka: użyj dwóch iteratorów (wskaźników) poruszających się po liście z różną prędkością.
2. Dane jest drzewo binarne. Zaprojektuj algorym, który wyznaczy długość najdłuższej ścieżki (licząc krawędzie) w tym drzewie - ma to byś ścieżka prosta, czyli bez powrotów (przechodząca przez każdy węzeł na ścieżce dokładnie raz). Napisz w pseudokodzie swój algorytm. Oszacuj jego złożoność obliczeniową (czasową i pamięciową).
   Wskazówka: znajdź zależność ostetecznego rozwiązania od rozwiązań mniejszych podzadań.
3. Zaprojektuj strukturę danych, która będzie efektywnie realizowała operacje insert (wstawienie nowego elementu do zbioru) oraz extract-median (usunięcie ze zbioru elementu środkowego co do wielkości, czyli mediany). Opisz dokładnie działanie tych operacji i oszacuj złożoność obliczeniową każdej z nich.
   Wskazówka: podziel zbiór na dwie równe ±1 części.

Zadania z kolokwium III z dnia 27 stycznia 2017 r.

Egzamin

Przykładowe zadania dotyczące grafów jakie mogą się znaleźć na egzaminie

Część testowa.

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. Czym jest składowa silnie spójna w digrafie?
6. Co to jest graf ważony?
7. Co to jest cykl Hamiltona w grafie? Podaj przykład grafu z cyklem Hamiltona.
8. Co to jest cykl Eulera w grafie? Podaj przykład grafu z cyklem Eulera.
9. Jaki jest warunek konieczny i wystarczający aby w grafie prostym istniał cykl Eulera?
10. Ile pamięci potrzeba na zapamiętanie grafu w postaci macierzy sąsiedztwa?
11. Ile czasu potrzeba na wyznaczenie stopnia zadanego wierzchołka w grafie, jeśli jest on zapamiętany w postaci list sąsiadów?
12. Ile krawędzi zawiera graf prosty n-wierzchołkowy, który jest drzewem?
13. Jaką strukturę danych wykorzystuje się do przeglądania grafu wszerz?
14. Co to jest drzewo rozpinające grafu?
15. Na czym polega relaksacja w algorytmie Dijkstry?
16. 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?
17. 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?

Część zadaniowa.

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

Zadania z egzaminu podstawowego z dnia 7 lutego 2017 r.

Zadania z egzaminu poprawkowego z dnia 21 lutego 2017 r.

Ranking

• ćwiczenia i laboratorium w grupie PRz hasło: stat
• ćwiczenia i laboratorium w grupie PSch hasło: stat
• kolokwium I (pdf)
• kolokwium II (pdf)
• kolokwium III (pdf)
• zwolnienia z egzaminu (pdf)
• egzamin podstawowy (pdf)

Instytut Informatyki