Paweł Rzechonek

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

C++17 i STL
zaawansowane techniki

data ostatniej modyfikacji

Data ostatniej modyfikacji dokumentu (cpp.phtml) to czwartek 28 stycznia 2021 roku (o godzinie 23:23).

ogłoszenia
7 stycznia 2021 r.
lista XIII na laboratorium:
Lista XIII będzie ostatnią listą zadań w tym semestrze. Ostatecznie będzie więc 12 list laboratoryjnych (pomijając przeterminowaną listę XI). Maksymalna liczba punktów do zdobycia za te zadania wyniesie 120, progiem zaliczeniowym będzie ostatecznie 60 punktów. Jeśli będą potrzebne zadania ratunkowe, to zostaną dopisane.

7 stycznia 2021 r.
lista XI na laboratorium:
Lista XI została opublikowana po terminie. Nie będzie więc punktowana. Entuzjastów zachęcam jednak do poeksperymentowania z tymi zadaniami - lokalizacja jest tylko w teorii prosta a w praktyce nastręcza wielu problemów.

8 października 2020 r.
pierwsze laboratoria:
W pierwszym tygodniu nauki laboratoria nie odbywają się. Pierwsze zajęcia laboratoryjne odbędą się w przyszłym tygodniu 15 października 2020 r.

1 października 2020 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ę czytać te ogłosznia na bieżąco.
terminarz
wykład:
czwartek 16-18 (Paweł Rzechonek)

laboratoria:
środa 12-14 (Marek Szykuła)
czwartek 14-16 (Marek Szykuła)
czwartek 18-20 (Paweł Rzechonek)
licznik wejść na stronę

2 dzisiaj
17 w obecnym miesiącu
523 w bieżącym roku
2158 od powstania strony

o przedmiocie

Kurs C++17 i STL

C++17 to najnowsza wersja języka C++. Język C++ prawdza się, gdy chcemy zapewnić wysoką wydajność programu. Język ten jest stale rozwijany a kolejne jego specyfikacje, czyli C++11, C++14 i C++17, przyniosły wiele udogodnień. Aby w pełni wykorzystać potencjał języka C++ należy go używać wraz z biblioteką standardową STL. C++ wraz z STL to doskonałe narzędzie do implementowania oprogramowania wysokiej jakości.

Wymagane przygotowanie
  •   Umiejętność programowania obiektowego w języku C++98.
  •   Podstawowa znajomość algorytmiki.
  •   Umiejętność czytania dokumentacji technicznej w języku angielskim.
Cel kursu
  •   Nauka programowania w języku C++17.
  •   Poznanie obszernych fragmentów biblioteki standardowej STL.

literatura

Podrędznik podstawowy
  •   N.M.Josuttis: C++. Biblioteka standardowa. Podręcznik programisty. Wydanie 2. Wydawnictwo Helion, Gliwice 2014.
Literatura papierowa
  •   B.Stroustrup: Język C++. Kompendium wiedzy. Wydanie 4. Wydawnictwo Helion, Gliwice 2014.
  •   J.Galowicz: C++17 STL. Receptury. Wydawnictwo Helion, Gliwice 2018.
Literatura elektroniczna

laboratorium

