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

Data ostatniej modyfikacji dokumentu (wip.phtml) to piątek 7 lutego 2020 roku (o godzinie 22:32).

data ostatniej modyfikacji

ogłoszenia
7 lutego 2020 r.
zaliczenie egzaminu na podstawie kolokwiów:
Wyliczone oceny na podstawie kolokwiów można znaleźć tutaj (należy odczytać ostatnią kolumnę korekta).

4 lutego 2020 r.
wyniki trzeciego kolokwium:
Wyniki trzeciego kolokwium można znaleźć tutaj.

4 lutego 2020 r.
egzamin:
Egzamin z tego przedmiotu odbędzie się we wtorek 18 lutego w sali 5 w Instytucie Informatyki w godzinach 8:15-10:45.
Egzamin będzie się składał z części testowej (test otwarty, 20 pytań) oraz z części zadaniowej (zadania problemowe, 2 zadania do wyboru spośród 4-6).
Egzamin jest zaliczony, jeśli uczestnik zdobędzie co najmniej 40% punktów możliwych do uzyskania z części testowej i 40% punktów za zadnia algorytmiczne. (ostateczną dezycję w sprawie zwolnień podejmę po ostatnim kolokwium).

17 stycznia 2020 r.
trzecie kolokwium:
Trzecie z trzech kolokwiów odbędzie się w piątek 31 stycznia w trakcie wykładu. Kolokwium będzie przeprowadzone w sali A w Instytucie Matematycznym w godzinach 15:15-16:30.
Na kolokwium będzie obowiązywał materiał omawiany na wykładach poświęconych listom, drzewom, kopcom, językom formalnym, gramatykom, wyrażeniom regularnym.
Kolokwium będzie się składało z części testowej (test otwarty, 10 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).

17 stycznia 2020 r.
wyniki drugiego kolokwium:
Wyniki drugiego kolokwium można znaleźć tutaj.

6 grudnia 2019 r.
drugie kolokwium:
Drugie z trzech kolokwiów odbędzie się w piątek 13 grudnia w trakcie wykładu. Kolokwium będzie przeprowadzone w sali A w Instytucie Matematycznym w godzinach 15:15-16:30.
Na kolokwium będzie obowiązywał materiał omawiany na wykładach poświęconych sortowaniu, buforom (stosy, kolejki), listom oraz ONP.
Kolokwium będzie się składało z części testowej (test otwarty, 10 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).

29 listopada 2019 r.
wyniki pierwszego kolokwium:
Wyniki pierwszego kolokwium można znaleźć tutaj.

8 listopada 2019 r.
pierwsze kolokwium:
Pierwsze z trzech kolokwiów odbędzie się w piątek 22 listopada w trakcie wykładu. Kolokwium będzie przeprowadzone w sali A w Instytucie Matematycznym w godzinach 15:15-16:30.
Na kolokwium będzie obowiązywał materiał omawiany na wykładzie od początku semestru algorytmu Hore'a włącznie.
Kolokwium będzie się składało z części testowej (test otwarty, 10 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).

25 października 2019 r.
zajęcia w środę 30 października:
Zajęcia z wykładowcą w środę 30 października 2019 r. nie odbędą się i zostaną przeniesione na termin późniejszy, o którym poinformuję Państwa na wykładzie.

1 października 2019 r.
pierwsze ćwiczenia:
W pierwszym tygodniu nauki ćwiczenia nie odbywają się. Pierwsze zajęcia ćwiczeniowe zaplanowałem dopiero na przyszły tydzień: 7 października 2019 r.

1 października 2019 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.A-IMat (Paweł Rzechonek)

konwersatorium:
piątek 14-15 s.A-IMat (Paweł Rzechonek)

ćwiczenia:
poniedziałek 12-13 s.6-IInf (Paweł Schmidt)
piątek 13-14 s.A-IMat (Paweł Rzechonek)

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

