Ten efekt nie jest obsługiwany przez Twoją przeglądarkę. Możesz go wyłączyć klikając ikonę na dole strony.


Teoria algorytmów i obliczeń


Wykład, realizacja - jesień 2018

  • 3 X 2018 (śr) Sprawy organizacyjne. Wiadomości wstępne - problem, zadanie problemu, algorytm, operacje elementarne, operacje dominujące, funkcja kosztu, złożoność czasowa i pamięciowa, pesymistyczna (najgorszego przypadku) i średnia, cdn.
  • 4 X 2018 (cz) Opisanie zadania laboratoryjnego. Operacje dominujące. Jednorodne i logarytmiczne kryteria wyznaczania kosztu.
  • 11 X 2018 (cz) Wartość vs. logarytm z wartości jako rozmiar liczby, kryterium jednorodne vs. kryterium logarytmiczne, przykład. maszyny RAM, definicja, model uproszczony, przykład programu - suma dwóch liczb binarnych. Adresowanie bezpośrednie i pośrednie.
  • 17 X 2018 (śr) Równoważność klasy maszyn Turinga i klasy maszyn RAM z adresowaniem bezpośrednim, symulacja maszyn RAM z adresowaniem pośrednim za pomocą maszyn Turinga.
  • 18 X 2018 (cz) Funkcje pierwotnie rekursywne, definicja, przykłady. Właściwości funkcji pierwotnie rekursywnych: całkowite, obliczane przez maszyny Turinga z własnością stopu, dowody.
  • 24 X 2018 (śr) Funkcje pierwotnie rekursywne cd., ograniczona suma, ograniczony iloczyn, ograniczone minimum, dzielenie, reszta z dzielenia, podzielnik, liczba podzielników, pierwszość, kodowanie/dekodowanie Cantora.
  • 25 X 2018 (cz) Kodowanie/dekodowanie Godla. Funkcja Ackermana, własności, szkic dowodu, że nie jest pierwotnie rekursywna.
  • 8 XI 2018 (cz) Bogactwo klasy funkcji pierwotnie rekursywnych: hierarchia Ritchiego, hierarchia Grzegorczyka.
  • 14 XI 2018 (śr) Teza Churcha. Teoria złożoności: transformacja wielomianowa, przechodniość ternaformacji wielomianowej, klasy problemów P, NP, NPC, lemat o transformacji problemu NPC do problemu NP, problem SAT, twierdzenie Cook'a.
  • 15 XI 2018 (cz) Twierdzenie Cook'a, dowód. Klasy P-space i NP-space. Twierdzenie Savitcha, dowód.
  • 21 XI 2018 (śr) Twierdzenie Savitcha, uzupełnienia. Hierarchia wielominowa.
  • 22 XI 2018 (cz) Powtórzenie materiału. Ankieta samooceny.
  • 28 XI 2018 (śr) Zaliczenie części teoretycznej.
  • 29 XI 2018 (cz) Zaliczenie części teoretycznej.
  • 30 XI 2018 (cz) Zaliczenie części teoretycznej, godz. 16.15, sala 216.
  • 11 I 2019 (cz) Poprawa zaliczenia części teoretycznej, godz 16.15, sala 216.

Ćwiczenia, realizacja - jesień 2018

Ćwiczenia prowadzi dr Michał Tuczyński

  • 2/3 X 2018 (cz) Maszyny Turinga. Charakteryzacja klas języków: rekurencyjne, rekurencyjnie przeliczalne i komplementarne do nich, przykłady języków z poszczególnych klas: Lu, Ld, Lnp, Lp, Lr, Lnr.
  • 9/10 X 2018 (cz) Maszyny Turinga. Charakteryzacja klas języków: rekurencyjne, rekurencyjnie przeliczalne i komplementarne do nich, przykłady języków z poszczególnych klas: Lu, Ld, Lnp, Lp, Lr, Lnr - kontynuacja.
  • 16/17 X 2018 Maszyny RAM, przykłady programów: konkatenacja zawartości rejestrów, kopiowanie odwróconej zawartości rejestru, suma i iloczyn liczb binarnych.
  • 23/24 X Funkcje prymitywnie rekursywne, przykłady funkcji prymitywnie rekursywnych, ograniczone minimum, kodowanie i dekodowanie Cantora.
  • 30/31 X 2018 Numeracja Godla. Funkcja Ackermanna. Minimum nieograniczone. Funkcje rekurencyjne i częściowo rekurencyjne. Równoważność funkcji częściowo rekurencyjnych i rekurencyjnych z maszynami Turinga i maszynami Turinga z własnością stopu.
  • 6/7 XI 2018 Problemy decyzyjne i optymalizacyjne. Transformacja wielomianowa. Klasy P, NP, coNP, NPC. Przykłady problemów NP-zupełnych.
  • 13/14 XI 2018 Konsultacje.