Zasady zaliczenia przedmiotu
Ogólnie:
W semestrze będzie opublikowanych (na tej stronie) kilkanaście prostych list z zadaniami do zaprogramowania. Za każde samodzielnie zaprogramowane zadanie/zadania i oddane w terminie można będzie dostać do 10 punktów (chociaż zadania będą różnej trudności).
Terminy:
Zadania do zaprogramowania będą ogłaszane w tygodniu poprzedzającym termin ich realizacji. Zadania należy oddawać w wyznaczonym terminie w trakcie trwania pracowni. Spóźnienia nie będą tolerowane, za wyjątkiem uzasadnionych sytuacji życiowych: choroba potwierdzona zwolnieniem lekarskim, wezwanie do Sądu, itp.
Prezentacje:
Programy należy prezentować osobiście w czasie pracowni - z każdym studentem chciałbym indywidualnie omówić jego rozwiązanie oraz wskazać wady i braki w programie. Po pracowni program należy mi przekazać (będę jeszcze robić weryfikację antyplagiatową) na SKOS. W trakcie prezentacji programu trzeba się liczyć z pytamiami dotyczącymi zadania: metoda rozwiązania, zastosowane konstrukcje językowe, wykorzystane technologie, itp.
Rozwiązania:
Kody źródłowe własnych programów należy zapisywać na SKOS, ponieważ tylko wtedy rozwiązania zadań będą podlegały weryfikacji autorskiej i ocenie. Jeśli student nie mógł uczestniczyć w zajęciach z powodu awarii połączenia internetowego, to oprócz programu ma przekazać sprawozdanie z realizacji zadania (co zostało zaprogramowane i w którym miejścu w pliku źródłowym oraz czego nie udało się osiągnąć).
Oceny:
Aby zaliczyć laboratorium na ocenę dostateczną trzeba do końca semestru zdobyć 50% z wszystkich możliwych do uzyskania punktów; na ocenę bardzo dobrą trzeba będzie zgromadzić 90% punktów; oceny pośrednie pozostją w liniowej zależności od przedstawionych wymagań granicznych.
Zadania laboratoryjne
  1. 14, 15 października 2020: nowe elementy języka C++
  2. Zadanie 1 (1 pkt).
    Sprawdź, czy w stosowanym przez Ciebie kompilatorze (co najmniej c++17) działają trójznaki (ang. trigraphs), takie jak na przykład ??- co tłumaczy się na znak tyldy ˜, itp. Co zrobić, aby kompilator właściwie zinterpretował występujące w programie trójznaki?
    Zadanie 2 (1 pkt).
    Wypisz na standardowym wyjściu std::out surowy łańcuch znaków (ang. raw string) zawierający:
    1. adres naszego Instytutu (w pierwszej linii pełną nazwę Instytutu, w drugiej ulicę z numerem, w trzeciej kod pocztowy i miasto);
    2. ścieżkę bezwzględną do katalogu z programami użytkowymi w systemie Windows;
    3. różne sekwencje znaków cudzysłowia i nawiasów okrągłych (a w szczególności sekwencję )").
    Zadanie 3 (2 pkt).
    Stwórz alias dla typu będącego zbiorem std::set<> łańcuchów znakowych. Następnie zadeklaruj i zainicjalizuj taki zbiór używając jednolitej inicjalizacji. Na koniec przejdź po tym zbiorze pętlą for dla zakresów (ang. range-based for-each loop)) dedukując automatycznie typ elementów zbioru; wypisz w pętli wszystkie łańcuchy na standardowym wyjściu std::out).
    Zadanie 4 (2 pkt).
    Zdefiniuj silnie stypizowany typ wyliczeniowy dla kilku wybranych imion męskich i żeńskich, którego elementy będa typu uint_16. Następnie zdefiniuj funkcję, która jako argumenty przyjmuje komunikat typu string i imię odbiorcy zdefiniowanego wcześniej typu wyliczeniowego (funkcja może wypisywać komunikat personalnie skierowany do wskazanej osoby używając instrukcji switch-case).
    Zadanie 5 (1 pkt).
    Zdefiniuj funkcję rekurencyjną, która będzie wyznaczała n-tą liczbę Lucasa. Funkcja ta ma przyjmować argument typu uint32_t, i która będzie automatycznie dedukować typ wyniku.
    Zadanie 6 (2 pkt).
    Napisz program, który dla podanych współczynników równania kwadratowego wyliczy wyróżnik tego równania (często oznaczany symbolem Δ) i w zależności od jego wartości wypisze miejsca zerowe. Użyj do tego celu instrukcji warunkowej if-else z lokalnym inicjalizatorem dla wyróżnika.
    Zadanie 7 (1 pkt).
    Napisz program, który dla podanej daty wypisze ją z nazwą miesiąca (na przykład: 15 października 2020). Użyj do tego celu instrukcji wyboru switch-case z lokalnym inicjalizatorem miesiąca w dacie.
  3. 21, 22 października 2020: sprytne wskaźniki
  4. Zadanie 1 (4 pkt).
    Zdefiniuj prostą klasę zawierającą licznik typu uint64_t, początkowo ustawiony na wartość 1. W kasie tej, oprócz innych funkcjonalności, umieść wirtualny destruktor, który wypisze komunikat ze stanem licznika na standardowym wyjściu dla błędów.
    Następnie stwórz n-elementową tablicę takich liczników i opakuj ją wskaźnikiem unique_ptr.
    Napisz też funkcję, która wywoła się rekurencyjnie m razy z argumentem będącym wskaźnikiem na taką tablicę (wskaźnik unique_ptr przekaż przez wartość). W i-tym wywołaniu funkcja ta ma losowo wybrane elementy zwiększyć o i-tą z kolei liczbę naturalną.
    Na koniec wywołaj tą funkcję, a po jej wywołaniu wypisz wartości wszystkich n liczników w tablicy. Parametry n i m możesz ustalić arbitralnie.
    Zadanie 2 (4 pkt).
    Zdefiniuj klasę opakowującą plik tekstowy line_writer. Obiekt takiej klasy ma przetrzymywać wskaźnik/referencję do strumienia plikowego ofstream. Zadaniem obiektów tej klasy będzie pisanie do pliku wiersz po wierszu. Czy klasa ta powinna zamykać strumień w destruktorze?
    Dalej w programie głównym stwórz kilka wskaźników shared_ptr odnoszących się do tego samego obiektu plikowego. Niech każdy fragment programu posiadający taki własny wskaźnik zapisze w tym pliku swoje dane. Plik powinien zostać zamknięty dopiero, gdy wszystkie sprytne wskaźniki zostaną zlikwidowane.
    Zadanie 3 (2 pkt).
    Przetestuj, kiedy wskaźnik weak_ptr będzie wskazywać na obiekt w pamięci, a kiedy stanie się wskaźnikiem wiszącym (po zwolnieniu zasobu przez wskaźnik macierzysty shared_ptr).
  5. 28, 29 października 2020: czasomierze
  6. Zadanie 1 (1 pkt).
    Wypisz najmniejszą i największą wartość jaką można zapisać w typie long long int. Na ilu bitach jest ta liczba zapisywana i ile to będzie cyfr dziesiętnych?
    Zadanie 2 (1 pkt).
    Jaka jest najbliższa 0 liczba dodatnia dla typów float i double? Jakie są maksymalne wartości zapisywane w tych typach? Jaka jest różnica pomiędzy 1 a najmniejszą liczbą >1 w tych typach?
    Zadanie 3 (2 pkt).
    Zdefiniuj początkowe liczby harmoniczne posługując się statyczną arytmetyką liczb wymiernych z wykorzystaniem szablonu ratio. Jaką największą liczbę harmoniczną udało Ci się zdefiniować?
    Zadanie 4 (3 pkt).
    Zdefinuj szablon funkcji, które przeniesie wartość ze wskazanego obiektu do innego obiektu. Uwzględnij dwa aspekty: po pierwsze obiekt źródłowy może być zadany przez wartość/referencję albo przez wskaźnik (rozróżnij te dwa przypadki za pomocą cechy typowej is_pointer), a po drugie obiekt docelowy ma być wskazany przez referencję niekoniecznie tego samego typu (ustal możliwość konwersji za pomocą cechy typowej is_convertible)
    Zadanie 5 (3 pkt).
    Stwórz macierze o rozmiarach odpowiednio 100×100, 1000×1000 i 10000×10000 i wypełnij je losowymi wartościami z zakrsu od 0.5 do 2.0. Następnie podnieś do kwadratu każdą z tych macierzy mierząc czas wykonania tych operacji za pomocą obiektu duration. Dla małych macierzy powtórz operację wielokrotnie a potem zmierzony czas podziel przez tą wielokrotność. Do pomiaru czasu użyj czasomierzy opartych na zegarze high_resolution_clock.
  7. 4, 5 listopada 2020: funktory
  8. Zadanie 1 (5 pkt).
    Stwórz w swoim programie trzy zbiory danych różnego typu vector<double>, list<string> i set<int>. Wypełnij te kontenery przypadkowymi wartościami (możesz losować albo arbitralnie coś wpisać). Następnie na zbiorach tych wykonaj pewne obliczenia z użyciem zdefiniowanych przez ciebie funktorów (obiekty funkcyjne albo lambdy):
    1. Wypisz wszystkie wartości z zadanego zakresu (większe od a i mniejsze od b).
    2. Wypisz co k-tą wartość zaczynając od pozycji p-tej.
    3. Wyznacz średnią arytmetyczną (dotyczy kolekcji z liczbami).
    4. Wyznacz element minimalny i maksymalny (zwróć parę iteratorów).
    5. Wyznacz sumę/konkatenację wszystkich elementów.
    Do każdego zadania zdefiniuj obiekt funkcyjny (ze stanem wewnętrznym) i użyj go w pętli for-each.
    Zadanie 3 (2 pkt).
    Zaimplementuj funktor compose_f_gx_hy realizujący złożenie dwuargumentowe f(g(x), h(x)). Podaj przykład jego użycia.
    Zadanie 4 (3 pkt).
    Zaimplementuj funktor do składania funkcji poprzez wykonywanie ich po kolei. Funkcja po_kolei(f1, f2)(x) powinna wykonać najpierw f1(x) a potem f2(x). Wartości zwracane przez te funkcje mają być ignorowane. Funkcja po_kolei() powinna zwracać taki funktor, aby możliwe było dalsze składanie, na przykład po_kolei(po_kolei(f1, f2), f3)(x).
  9. 18, 19 listopada 2020: kolekcje
  10. Zadanie 1 (4 pkt).
    Zaprogramuj algorytm stacji rozrządowej Dijkstry, który przekształca wyrażenie arytmetyczne z postaci infiksowej z nawiasami do postaci postfiksowej bez nawiasów (Odwrotna Notacja Polska). Wykorzystaj do tego celu kolekcje standardowe.
    W swoim algorytmie najpierw podziel wejściowe wyrażenie arytmetyczne na kolejkę/listę leksemów. Wynikiem działania procedury przekształcającej ma być kolejka/lista symboli.
    Zadanie 2 (6 pkt).
    Zaprogramuj strukturę danych do przetrzymywania ważonego grafu dynamicznego w postaci list sąsiadów. Wspomniana dynamiczność oznacza, że można dodawać nowe a także usuwać istniejące wierzchołki w grafie. Co się tyczy krawędzi, krawędzie można dodawać i usuwać, a także zmieniać ich wagę. Wykorzystaj do tego celu kolekcje standardowe.
    Każdy wierzchołek grafu niech oprócz kolejnego numeru będzie miał przypisaną nazwę. Do wierzchołków grafu chcielibyśmy odwoływać się zarówno poprzez jego numer jak i nazwę.
    Zaprogramuj też w grafie algorytm sprawdzania czy istnieje ścieżka pomiędzy zadanymi wierzchołkami.
  11. 18, 19 listopada 2020: algorytmy
  12. Zadanie 1 (3 pkt).
    Pojedyncza osoba jest opisana za pomocą iminia, nazwiska, wieku, wagi i wzrostu (zdfiniuj klasę reprezentującą osobę person). Dane o 11 osobach są zgromadzone w deku deque<person>. Wykonaj po kolei następujące czynności:
    1. posortuj osoby według współczynnika BMI (funkją porównującą niech będzie lambda); posortowaną grupę osób wypisz na standardowym wyjściu;
    2. osoby odchudziły się na obozie sportowym i straciły 10% swojej pierwotnej wagi (funkją modyfikującą niech będzie lambda); zmodyfikowaną grupę osób wypisz na standardowym wyjściu;
    3. podziel osoby na dwie grupy: ciężkie z wagą powyżej 100[kg] i lekkie z wagą niewiększą niż 100[kg] (użyj lambdy jako predykatu); wypisz grupę osób po podziale na standardowym wyjściu;
    4. ustaw osobę o środkowym w tej populacji wzroście na pozycji 5 (pośrodku listy); wypisz grupę osób po takiej modyfikacji na standardowym wyjściu;
    5. losowo poprzestawiaj między sobą pierwsze 5 osób a potem ostatnie 5 osób; wypisz grupę osób po takiej modyfikacji na standardowym wyjściu;
    6. wypisz osobę najstarszą i najmłodszą na standardowym wyjściu (nie korzystaj z sortowania danych).
    Zadanie 2 (2 pkt).
    Pojedynczy punkt jest opisany za pomocą współrzędnych, koloru w postaci RGB i nazwy (zdfiniuj klasę reprezentującą punkt point). Dane o 17 kolorowych punktach na płaszczyźnie są zgromadzone w liście list<point>. Wykonaj po kolei następujące czynności:
    1. usuń z listy wszystkie punkty, których nazwy są dłuższe niż 5 znaków; wypisz pozostałe na liście punkty;
    2. policz ile jest punktów leżących w I, II, III i IV ćwiartce układu współrzędnych;
    3. posortuj punkty ze względu na ich jasność (luminancja koloru RGB jest określona wzorem 0.3⋅R + 0.59⋅G + 0.11⋅B); wypisz punkty po posortowaniu;
    4. policz ile jest ciemnych punktów, dla których luminancja ma warość poniżej 64; prznieś te punty do innej listy i wypisz je.
    Zadanie 3 (2 pkt).
    Napisz funkcję, która zwróci najczęściej pojawiający się element w zbiorze danych oraz liczbę jego wystąpień. Dane to liczby całkowite z pewnego wąskiego zakresu umieszczone w wektorze vector<int>. Jeśli więcej niż jeden element pojawia się pojawia się taką samą maksymalną liczbę razy, to funkcja powinna zwrócić wszystkie je wszystkie - na przykład dla danych {1, 1, 3, 5, 8, 9, 5, 8, 8, 5} powinny zostać zwrócone dwie pary {5, 3} oraz {8, 3} (pierwsza pozycja w parze to wartość a druga to liczba wystąpień).
    Zadanie 4 (2 pkt).
    Napisz progam, który oblicza i wyświetla histogram zawierający częstość występowania liter alfabetu angielskiego (bez rozróżniania małych i dużych liter) w zadanym tekście. Tekst pobierz z pliku tekstowego, którego nazwę przekażesz do progamu poprzez argumenty wywołania. Częstość występowania danej litery jest zdefiniowana jako proporcja liczby wystąpień tej litery w stosunku do wszstkich liter w tekście (częstość musi być określona na podstawie liczby liter a nie rozmiaru tekstu).
    Zadanie 5 (1 pkt).
    Napisz funkcję, która wygeneruje wszystkie możliwe permutacje podanego napisu string.
  13. 25, 26 listopada 2020: liczby pseudolosowe
  14. Zadanie 1 (2 pkt).
    Zdefiniuj szablon funkcji, który losowo spermutuje zadaną tablicę obiektów. Każda permutacja ma być jednakowo prawdopodobna.
    Zadanie 2 (4 pkt).
    Napisz program, który wygeneruje 1000 losowych liczb z rozkładem:
    1. jednostajnym, używając uniform_real_distribution;
    2. dwumianowym, używając binomial_distribution;
    3. normalnym, używając normal_distribution.
    Wygenerowane liczby zapisz w pliku .csv (dla każdego rozkładu w osobnym pliku). Zrób w arkuszu kalkulacyjnym wykresy dla danych wygenerowanych w taki sposób, aby sprawdzić poprawność zastosowanego rozkładu prawdopodobieństwa.
    Z formatem pliku CSV można się zapoznać na przykład na Wikipedii:
          https://pl.wikipedia.org/wiki/CSV_(format_pliku)
          https://en.wikipedia.org/wiki/Comma-separated_values
    Zadanie 3 (4 pkt).
    Napisz program, który wygeneruje losowy tekst złożony tylko z małych liter alfabetu angielskiego i spacji (bez znaków interpunkcyjnych). Długość tekstu oraz nazwę pliku .txt do zapisania tekstu podaj poprzez argumenty wywołania progamu. Litery w tym tekście mają się pojawiać z częstotliwością zgodną ze statystyką podaną w tabelce (rozkład taki musisz więc samodzielnie zdefiniować/zaprogramować). Kolejne słowa w tekście mają być odzielone pojedynczymi spacjami. Każde słowo ma mieć losową długość z zakresu od 1 do 12 liter a długości te mają być wybierane zgodnie z rozkładem dwumianowym.
  15. 2, 3 grudnia 20: liczby zespolone
  16. Zadanie 1 (4 pkt).
    Zdefiniuj funkcje pracujące na liczbach zespolonych, które będą wyliczać wartość:
    1. funkcji gamma Eulera $\Gamma(z) = \frac{1}{z} \prod_{n=1}^{\infty} \frac{(1+\frac{1}{n})^z}{1+\frac{z}{n}}$
    2. i odwrotności tej funkcji $\frac{1}{\Gamma(z)} = ze^{\gamma z} \prod_{n=1}^{\infty} \left(\left(1+\frac{z}{n}\right)e^{-\frac{z}{n}}\right)$.
    Symbol $\gamma$ reprezentuje stałą Eulera-Mascheroniego wynoszącą około 0.5772156649. Funkcje te mają liczyć wartość funkcji w zadanym punkcie zespolonym z określoną dokładnością (liczba iteracji).
    Zadanie 2 (6 pkt).
    Zdefiniuj funkcję pracującą na liczbach zespolonych, które będą wyliczać wartość funkcji dzeta Riemanna $\zeta(z) = \sum_{n = 1}^{\infty} \left(\frac{1}{n}\right)^z$. Szereg ten jest zbieżny dla takich $z$, których część rzeczywista jest $>1$. Funkcja ta ma liczyć wartość funkcji w zadanym punkcie zespolonym z określoną dokładnością (liczba iteracji).
    Policz i stablicuj wartości tej funkcji na prostej krytycznej $\Re(z) = 0.5$ z hipotezy Riemanna (musisz użyć innego wzoru). Wygenerowane liczby zapisz w pliku .csv (w osobnych kolumnach części rzeczywiste i urojone). Następnie zrób w arkuszu kalkulacyjnym podwójny wykres dla danych wygenerowanych w taki sposób (nałożone na siebie wykresy dla części rzeczywistych i urojonych).
    Z formatem pliku CSV można się zapoznać na przykład na Wikipedii:
        https://pl.wikipedia.org/wiki/CSV_(format_pliku)
        https://en.wikipedia.org/wiki/Comma-separated_values
  17. 9, 10 grudnia 2020: wyrażenia regularne
  18. Zadanie 1 (1 pkt).
    Zdefiniuj wyrażenie regularne do rozpoznawania prawidłowo zapisanej godziny. Zapis godziny to liczba godzin (0-23) i liczba minut (0-59) oddzielone dwukropkiem (obydwie liczby zapisane za pomoca dwóch cyfr); opcjonalnie w godzinie mogą sie pojawić sekundy (0-59).
    Przetestuj wyrażenie na danych wprowadzonych ze standardowego wejścia.
    Zadanie 2 (2 pkt).
    Zdefiniuj wyrażenie regularne do rozpoznawania prawidłowo zapisanej daty. Zapis daty składa się z numeru dnia w miesiącu (1-31), numeru miesiąca(1-12) i roku; liczby te mają być od siebie oddzielone minusem (numer dnia i miesiąca zapisane za pomoca dwóch cyfr a rok za pomocą czterech). Zadbaj o sprawdzanie górnych ograniczeń na liczbę dni w poszczególnych miesiącach (nie musisz sprawdzać przestępności roku ale byłoby to mile widziane).
    Przetestuj wyrażenie na danych wprowadzonych ze standardowego wejścia.
    Zadanie 3 (2 pkt).
    Zdefiniuj wyrażenie regularne do rozpoznawania prawidłowo zapisanej nazwy miejscowości w Polsce. Zapis nazwy miejscowości to ciąg słów, gdzie każde słowo rozpoczyna się z dużej litery. Poszczególne słowa mogą być odseparowane dowolną liczbą białych znaków. W nazwach miejscowości zdarzają się też połączenia słów za pomocą myślnika (w okolicach łącznika nie występują białe znaki).
    Przetestuj wyrażenie na danych wprowadzonych ze standardowego wejścia.
    Zadanie 4 (2 pkt).
    Zdefiniuj wyrażenie regularne do rozpoznawania prawidłowo zapisanej liczby zespolonej. Zapis liczby zespolonej składa się z dwóch liczb rzeczywistych (z opcjonalna możliwością wystąpienia części ułamkowej po kropce dziesiętnej) połączonych znakiem plusa albo minusa (w pierwszej liczbie opcjonalny znak minusa), przy czym druga liczba jest zakończona małą albo dużą literą "i"; całość jest ujęta w nawiasy okrągłe.
    Przetestuj wyrażenie na danych wprowadzonych ze standardowego wejścia.
    Zadanie 5 (3 pkt).
    Zadefiniuj wyrażenie regularne wykrywające hiperłącze w dokumencie HTML - chodzi o znacznik <a href="..." />. Następnie użyj tego wyrażenia do wypisania na standardowym wyjściu wszystkich znalezionych w tekście hiperłączy (bez opakowania w postaci znacznia <a /> - sama treść atrybutu href).
    Przetestuj wyrażenie na tekście ze wskazanych za pomocą argumentów wywołania programu plików typu HTML (html, php, itp.).
  19. 16, 17 grudnia 2020: iteratory strumieniowe i plikowe
  20. Zadanie 1 (2 pkt).
    Odczytaj ze standardowego wejścia ciąg liczb rzeczywistych pooddzielanych białymi znakami. Używając iteratora strumieniowego istream_iterator odczytaj te liczby, zapisz w wektorze a następnie policz średnią arytmetyczną i odchylenie standardowe dla tego zbioru danych i wypisz wyniki na standardowym wyjściu z dokładnością do 3 miejsc po kropce dziesiętnej.
    Zadanie 2 (2 pkt).
    Niech $\Phi(n)$ oznacza funkcję Eulera (tocjent), która dla każdej dodatniej liczby naturalnej zwraca liczbę liczb naturalnych nie większych od $n$ i względnie pierwszych z $n$. Dla zadanej wartości $k$ stablicuj kolejne wartości tocjenta $\Phi(1), \Phi(2), \ldots, \Phi(k)$ a następnie zapisz je do pliku phi.txt, używając iteratora strumieninowego ostream_iterator z separatorem w postaci średnika i spacji "; ".
    Zadanie 3 (2 pkt).
    Napisz program, który sprawdzi czy w lokalnym systemie plików istnieją podane pliki lub foldery. Jeśli tak, to wypisz ich najważniejsze parametry (ścieżka kanoniczna, data ostatniej modyfikacji, rozmiar dla pliku itp.). Nazwy plików i folderów przekaż do programu poprzez argumenty wywołania.
    Zadanie 4 (2 pkt).
    Napisz program, który wypisze zawartoś wskazanego folderu w lokalnym systemie plików. Jeśli podany przez użytkownika folder nie istnieje, to wypisz stosowną informację. Wypisując zawartość folderu posłuż się iteratorem directory_iterator.
    Zadanie 5 (2 pkt).
    Napisz program, który policzy i wypisze sumę rozmiarów wszystkich plików we wskazanym folderze i jego podfolderach. Jeśli podany przez użytkownika folder nie istnieje, to wypisz stosowną informację. Analizując zawartość folderu i podfolderów posłuż się iteratorem recursive_directory_iterator.
  21. 6, 7 stycznia 2020: lokalizacja
  22. Zadanie 1 (2 pkt).
    Zdefiniuj napis wstring i zawierający wszystkie polskie znaki diakrytyczne i wypisz go na standardowym wyjściu wcout.
    Zadanie 2 (2 pkt).
    Wypisz kilka liczb całkowitych, zmiennopozycyjnych i wartości pieniężnych w trzech różnych lokalizacjach.
    Zadanie 3 (2 pkt).
    Sformatuj i wypisz bieżącą datę i godzinę w trzech różnych lokalizacjach.
    Zadanie 4 (2 pkt).
    Przekonwertuj plik tekstowy używający kodowania UTF-8 na Unicode.
    Zadanie 5 (2 pkt).
    W wektorze vector<wstring> znajdują się nazwy różnych zwierząt i roślin. Posortuj je używając kolatora dla polskiej lokalizacji.
  23. 13, 14 stycznia 2021: metaprogramowanie
  24. Zadanie 1 (1 pkt).
    Wykorzystując metaprogramowanie zdefiniuj szablon obiektu funkcyjnego, pozwalającego obliczyć na poziomie kompilacji n-tą liczbę Lucasa dla liczby naturalnej n ≥ 0. Funkcja powinna działać (w trakcie kompilacji) w liniowym czasie O(n).
    Zadanie 2 (2 pkt).
    Wykorzystując metaprogramowanie zdefiniuj szablon obiektu funkcyjnego, pozwalającego obliczyć na poziomie kompilacji współczynnik dwumianowy (nk) dla liczb naturalnych 0 ≤ k ≤ n. Funkcja powinna działać (w trakcie kompilacji) w liniowym czasie O(n).
    Zadanie 3 (1 pkt).
    Wykorzystując metaprogramowanie zdefiniuj szablon obiektu funkcyjnego, pozwalającego obliczyć na poziomie kompilacji największy wspólny dzielnik NWD(a, b) dla liczb naturalnych a, b ≥ 1 dla naturalnych liczb 0 ≤ k ≤ n. Funkcja powinna działać (w trakcie kompilacji) w logarytmicznym czasie O(log a + log b).
    Zadanie 4 (2 pkt).
    Wykorzystując metaprogramowanie zdefiniuj szablon funkcji liczącej iloczyn skalarny dwóch wektorów:
    template<size_t N> double inner(double *x, double *y);
    Parametrem szablonu ma być dlugość mnożonych wektorów.
    Zmodyfikuj poprzedni szablon funkcji liczącej iloczyn skalarny w taki sposób, aby drugim parametrem był typ danych:
    template<size_t N, typename T = double> T inner(T *x, T *y);
    Zadanie 5 (4 pkt).
    Wykorzystując metaprogramowanie zdefiniuj szablon klasy będącej opakowanien dla obiektu określonego w parametrze typu template<typename T> struct obj_holder. Opakowanie to ma konieczne zaalokować pamięć dla obiektu na stosie, jeśli jest on mały (jego rozmiar jest niewięszy niż sizeof(string)) i nie jest tablicą albo na stercie w przeciwnym przypadku.
    W strukturze obj_holder zdefiniuj alias type dla docelowego typu ustalony w oparciu o selektor std::conditional<> - będzie to albo struktura on_stack (dla małych obiektów) albo on_heap (dla dużych obiektów tworzonych dynamicznie na stercie, pamiętaj aby w destruktorze tego opakowania zwolnić przydzieloną pamięć). W obu tych strukturach zaimplementuj semantykę wskaźników, czyli operator wyłuskania (gwiadka *) udostępniający referencję do obiektu i operator dostępu do składowych (strzałka ->) udostępniający adres obiektu.
    W kolejnym kroku zdefiniuj szablon klasy będącej opakowanien dla tablicy obiektów określonego w parametrze typu template<typename T> struct arr_holder. Zaadoptuj poprzednie definicje na przypadek dotyczący tablic - struktura array_on_heap dla małych tablic tworzonych na stercie i albo array_in_file dla dużych tablic przechowywanych w plikach o dostępie swobodnym (pojęcie "mały" i "duży" w odniesieniu do tablic należy rozsądnie doprecyzować). W obu tych strukturach zaimplementuj semantykę indeksowania.
  25. 20, 21 stycznia 2021: programowanie współbieżne
  26. Zadanie 1 (1 pkt).
    Napisz program, który utworzy kilka wątków nadając im arbitralnie pewne nazwy. Każdy wątek ma wypisywać swoją nazwę na standardowym wyjściu co losową ilość milisekund (od 500 do 1000). Działanie programu powinno się zakończyć po minucie – decyzję o zakończeniu niech podejmie główny wątek programu.
    Zadanie 2 (2 pkt).
    Napisz program, który będzie się wykonywać dokładnie 10 sekund. Na 5 sekund przed zakończeniem należy użytkownika poinformować, że program wkrótce się zakończy (za 5 sekund). Podobną informację należy podać 3 sekundy przed końcem i 1 sekundę przezd końcem.
    Zadanie 3 (3 pkt).
    Zaimplementuj algorytm sortowania przez scalanie merge_sortalbo sortowania przez podział quick_sort (jedna metoda do wyboru) dla danych przechowywanych w tablicy. Działanie algorytmu ma bazować na wątkach zamiast na rekurencji – każde wywołanie rekurencyjne funkcji sortującej zastąp wątkiem pracującym na podtablicy (podziały danych kończą się na tablicach jednoelementowych albo pustych).
    Zadanie 4 (4 pkt).
    Problem producentów i konsumentów to klasyczny problem synchronizacji wątków na współdzielonych zasobach. W problemie występują dwa rodzaje wątków: producent i konsument. Wątki te korzystają ze wspólnego zasobu jakim jest bufor dla produkowanych i konsumowanych produktów. Zadaniem producenta jest wytworzenie produktu, umieszczenie go w buforze i rozpoczęcie pracy nad nowym. Jednocześnie konsument ma pobrać produkt z bufora, skonsumować go i sięgnąć po następny. Problemem jest taka synchronizacja wątków, żeby żaden producent nie mógł dodać nowego produktu do pełnego bufora, ani żaden konsument nie mógł pobrać produktu z pustego bufora.
    Rozwiązaniem tego problemu dla producenta jest uśpienie wątku producenta w momencie, gdy bufor jest pełny; pierwszy konsument, który pobierze produkt z bufora budzi wątki producentów, aby któryś uzupełnił bufor. W analogiczny sposób usypiany jest wątek konsumenta próbujący pobrać produkt z pustego bufora; pierwszy producent, który wstawi produkt do bufora budzi wątki konsumentów, aby któryś opróżnił bufor.
    Napisz program, który zilustruje problem producentów i konsumentów z wykorzystaniem wątków i blokad.