1 dzisiaj
5 w obecnym miesiącu
955 w bieżącym roku
2478 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 proceduralnego z elementami obiektowości oraz podstawowe elementy z biblioteki standardowej; następnie język programowania F# na poziomie programowania funkcyjnego. Krótkie i proste przykłady powinny wspomóc naukę programowania w tych językach.

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
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 10 pytań otwartych, na które trzeba krótko i precyzyjnie odpowiedzieć. Część zadaniowa będzie polegała na rozwiązaniu jednego wybranego 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 co najmniej dwa 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.
Spis wykładów
  1. zadania obliczeniowe i algorytmy
  2. rekurencja
  3. dziel i zwyciężaj
  4. liczby w zapisie binarnym
  5. sortowanie i wyszukiwanie binarne
  6. kolokwium I
  7. zbiory dynamiczne - bufory i listy
  8. Odwrotna Notacja Polska
  9. kolokwium II
  10. słowniki - drzewa BST
  11. kolejki priorytetowe - kopce
  12. automaty skończone, języki formalne i gramatyki
  13. wyrażenia regularne, notacje BNF i EBNF
  14. kolokwium III
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

11 października 2019 r: rekurencja

18 października 2019 r: dziel i zwyciężaj

25 października 2019 r: liczby w zapisie binarnym

8 listopada 2019 r: sortowanie i wyszukiwanie binarne

22 listopada 2019 r: kolokwium I

  • Kolokwium I odbędzie się w trakcie wykładu - rozpocznie się o godzinie 15:15 w sali A w IMat.
  • Zakres materiału: złożoność obliczeniowa, algorytmy rekurencyjne, reprezentacja liczb w komputerze, sortowanie, wyszukiwanie binarne.

29 listopada 2019 r: bufory, listy

  • tablica - podstawowa struktura danych
  • tablica dynamiczna - dopasowuje się do rozmiaru danych
  • stos - bufor LIFO
  • kolejka - bufor FIFO
  • implementacja stosu i kolejki na tablicy
  • zbiór dynamiczny
  • abstrakcyjne struktury danych
  • słowniki
  • lista jednokierunkowa
  • operacje słownikowe na liście jednokierunkowej
  • implementacja stosu i kolejki na liście
  • slajdy z wykładu: Bufory.pdf, Listy.pdf

6 grudnia 2019 r: Odwrotna Notacja Polska

13 grudnia 2019 r: kolokwium II

  • Kolokwium II odbędzie się w trakcie wykładu - rozpocznie się o godzinie 15:15 w sali A w IMat.
  • Zakres materiału: sortowanie, wyszukiwanie binarne, stosy, kolejki, listy, ONP.

20 grudnia 2019 r: drzewa binarne

10 stycznia 2020 r: kolejki priorytetowe

17 stycznia 2020 r: automaty skończone, gramatyki regularne, gramatyki bezkontekstowe

24 stycznia 2020 r: wyrażenia regularne, notacje BNF i EBNF

31 stycznia 2020 r: kolokwium III

  • Kolokwium III odbędzie się w trakcie wykładu - rozpocznie się o godzinie 15:15 w sali A w IMat.
  • Zakres materiału: listy, drzewa, kopce, języki formalne, gramatyki, wyrażenia regularne.

ćwiczenia

Zasady zaliczenia przedmiotu
Ogólnie:
W semestrze będzie opublikowanych na tej stronie kilkanaście list z zadaniami teoretycznymi. Na ćwiczeniach Studenci powinni 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. rekurencja
  3. dziel i zwyciężaj
  4. liczby w zapisie binarnym
  5. sortowanie
  6. wyszukiwanie binarne
  7. listy
  8. ONP
  9. drzewa
  10. kopce
  11. automaty skończone, gramatyki regularne, gramatyki bezkontekstowe
  12. wyrażenia regularne, notacja BNF i EBNF
Zadania realizowane na ćwiczeniach
11 października 2019: 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.
18 października 2019 r: rekurencja (lista 2)
  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 zbioru punktów na płaszczyźnie? Można przyjąć, że wielkość zbioru 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.