Laboratoria, realizacja - jesień 2018

Etapy realizacji zadania laboratoryjnego:

  • Pierwszy etap realizacji zadania semestralnego obejmuje ustalenie składu zespołów i opracowanie koncepcji rozwiązania. Zaliczenie etapu jest w formie ustnej na zajęciach laboratoryjnych 16 października. Jeśli w zespole są osoby z różnych grup laboratoryjnych, należy wcześniej uzgodnić termin zaliczenia. Obecność wszystkich obowiązkowa.
  • Drugi etap obejmuje przygotowanie dokumentacji algorytmów (opis, analiza złożoności). Termin oddania dokumentacji - zajęcia laboratoryjne 6 listopada. Obecność obowiązkowa, zespół przynosi wydrukowaną i zszytą dokumentację.
  • Etap trzeci obejmuje oprogramowanie algorytmów i przygotowanie przykładów. Termin oddania programów i przykładów - zajęcia laboratoryjne 13 i 20 listopada. Obecność obowiązkowa, zespół prezentuje program na komputerze w laboratorium.
  • Etap czwarty obejmuje przeprowadzenie testów i przygotowanie sprawozdania z testów. Termin zaliczenia tego etapu - zajęcia laboratoryjne 27 listopada i 11 grudnia. Obecność obowiązkowa, zespół przynosi wydrukowaną i zszytą dokumentację oraz płytkę CD, na której znajduje się program oraz wszystka dokumentacja wytworzona w ramach projektu. Płytka jest opisana niezmywalnym markerem: nazwa przedmiotu (może być akronim), imiona i nazwiska członków zespołu, data oddania płytki.

Nie ma możliwości uzyskania punktów z laboratorium w postaci innej niż opisana powyżej.

Ocenianie:

  • Etap 1: -
  • Etap 2: 50% oceny
  • Etap 3: 25% oceny
  • Etap 4: 25% oceny

Uwagi:

  • Etapy 2-4 musża być wykonane co najmniej w połowie, żeby uzyskać zaliczenie.
  • Nieobecność na którymkolwiek z deadline’ów to -10% z oceny końcowej nieobecnego.
  • jeśli dokumentacja jest przygotowana w sposób niestaranny (z błędami językowymi, niechlujną notacją, nie jest zszyta lub wydrukowana itp.), wówczas od ocena danego etapu zostanie pomniejszona o pomiędzy 10 a 20%.

 

 

Zagadnienia z wykładu na zaliczenie sprawdzianu dopuszczającego

pojęcie problemu, zadania problemu i algorytmu, problemy decyzyjne i optymalizacyjne, problemy, języki, funkcje, definicja funkcji złożoności czasowej i pamięciowej, operacje dominujące, złożoność asymptotyczna, pesymistyczna, średnia, kryterium logarytmiczne i jednorodne wyznaczania złożoności,

 

