Wykład (30 h):
- Definicje, schematy blokowe, złożoność obliczeniowa
- Algorytmy zachłanne, programowanie dynamiczne, heurystyki
- Liczby pseudolosowe
- Przetwarzanie tekstu, wyrażenia regularne
- Struktury danych, stosy, kolejki, listy
- Tablice, Sortowanie, Rekurencja
- Drzewa, Funkcje mieszające, Grafy
Ćwiczenia (30h):
- Wybrane algorytmy i struktury danych zaimplementowane w C# lub Java
Laboratorium 2 – 08.10 g. 11
Zad 1. Ile jest liczb czterocyfrowych, które są liczbami pierwszymi i zawierają cyfrę 5 i 6
Zad 2. Znaleźć wszystkie trójki pitagorejskie (z wikipedii definicja) dla a, b, c < 10000
Zad 3. Znaleźć minimalną i maksymalną wartość funkcji (wskazać też dla jakich x i y) f(x, y) = sin(2x) * tg(y – ln(x)) + x^3 dla x z przedziału <2, 6> i y z przedziału <-1, 5> analizowanych z dokładnością 3 miejsc po przecinku.
Zad 4. Napisać metodą wyznacząjącą ile wynosi różnica sumy nieparzystych dzielników liczby i sumy jej cyfr
Laboratorium 2 – 08.10 g. 13:
Zad 1. Ile jest liczb pierwszych mniejszych od 100000 zawierających co najmniej dwie cyfry 3 (sito Eratostenesa)
Zad 2. Znaleźć ilość par liczb zaprzyjaźnionych których suma < 100000 (z wikipedii definicja)
Zad 3. Znaleźć minimalną i maksymalną wartość funkcji( wskazać też dla jakich x i y) f(x, y) = cos(3x^4 – 1) * sin(y^2) dla x z przedziału <3, 7> i y z przedziału <-2, 1> analizowanych z dokładnością 3 miejsc po przecinku.
Zad 4. Napisać metodą wyznaczającą największą liczbę pierwszą mniejszą od wskazanej liczby, dla której suma cyfr też jest liczbą pierwszą.
Laboratorium 2 – 09.10 g. 14.00:
Zad 1. Znaleźć sumę cyfr największej liczby pierwszej < 1000000.
Zad 2. Znaleźć ilość liczb czterocyfrowych, dla których suma cyfr jest dzielnikiem tej liczby.
Zad 3. Znaleźć minimalną i maksymalną wartość funkcji (wskazać też dla jakich x) f(x) = tg(3x^3) * cos(x^2 – ln(x)) dla x z przedziału <-2, 5> analizowanych z dokładnością 4 miejsc po przecinku.
Zad 4. Napisać metodą sprawdzająca jaki trójkąt mogą stworzyć trójki liczb a, b, c.
Laboratorium 3 – 15.10 g. 11:
Zad 1. Wygenerować tablicę 30 liczb z zakresu <15, 28> przy czym każda z liczb może być wylosowana maksymalnie 3 razy
Zad 2. Napisać metodę wyznaczającą liczbę elementów mniejszych od średniej liczby parzystej w tej tablicy
Zad 3. Napisać metodę wyznaczającą najdłuższy podciąg kolejnych liczb nieparzystych
Zad 4. Ile jest liczb w tej tablicy występujących nieparzystą ilość razy.
Laboratorium 3 – 15.10 g. 13:
Zad 1. Wygenerować tablicę 40 liczb z zakresu <7, 100> przy czym każda z liczb może być wylosowana maksymalnie 2 razy
Zad 2. Napisać metodę wyznaczającą sumę elementów najdłuższego podciągu malejącego sąsiednich liczb nieparzystych w tej tablicy
Zad 3. Napisać metodę wyznaczającą minimalny iloczyn 3 sąsiednich liczb w tej tablicy, spośród których dokładnie dwie liczby są nieparzyste
Zad 4. Ile jest liczb w tej tablicy występujących parzystą ilość razy
Laboratorium 3 – 16.10 g. 14.00:
Zad 1. Wylosować liczby do LOTTO: 6 liczb bez powtórzeń z przedziału <1, 49>
Do zadań 2-4 Wylosować 25-elementową tablicę złożoną z liczb dwucyfrowych
Zad 2. Napisać metodę wyliczającą liczbę elementów najdłuższego podciągu rosnącego kolejnych liczb nieparzystych
Zad 3. Napisać metodę wyznaczającą liczbę podciągów kolejnych 3 liczb tworzących ciąg arytmetyczny
Zad 4. Napisać metodą wyznaczającą krotność występowania poszczególnych liczb w tablicy
Laboratorium 4 – 22.10 g. 11:
Zad 1. Utworzyć 10-elementową losową tablicę liczb trzycyfrowych zawierającą dokładnie 4 liczby pierwsze.
Zad 2. Wskazać liczbę pierwszą „najbliższą” średniej w tej tablicy
Zad 3. Metoda d’Hondta https://pl.wikipedia.org/wiki/Metoda_D%E2%80%99Hondta
Zad 4. Wydawanie kwoty (reszty) z ograniczeniami (każdy z nominałów dostępny w określonej ilości)
Laboratorium 4 – 22.10 g. 13:
Zad 1. Utworzyć 40-elementową losową tablicę cyfr, w której każda z cyfr występuje co najmniej trzykrotnie.
Zad 2. Znaleźć w tej tablicy najdłuższy podciąg liczb pierwszych.
Zad 3. Metoda d’Hondta https://pl.wikipedia.org/wiki/Metoda_D%E2%80%99Hondta
Zad 4. Wydawanie kwoty (reszty) z ograniczeniami (każdy z nominałów dostępny w określonej ilości)
Laboratorium 4 – 23.10 g. 14:
Zad 1. Utworzyć losową tablicę liczb dwucyfrowych zawierającą dokładnie 7 liczb parzystych i 6 nieparzystych.
Zad 2. Ile jest liczb większych od średniej w tej tablicy
Zad 3. Metoda d’Hondta https://pl.wikipedia.org/wiki/Metoda_D%E2%80%99Hondta
Zad 4. Wydawanie kwoty (reszty) bez ograniczeń (każdy z nominałów dostępny w nieograniczonej ilości)
Laboratorium 5 – 30.10 g. 14:
Zad 1. Znaleźć minimalną i maksymalną wartość funkcji (wskazać też dla jakich x) f(x) = sin(3x) * cos(x – ln(x)) + x^3 dla x z przedziału <3, 6> analizowanych z dokładnością 4 miejsc po przecinku.
Zad 2. Wygenerować tablicę 10 liczb dwucyfrowych zawierającą dokładnie 4 liczby nieparzyste, w której średnia liczba parzysta jest mniejsza od średniej liczby nieparzystej.
Zad 3. Napisać metodę do rozwiązania klasycznego problemu plecakowego metodą zachłanną (2 pkt.).
Laboratorium 5 – 29.10 dodatkowe dla obu grup
Napisać metodę do rozwiązania klasycznego problemu plecakowego metodą zachłanną i siłową (4 pkt.).
Laboratorium 6 – 05.11 g. 11, 06.11. g. 14:
Zad 1. Utworzyć losową macierz zerojedynkową o rozmiarze n x k (n, k losowe z przedziału <4,7>). Znaleźć średnią wartość elementu całej macierzy. Znaleźć liczbę wierszy, kolumn, przekątnych (jeśli to macierz kwadratowa) o średniej wartości elementu mniejszej od średniej całej macierzy.
Zad 2. Wygenerować tablicę poszarpaną (jagged array) złożoną z liczb dwucyfrowych w n wierszach i maksymalnie k kolumnach (n, k losowe z przedziału <3,6>) – w każdym wierszu od 1 do k elementów (losowa ilość). Ile jest wierszy, w których średnia liczba parzysta jest większa od średniej liczby nieparzystej.
Zad. 3. Wygenerować napis złożony z 8 dowolnych cyfr i 7 liter w dowolnej kolejności a) czy napis zawiera 3 sąsiadujące małe litery lub 3 cyfry? b) Jaki jest najdłuższy podciąg zawierający litery? c) ile jest podciągów zawierających co najmniej 2 sąsiednie cyfry? (2 pkt.)
Laboratorium 6 – 05.11 g. 13:
Zad 1. Utworzyć losową macierz zawierającą cyfry o rozmiarze n x k (n, k losowe z przedziału <3,5>). Znaleźć najmniejszą sumę elementów parzystych w wierszu, kolumnie lub przekątnych (jeśli to macierz kwadratowa).
Zad 2. Wygenerować tablicę poszarpaną (jagged array) złożoną z liczb dwucyfrowych w n wierszach i maksymalnie k kolumnach (n, k losowe z przedziału <4,6>) – w każdym wierszu od 1 do k elementów (losowa ilość). Ile jest wierszy, w których średnia liczba parzysta jest większa niż średnia liczba w całej tablicy.
Zad. 3. Wygenerować napis złożony z 5 dowolnych cyfr i 6 liter w dowolnej kolejności a) czy napis zawiera kolejno 2 małe litery i 2 cyfry? b) Jaki jest najdłuższy podciąg zawierający cyfry? c) ile jest podciągów zawierających co najmniej 2 sąsiednie litery? (2 pkt.)
Laboratorium 7 – 19.11 g. 11:
Zad. 1: Wygenerować napis złożony z 5 dowolnych małych liter i 6 dużych liter i 5 cyfr w dowolnej kolejności. Ile w tym napisie jest samogłosek?
Zad. 2: Korzystając z Regexa a) czy ten napis zaczyna się od 2 liter lub 2 cyfr lub czy zawiera 3 kolejne litery b) ile jest fragmentów zawierających same litery. Który fragment zawiera ich najwięcej
Zad. 3: Czy napis to poprawny adres „Biała Podlaska ul. Nowa 137b/27” Miasto (maksymalnie dwuczłonowy napis oddzielony spacją lub łącznikiem -) ulica też dwuczłonowa nr mieszkania opcjonalny i inne „wymyślone” walidacje
Zad. 4: Sprawdzić ile w napisie jest zawartych poprawnych numerów PESEL, przed sprawdzaniem usunąć białe znaki i znaki specjalne.
Laboratorium 7 – 19.11 g. 13:
Zad. 1: Wygenerować napis złożony z 7 dowolnych cyfr i 8 liter i 5 znaków specjalnych w dowolnej kolejności. Ile w tym napisie jest samogłosek?
Zad. 2: Korzystając z Regexa a) czy napis zaczyna się od 3 liter lub 3 cyfr lub czy zawiera 4 kolejne litery b) ile jest fragmentów zawierających same cyfry. Który fragment zawiera ich najwięcej
Zad. 3: Czy napis to poprawny adres w formacie „21-500 woj. lubelskie” [2cyfry]-[3cyfry] (opcjonalne woj.) xx prawidłowe napisy np.: 21-500 woj. lubelskie lub 21-500 lubelskie
Zad. 4: Sprawdzić ile w napisie jest zawartych poprawnych numerów NIP, przed sprawdzaniem usunąć białe znaki i znaki specjalne.
Laboratorium 7 – 20.11 g. 14:
Zad. 1: Wygenerować napis złożony z 5 dowolnych cyfr i 5 małych liter i 5 dużych liter w dowolnej kolejności. Ile w tym napisie jest samogłosek?
Zad. 2: Korzystając z Regexa a) czy napis zaczyna się od 3 liter, zawiera 3 kolejne cyfry i ma więcej dużych liter niż małych b) ile jest fragmentów zawierających same litery. Który fragment zawiera ich najwięcej?
Zad. 3: Czy napis to poprawny adres w formacie „21-500 m. Biała Podlaska” [2cyfry]-[3cyfry] (opcjonalne m.) Miasto (maksymalnie dwuczłonowy napis oddzielony spacją lub łącznikiem -. Prawidłowe napisy np.: 21-500 m. Biała Podlaska lub 34-500 Bielsko-Biała lub 00-254 Warszawa
Zad. 4: Sprawdzić ile w napisie jest zawartych poprawnych identyfikatorów w formacie 2 litery i 5 cyfr lub 3 litery i 4 cyfry, przed sprawdzaniem usunąć białe znaki i znaki specjalne.
https://regexr.com/
https://learn.microsoft.com/pl-pl/dotnet/api/system.text.regularexpressions.regex?view=net-7.0
Laboratorium 8 – 26.11 g. 11
Zad. 1: Wyszukiwanie binarne – iteracyjnie i rekurencyjnie
Zad. 2: Metoda do wyznaczenia 2^n * (n-1)! Iteracyjnie i rekurencyjnie
Zad 3. Metoda do zamiany liczb dziesiętnych na dwójkowe: iteracyjnie i rekurencyjnie
Zad 4. Metoda do wyliczenia iteracyjnie i rekurencyjnie a(n) = 3*n – 2^n dla n<4 i a(n) = 2*a(n-1) + 3*a(n-2) dla n>=4. Testowo wypisać elementy do a(8)
Laboratorium 8 – 26.11 g. 13
Zad. 1: Wyszukiwanie binarne – iteracyjnie i rekurencyjnie
Zad. 2: Metoda do wyznaczenia a^n (a, n całkowite nieujemne): iteracyjnie i rekurencyjnie.
Zad 3. Metoda do zamiany liczb dziesiętnych na szesnastkowe: iteracyjnie i rekurencyjnie
Zad 4. Metoda do wyliczenia iteracyjnie i rekurencyjnie a(n) = 2*n + 2 dla n<4 i a(n) = 3*a(n-1) – a(n-2) + 1 dla n>=4. Ile wynosi a(9)
Laboratorium 8 – 27.11 g. 14
Zad. 1: Wyszukiwanie binarne – iteracyjnie i rekurencyjnie
Zad. 2: Metoda do wyznaczenia a^n*n! (a, n całkowite nieujemne): iteracyjnie i rekurencyjnie.
Zad 3. Metoda do zamiany liczb dziesiętnych na ośemkowe: iteracyjnie i rekurencyjnie
Zad 4. Metoda do wyliczenia iteracyjnie i rekurencyjnie a(n) = 2*n – 2 dla n<4 i a(n) = 2*a(n-1) – a(n-3) dla n>=4. Ile wynosi a(9)
Laboratorium 9 – 03.12 g. 11
Zad. 1: Dla dowolnego napisu znaleźć najdłuższy palindrom w nim zawarty. Dla arkobyłamamałybokbdg palindrom kobyłamamałybok.
Zad. 2: Dla dowolnego zdania sprawdzić ile jest słów co najmniej 8-literowych zawierających co najmniej 3 samogłoski (ignorować znaki interpunkcyjne).
Zad. 3: Napisać metodę bool ContainsInWord(string word1, string word2), która zwróci true gdy wyraz word1 zawiera wszystkie litery wykorzystane w word2 i false w przeciwnym wypadku.
Zad. 4. Sprawdzić czy napis jest poprawną datą w XX wieku o formacie dd-mm-rrrr. Uwzględnić liczbę dni miesiąca i lata przestępne.
Zad. 5. Obliczyć a(9) iteracyjnie i rekurencyjnie gdy a(n) = 2*n + 2 dla n<4 i a(n) = 2*b(n+2) – a(n-2) dla n>=4 oraz b(n) = 2^n dla n<=2 i b(n) = b(n-1)-b(n-1) dla n>2
Laboratorium 9 – 03.12 g. 13
Zad. 1: Dla dowolnego zdania sprawdzić ile słów w nim to palindromy co najmniej trzyliterowe (ignorować znaki interpunkcyjne).
Zad. 2: Napisać metodę bool AreAnagrams(string word1, string word2), która zwróci true gdy wyrazy są anagramami i false w przeciwnym wypadku.
Zad. 3: Dla dowolnego wyrazu sprawdzić czy można dla niego ułożyć anagram, który jest palindromem.
Zad. 4. Sprawdzić czy napis jest poprawnym identyfikatorem w formacie: zaczyna się co najmniej jedną cyfrą, kończy się co najmniej jedną literą, składa się z ciągów 2-4 cyfrowych lub 3-5 literowych oddzielonych „-„.
Zad. 5. Obliczyć a(7) iteracyjnie i rekurencyjnie gdy a(n) = 2*n – 2 dla n<3 i a(n) = 2*b(n+3) – a(n-2) dla n>=3 oraz b(n) = 2^n – 1 dla n<=4 i b(n) = b(n-1)-b(n-2) + 3 dla n>4
Laboratorium 9 – 04.12 g. 14
Zad. 1: Dla dowolnego zdania sprawdzić ile słów w nim to palindromy (ignorować znaki interpunkcyjne), który jest najdłuższy.
Zad. 2: Napisać metodę bool AreAnagrams(string word1, string word2), która zwróci true gdy wyrazy są anagramami i false w przeciwnym wypadku.
Zad. 3: Dla dowolnego napisu sprawdzić Regex, ile zawiera fragmentów zawierających małe litery lub cyfry, który z tych fragmentów jest najdłuższy.
Zad. 4. Sprawdzić czy napis jest poprawnym identyfikatorem w formacie: zaczyna się co najmniej dwoma cyframi, kończy się co najmniej jedną literą, składa się z ciągów 2-4 cyfrowych lub 1-5 literowych oddzielonych „-” lub „.”.
Zad. 5. Obliczyć a(6) iteracyjnie i rekurencyjnie gdy a(n) = n – 2 dla n<3 i a(n) = 2*b(n+4) – a(n-2) dla n>=3 oraz b(n) = 2*n – 1 dla n<=4 i b(n) = b(n-1)-b(n-2) + 3 dla n>4.
Laboratorium 11 – sortowanie, 17.12, 08.01
Dla każdego indywidualnie przekazanego ciągu liczb sortowanie bąbelkowe, przez wybór, przez wstawianie „graficznie” sortowanie i analiza kodu qsort, quicksort szybkie (5 pkt.)
Zad 1. Sortowanie przez wybór, w jednym przejściu równocześnie przesuwanie elementu min i max.
Zad 2. Sortowanie przez wstawianie z wyszukiwaniem binarnym miejsca wstawienia.
Zad 3. Sortowanie bąbelkowe z flagą czy była zamiana elementów w przejściu.
Powyższe do 15.01
Porównanie algorytmów sortowania klasycznych (bąbelkowe, przez wybór, wstawianie, qsort) z opracowanymi, liczba porównań, czas działania (10 pkt.) – do 22.01
Laboratorium 12 – 14.01. g. 11
Zad. 1: Znaleźć podkatalog dla wybranego katalogu, w którym bezpośrednio znajduje się najwięcej plików tekstowych utworzonych w roku 2024. Znaleźć dla wybranego katalogu średni rozmiar plików z określonym rozszerzeniem.
Zad. 2: Znaleźć dla wybranego katalogu listę podfolderów z informacją o łącznej liczbie plików bezpośrednio w nim się znajdujących posortowanych malejąco po liczbie plików.
Zad 3. (2 pkt.)::
a) Do klasy Stos dodać konstruktor Stos(Kolejka k), który tworzy nowy stos o rozmiarze 3 razy większym niż kolejka k i dodaje elementy z kolejki k.
b) Do klasy Stos dodać metodę int[] zdejmij(int n), która zwraca n elementów ze stosu (jeśli jest mniej niż n elementów to zwraca tyle ile ich jest aktualnie na stosie).
c) Utworzyć stos o dowolnym rozmiarze. Wypełnić losowymi cyframi. Odwrócić zawartość elementów na stosie z wykorzystaniem dodatkowej kolejki lub dodatkowego stosu.
Laboratorium 12 – 14.01. g. 13
Zad. 1: Znaleźć dla wybranego katalogu łączną liczbę plików o rozmiarze > 3MB utworzonych w latach 2015-2024.
Zad 2. Znaleźć dla wybranego katalogu zestawienie podkatalogów (w całej strukturze podkatalogu) posortowanych po malejącej liczbie plików bezpośrednio w nim zawartych z informacją o łącznej liczbie plików z poszczególnymi rozszerzeniami.
Zad 3. (2 pkt.)::
a) Do klasy Kolejka dodać konstruktor Kolejka(Kolejka k), który tworzy nową kolejkę o rozmiarze 3 razy większym niż kolejka k i dodaje elementy z kolejki k.
b) Do klasy Kolejka dodać metodę Stos pobierzStos(int n), która zwraca stos o rozmiarze 2 * n, złożony z n elementów z aktualnej kolejki (jeśli jest mniej niż n elementów to przepisuje tyle ile jest w kolejce).
c) Utworzyć kolejkę o dowolnym rozmiarze. Wypełnić losowymi cyframi. Odwrócić zawartość elementów w kolejce z wykorzystaniem dodatkowej kolejki lub dodatkowego stosu.
Laboratorium 12 – 15.01. g. 14
Zad. 1: Znaleźć dla wybranego katalogu średni rozmiar plików utworzonych w latach 2015-2024 z podziałem na poszczególne lata.
Zad 2. Znaleźć dla wybranego katalogu zestawienie podkatalogów (w całej strukturze podkatalogu) posortowanych po malejącej liczbie plików bezpośrednio w nim zawartych.
Zad 3. Do klasy Kolejka dodać konstruktor Kolejka(Stos s), który tworzy nową kolejkę o rozmiarze 2 razy większym niż stos s i dodaje elementy ze stosu s (bez zmiany jego zawartości).
Zad 4. Utworzyć stos o dowolnym rozmiarze. Wypełnić losowymi cyframi. Odwrócić zawartość elementów w stosie z wykorzystaniem dodatkowej kolejki lub dodatkowego stosu.
Laboratorium 13 – 21.01. g. 11
Zad. 1 (2 pkt.): Wygenerować losowo słownik SortedList zawierający 200 elementów, w którym klucz jest w postaci cyfra + litera a wartość jest z zakresu <0, 150>.
a) Jaka jest średnia wartość elementów?
b) Ile jest elementów > średniej? Który element ma wartość najbardziej zbliżoną do średniej?
c) Ile jest elementów z przypisaną wartością z przedziału <50, 60>?
d) Ile kluczy zawiera cyfrę 3 lub wszystkie duże litery?
Zad. 2 (2 pkt.). Napisać klasy generyczne obsługujące stos i kolejkę. Przetestować je.
Zad 3 (2 pkt.). Algorytm Dijkstry.
Laboratorium 13 – 21.01. g. 13
Zad. 1 (2 pkt.): Wygenerować losowo słownik Dictionary zawierający 200 elementów, w którym klucz jest w postaci cyfra + litera a wartość jest z zakresu <0, 100>.
a) Jaka jest średnia wartość elementów?
b) Ile jest elementów > średniej? Który element ma wartość najbardziej zbliżoną do średniej?
c) Ile jest kluczy z przypisaną wartością 55 lub 60?
d) Ile kluczy zawiera cyfrę 4 lub dużą literę?
Zad. 2 (2 pkt.). Napisać klasy generyczne obsługujące stos i kolejkę. Przetestować je.
Zad 3 (2 pkt.). Algorytm Dijkstry.
Laboratorium 13 – 22.01. g. 14
Zad. 1 (2 pkt.): Wygenerować losowo słownik Dictionary zawierający 300 elementów, w którym klucz jest w postaci cyfra + litera a wartość jest z zakresu <0, 1000>.
a) Jaka jest średnia wartość elementów parzystych?
b) Ile jest elementów > średniej parzystej? Który element ma wartość najbardziej zbliżoną do tej średniej?
c) Ile jest kluczy z przypisaną wartością między 500 a 600?
d) Ile kluczy zawiera cyfrę 5 lub małą literę?
Zad. 2 (2 pkt.). Napisać klasy generyczne obsługujące stos i kolejkę. Przetestować je.
Zad 3 (2 pkt.). Algorytm Dijkstry.