25 października 2019 r: dziel i zwyciężaj (lista 3)
  1. Zmodyfikuj algorytm Karatsuby 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. Dana jest funkcja f(x) ciągła na zadanym przedziale [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.
    Wskazówka: popatrz na wartość funkcji w środku przedziału.
  3. Dany jest n-elementowy ciąg pewnych wartośći (wartości te możemy rozróżniać między sobą, czyli określać, że są równe bądź różne, ale nie możemy porównywać za pomocą relacji ≤). Powiemy, że ciąg ma element dominujący, gdy ponad połowa elementów tego ciągu ma tą samą wartość. Opracuj efektywny algorytm rozstrzygający, czy zadany ciąg ma element dominujący, a jeśli tak, to jaka jest jego wartość.
    Wskazówka: podziel ciąg na dwie równe części i rozwiąż podproblemy.
  4. Dana jest liczba naturalna n. Opracuj efektywny algorytm znajdowania największej potęki 2, która będzie nie większa od n.
    Uwaga: postaraj się znaleźć algorytm istotnie lepszy od działającego w czasie O(log n).
8 listopada 2019 r: liczby w zapisie binarnym (lista 4)
  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.   -91
    2.   -347
    3.   -8976
    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.
22, 29 listopada 2019 r: sortowanie (lista 5)
  1. 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 + n) dla takich danych? Zapisz go w pseudokodzie.
  2. 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.
  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. Podaj przykład danych wejściowych, dla których algorytm sortowania przez wstawianie wykona:
    1. Ο(n) operacji;
    2. Ω(n2) operacji;
    3. Θ(n1.5) operacji.
29 listopada 2019 r: wyszukiwanie binarne (lista 6)
  1. 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.
  2. 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 nie jest stabilny:
    1.   algorytm sortowania przez wybieranie
    2.   algorytm Lomuta dla podziału danych względem piwota
  3. 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).
  4. 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).
  5. 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 podzielonego prze π. Zaprojektuj algorytm sortujący te punkty według ich odległości od początku układu współrzędnych, działający w oczekiwanym przypadku w czasie liniowym O(n).
6 grudnia 2019 r: listy (lista 7)
  1. Rozważmy listę nieuporządkowaną z wartościami, które mogą się często powtarzać. Opracuj algorytm usuwania zadanej wartości z takiej listy:
    1. usuń pierwsze wystąpienie zadanej wartości na liście;
    2. wszystkie wystąpienia na zadanej wartości liście;
    3. usuń ostatnie wystąpienie zadanej wartości na liście;
    Opisz ideę rozwiązania każdego zadania. Zapisz swoje algorytmy w pseudokodzie.
  2. Opracuj algorytm odwracania listy jednokierunkowej. Metoda ta powinna działać w miejscu w liniowym czasie. Zapisz swój algorytm w pseudokodzie.
    Czy odwrócenie listy dwukierunkowej jest zadaniem prostszym?
  3. Jak wskazać element środkowy na liście dwykierunkowej? Zapisz swój algorytm w pseudokodzie.
    Czy wskazanie elementu środkowego na liście jednokierunkowej jest zadaniem trudniejszym?
  4. Może (ale nie musi) tak się zdarzyć, że w ostatnim węźle listy będziemy mieli odniesienie do jakiegoś węzeła w środku tej samej listy (może to być również pierwszy albo ostatni węzeł w tej liście). Wówczas na końcu takiej lity powstanie cykl. Wymyśl metodę, która sprawdzi, czy zadana lista jest listą prostą czy listą z cyklem na końcu. Opracuj algorytm, który rozwiązuje ten problem w liniowym czasie i zapisz go w pseudokodzie.
    Jak można zmodyfikować przedstawiony algorytm, aby dodatkowo wyliczał on długość całej listy?
13 grudnia 2019 r: ONP (lista 8)
  1. Zapisz w pseudokodzie algorytm obliczania wartości wyrażenia zapisanego w postaci ONP. Twój algorytm powinien wykrywać błędne stany w trakcie obliczeń (brak argumentów, zbyt dużo wyników). Jakie struktury danych wykorzystujesz w swoim algorytmie? Czy Twój algorytm jest rekurencyjny czy iteracyjny?
  2. 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?
  3. Zapisz w notacji prefiksowej (notacja polska Łukasiewicza) i postfiksowej (Odwrotna Notacja Polska) następujące wyrażenia (z uwzględnieniem priorytetów występujących tam operatorów):
    1. d / (4 * (a - 1) + 2) / c * (b + 3)
    2. 3 * x - y / 7 + z - 1
    3. 1 + 9 * x ^ 3 ^ (y / 7 - 5)
  4. 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 /
  5. Zapisz w notacji ONP następujące wyrażenia:
    1. d / (4 * a / (c * b + 2) - 1)
    2. 3 * (x - y) / (4 + z) ^ 7
    3. (2 * x - 1) ^ 3 ^ (y / 4 + 7)
