czy_wszystko_mozna_policzyc_na_komputerze.pps

Cel kursu
Celem kursu jest łagodne wprowadzenie do złożoności problemów i algorytmów.

Tematyka kursu
Przewodnim pytaniem kursu, jest jak dobrze sprawują się algorytmy i komputery i czy komputery już mogą wszystko obliczyć. Z jednej strony, dla niektórych problemów (jak znajdowanie najmniejszego elementu) znane są algorytmy, które nie mają konkurencji, gdyż są bezwzględnie najlepsze, a z drugiej – istnieją problemy, o których przypuszcza się, że komputery nigdy nie będą w stanie ich rozwiązywać dostatecznie szybko. Przedstawione zostaną problemy, dla których są znane algorytmy optymalne (tj. takie, których nie można już przyspieszyć), oraz takie problemy, których nie potrafimy rozwiązywać szybko, nawet z użyciem najszybszych komputerów. Problemy z tej drugiej grupy znajdują zastosowanie na przykład w kryptografii. Rozważania będą ilustrowane praktycznymi zastosowaniami omawianych problemów i ich metod obliczeniowych.

Wprowadzenie
Superkomputery i algorytmy
Przykłady trudnych problemów
3.1. Najkrótsza trasa zamknięta
3.2. Rozkład liczby na czynniki pierwsze
3.3. Podnoszenie do potęgi
3.4. Porządkowanie
Proste problemy i najlepsze algorytmy ich rozwiązywania
4.1. Znajdowanie elementu w zbiorze – znajdowanie minimum
4.2. Kompletowanie podium zwycięzców turnieju
4.3. Jednoczesne znajdowanie najmniejszego i największego elementu
4.4. Poszukiwanie elementów w zbiorze
4.4.1. Poszukiwanie elementu w zbiorze nieuporządkowanym
4.4.2. Poszukiwanie elementu w zbiorze uporządkowanym
4.5. Algorytmy porządkowania
4.5.1. Porządkowanie przez wybór
4.5.2. Porządkowanie przez scalanie
4.6. Obliczanie wartości wielomianu – schemat Hornera
Dwa trudne problemy, ponownie
5.1. Badanie złożoności liczb
5.2. Szybkie podnoszenie do potęgi
Struktura kursu
Kurs składa się z następujących elementów:

Wykład wprowadzający do kursu (video),
Zeszyt dydaktyczny do kursu - w formacie PDF,
Prezentacja PowerPoint do kursu - w formacie .ppt,
Test z pytaniami sprawdzającymi wiedzę
Sposób realizacji kursu
Kurs jest przeznaczony do realizacji w trybie samokształcenia lub pod kierunkiem nauczyciela. Po zapoznaniu się ze wszystkimi elementami kursu oraz wykonaniu testu sprawdzającego wiedzę, uczestnik otrzymuje prawo do samodzielnego wystawienia certyfikatu potwierdzającego zrealizowanie kursu e-learningowego „Czy wszystko można policzyć na komputerze ” przygotowanego przez Warszawską Wyższą Szkołę Informatyki.