Paweł Rzechonek

Zainteresowania zawodowe: programowanie (C++, Java, C#, F#), technologie webowe, szeroko rozumiana algorytmika, metematyka klasyczna.

Wstęp do informatyki
i programowania

data ostatniej modyfikacji

ogłoszenia
14 grudnia 2018 r.
egzamin:
Dla studentów, którzy nie zaliczą egzaminu kolokwiami zostanie przeprowadzony normalny egzamin w sesji egzaminacyjnej w czwartek 7 lutego 2019 r. o godzinie 14:15.
Sala zostanie zarezerwowana w IMat lub IInf.

14 grudnia 2018 r.
laboratorium i konwersatorium w czwartek 20 grudnia:
Zajęć laboratoryjnych 20 grudnia w pracowni nie będzie. Ale będzie lista zadań z F#, które należy zaprogramować na dostępnych komputerach osobistych albo w pracowni na wydziale i odesłać mi rozwiązania na maila.
Zajęcia konwersatoryjne 20 grudnia zostaną odrobione w najbliższym terminie, czyli 3 stycznia.

7 grudnia 2018 r.
drugie kolokwium:
Drugie z trzech kolokwiów odbędzie się w piątek 4 stycznia w trakcie wykładu. Kolokwium będzie przeprowadzone w sali 601 w Instytucie Matematycznym w godzinach 12:15-13:30.
Na kolokwium będzie obowiązywał materiał dotyczący problemów porządkowych (sortowanie, wyszukiwanie binarne, scalanie, podział, itp).
Kolokwium będzie się składało z części testowej (test otwarty, 8-12 pytań) oraz z części zadaniowej (zadania problemowe, 1 zadanie do wyboru spośród 2-4).

26 października 2018 r.
pierwsze kolokwium:
Pierwsze z trzech kolokwiów odbędzie się w piątek 23 listopada w trakcie wykładu. Kolokwium będzie przeprowadzone w sali 601 w Instytucie Matematycznym w godzinach 12:15-13:30.
Na kolokwium będzie obowiązywał materiał od początku semestru do wyrażeń ONP włącznie.
Kolokwium będzie się składało z części testowej (test otwarty, 8-12 pytań) oraz z części zadaniowej (zadania problemowe, 1 zadanie do wyboru spośród 2-4).
Kolokwium jest zaliczone, jeśli uczestnik zdobędzie co najmniej 40% punktów możliwych do uzyskania z części testowej i 40% punktów za zadnie algorytmiczne. Zaliczenie wszystkich kolokwiów w semestrze będzie podstawą do zwolnienia z egzaminu (ostateczną dezycję w sprawie zwolnień podejmę po ostatnim kolokwium).

5 października 2018 r.
odwołane zajęcia w następny piątek:
Zajęcia piątkowe (wykład i konwersatorium/ćwiczenia) w dniu 12 listopada 2018 nie odbędą się. Termin ich odrobienia uzgodnimy na najbliższym wykładzie.

5 października 2018 r.
zmiany w planie zajęć:
Proszę zapoznać się ze zmodyfikowanym planem zajęć. Aktualnie obowiązujący jest na tej stronie. Plan w USOS'ie zostanie poprawiony w poniedziałek.

5 października 2018 r.
punkt informacyjny:
W tym miejscu będą się pojawiać ważne ogłoszenia dotyczące organizacji wszystkich zajęć związanych z tym przedmiotem. Proszę sprawdzać te ogłosznia na bieżąco.
terminarz
wykład:
piątek 15-18 s.601 (Paweł Rzechonek)

konwersatorium:
czwartek 16-17 s.601 (Paweł Rzechonek)

ćwiczenia:
poniedziałek 16-17 s.606 (Paweł Schmidt)
piątek 15-16 s.601 (Paweł Rzechonek)

laboratoria:
poniedziałek 17-19 s.6-IInf (Paweł Schmidt)
czwartek 14-16 s.6-IInf (Paweł Rzechonek)
licznik wejść na stronę

1 dzisiaj
266 w obecnym miesiącu
1071 w bieżącym roku
1071 od powstania strony

o przedmiocie

Wstęp do informatyki i programowania

Celem tych zajęć jest zapoznanie studentów z podstawowymi zagadnieniami algorytmicznymi oraz metodami ich skutecznego rozwiązywania za pomocą programów pisanych w języku C# i F# w środowisku programistycznym Mono Develop pod Linuxem albo Visual Studio na platformie .Net pod Windowsem.

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

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

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

literatura

Literatura podstawowa algorytmiczna
  • P.Wróblewski: Algorytmy, struktury danych i techniki programowania. Wydanie 4. Helion, Gliwice 2009.
  • L.Banachowski, K.Diks, W.Rytter: Algorytmy i struktury danych. Wydanie 5. WNT, Warszawa 2011.
  • T.H.Cormen: Algorytmy bez tajemnic. Helion, Gliwice 2013.
Literatura uzupełniająca algorytmiczna
  • T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein: Wprowadzenie do algorytmów. Nowe wydanie. PWN, Warszawa 2012.
  • S.Dasgupta, C.Papadimitriou, U.Vazirani: Algorytmy. PWN, Warszawa 2012.
  • R.Sedgewick, K.Wayne: Algorytmy. Wydanie 4. Helion, Gliwice 2012.
  • R.Neapolitan, K.Naimipour: Podstawy algorytmów z przykładami w C++. Helion, Gliwice 2004.
  • N.Wirth: Algorytmy + struktury danych = programy. WNT, Warszawa 2004.
  • A.V.Aho, J.E.Hopcroft, J.D.Ullman: Projektowanie i analiza algorytmów. Helion, Gliwice 2003.
  • A.V.Aho, J.E.Hopcroft, J.D.Ullman: Algorytmy i struktury danych. Helion, Gliwice 2003.
  • A.V.Aho, J.D.Ullman: Wykłady z informatyki z przykładami w języku C. Helion, Gliwice 2003.
  • D.Knuth: Sztuka programowania (tom 1, 2, 3). WNT, Warszawa 2001.
  • D.Harel: Rzecz o istocie informatyki. Algorytmika. WNT, Warszawa 2001.
  • J.Bentley: Perełki oprogramowania. WNT, Warszawa 2001.
  • J.Bentley: Więcej perełek oprogramowania.Wyznania programisty. WNT, Warszawa 2007.
Literatura elektroniczna algorytmiczna
Literatura programistyczna
    C#
  • Ian Griffiths, Matthew Adams, Jesse Liberty: C#. Programowanie. Wydanie 6. Wydawnictwo Helion, Gliwice 2012.
  • Andrew Troelsen: Język C# 2010 i platforma .NET 4. Wydawnictwo Helion, Gliwice 2011.
  • Anders Hejlsberg, Mads Torgersen, Scott Wiltamuth, Peter Golde: Język C#. Programowanie. Wydanie 3. Wydawnictwo Helion, Gliwice 2010.
  • F#
  • M.Mysior: Język F# w praktyce. Wydawnictwo EscapeMagazine.pl, Toruń 2012.
  • D.Syme, A.Granicz, A.Cisternino: F# 4.0 dla zaawansowanych. Wydanie 4. Wydawnictwo Helion, Gliwice 2017.
Literatura elektroniczna programistyczna
środowiska programistyczne online

wykład

Zasady zaliczenia przedmiotu

...

Spis wykładów
  1. zadania obliczeniowe i algorytmy
  2. liczby w zapisie binarnym
  3. rekurencja
  4. Odwrotna Notacja Polska
  5. proste sortowanie
  6. sortowanie metodą D&C
  7. listy
  8. drzewa
  9. kolejki priorytetowe
  10. drzewa zrównoważone
  11. kolokwium II
Materiał omawiany na wykładach

5 października 2018 r: zadania obliczeniowe i algorytmy

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

19 października 2018 r: liczby w zapisie binarnym

26 października 2018 r: rekurencja

9 listopada 2018 r: Odwrotna Notacja Polska

16 listopada 2018 r: proste sortowanie, wyszukiwanie binarne

23 listopada 2018 r: kolokwium I

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

30 listopada 2018 r: listy jednokierunkowe

  • Zbiór dynamiczny.
  • Abstrakcyjne struktury danych.
  • Słowniki.
  • Lista jednokierunkowa.
  • Operacje słownikowe na liście jednokierunkowej.
  • slajdy z wykładu: Listy.pdf

7 grudnia 2018 r: drzewa binarne

  • drzewo jako struktura hierarchiczna (rozgałęziona)
  • drzewa jednokierunkowe i dwukierunkowe
  • drzewa z wartownikiem
  • implementacja drzew metodą "na lewo syn na prawo brat"
  • drzewa binarne
  • wysokość drzewa a głębokość węzła/liścia
  • slajdy z wykładu: Drzewa.pdf

14 grudnia 2018 r: kolejki priorytetowe

21 grudnia 2018 r: zrównoważone drzewa BST

4 stycznia 2019 r: kolokwium II

  • Kolokwium II odbędzie się w trakcie wykładu - rozpocznie się o godzinie 12:15 w sali 601 w IMat.
  • Zakres materiału: problemy porządkowe - sortowanie, wyszukiwanie binarne, scalanie, podział, itp.

Wyniki z kolokwiów i egzaminów

ćwiczenia

Zasady zaliczenia przedmiotu
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ń. Po ćwiczeniach wszyscy Studenci (obecni i nieobecni) mają przedstawić pisemne rozwiązanie wskazanego zadania.
Obecności:
Obecność na ćwiczeniach jest obowiązkowa. Za każdą nieobecność 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.
Rozwiązania pisemne:
Za poprawne rozwiązanie pisemne zadania wskazanego na ćwiczeniach 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 1. Oceny wyższe będą wynikały z rankingu i oceny własnej Nauczyciela prowadzącego ćwiczenia.
Spis zajęć ćwiczeniowych
  1. algorytmy i ich złożoność
  2. liczby w zapisie binarnym
  3. rekurencja
  4. ONP
  5. sortowanie 1
  6. sortowanie 2
  7. listy jednokierunkowe
  8. drzewa binarne
  9. kolejki priorytetowe
Zadania realizowane na ćwiczeniach
19 października 2018: algorytmy i ich złożoność (lista 1)
  1. Zakładamy, że program rozwiązujący pewno zadanie potrzebuje f(n) mikrosekund (1 μs = 0.000001 s) dla danych rozmiaru n. Uzupełnij poniższą tabelę dla każdej funkcji f(n) i czasu t, wyliczając największy rozmiar danych n, dla których program wykona obliczenia w czasie t.
    f(n) mikrosekundczas t
    sekundaminutagodzinadzieńmiesiąc
    log(n) 
    √n 
    n 
    n2
    2n
  2. Dane są dwa algorytmy A i B, które rozwiązują ten sam problem P. Dla danych o rozmiarze n algorytm A działa w czasie f(n) a algorytm B w czasie g(n): Dla jakich wartości n bardziej opłaca się stosować algorytm A a dla jakich algorytm B?
    1.   f(n) = n3   oraz   g(n) = 100·n
    2.   f(n) = 10·n2   oraz   g(n) = 2n
    3.   f(n) = 10·n·log(n)   oraz   g(n) = n2
    Odpowiedź uzasadnij.
  3. Przypomnij sobie definicję operatora Ο i uporządkuj poniższe funkcje ze względu na ich rząd wielkości, od asymptotycznie najwolniej rosnącej do asymptotycznie rosnącej najszybciej posługując się relacjami ⊆ i ≡:
    1.   (n+1)0.5
    2.   3·n2+5·n
    3.   2n
    4.   5·n+3
    5.   nn+1
    6.   n0.1
    7.   log2(5·n)
    8.   2·n3+5
    9.   32·n
    10.   √n
    11.   4n+1
    12.   log3(n5)
    13.   (n+1)n
    14.   3n+2
    15.   2·n+7
    Przykład. Początek rozwiązania tego zadania wygląda następująco: Ο(log2(n)) ≡ Ο(log3(n5)) ⊆ Ο(n0.1) ...
  4. Korzystając z definicji operatorów Ο, Ω i Θ udowodnij, że:
    1.   10·n3 ∈ Ο(n5)
    2.   n+1 ∈ Ω(√n)
    3.   5·n2+7·n-3 ∈ Θ(n2)
    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 2018 r: liczby w zapisie binarnym (lista 2)
  1. Zapisz w postaci schematu blokowego:
    1. algorytm generowania binarnej reprezentacji liczby naturalnej, zaczynając od najmniej znaczącego bitu;
    2. algorytm inkrementacji (zwiększenia o 1) albo algorytm dekrementacji (zmniejszenia o 1) zadanej liczby całkowitej zapisanej w postaci U2;
    3. algorytm zmiany znaku w binarnej liczbie całkowitej zapisanej w postaci U2.
  2. Zapisz następujące liczby całkowite w postaci dwójkowej stosując kodowanie ZM, U1 i U2:
    1.   -97
    2.   -341
    3.   -8952
    Uwaga. Użyj najmniejszej możliwej liczby bitów (wliczając w to bit znaku).
  3. Zapisz następujące liczby w postaci binarnej stałopozycyjnej z dokładnością do 6 bitów po kropce dwójkowej stosując kodowanie U2:
    1.   3/49
    2.   211/25
    3.   -12 4/35
    Wskazówka. Wylicz 7 bitów po kropce dwójkowej i dopiero wtedy zaokrąglij wynik do 6 miejsc.
  4. Zapisz następujące liczby w unormowanej postaci binarnej zmiennopozycyjnej (mantysa zawiera się w przedziale [1, 2)):
    1.   1.832482
    2.   -0.00735
    3.   -91573.0
  5. Rozważmy prostą arytmetykę zmiennopozycyjną, w której liczby są zapisywane w jednym bajcie. W arytmetyce tej ma mantysę przeznaczymy 4 bity, na cechę 3 bity i 1 bit na znak. Jeżeli bit znaku jest ustawiony na 1 to liczba jest ujemna, w przeciwnym przypadku jest dodatnia. Cecha niech będzie 3-bitową liczbą ze znankiem zapisana w kodzie uzupełnieniowym. Mantysa po znormalizowaniu jest liczbą z przedziału [1, 2) ale zapisujemy tylko część ułamkową.
    1.   Wylicz, jaka jest najmniejsza wartość ujemna i największa wartość dodatnia, którą można zapisać w takiej arytmetyce.
    2.   Wylicz, jaka jest najmniejsza wartość dodatnia, którą można zapisać w takiej arytmetyce.
    3.   Wylicz, jaka jest największa wartość x w takiej arytmetyce taka, że 1 + x = 1 po zaokrągleniu.
9 listopada 2018 r: rekurencja (lista 3)
  1. Jak za pomocą rekurencji wyrazić operację znajdowania wartości minimalnej dla zadanego skończonego ciągu liczbowego? Można przyjąć, że długość ciągu n jest parametrem funkcji. Napisz w pseudokodzie funkcję rekurencyjną implementującą ten wzór. Jaka będzie złożoność obliczeniowa tej funkcji?
  2. Jak za pomocą rekurencji wyrazić operację znajdowania punktu środkowego (środek ciężkości dla punktów o takiej samej wadze) dla zadanego skończonego ciągu punktów na płaszczyźnie? Można przyjąć, że długość ciągu n jest parametrem funkcji. Napisz w pseudokodzie funkcję rekurencyjną implementującą ten wzór. Jaka będzie złożoność obliczeniowa tej funkcji?
  3. Napisz rekurencyjną definicję dla współczynnika dwumianowego, jako sumę dwóch innych współczynników. Uzasadnij, skąd się wziął ten wzór. Napisz w pseudokodzie funkcję rekurencyjną implementującą ten wzór. Jaka będzie złożoność obliczeniowa tej funkcji? Postaraj się przekształcić wzór rekurencyjny dla współczynnika dwumianowego w taki sposób, aby po prawej stronie znajdował się tylko jeden współczynnik dwumianowy. Czy implementując ten wzór polepszy się złożoność obliczeniowa funkcji?
  4. Napisz rekurencyjną definicję n-tej liczby Catalana. Jaką interpretację mają te liczby? Napisz w pseudokodzie funkcję rekurencyjną implementującą ten wzór.
  5. Napisz rekurencyjną definicję dla funkcji Ackermanna. Wylicz kilka pierwszych wartości dla tej funkcji. Napisz w pseudokodzie funkcję rekurencyjną implementującą ten wzór.
  6. Co oblicza rozszerzony algorytm Euklidesa? Wyjaśnij ideę działania tego algorytmu. Przedstaw obliczenia wykonane dla liczb 1001 i 357.
16 listopada 2018 r: ONP (lista 4)
  1. Kolejka dwukierunkowa to struktura danych podobna do kolejki, pozwalająca jednak na wstawianie i usuwanie elementów na obu jej końcach. Jak zaimplementować taką strukturę na tablicy, aby wszystkie operacje wstawiania i usuwania działały w czasie stałym Ο(1)? Przedstaw ideę rozwiązania. Napisz w pseudokodzie wszystkie cztery procedury.
  2. Znana jest tablicowa implementacja kolejki i stosu. Pokaż, jak zmodyfikować te implementacje, aby można było odwrócić kolejność elementów w tych buforach w stałym czasie Ο(1).
  3. Zapisz w pseudokodzie algorytm obliczania wartości wyrażenia zapisanego w postaci ONP. Jakie struktury danych wykorzystujesz w swoim algorytmie? Czy Twój algorytm jest rekurencyjny czy iteracyjny?
  4. Zapisz w pseudokodzie algorytm przekształcania wyrażenia zapisanego w postaci infiksowej (z funkcjami oprócz operatorów) na postać ONP. Jakie struktury danych wykorzystujesz w swoim algorytmie? Czy Twój algorytm jest rekurencyjny czy iteracyjny?
  5. Zapisz w notacji prefiksowej (notacja polska Łukasiewicza) następujące wyrażenia (z uwzględnieniem priorytetów występujących tam operatorów):
    1. d / 4 * a / c * b
    2. 3 * x - y / 7 + z
    3. 1 + 2 * x ^ 2 ^ (y / 4 - 8)
  6. Wylicz wartość zapisanych w notacji ONP następujących wyrażeń:
    1. 7 5 3 2 + / ^
    2. 2 8 ^ 4 / 6 +
    3. 3 2 17 13 - ^ * 7 5 + / 19 + 11 -
    4. 1 1 1 1 + * 1 1 + 1 + * 1 + 1 + *
    5. 3 2 1 + ^ 1 - 2 / 3 - 2 3 1 + * - 2 ^ 1 - 3 ^
    6. 10 16 14 - ^ 12 18 + - 26 + 28 22 - / 24 + 20 /
  7. Zapisz w notacji ONP następujące wyrażenia:
    1. d / (4 * a / (c * b))
    2. 3 * (x - y) / (7 + z)
    3. (1 + 2 * x) ^ 2 ^ (y / 4 - 8)
23 listopada 2018 r: sortowanie 1 (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 Ai>Aj. Uzasadnij, że algorytm sortowania bąbelkowego na ciągu n-elementowym wykona liniową liczbę zamian elementów Ο(n) (chociaż liczba porównań będzie kwadratowa) w przypadku, gdy liczba inwersji związanych z każdym elementem jest stała Ο(1).
  2. W posortowanym n-elementowym ciągu wykonano losową permutację na pierwszych k elementach. Jak zmodyfikować algorytm sortowania bąbelkowego, aby działał w czasie Ο(k2) dla takich danych? Zapisz go w pseudokodzie.
  3. W posortowanym n-elementowym ciągu dokonano losowej transpozycji pary elementów. Jak zmodyfikować algorytm sortowania bąbelkowego, aby działał w czasie Ο(n) dla takich danych? Zapisz go w pseudokodzie.
  4. 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).
  5. 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?
  6. 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.
30 listopada 2018 r: sortowanie 2 (lista 6)
  1. Podaj przykład danych wejściowych, dla których algorytm sortowania przez wstawianie wykona:
    1. Ο(n) operacji;
    2. Ω(n2) operacji;
    3. Θ(n1.5) operacji.
  2. Posortowany n-elementowy ciąg został pocięty na √n kawałków, każdy o długości √n (zakładamy, że n jest kwadratem jakiejś liczby naturalnej). Kawałki te zostały potem losowo wymieszane (każdy kawałek jest jakby pojedynczym elementem). Jak zaadoptować algorytm sortowania przez wybieranie do takich danych, aby działał on w czasie liniowym Ο(n). Zakładamy, że dane dostarczone do algorytmu znajdują się w tablicy.
  3. W tablicy n-elementowej zapisane są dwa posortowane ciągi: pierwszy ciąg o długości m a za nim drugi ciąg o długości n-m. Opracuj algorytm obliczania liczby inwersji występujących w tym ciągu. Opisz ideę działania algorytmu a potem zapisz go w pseudokodzie. Złożoność czasowa tego algorytmu powinna być liniowa Ο(n).
  4. Jak zmodyfikować algorytm sortowania szybkiego, aby w każdym przypadku głębokość wywołań rekurencyjnych była nie większa niż log(n) dla danych rozmiaru n?
    Wskazówka: jedno z wywołań rekurencyjnych rozwiń w miejscu.
  5. W n-elementowej tablicy A[0...n-1] zapisany jest rosnący ciąg liczb całkowitych (może on rozpoczynać się od liczby ujemnej a kończyć na dodatniej). Opracuj algorytm sprawdzania, czy w tym ciągu znajduje się chociaż jedna taka liczba x, że A[x] = x. Złożoność czasowa tego algorytmu powinna być logarytmiczna O(log n).
  6. Dany jest n-elementowy ciąg liczb całkowitych z zakresu od 0 do n2-1. Zaprojektuj algorytm sortowania, który dla takich danych będzie działał w czasie liniowym O(n).
  7. Danych jest n punktów {p1, p2, ...,pn} leżących w kole jednostkowym, co oznacza że dla każdego punktu pi = (xi, yi) dla i = 1, 2, ...n jest spełniony warunek 0 ≤ xi2 + yi2 ≤ 1 dla i = 1, 2, ...,n. Zakładamy, że punkty w tym kole są rozmieszczone jednostajnie, czyli prawdopodobieństwo zdarzenia, że punkt znajduje się w dowolnym ustalonym obszarze wewnątrz koła jednostkowego jest proporcjonalne do pola tego obszaru. Zaprojektuj algorytm sortujący te punkty według ich odległości od początku układu współrzędnych, działający w średnim przypadku w czasie liniowym O(n).
7 grudnia 2018 r: listy jednokierunkowe (lista 7)
  1. Opracuj rekurencyjny algorytm zlicania elementów na liście jednokierunkowej, które spełniają pewien warunek, na przykład są mniejsze od zadanej wartości x. Opisz ideę rozwiązania tego zadania. Zapisz algorytm w pseudokodzie. Oszacuj czas działania zaprezentowanej metody.
  2. Opracuj rekurencyjny algorytm odwracania listy jednokierunkowej. Opisz ideę rozwiązania tego zadania. Zapisz algorytm w pseudokodzie. Oszacuj czas działania zaprezentowanej metody.
  3. Rozważmy listę jednokierunkową. Opracuj rekurencyjny algorytm usuwania z takiej listy:
    1. n pierwszych elementów;
    2. n ostatnich elementów;
    3. n-ty element (elementy numerujemy od 0).
    Opisz ideę rozwiązania każdego zadania. Zapisz swoje algorytmy w pseudokodzie.
  4. Rozważmy jednokierunkową listę nieuporządkowaną z wartościami, które mogą się często powtarzać. Opracuj rekurencyjny algorytm usuwania zadanej wartości z takiej listy:
    1. usuń pierwsze wystąpienie zadanej wartości na liście;
    2. wszystkie wystąpienia na zadanej wartości liście;
    3. usuń ostatnie wystąpienie zadanej wartości na liście.
    Opisz ideę rozwiązania każdego zadania. Zapisz swoje algorytmy w pseudokodzie.
14 grudnia 2018 r: drzewa binarne (lista 8)
  1. Dane jest drzewo binarne. Opracuj rekurencyjną funkcję, która wyznaczy wysokość tego drzewa. Opisz taki algorytm i zapisz go w pseudokodzie.
  2. Dane jest drzewo binarne. Opracuj rekurencyjną funkcję, która wyznaczy liczbę liści w tym drzewie. Opisz taki algorytm i zapisz go w pseudokodzie.
  3. Dane jest drzewo BST. Jak przekształcić to drzewo w posortowaną listę? Opisz algorytm i zapisz go w pseudokodzie.
  4. Opracuj metodę, która pozwoli wyszukać w drzewie BST węzeł z natępnikiem zadanej wartości (o ile istnieje), czyli najmniejszą wartość w drzewie spośród wartości większych. Opisz taki algorytm i zapisz go w pseudokodzie.
21 grudnia 2018 r: kolejki priorytetowe (lista 9)
  1. Zaprojektuj strukturę danych wykorzystującą kolejki priorytetowe, która będzie efektywnie realizowała operacje insert (wstawienie nowego elementu do zbioru), extract-max (usunięcie ze zbioru elementu największego) oraz extract-kth (usunięcie ze zbioru elementu k-tego co do wielkości dla ustalonego i niezmiennego parametru k, na przykład dla k=2 należy udostępniać wicemaksimum). Operacje te mają być efektywne. Opisz dokładnie działanie tych operacji i przeanalizuj złożoność obliczeniową każdej z nich.
  2. Zaprojektuj strukturę danych wykorzystującą kolejki priorytetowe, która będzie efektywnie realizowała operacje insert (wstawienie nowego elementu do zbioru) oraz extract-median (usunięcie ze zbioru elementu środkowego co do wielkości, czyli mediany). Operacje te mają być efektywne. Opisz dokładnie działanie tych operacji i przeanalizuj złożoność obliczeniową każdej z nich.

konwersatorium

Omawiane zagadnienia
4 października 2018: spotkanie organizacyjne
  • środowisko programistyczne Mono Develop
  • platforma uruchomieniowa .NET
11 października 2018: podstawy języka C#
  • struktura prostego programu w języku C#
  • typy podstawowe i referencyjne
  • literały
  • zmienne
  • przypisanie
  • inicjalizacja
  • stałe
  • komunikacja z użytkownikiem za pomocą Console
  • przekształcanie danych napisowych na liczbowe za pomocą Convert
  • operatory i wyrażenia
18 października 2018: instrukcje sterujące
  • instrukcja blokowa
  • zasięg zmiennych w bloku
  • instrukcja warunkowa if-else
  • instrukcja wyboru switch-case
  • instrukcje pętli while i do-while
  • instrukcja pętli for
  • instrukcja przerwania pętli break
  • instrukcja przyspieszenia pętli continue
25 października 2018: funkcje
  • definicja funkcji statycznej
  • wywołanie funkcji
  • argumenty przekazywane do funkcji
  • wynik funkcji zwracany instrukcją return
  • przeciążanie funkcji
  • lokalny zasięg zmiennych w funkcji
  • funkcje rekurencyjne
8 listopada 2018: tablice
  • typ tablicowy
  • tworzenie tablic operatorem new
  • inicjalizacja tablic listą wartości
  • operator indeksowania
  • rozmiar tablicy - właściwość Length
  • przekazywanie tablic do funkcji
  • tablice dwuwymiarowe (następne zajęcia)
22 listopada 2018: przygotowanie do kolokwium
  • powtórzenie materiału przed kolokwium
29 listopada 2018: wstęp do programowania funkcyjnego
  • cechy programowania funkcyjnego
  • podstawowe typy danych
  • definicje obiektów i funkcji za pomocą let
  • formatowane wypisywanie wartości na standardowe wyjście
6 grudnia 2018: przetwarzanie list
  • zapis listy
  • głowa i ogon listy
  • sprawdzanie warunków za pomocą if
  • definicje funkcji rekurencyjnych za pomocą let rec
  • dopasowywanie przypadków za pomocą match with
13 grudnia 2018: ...
  • ...
20 grudnia 2018: ...
  • ...

laboratorium

Zasady zaliczenia przedmiotu
Ogólnie:
W semestrze będzie opublikowanych na tej stronie kilkanaście zadań programistycznych. Część zadań będzie realizowana na laboratoriach a część będzie do zrealizowania w domu.
Obecności:
Obecność na laboratoriach jest obowiązkowa. Aby zaliczyć laboratorium Student musi uczestniczyć w co najmniej 60% zajęć.
Zadania programistyczne:
Za każde zaprogramowane zadanie w trakcie laboratorium można uzyskać do 4 punktów (za zadanie przesłane po zajęciach do 2 punktów). Za każde zaprogramowane zadanie domowe można uzyskać do 2 punktów (za zadanie przesłane po terminie do 1 punkta).
Terminy:
Zadania do zaprogramowania będą ogłaszane w tygodniu poprzedzającym termin ich realizacji. Zadania należy oddawać w wyznaczonym terminie wysyłając kody źródłowe na maila do prowadzącego zajęcia laboratoryjne. Spóźnienia nie będą tolerowane, za wyjątkiem uzasadnionych sytuacji życiowych: choroba potwierdzona zwolnieniem lekarskim, wezwanie do Sądu, itp.
Plagiaty:
Zadań programistycznych nie wolno kopiować. Studentów, których złapię na wysyłaniu izomorficznych rozwiązań po raz pierwszy otrzymają po -20 punktów karnych. Druga próba kopiowania rozwiązań to -40 punktów karnych i notatka do Dziekana. Trzecia próba oszustwa zakończy się niezaliczeniem przedmiotu i wnioskiem do Wydziałowej Komisji Dyscyplinarnej. Uwaga: mam narzędzie do automatycznego sprawdzania podobieństw programów, aby skuteczniej wyszukiwać potencjalnych przestępców!
Oceny zaliczeniowe:
Aby zaliczyć laboratorium na ocenę dostateczną Student potrzebuje zgromadzić do końca semestru co najmniej 40% możliwych do zdobycia punktów. Na ocenę bardzo dobrą Student potrzebuje zgromadzić 80% możliwych do zdobycia punktów. Oceny pośrednie pozostaną w liniowej zależności od przedstawionych wymagań granicznych.
Zadania laboratoryjne
4 października 2018: spotkanie organizacyjne

Zadady zaliczenia laboratorium.

Zapoznanie ze środowiskiem programistycznym Mono Develop.

11 października 2018: komunikacja z użytkownikiem za pomocą konsoli, konwersje napisowo-liczbowe

Zadanie 1 (pokazowe).

Napisz program, który obliczy kwadrat zadanej liczby rzeczywistej x.

Zadanie 2.

Napisz program, który obliczy pierwiastek zadanej dodatniej liczby rzeczywistej x.

18 października 2018: operatory i wyrażenia

Zadanie 1 (pokazowe).

Napisz program, który rozwiąże równanie liniowe z jedną niewiadomą ax+b = 0.

Zadanie 2.

Napisz program, który wyznaczy wartości liczb a i b, jeśli znana jest suma a+b i różnica a-b.

Zadanie 3.

Napisz program, który wyznaczy liczbę miejsc zerowych równania kwadratowego ax2+bx+c = 0.

25 października 2018: instrukcje sterujące, funkcje

Zadanie 1 (pokazowe).

Napisz program, który obliczy wartość bezwzględną zadanej liczby rzeczywistej x. Obliczenie Abs(x) zrealizuj za pomocą funkcji.

Zadanie 2.

Napisz program, który wyznaczy znak zadanej liczby rzeczywistej x. Obliczenie Sgn(x) zrealizuj za pomocą funkcji.

Zadanie 3.

Napisz program, który sprawdzi czy podany rok r jest przestępny. Sprawdzenie przestępności Przestępny(r) zrealizuj za pomocą funkcji.

8 listopada 2018: rekurencja

Zadanie 1 (pokazowe).

Napisz program, który obliczy silnię n! dla zadanej liczby naturalnej n. Obliczenie n! zrealizuj za pomocą funkcji rekurencyjnej.

Zadanie 2a.

Napisz program, który obliczy n-ty wyraz ciągu Fibonacciego Fn dla zadanej liczby naturalnej n. Obliczenie Fn zrealizuj za pomocą funkcji rekurencyjnej.

Zadanie 2b.

Napisz program, który obliczy n-ty wyraz ciągu Lucasa Ln dla zadanej liczby naturalnej n. Obliczenie Ln zrealizuj za pomocą funkcji rekurencyjnej.

Zadanie 3.

Napisz program, który obliczy współczynnik dwumianowy (nk) dla zadanych wartości naturalnych 0 ≤ k ≤ n. Obliczenie (nk) zrealizuj za pomocą funkcji rekurencyjnej.

Zadanie 4.

Napisz program, który wyznaczy największy wspólny dzielnik NWD(a, b) dla zadanych wartości naturalnych a i b. Obliczenie NWD(a, b) zrealizuj za pomocą funkcji rekurencyjnej, implementującej algorytm Euklidesa.

22 listopada 2018: rekurencja

Zadanie 1 (pokazowe).

Napisz program, który utworzy n-elementową tablicę liczb całkowitych, a następnie wygeneruje i wpisze do niej losowe wartości ze zbioru {2, ..., 5}. Liczbę n podaj poprzez standardowe wejście. Program ma wypisać wszystkie wylosowane i wpisane do tablicy wartości. Na koniec napisz i uruchom funkcję, która policzy średnią arytmetyczną liczb w tablicy.

Zadanie 2.

Napisz program, który utworzy n-elementową tablicę liczb całkowitych, a następnie wczyta do niej dane ze standardowego wejścia. Program ma wypisać wszystkie wczytane do tablicy liczby od końca.

Zadanie 3.

Napisz program, który utworzy n-elementową tablicę liczb rzeczywistych, a następnie wygeneruje i wpisze do niej losowe wartości ze zakresu [0, 100). Liczbę n podaj poprzez standardowe wejście. Program ma wypisać minimalną i maksymalną wartość wpisaną do tablicy. Do wyznaczenia wartości minimalnej i maksymalnej zdefiniuj odpowiednie funkcje.

Zadanie 4 (domowe).

Napisz program, który wczyta linię tekstu ze standardowego wejścia. Następnie z przeczytanej linii przekopiuj do tablicy znaków tylko litery i cyfry (powinieneś najpierw policzyć ile ich jest w tekście). Na koniec napisz i uruchom funkcję, która sprawdzi czy napis ten zawierał palindrom.

29 listopada 2018: sortowanie

Zadanie 1 (pokazowe).

Napisz program, który posortuje bąbelkowo tablicę liczb. Program ma w trakcie sortowania prezentować stan tablicy (po każdym przesiewaniu).

Dane do programu wczytaj z klawiatury.

Zadanie 2a.

Zaimplementuj algorytm sortowania bąbelkowego ze sprawdzaniem liczby wykonanych zamian po każdym przesiewaniu. Jeżli liczba zamian wynosiła 0, to algorytm można przerwać.

Dane do programu wczytaj z klawiatury.

Zadanie 2b.

Zaimplementuj algorytm sortowania bąbelkowego ze sprawdzaniem miejsca ostatniej zamiany. Za każdym razem granicę przesiewania ustaw przed ostatnio zamienionym elementem.

Dane do programu wygeneruj za pomocą generatora liczb pseudolosowych.

Zadanie 3.

Zaimplementuj algorytm wyszukiwania binarnego, tak aby wyliczał ile jest wartości mniejszej od podanej w posortowanym ciągu. Program ma najpierw posortować dane a potem odpowiadać ile jest wartości mnieszych od zadanej przez użytkownika. Proces podawania liczby i jej wyszukiwania w posortowanym ciągu możesz zapętlić w nieskończoność.

Dane do programu wygeneruj za pomocą generatora liczb pseudolosowych.

6 grudnia 2018: F# (1)

Zrób zadania z listy 1 (autor: P.Schmidt).

13 grudnia 2018: F# (2)

Zrób zadania z listy 2 (autor: P.Schmidt).

20 grudnia 2018: F# (3)