10 stycznia 2020 r: drzewa (lista 9)
  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.
17 stycznia 2020 r: kopce (lista 10)
  1. Jak wstawić kopiec trynarny (albo ogólnie d-arny) do tablicy? Jak wyliczyć w takim przypadku indeks lewego syna i rodzica?
  2. Jak zaimplementować drzewo dwumianowe k-tego stopnia w tablicy 2k 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 znajduje się węzeł, jego stopień oraz indeksy ojca, brata i kolejnych synów.
  3. Zaprojektuj strukturę danych wykorzystującą kolejki priorytetowe, która będzie efektywnie realizowała operacje insert (wstawienie nowego elementu do zbioru) oraz extract-median (usunięcie ze zbioru elementu środkowego co do wielkości, czyli mediany). Operacje te mają być efektywne. Opisz dokładnie działanie tych operacji i przeanalizuj złożoność obliczeniową każdej z nich.
24 stycznia 2020 r: automaty skończone, gramatyki regularne i bezkontekstowe (lista 11)
  1. Zaprojektuj automat skończony akceptujący liczby zapisane w systemie dwójkowym, które są podzielne przez 5. Przykłady: 101, 110001, 10100101.
  2. 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.
  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. są niepuste i nie ma obok siebie dwóch takich samych liter;
    3. są niepustym ciągiem takich samych liter (na przykład b, aa, cccc);
    4. zaczynają się prefiksem bab i kończą sufiksem aba (na przykład babcccaba, babababa, baba).
  4. 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. zawierają podsłowo aba;
    2. nie zawierają podsłowa aa;
    3. zawierają podsłowo aba lub nie zawierają podsłowa aa;
    4. zawierają podsłowo aba i nie zawierają podsłowa aa.
  5. Zdefiniuj gramatykę regularną, która będzie definiowała języki zawierające słowa nad alfabetem Σ = {a, b}, w których:
    1. występuje podsłowo baba;
    2. nie występuje podsłowo baba;
    3. pierwsza i ostatnia litera są takie same
    4. liczba liter a jest równa liczbie liter b modulo 2.
  6. Zdefiniuj gramatykę bezkontekstową, która będzie definiowała języki zawierające:
    1. poprawnie rozstawione nawiasy;
    2. słowa nieparzystej długości, które są palindromami nad alfabetem Σ = {a, b}.
  7. Zdefiniuj gramatykę bezkontekstową generującą język L:
    1. {anb2n+1 : n > 0};
    2. {anbk : n ≥ 2k ≥ 0};
    3. {anbkcn+k : n, k > 0};
    4. {anbmckdl : n + m = k + l}.
31 stycznia 2020 r: wyrażenia regularne, notacja BNF i EBNF (lista 12)
  1. Napisz wyrażenie regularne, do którego dopasuje się:
    1. poprawnie zapisana liczba całkowita dziesiętna (uwzględnij zero i liczby ujemne z minusem na początku);
    2. poprawnie zapisana liczba zmiennopozycyjna z kropką dziesiętną (na przykład 123.45, -0.987, 0.00001);
    3. poprawnie zapisana godzina z dokładnością do minut albo sekund (na przykład 14:51, 00:15, 17:03:59);
    4. 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.
  2. Zdefiniuj zestaw reguł produkcji w notacji BNF, które opisują:
    1. łańcuch znakowy w języku C# - ciąg znaków ujęty w znaki cudzysłowia "..."; w łańcuchu może wystąpić sekwencja specjalna rozpoczynająca się od odwrotnego ukośnika (na przykład \n, \t, \\, \', \", \0);
    2. liczbę zmiennoprzecinkową, która może posiadać część ułamnową po krpoce dziesiętnej (na przykład 2, -3.7, .5), i która może posiadać współczynnik skalujący oznaczony literą E lub e (na przykład -3e8, 5.1E-9, -.7e10).
  3. Zdefiniuj zestaw reguł produkcji w notacji EBNF, które opisują:
    1. liczbę zespoloną zapisaną w postaci sumy/różnicy częsci rzeczywistej i zespolonej oznaczonej literą I lub i (na przykład 2.4+6.8i, -7i, .5-2i, 1+.9i, -0.4-i);
    2. wyrażenie logiczne budeowane ze stałych logicznych T (prawda) i F (fałsz), identyfikatorami zmiennych (niepuste ciągi małych liter), operatorami (negacja, koniunkcja, alternatywa, implikacja, równoważność) oraz nawiasy okrągłe do grupowania podwyrażeń.

