Katalog przedmiotów
Budowa i analiza algorytmów
CeleZapoznanie studentów z elementami budowy algorytmów: strukturami sterującymi, strukturami danych i metodami konstruowania. Przedstawienie klasycznych algorytmów rozwiązywania zadań wyszukiwania i sortowania. Nauczenie zasad myślenia algorytmicznego oraz podstaw analizy poprawności i złożoności algorytmów. Zapoznanie studentów z podstawowymi klasami problemów algorytmicznych i klasycznymi modelami obliczeń komputerowych.
Zakres
Komputer jako zestaw przełączników, które wykonują podstawowe operacje na bitach; podstawowe rozkazy procesora. Podstawowe założenia algorytmicznego podejścia do rozwiązywania zadań: algorytm jako rozwiązanie problemu algorytmicznego, proste przykłady algorytmów. Podstawowe struktury sterujące: bezpośrednie następstwo, wybór warunkowy, iteracje (pętle) w odmianach - iteracja ograniczona, iteracja warunkowa w dwóch podstawowych wariantach. Zagnieżdżanie struktur sterujących: przykład rozwiązania problemu sortowania – algorytm sortowania bąbelkowego. Schematy blokowe algorytmów. Rola podprogramów (procedur) w językach programowania: budowanie algorytmów w sposób „analityczny” lub „syntetyczny”. Rekurencja jako zdolność podprogramu (procedury) do wywoływania samego siebie. Przykład algorytmu rekurencyjnego: rozwiązanie problemu „wież Hanoi”. Minimalny zbiór struktur sterujących. Usuwanie rekurencji z algorytmów. Podstawowe typy danych: liczbowe, znakowe i wskaźnikowe. Kodowanie danych dla potrzeb obliczeń komputerowych. Struktury danych jako organizacja elementów zbioru danych dla potrzeb algorytmu. Abstrakcyjne struktury danych: statyczne i dynamiczne. Przykłady struktur statycznych: zmienne, wektory – tablice jednowymiarowe, tabele (macierze) – tablice dwuwymiarowe. Związek struktur danych i struktur sterujących. Budowa rekordu jako podstawowego obiektu w strukturach dynamicznych. Przykłady struktur dynamicznych (wskaźnikowych): listy jedno- i dwukierunkowe, kolejki (listy FIFO), stosy (listy LIFO), drzewa ukorzenione, drzewa binarne i drzewa BST. Przykład wykorzystania struktury drzewa BST w algorytmie sortowania drzewiastego; algorytm sortowania drzewiastego z samoorganizacją drzewa. Metody algorytmiczne jako schematy konstruowania algorytmów: metoda „wędruj i sprawdzaj”, na przykładzie algorytmu wyznaczania maksymalnej przekątnej w wielokącie wypukłym, metoda „dziel i zwyciężaj” na przykładzie rekurencyjnego algorytm sortowania przez scalanie. Metoda zachłanna na przykładzie algorytmu wyznaczania minimalnego drzewa rozpinającego w grafie z wagami krawędzi – „sieć połączeń kolejowych”. Programowanie dynamiczne na przykładzie algorytmu znajdowania najkrótszej drogi w skierowanym grafie acyklicznym z wagami krawędzi – „najkrótsza ścieżka”. Składnia typowego języka programowania. Sposoby definiowania rozmaitych struktur danych i wzorce podstawowych instrukcji: Notacja BNF (Backus-Naur Form), diagramy składniowe. Składnia i semantyka typowego języka programowania. Kompilatory a interpretatory. Zagadnienie poprawności algorytmu: błędy językowe – naruszenia reguł składni języka programowania; błędy semantyczne – niezrozumienie znaczenia poleceń; błędy logiczne – algorytm przestaje być poprawnym rozwiązaniem zadania algorytmicznego; błędy algorytmiczne – algorytm dla pewnych dopuszczalnych danych wejściowych daje niepoprawny wynik, wykonanie programu realizującego algorytm jest przerywane lub program realizujący algorytm nie kończy swego działania. Problem poprawności częściowej i całkowitej algorytmu: dowodzenie częściowej poprawności algorytmu - punkty kontrolne, asercje i niezmienniki w obrębie iteracji; dowodzenie całkowitej poprawności - ustalanie zbieżnika. Badanie złożoności algorytmów – złożoność pamięciowa i czasowa. Porównywanie złożoności algorytmów wykonujących to samo zadanie. Notacja złożoności. Złożoność liniowa, kwadratowa i logarytmiczna. Analiza złożoności czasowej algorytmu w najgorszym przypadku. Przykłady algorytmów o niskiej złożoności: proste wyszukiwanie elementu z listy i algorytm wyszukiwania binarnego z listy uporządkowanej. Badanie złożoności algorytmu sortowania drzewiastego i algorytmu sortowania przez scalanie. Analiza złożoności algorytmu na przykładzie algorytmu wyznaczania powłoki wypukłej dla n punktów na płaszczyźnie. Górne i dolne ograniczenia złożoności problemu – problemy zamknięte i luki algorytmiczne (przykłady). Tempo wzrostu niektórych popularnych funkcji złożoności. Podział funkcji złożoności na wielomianowe oraz ponadwielomianowe. Algorytmy niedeterministycznie wielomianowe. Problemy algorytmiczne łatwo i trudno rozwiązywalne (klasa P i NP). Klasa problemów NPC (NP-zupełne). Przykłady problemów NP-zupełnych: problem ułożenia prostokąta z wielokątów, problem komiwojażera, problem przydziału i problem układania planu zajęć, problem spełnialności zdania logicznego, problem kolorowania mapy 3 kolorami, problem załadunku plecaka. Konsekwencje znalezienia algorytmu wielomianowego dla jednego z problemów NP-zupełnych; konsekwencje udowodnienia wykładniczego dolnego oszacowania dla jednego z problemów NP-zupełnych. Wykazywanie, że nowy problem jest NP-zupełny – przekształcanie problemów w czasie wielomianowym. Problemy nierozstrzygalne np. problem domina. Warianty problemu istnienia węża domino na obszarze: obszar ograniczony, płaszczyzna, półpłaszczyzna. Inne problemy nierozstrzygalne: problem odpowiedniości zbiorów słów, równoważność składniowa języków programowania, problem stopu w algorytmie. Problem okresowego domina jako wysoce nierozstrzygalny. Odmiany problemu domina: problem ograniczony ze stałą szerokością, problem ograniczony, problem nieograniczony, problem okresowy. Podział problemów algorytmicznych na łatwo rozwiązywalne, trudno rozwiązywalne, nierozstrzygalne i wysoce nierozstrzygalne. Deterministyczna maszyna Turinga – modelowanie podstawowych elementów składowych maszyny obliczeniowej. Podstawowe elementy diagramu przejść międzystanowych i jego budowa. Przykłady prostych maszyn Turinga: wykrywanie palindromów, dodawanie dwóch liczb. Teza Churcha-Turinga i jej konsekwencje. Siła klasy problemów obliczalnych, czyli niewrażliwość na zmianę modelu lub języka. Siła klas problemów P, NP i problemów o czasowej złożoności wykładniczej. Formalne definicje klas problemów P i NP w oparciu o maszynę Turinga (deterministyczną i nie). Wyznaczanie górnych ograniczeń dla złożoności problemu algorytmicznego z użyciem najbogatszego formalizmu i dowodzenie dolnych ograniczeń złożoności za pomocą maszyny Turinga. Inteligencja algorytmiczna – test Turinga. Reprezentacja wiedzy. Algorytmy uczące się. Rozgrywanie gier – analiza drzewa gry; strategia minimaksowa na drzewie gry. Algorytmy heurystyczne. Systemy ekspertowe. Maszynowe rozumienie języka naturalnego.
Literatura podstawowa
1. D.Harel: Rzecz o istocie informatyki. Algorytmika, WNT (2000).
2. A.J.Aho, J.E.Hopcroft, J.D.Ullman: Struktury danych i algorytmy, PWN (1983).
Literatura uzupełniająca
1. T.H.Cormen, C.E.Leiserson, R.L.Rivest: Wprowadzenie do algorytmów, WNT (2005).
2. L.Banachowski, A.Kreczmar: Elementy analizy algorytmów, WNT (1990, wyd. 2).
Punkty ECTS
4 - niestacjonarne,
4 - stacjonarne
Rodzaje studiów, na których przedmiot jest realizowany
niestacjonarne - 1-go stopnia,
stacjonarne - 1-go stopnia
Specjalności, na których przedmiot jest realizowany
Informatyka w telekomunikacji,
Bazy danych,
Inżynieria oprogramowania,
Komputerowe wspomaganie grafiki,
Sieci komputerowe
Prowadzący
dr inż. Grzegorz Borowik, dr inż. Jarosław Sikorski, dr inż. Mariusz Rawski, dr inż. Waldemar Jęda, dr Mirosława Nowicka