Ranking

grupa PRz, czwartek 18 (pdf)

wykłady

8 października 2020 r: nowe elementy języka w C++17

organizacja zajęć
nowe elementy języka C++ 11/14/17
  • trójznaki
  • surowe łańcuchy znakowe
  • pętla for-each
  • jednolita inicjalizacja
  • stypizowane typy wyliczeniowe
  • dedukcja typów za pomocą auto i decltype
  • instrukcje if i switch-case z częścią inicjalizującą zmienne lokalne dla tych instrukcji
  • instrukcja constexpr-if

slajdy: organizacja.pdf, nowe.pdf

C++ compiler support

Wandbox (C++2a compiler online)

15 października 2020 r: sprytne wskaźniki

sprytne wskaźniki
  • wskaźniki współdzielone shared_ptr
  • wskaźniki unikatowe unique_ptr
  • słabe wskaźniki weak_ptr

slajdy: wskazniki.pdf

22 października 2020 r: czasomierze

sprytne wskaźniki
  • limity liczbowe
  • cechy typowe
  • współczynniki ułamkowe ratio
  • zegary clock, punkty time_point i odcinki czasowe duration
  • czas w systemie POSIX

slajdy: czasomierze.pdf

29 października 2020 r: funktory

funktory
  • obiekty funkcyjne
  • lambdy