konwersatorium

Omawiane zagadnienia
4 października 2019: spotkanie organizacyjne
  • środowisko programistyczne Mono Develop
  • platforma uruchomieniowa .NET
11 października 2019: 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 2019: 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 skracania pętli continue
25 października 2019: 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
  • zgłasanie wyjątków w funkcjach
8 listopada 2019: 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
  • przeglądanie tablic pętlą foreach
15 listopada 2019: programowanie obiektowe - abstrakcja i hermetyzacja
  • definiowanie klas
  • tworzenie obiektów operatorem new
  • inicjalizacja obiektów za pomocą konstruktorów
  • stan obiektu (pola) i funkcjonalność (metody)
  • ukrywanie pól - pola prywatne opatrzone deklaratorem private
  • wystawianie interfejsu - metody publiczne opatrzone deklaratorem public
  • pola i metody statyczne w klasie opatrzone deklaratorem static
  • referencja this
  • nadpisywanie funkcji ToString()
  • nadpisywanie funkcji Equals()
22 listopada 2019: programowanie obiektowe - dziedziczenie i polimorfizm
  • definiowanie hierarchii klas
  • klasa Object stojąca na szczycie hierarchii klas
  • konstruowanie obiektów w przypadku dziedziczenia
  • wywołanie konstruktora klasy bazowej za pomocą base
  • udostępnianie pól w klasach potomnych za pomocą deklaratora protected
  • pola tylko do odczytu z deklaratorem readonly
  • nadpisywanie metod i pól
  • dostęp do składowych odziedziczonych za pomocą wskaźnika base
  • metody wirtualne z deklaratore virtual
  • nadpisywanie metod wirtualnych z deklaratore override
  • wywoływanie metod zwykłych i wirtualnych
  • blokowanie dziedziczenia deklaratorem sealed
  • metody i klasy abstarkcyjne z deklaratorem abstract
  • nadpisywanie metod abstrakcyjnych z użyciem deklaratora override
29 listopada 2019: kolokwium
  • omówienie zadań z kolokwium I
6 grudnia 2019: 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
13 grudnia 2019: funkcje
  • definicja funkcji
  • wywołanie funkcji
  • specyfikowanie typów argumentów i wyniku w funkcji
  • definicje funkcji rekurencyjnych za pomocą let rec
20 grudnia 2019: przetwarzanie list
  • lista jako sekwencyjna struktura danych
  • definicja listy
  • głowa i ogon listy
  • sprawdzanie warunków za pomocą if
  • dopasowywanie przypadków za pomocą match with
10 stycznia 2020: kolokwium
  • omówienie zadań z kolokwium II
17 stycznia 2020: przetwarzanie drzew BST
  • definicja drzewa BST
  • wyszukiwanie w drzewach BST
  • rotacje w drzewach BST
  • przywracanie zrównoważenia w drzewach AVL
  • przywracanie zrównoważenia w drzewach R-B
24 stycznia 2020: przetwarzanie kopców
  • definicja kopca binarnego
  • przesiewanie w kopcu binarnym
  • definicja kopca dwumianowego
  • łączenie kopców dwumianowych
  • definicja kopca lewicowego
  • łączenie kopców lewicowych

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
7 października 2019: spotkanie organizacyjne

Zadady zaliczenia laboratorium.