Zagadnienia z wykładu na zaliczenie

  • Nierozstrzygalność:
    • maszyny Turinga – deterministyczne i niedeterministyczne, opis chwilowy, obliczenie, akceptacja, hierarchia Chomsky’ego,
    • domkniętość klasy języków rekurencyjnych i rekurencyjnie przeliczalnych,
    • języki przekątniowy i uniwersalny, ich miejsce w hierarchii Chomskyego z dowodami,
    • języki kodów maszyn Turinga akceptujących zbiór pusty i niepusty, rekurencyjny i nie rekurencyjny, ich miejsce w hierarchii Chomskyego z dowodami,
    • problem odpowiedniości Posta - definicja, zastosowanie,
    • maszyna Turinga z wyrocznią, hierarchia pustości, równoważność S1 i S2 z problemami akceptacji słowa przez maszynę Turinga (dowód) i akceptacji wszytkich słów,
  • Równoważność modeli obliczeń:
    • definicji maszyn RAM, implementacja prostych algorytmów na maszynach RAM,
    • równoważność z maszynami Turinga w sensie akceptowanych języków z uzasadnieniem,
    • równoważność maszyn RAM z maszynami Turinga w sensie złożoności algorytmów, idea dowodu.
  • Teoria funkcji rekurencyjnych:
    • klasa funkcji pierwotnie rekursywnych – definicje,
    • całkowitość i obliczalność przez maszyny Turinga funkcji pierwotnie rekursywnych z dowodami,
    • przykłady funkcji pierwotnie rekursywnych, dowody z definicji pierwotnej rekursywności prostych funkcji, dowody rekursywności wybranych funkcji (ograniczona suma, ograniczony iloczyn, ograniczone minimum, numery Cantora i Godla, dowody pierwotnej rekursywności kodowania i dekodowania Cantora,
    • funkcja Ackermana, definicja, idea konstrukcji, idea dowodu: funkcja Akermana nie jest pierwotnie rekursywna i jest rekurencyjna,
    • klasy funkcji rekurencyjnych (pierwotnie rekursywnych, rekurencyjnych, częściowo rekurencyjnych), definicje, hierarchia, uzasadnienia inkluzji.
  • Równoważność klas funkcji rekurencyjnych i klasy maszyn Turinga idea dowodu równoważności odpowiednich klas.
  • Teoria złożoności – charakteryzacja klasy problemów i języków:
    • transformacja wielomianowa problemów decyzyjnych i języków, definicje, przechodniość, przykłady,
    • klasy problemów ze względu na złożoność czasową: P, NP, NP-zupełne, coNP, coNP-zupełne, NPI, definicje, inkluzje, uzasadnienia,
    • NP-zupełność, przykłady problemów, twierdzenie Cook’a z dowodem, lemat w dowodzeniu NP-zupełności z dowodem,
    • klsay problemów ze względu na złożoność pamięciową: P-space, NP-space, DLOGSPACE, POLYLOGSPACE, definicje,
    • twierdzenie Savitcha z dowodem, zawieranie klas problemów,
    • relacje między klasami złożoności czasowej i pamięciowej.
  • Problem P?=NP, p-izomorfizm, gęstość języków, istnienie problemów NPI, relacje między klasami NP i coNP – definicje, relacje z pytaniem P?=NP.

Opis przedmiotu


Przedmiot Teoria algorytmów i obliczeń
Kierunek/Semestr Informatyka/ sem VIII
Rodzaj przedmiotu obowiązkowy
Prowadzący dr hab. inż. Władysław Homenda
Godziny tygodniowo i sposób zaliczenia 2 / 1 / 1 / 0 / zal
Kod przedmiotu ----

Program wykładu: patrz realizacja wykładu 2014


Program ćwiczeń:

Rozwiazanie przykładów teoretycznych i laboratoryjnych


Program laboratorium:

Problemy NP-zupełne, aproksymacja problemów NP-zupełnych.


Literatura podstawowa:

  • Aho A,V, Hopcroft J,E, Ullman J,D, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing Company,
  • Aho A,V, Hopcroft J,E, Ullman J,D, The design and Analysis of Computer Algorithms, Addison-Wesley Publishing Company,
  • Bovet P,B, Crescenzi P, Introduction to the theory of Complexity, Prentice Hall,
  • Moret M,B, The Theory of Computation, Addison-Wesley Publishing Company,
  • C. H. Papadimitriou, Złożonoscc obliczeniowa, WNT, Warszawa
  • Yasuhara A, Recursive Function Theory and Logic, Academic Press,

Przedmioty poprzedzajace:

Wstep do lingwistyki matematycznej i teorii automatów
Algorytmy i struktury danych


Regulamin zaliczenia przedmiotu:

  • Do zaliczenia przedmiotu wymagane jest zaliczenie części teoretycznej i zaliczenie części praktycznej, oba zaliczenia muszą być uzyskane  w bieżącym semestrze.
  • Ocena z przedmiotu jest średnią z ocen z części teoretycznej i praktycznej zaokrąglona w kierunku oceny z części teoretycznej.
  • Zaliczenie części teoretycznej następuje na podstawie bezbłędnego zaliczenia sprawdzianu dopuszczającego (pod koniec października) oraz zaliczenia sprawdzianu końcowego (pod koniec listopada). Do sprawdzianu końcowego można przystąpić po zaliczeniu sprawdzianu dopuszczającego. Ocena ze sprawdzianu końcowego jest oceną z części teoretycznej.
  • Zaliczenie części laboratoryjnej następuje na podstawie rozwiązania przydzielonego problemu w czasie semestru.
  • Wymagana jest obecność na zajeciach laboratoryjnych w celu kontroli realizacji zdania laboratoryjnego.