slajdy: funktory.pdf

5 listopada 2020 r: kolekcje standardowe

kolekcje standardowe
  • wartościowa semantyka kolekcji
  • elementy kolekcji
  • rodzaje kolekcji i ich implementacja
  • tablice
  • wektory i deki
  • listy dwukierunkowe i jednokierunkowe
  • zbiory i multizbiory
  • mapy i multimapy
  • zbiory i mapy nieuporządkowane
  • adaptery kolekcji

slajdy: kolekcje.pdf

12 listopada 2020 r: algorytmy

algorytmy
  • klasyfikacja algorytmów
  • iteratory i zakresy danych w algorytmach
  • algorytm for_each
  • algorytmy niemodyfikujące:
    • zliczanie elementów count
    • wartość minimalna i maksymalna min_element, max_element, minmax_element
    • wyszukiwanie pierwszego pasującego elementu find
    • wyszukiwanie pierwszego podzakresu search
    • porównywanie zakresów equal
    • wykrywanie sekwencji tych samych elementów w innym porządku is_permutation
    • porównywanie leksykograficzne lexicographical_compare
    • sprawdzanie czy zakres jest uporządkowany is_sorted, is_sorted_until
    • sprawdzanie rozdzielenia elementów is_partitioned, partition_point
    • sprawdzanie czy zakres jest kopcem is_heap, is_heap_until
    • wszystkie all_of, którykolwiek any_of, żaden none_of
  • algorytmy modyfikujące:
    • kopiowanie copy, copy_backward
    • przenoszenie elementów między zakresami move, move_backward
    • przekształcanie elementów transform
    • wymienianie elementów swap_ranges
    • przypisywanie tej samej wartości fill
    • przypisywanie wartości generowanych generate
    • zastępowanie wartości wewnątrz zakresureplace, replace_copy
  • algorytmy usuwające:
    • usuwanie elementów z zakresu remove, remove_copy
    • usuwanie kolejnych powtórzeń unique, unique_copy
  • algorytmy mutujące:
    • odwracanie kolejności elementów reverse, reverse_copy
    • przesunięcia cykliczne elementów rotate, rotate_copy
    • permutacje elementów next_permutation, prev_permutation
    • tasowanie elementów random, random_shuffle
    • rozdzielenie elementów partition, stable_partition, partition_copy
  • algorytmy sortujące:
    • sortowanie elementów sort, stable_sort
    • sortowanie częściowe partial_sort, partial_sort_copy
    • wybór n-tego co do wielkości elementu nth_element
  • algorytmy sortujące:
    • sortowanie elementów sort, stable_sort
    • sortowanie częściowe partial_sort, partial_sort_copy
    • wybór n-tego co do wielkości elementu nth_element
  • algorytmy kopcowe
    • utworzenie kopca make_heap
    • wstawienie elementu do kopca push_heap
    • przesunięcie elementu największego na koniec kopca pop_heap
    • sortowanie kopcowe sort_heap
  • algorytmy przeznaczone dla zakresów posortowanych
    • sprawdzanie obecności elementu binary_search
    • wyszukiwanie pierwszej lub ostatniej możliwej pozycji lower_bound, upper_bound
    • scalanie elementów merge, inplace_merge
    • wyznaczanie sumy dwóch posortowanych zbiorów set_union
    • wyznaczanie iloczynu dwóch posortowanych zbiorów set_intersection
    • wyznaczanie różnicy dwóch posortowanych zbiorów set_difference, set_symmetric_difference
  • algorytmy numeryczne
    • iterowanie i kumulowanie obliczeń accumulate
    • iloczynu skalarny inner_product
    • sumy częściowe partial_sum