Zapoznanie ze środowiskiem programistycznym MonoDevelop.

Zadanie 1 (pokazowe).
Przeanalizuj program powitalny hello world w MonoDevelop albo na repl.it, skompiluj go i uruchom.

Zadanie 2.
Napisz program, który obliczy kwadrat i sześcian zadanej liczby rzeczywistej. Użyj metody Convert.ToDouble() do konwersji wczytanego łańcucha na liczbę zmiennopozycyjną.

Zadanie 3.
Napisz program, który obliczy pierwiastek z zadanej dodatniej liczby rzeczywistej. Użyj metody Math.Sqrt() do policzenia pierwiastka.

Zadanie 4.
Napisz program, który obliczy wartości liczb rzeczywistych a i b dla podanej sumy a+b i różnicy a-b.

14 października 2019: instrukcja warunkowa if-else oraz instrukcja wyboru switch-case

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. Zgłoś wyjątek ArgumentException, gdy użytkownik wprowadzi rok ≤0.

Zadanie 4.
Napisz program, który rozwiąże równanie kwadratowe z jedną niewiadomą ax2+bx+c = 0. Wypisz wszystkie rozwiązania rzeczywiste takiego równania dla podanych parametrów rzeczywistych a, b i c. Zgłoś wyjątek ArgumentException, gdy użytkownik wprowadzi parametr a &eq;0.

Zadanie 5 (dodatkowe).
Każdy rok w kalendarzu chińskim ma swojego patrona - jest 12 zwierząt, które są cyklicznie patronami kolejnych lat: szczur, bawół, tygrys, królik, smok, wąż, koń, baran, małpa, kogut, pies, świnia (patronem 2019 roku jest właśnie świnia). Napisz program, który dla podanego roku r wyznaczy i wypisze patrona tego roku. Zgłoś wyjątek ArgumentException, gdy użytkownik wprowadzi rok ≤0. Użyj instrukcji wyboru switch-case.

21 października 2019: instrukcje pętli while, do-while, for

Zadanie 1 (pokazowe).
Napisz program, który dla podanej liczby całkowitej n wypisze n gwiazdek w wierszu. Gdy n będzie miało wartość ujemną albo zero, to nie wypisuj żadnej gwiazdki. Użyj pętli while.

Zadanie 2.
Napisz program, który dla podanej liczby całkowitej n wypisze kolejne liczby całkowite, zaczynając od 0 a kończąc na wartości n. Gdy n będzie miało wartość ujemną, to wypisany ciąg ma być malejący (na przykład dla n = -3 należy wypisać: 0 -1 -2 -3). Użyj pętli do-while.

Zadanie 3.
Napisz program, który podanej liczby całkowitej n wypisze i sformatuje tabliczkę mnożenia o rozmiarze n × n. Gdy n będzie ≤2, to przyjmij, że n = 2. Gdy n będzie ≥30, to przyjmij, że n = 30. Użyj zagnieżdżonych pętli for.

Zadanie 4.
Napisz program, który podanej liczby całkowitej n wypisze kolejno jej podzielniki naturalne (zacznij od 1 a zakończ na |n|). Gdy n będzie miało wartość 0, to wypisz tylko liczbę 0.

Zadanie 5 (dodatkowe).
Napisz program, który podanych liczb całkowitych a i b wypisze kolejno wszytkie liczby parzyste z przedziału [a, b]. Zgłoś wyjątek ArgumentException, gdy a > b. Użyj pętli for.

Zadanie 6 (dodatkowe).
Napisz program, który podanych liczb całkowitych a, b oraz k wypisze kolejno wszytkie liczby z przedziału [a, b], które są podzielne przez k. Zgłoś wyjątek ArgumentException, gdy a > b lub k = 0. Użyj pętli for.

28 października 2019: funkcje rekurencyjne

Zadanie 1 (pokazowe).
Napisz program, który podanej liczby naturalnej n policzy i wypisze n! (silnia). Zdefiniuj funkcję rekurencyjną do policzenia silni.

