Your browser doesn't support this content. You can turn it off by clicking on/off icon on the footer area of the page.


Algorytmy, złożoność obliczeniowa, granice obliczalności



Wykład prowadzony w latach 2007 - 2010



Wykład, realizacja - wiosna 2010


  • 25 II 2010. Problem, algorytm, rozmiar zadania, funkcje złożoności, złożoność pesymistyczna i średnia, czasowa, pamięciowa, oszacowania asymptotyczne.
  • 4 III 2010. Kryteria jednorodne i logarytmiczne wyznaczania kosztów. Reprezentacja liczb stałopozycyjna i zmiennopozycyjna.
  • 11 III 2010. Tablice, listy drzewa, kolejki, stosy, kopce, kolejki priorytetowe. Rekuremcja vs. programowanie dynamiczne, obliczanie wyrazów ciągu Fibonacciego za pomocą obu metod.
  • 18 III 2010. Rekuremcja vs. programowanie dynamiczne, sortowanie przez scalanie za pomocą obu metod. Sortowanie przez kopcowanie. Dolne ograniczenie złożoności algorytmów sortowania przez porównania elementów. Sortowanie szybkie. Metody elementarne sortowania (bąbelkowa, przez wybór, przez wstawianie).
  • 25 III 2010. Sortowanie Shella. Obniżanie złożoności za pomocą dodatkowych założeń: sortowanie przez zliczanie, sortowanie kubełkowe. Wyszukiwanie, metody liniowa, połowienia, interpolacyjna.
  • 1 IV 2010. Binarne drzewa wyszukiwania, operacje wyszukiwania, wstawiania, usuwania. Drzewa zrównoważone, drzewa AVL, B-drzewa, 2-drzewa i drzewa czerwono-czarne.
  • 8 IV 2010. Mieszanie, metody usuwania kolizji, konstrukcja funkcji mieszających.
  • 15 IV 2010. Studium literaturowe: klasa uniwersalna funkcji mieszających, konstrukcja klasy uniwersalnej funkcji mieszających w oparciu o ciało Zp.
  • 22 IV 2010. Metody reprezentacji grafów. Przeglądanie grafów metodami w głab i wszerz. Algorytmy najkrótszych dróg Forda-Bellmana i Dijkstry.
  • 29 IV 2010. Przepływy w sieciach, wyznaczanie przepływu maksymalnego, algorytm Forda-Fulkersona.
  • 6 V 2010. Charakteryzacja klasy funkcji decyzyjnych. Klasy funkcji obliczalnych, częściowo obliczalnych, komplementarnych do częściowo obliczalnych, nie obliczalnych. Funkja przekątniowa, funkcja uniwersalna.
  • 13 V 2010. Funkcje pustości i niepustości oraz rozstrzygalności i nierozstrzygalności.
  • 20 V 2010. Niedeterminizm. Klasy złożoności P, NP, coNP, NPC. Problem P=?NP.