slajdy: algorytmy.pdf

19 listopada 2020 r: generatory liczb pseudolosowych

generatory liczb pseudolosowych
  • mechanizmy losowości
  • rozkłady

slajdy: losowe.pdf

26 listopada 2020 r: liczby zespolone

liczby zespolone
  • szablon klasy complex<>
  • funkcje i operatory działające na liczbach zespolonych

slajdy: zespolone.pdf

3 grudnia 2020 r: wyrażenia regularne

wyrażenia regularne
  • budowa wyrażeń regularnych
  • klasa regex
  • funkcje dopasowujące
  • podwyrażenia
  • iterowanie po dopasowaniach

slajdy: regularne.pdf

10 grudnia 2020 r: iteratory strumieniowe i plikowe

iteratory strumieniowe i plikowe
  • iterator strumieniowy wejściowy istream_iterator
  • iterator strumieniowy wyjściowy ostream_iterator
  • klasa std::filesystem::path i funkcja std::filesystem::exists()
  • iteratory po systemie plików directory_iterator i recursive_directory_iterator

17 grudnia 2020 r: lokalizacja

zestawy znaków
  • kodowanie znaków
  • zestawy znaków obsługiwane w C++
  • literały napisowe
  • cechy znaków char_traits
lokalizacja
  • obiekty ustawień lokalnych locale
  • aspekty ustawień lokalnych facet
  • formatowanie liczb, wartości pieniężnych, czasu i daty
  • klasyfikacja znaków
  • konwersja standardów kodowania znaków
  • sortowanie łańcuchów znakowych