Zadanie 2.
Napisz program, który podanej liczby naturalnej n policzy i wypisze sumę kwadratów kolejnych liczb 12 + 22 + ... + n2. Zdefiniuj funkcję rekurencyjną, która to policzy.

Zadanie 3.
Napisz program, który podanej liczby naturalnej n policzy i wypisze n-tą liczbę Fibonacciego (F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2 dla n ≥ 2). Zdefiniuj funkcję rekurencyjną do policzenia n-tej liczby Fibonacciego.

Zadanie 4.
Napisz program, który podanych liczb naturalnych n i k policzy i wypisze współczynnik dwumianowy (nk). Zdefiniuj funkcję rekurencyjną do policzenia współczynnika dwumianowego.

Zadanie 5 (dodatkowe).
Napisz program, który podanej liczby naturalnej n policzy i wypisze n-tą liczbę Lucasa (L0 = 2, L1 = 1, Ln = Ln-1 + Ln-2 dla n ≥ 2). Zdefiniuj funkcję rekurencyjną do policzenia n-tej liczby Lucasa.

Zadanie 6 (dodatkowe).
Napisz program, który podanych liczb naturalnych m i n policzy i wypisze wartość funkcji Ackermanna A(m, n) (A(0, n) = n+1 gdy m = 0, A(m, 0) = A(m-1, 0) gdy m > 0 i n = 0, A(m, n) = A(m-1, A(m, n-1)) gdy m > 0 i n > 0). Zdefiniuj funkcję rekurencyjną do policzenia funkcji Ackermanna.

4 listopada 2019: tablice

Zadanie 1 (pokazowe).

Napisz program, który najpierw wczyta ze standardowego wejścia liczbę naturalną n a potem utworzy n-elementową tablicę liczb całkowitych i wczyta do niej wartości podane przez użytkownika. Program ma wypisać wszystkie wczytane do tablicy liczby od końca, pomijając liczby ujemne i zera.

Zadanie 2.

Napisz program, który najpierw wczyta ze standardowego wejścia liczbę naturalną n a potem utworzy n-elementową tablicę liczb całkowitych i wpisze do niej losowe wartości ze zbioru {2, ..., 5}. Program ma wypisać wszystkie wylosowane i wpisane do tablicy wartości.

Na koniec program ma wypisać średnią arytmetyczną, odchylenie standardowe i wariancję dla liczb w tablicy. Do wyznaczenia średniej, odchylenia i wariancji zdefiniuj osobne funkcje.

Zadanie 3.

Napisz program, który najpierw wczyta ze standardowego wejścia liczbę naturalną n a potem utworzy n-elementową tablicę liczb rzeczywistych i wpisze do niej losowe wartości ze zakresu [0, 100).

Na koniec program ma wypisać minimalną i maksymalną wartość wpisaną do tablicy. Do wyznaczenia wartości minimalnej i maksymalnej zdefiniuj osobne funkcje.

Zadanie 4.

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 program ma sprawdzić czy podany przez użytkownika napis jest palindromem. Do sprawdzenia czy dane w tablicy tworzą palindrom zdefiniuj osobną funkcję.

18 listopada 2019: klasy i obiekty

Zadanie 1 (pokazowe).

Zdefiniuj klasę reprezentującą punkt na płaszczyźnie. Klasa Punkt powinna zawierać dwa niepubliczne pola typu double do pamiętania współrzędnych. W klasie Punkt zdefuniuj konstruktory - jeden bezargumentowy a drugi nadający konkretne wartości współrzędnym punktu. Wyposaż tą klasę w gettery umożliwiające odczytanie współrzędnych oraz nadpisz metodę ToString() zwracającą tekstową reprezentację współrzędnych punktu.

Zadanie 2.

Zdefiniuj klasę reprezentującą odcinek na płaszczyźnie. Klasa Odcinek powinna być reprezentowana za pomocą dwóch różnych punktów na płaszczyźnie. W klasie Odcinek zdefuniuj konstruktor, który sprawdzi czy podane punkty końcowe nie są identyczne (jeśli tak, to należy zgłosić wyjątek). Wyposaż tą klasę w gettery udostępniające końce odcinka oraz nadpisz metodę ToString().

Zadanie 3.

