Ta witryna wykorzystuje pliki cookie, dowiedz się więcej Zgadzam się
Czy wszystko można policzyć na komputerze?


O Kursie

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.

  1. Wprowadzenie
  2. Superkomputery i algorytmy
  3. 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
  4. 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
  5. 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:

  1. Wykład wprowadzający do kursu (video),
  2. Zeszyt dydaktyczny do kursu - w formacie PDF,
  3. Prezentacja PowerPoint do kursu - w formacie .ppt,
  4. Materiały dodatkowe,
  5. 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.

Certyfikat potwierdzający realizację kursu

certyfikat

O wykładowcy
Prof. dr hab. Maciej M. Sysło jest wykładowcą Uniwersytetu Wrocławskiego oraz Uniwersytetu Mikołaja Kopernika w Toruniu. Specjalizuje się w teorii grafów, matematyce dyskretnej, algorytmice, optymalizacji oraz dydaktyce informatyki. W latach 2010-2012 prowadził szkolenia z zakresu algorytmiki i programowania w ramach projektu Informatyka +. Prof. dr hab. Maciej M. Sysło jest koordynatorem merytorycznym w projekcie  „Informatyka – mój sposób na poznanie i opisanie świata – program nauczania informatyki z elementami przedmiotów matematyczno-przyrodniczych”