slajdy: lokalizacja.pdf

7 stycznia 2021 r: metaprogramowanie

metaprogramowanie
  • przypadki użycia metaprogramowania
  • funkcje typowe
  • aliasy i predykaty typów
  • trejty które wiążą typy z ich właściwościami
  • struktury sterujące Conditional i Select
  • iteracja za pomocą szablonów rekurencyjnych
  • definicja warunkowa Enable_if

slajdy: meta.pdf

14 stycznia 2021 r: współbieżność 1

współbieżność wysokopoziomowa
  • wątki w procesie jako niezależne ścieżki obliczeń
  • wątki sprzętowe, systemowe i programowe thread
  • asynchroniczne wykonywanie zadań za pomocą funkcji async()
  • strategie wykonywania zadań przez funkcję async(): launch::async i launch::deferred
  • klasy reprezentujące wynik działania funkcji zrealizowanej przez wątek future<> i shared_future<>
  • odbieranie wyniku od futury za pomocą funkcji get()
  • funkcja get() i valid() działająca na obiekcie futury
  • oczekiwanie na zakończenie i wynik zadania w futurze za pomocą funkcji wait_for() i wait_until()
  • status futury: future_status::deferred, future_status::timeout, future_status::ready
  • obsługa wyjątków w trakcie pracy wątku
  • wstrzymanie realizacji zadania za pomocą funkcji yield()
  • synchroniazacja pracy wątków za pomocą funkcji join()
  • usypianie wątków za pomocą funkcji this_thread::sleep_for()