Zdefiniuj klasę reprezentującą trójkąt na płaszczyźnie. Klasa Trojkat powinna być reprezentowana za pomocą trzech różnych i niewspółliniowych punktów na płaszczyźnie. W klasie Trojkat zdefuniuj konstruktor, który sprawdzi czy podane punkty końcowe nie są niewspółliniowe (jeśli tak, to należy zgłosić wyjątek). Wyposaż tą klasę w gettery udostępniające rogi trójkąta oraz nadpisz metodę ToString().

Zadanie 4 (dodatkowe).

W klasach reprezentujących punkt, odcinek i trójkąt na płaszczyźnie zaimplementuj metody dokonujące trzech zasadnich przekształceń:

  1. Przesuń(Wektor w) - przesunięcie (translacja), polegające na przemieszczeniu wszystkich punktów figury o tę samą odległość w ustalonym kierunku (za pomocą obiektu klasy Wektor);
  2. Obróć(Punkt p, double kąt) - obrót wokół ustalonego punktu wszystkich punktów figury o zadany kąt;
  3. Odbij(Prosta p) - symetria (odbicie) względem osi wszystkich punktów figury (za pomocą obiektu klasy Prosta).
Klasy Wektor i Prosta zdefiniuj tak, aby obiekty tych klas były niemodyfikowalne. Klasa Wektor ma zawierać dwa publiczne i finalne pola dx i dy typu double do pamiętania kierunku przesunięcia; w klasie tej umieść statyczną metodę do składania wektorów i mnożenia przez skalar. Natomiast klasa Prosta ma reprezentować prostą na płaszczyźnie w postaci ogólnej Ax + By + C = 0, a więc w klasie tej powinny być zadeklarowane trzy publiczne i finalne pola a, b i c do zapamiętania tych współczynników; w klasie tej umieść statyczne metody do sprawdzania, czy proste są równoległe oraz czy są prostopadłe.

25 listopada 2019: dziedziczenie i polimorfizm

Zadanie 1 (pokazowe).

Zdefiniuj klasę abstrakcyjną reprezentującą wyrażenie arytmetyczne działające na liczbach rzeczywistych. Klasa Wyrażenie powinna zawierać abstrakcyjną metodę oblicz() do obliczania wartości wyrażenia. Klasa ta będzie bazą dla potomnych klas realizujących określone zadania obliczeniowe w wyrażeniu.

Zadanie 2.

Zdefiniuj klasy operandów dziedziczące po wyrażeniu: Liczba reprezentująca liczbę zmiennopozycyjną oraz Stała reprezentująca nazwaną stałą (liczby π, e, φ, itp).

W klasie Stała zdefiniuj statyczne pole finalne do przechowywania zbioru wszystlich stałych (pary identyfikator--liczba). Do przechowywania stałych wykorzystaj kolekcję Dictionary. Odczytywanie wartości stałej ma polegać na zidentyfikowaniu pary w tym zbiorze i odczytaniu wartości związanej z kluczem.

W klasach tych nadpisz metody ToString(), które będą zwracać napis reprezentujący operancy.

Zadanie 3.

Zdefiniuj klasy operatorów dziedziczące po wyrażeniu, reprezentujące operacje arytmetyczne dodawania, odejmowania, mnożenia i dzielenia oraz jednoargumentowe operacje zmiany znaku na przeciwny i odwrotności. Klasy te powinny być tak zaprojektowane, aby można z nich było zbudować drzewo wyrażenia: argumentami operatorów mają być wyrażenia.

W klasach tych nadpisz metody ToString(), które będą zwracać napis reprezentujący wyrażenia używające tych operatorów (dopisz niezbędne nawiasy).

2 grudnia 2019: F# (1)

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

9 grudnia 2019: F# (2)

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

16 grudnia 2019: F# (2 ciąg dalszy)

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

7 stycznia 2020: F# (3)

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

20 stycznia 2020: F# (4)

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

27 stycznia 2020: F# (4 ciąg dalszy)

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

3 lutego 2020: F# (5)

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

Ranking

Ranking osiągnięć na laboratorium w grupie PRz.

Ranking osiągnięć na ćwiczeniach w grupie PRz.