Paweł Rzechonek

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

Instytut Informatyki
Uniwersytetu Wrocławskiego

data ostatniej modyfikacji

ogłoszenia
4 października 2017 r.
pierwsze ćwiczenia:
W pierwszym tygodniu nauki ćwiczenia nie odbywają się. Pierwsze ćwiczenia zaplanowałem dopiero na przyszły tydzień: 9-13 października 2017 r.

4 października 2017 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:
środa 15-18 s.A (Paweł Rzechonek)

konwersatorium:
środa 18-19 s.A (Paweł Rzechonek)

ćwiczenia:
piątek 12-13 s.604 (Paweł Rzechonek)
piątek 14-15 s.604 (Paweł Schmidt)

laboratoria:
środa 10-12 s.411 (Krzysztof Tabisz)
piątek 10-12 s.410 (Paweł Rzechonek)
piątek 10-12 s.411 (Paweł Schmidt)
piątek 12-14 s.411 (Paweł Schmidt)
licznik wejść na stronę

7 dzisiaj
328 w obecnym miesiącu
328 w bieżącym roku
328 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++ w środowisku programistycznym Code::Blocks a także w językach C# i F# na platformie .Net.

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

Wymagane przygotowanie
  • Dobra znajomość matematyki na poziomie szkoły średniej.
  • Umiejętność 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 podstawowa programistyczna
    C++
  • S.Rao: C++. Dla każdego. Wydanie 7. Helion, Gliwice 2014.
  • S.Prata: Język C++. Szkoła programowania. Wydanie 6. Helion, Gliwice 2013.
  • K.Kuczmarski: Od zera do gier kodera. WNT, Warszawa 2004.
  • J.Grębosz: Symfonia C++ (tom 1, 2, 3). Oficyna Kallimach, Kraków 2002.
  • J.Grębosz: Pasja C++ (tom 1, 2). Oficyna Kallimach, Kraków 2003.
  • 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.
  • F#
  • D.Syme, A.Granicz, A.Cisternino: F# 4.0 dla zaawansowanych. Wydanie 4. Wydawnictwo Helion, Gliwice 2017.
Literatura elektroniczna programistyczna

wykład

Zasady zaliczenia przedmiotu

...

Spis wykładów
  1. zadania obliczeniowe i algorytmy
  2. liczby w zapisie binarnym
  3. rekurencja
Materiał omawiany na wykładach
4 października 2017 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].
11 października 2017 r: liczby w zapisie binarnym

18 października 2017 r: rekuremcja

konwersatorium

ćwiczenia

Zasady zaliczenia przedmiotu

...

Spis zajęć ćwiczeniowych
  1. algorytmy i ich złożoność
  2. liczby w zapisie binarnym
  3. rekurencja
Zadania realizowane na ćwiczeniach
13 października 2017 r: 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.
20 października 2017 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 postaci binarnej zmiennopozycyjnej w obiekcie typu single (4 bajty) zgodnie ze standardem IEEE-754:
    1.   1.832482
    2.   -0.00735
    3.   -93573.0
    Uwaga. Wyznacz bit znaku, bity cechy (z uwzględnieniem BIAS) i mantysy (kodujemy tylko część ułamkową po normalizacji).
  5. Wylicz, jaka jest najmniejsza i największa wartość dodatnia, którą można zapisać w notacji zmiennopozycyjnej w obiekcie typu double (8 bajtów) zgodnie ze standardem IEEE-754.
27 października 2017 r: rekurencja (lista 3)
  1. Zapisz rekurencyjne wzory dla:
    1. ciągu arytmetycznego;
    2. ciągu geometrycznego.
    Napisz w pseudokodzie funkcje rekurencyjne implementujące te wzory. Jaka będzie złożoność obliczeniowa tych 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 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.
  6. Co oblicza rozszerzony algorytm Euklidesa? Wyjaśnij ideę jego działania i uzasadnij poprawność.

laboratorium

Zasady zaliczenia przedmiotu
Ogólnie:
W semestrze będzie opublikowanych na themisie i na tej stronie kilkanaście list z zadaniami programistycznymi. 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).
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
  1. ...