21 stycznia 2021 r: współbieżność 2

współbieżność niskopoziomowa
  • klasa wątku thread
  • klasa promesy promise
  • problem synchronizacji
  • muteksy i blokady
  • zmienne warunkowe
  • atomowe typy danych

28 stycznia 2021 r: folding

folding
  • szablony i funkcje wariadyczne
  • wyrażenia fold
  • folding lewostronny i prawostrony
  • folding jednoargumetowy i dwuargumentowy
  • operatory w wyrażeniach fold
  • operatory logiczne && oraz || dostarczane wraz z wbudowanymi elementami neutralności
  • operatory sekwencji obliczeń , (przecinek) dostarczany wraz z domyślnym wywołaniem funkcji void()
  • studium zadania - dopasowanie zakresu względem poszczególnych elementów:
    template <typename R, typename ... Ts>
    auto matches(const R& range, Ts ... ts) {
        return (count(begin(range), end(range), ts) + ...);
    }
  • studium zadania - sprawdzenie, czy operacja wstawienia wielu elementów do zbioru zakończyła się pomyślnie:
    template <typename R, typename ... Ts>
    bool insert_all(T &set, Ts ... ts) {
        return (set.insert(ts).second && ...);
    }
  • studium zadania - sprawdzenie, czy wszystkie parametry znajdują się w danym zakresie:
    template <typename R, typename ... Ts>
    bool within(T min, T max, Ts ... ts) {
        return ((min <= ts && ts <= max) && ...);
    }
  • studium zadania - umieszczenie wielu elementów w wektorze:
    template <typename R, typename ... Ts>
    void insert_all(vector<T> &vec, Ts ... ts) {
        (vec.push_back(ts), ...);
    }