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ń 2017

  • 4 X 2017 (ś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.
  • 5 X 2017 (cz) Operacje dominujące. Jednorodne i logarytmiczne kryteria wyznaczania kosztu, kiedy stosować, przykład: złożoność algorytmu obliczania wartości funkcji f(n)=n^n.
  • 11 X 2017 (śr) Maszyny RAM, definicja, uproszczenie modelu maszyny, równoważność modelu podstawowego i uproszczonego, przykłady programów: konkatenacja zawartości rejestrów, kopiowanie zawartosci rejestru w kolejności odwrotnej, suma liczb binarnych.
  • 12 X 2017 (cz) Maszyny RAM z adresowaniem pośrednim, równoważność tej klasy maszyn z klasą maszyn Turinga. Ustalenie zasad zaliczania przedmiotu.
  • 18 X 2017 (śr) Funkcje pierwotnie rekursywne, całkowitość i obliczalność przez maszyny Turinga z własnościa stopu.
  • 19 X 2017 (cz) Funkcje pierwotnie rekursywne cd., ograniczona suma i iloczyn, operacja minimum efektywnego, iloraz reszta, podzielnik, liczba podzielników, liczba pierwsza.
  • 26 X 2017 (cz) Funkcje pierwotnie rekursywne cd., kodowanie Cantora i Godla. Funkcja Ackermana, własności, szkic dowodu, że nie jest pierwotnie rekursywna.
  • 2 XI 2017 (cz) Operacja minmum nieogranoczonego, klasy funkcji rekurencyjnych i częściowo rekurencyjnych. Rekurencyjność funkcji Ackermana. Równoważność klasy funkcji rekurencyjnych i klasy maszyn Turinga z własnością stopu oraz klasy funkcji częściowo rekurencyjnych i klasy maszyn Turinga, dowód, że klasy funkcji rekurencyjnych są obliczane przez odpowiadające klasy maszy Turinga.
  • 8 XI 2017 (śr) Dowód, że obliczenia maszyny Turinga są symulowane za pomocą funkcji rekurencyjnych. Wstęp do teorii złożoności: problemy decyzyjne rozstrzygalne, zbiór zadań problemów, transformacja wielomianowa, przechodniość transformacji wielomianowej.
  • 9 XI 2017 (cz) Klasy problemów P, NO, coNP, NPC, lemat o problemie NPC, twierdzenie Cooke'a, dowód.
  • 15 XI 2017 (śr) Święto Politechniki Warszawskiej, wykład odwołany.
  • 23 XI 2017 (cz)
  • 29 XI 2017 (śr)
  • 13 XII 2017, 10-12 - ankieta, 14-20 - zaliczenia.
  • zaliczenia, termin do uzgodnienia

Ćwiczenia, realizacja - jesień 2017

  • 4 X 2017. Charakteryzacja klasy 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.
  • 11 X 2017. Maszyny RAM, definicja, uproszczenie modelu maszyny, równoważność modelu podstawowego i uproszczonego, przykłady programów: konkatenacja zawartości rejestrów, kopiowanie zawartosci rejestru w kolejności odwrotnej, suma liczb binarnych.
  • 18 X 2017. Maszyny RAM, cd.
  • 8 XI 2017. Powtórzenie materiału.
  • 15 XI 2017. Święto Politechniki Warszawskiej, ćwiczenia odwołane,
  • 29 XI 2017
  • 13 XII 2017. Zaliczenia.

Wykład, realizacja - jesień 2016

  • 5 X 2016 (śr) Języki uniwersalny i przekątniowy oraz ich dopełnienia. Charakteryzacja klasy 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.
  • 6 X 2016 (cz) Sprawy organizacyjne. Prezentacja zadania laboratoryjnego. Wiadomości wstępne - problem, zadanie problemu, algorytm, operacje elementarne, operacje dominujące, funkcja kosztu, cdn.
  • 12 X 2016 (śr) Złożoność czasowa i pamięciowa, pesymistyczna (najgorszego przypadku) i średnia, jednorodne i logarytmiczne kryteria wyznaczania kosztów.
  • 13 X 2016 (cz) Maszyny RAM, definicja, uproszczenie modelu maszyny, równoważność modelu podstawowego i uproszczonego, przykłady programów: konkatenacja zawartości rejestrów, kopiowanie zawartosci rejestru w kolejności odwrotnej, suma liczb binarnych.
  • 19 X 2016 (śr) Równoważność klas maszyn RAM i maszyn Turinga.
  • 20 X 2016 (cz) Funkcje pierwotnie rekursywne, definicja, przykłady, dowód całkowitości i obliczalności przez maszyny Turinga z własnością stopu.
  • 26 X 2016 (śr) Sprawdzian dopuszczający. Funkcje pierwotnie rekursywne cd. operacja minimum ograniczonego, dzielenie i funkcje pochodne, numeracja Cantora.
  • 27 X 2016 (cz) Hierarchia funkcji rekurencyjnych, funkcja Ackermana: rekurencyjna, ale nie pierwotnie rekurencyjna.
  • 2 XI 2016 (śr) Symulacja obliczeń klas maszyn Turinga przez klasy funkcji rekurencyjnych. Teza Churcha. Hierarchie Grzegorczyka i Ritchiego - informacja.
  • 3 XI 2016 (cz) Transformacja wielomianowa, przechodniość. Charakteryzacja klasy problemów rozstrzygalnych. Klasy problemów NP, coNP, P, NPC.
  • 9 XI 2016 (śr) Twierdzenie Cook'a.
  • 16 XI 2016 (śr) Próby odpowiedzi na pytanie P=NP?
  • 17 XI 2016 (cz) Twierdzenie Savitcha.
  • 23 XI 2016 (śr) Sprawdzian końcowy.
  • 7 XII 2016, sala 329 (śr), godz. 10.15 Sprawdzian końcowy pierwszy termin dla osób uprawnionych, które nie przystąpiły do sprawdzianu 23 XI.
  • 14 grudnia 2016, godz. 15.00, 15 i 16 grudnia 2016, godz 16.00, pokój rozmów na IV/V piętrze. Konsultacje dotyczące zaliczenia sprawdzianu końcowego, zaliczenia przedmiotu i wpisy do dokumentów.
  • 9 stycznia 2017. Sprawdzian końcowy poprawkowy, szczegóły w zakładce "Ogłoszenia".

Ćwiczenia, realizacja - jesień 2016

  • 5 X 2016. Języki uniwersalny i przekątniowy oraz ich dopełnienia. Charakteryzacja klasy 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.
  • 12 X 2016. Definicje funkcji rozmiaru zadania (wartość, długość zapisu), kryteria wyznaczania kosztów, przykłady.
  • 19 X 2016. Równoważność klas maszyn RAM i maszyn Turinga.
  • 26 X 2016. Funkcje pierwotnie rekursywne: numeracja Godla. Funkcja Ackermana - wprowadzenie.
  • 2 XI 2016. Symulacja obliczeń klas maszyn Turinga przez klasy funkcji rekurencyjnych. Transformacja wielomianowa - definicja.
  • 16 XI 2016. Przykłady problemów NP zupełnych, dowody.
  • 21 XI 2016, godz. 12-16. Przygotowanie do sprawdzianu końcowego - konsultacje, sala 210
  • 1 XII 2016, 18.15, sala 102. Sprawdzianu dopuszczający poprawkowy.

Laboratoria, realizacja - jesień 2016

Etapy realizacji zadania laboratoryjnego:

  • Pierwszy etap realizacji zadania semestralnego obejmuje przygotowanie części programu dotyczącej komunikacji z użytkownikiem z uwzględnieniem wczytania danych i kontroli parametrów zadania, powinien być wykonany i rozliczony w październiku. 
  • Drugi etap obejmuje opracowanie metodologiczne i oprogramowanie zadania oraz prezentację rozwiązania na forum całej grupy. Ten etap należy wykonać i rozliczyć do połowy semestru.
  • Etap trzeci obejmuję przeprowadzenie testów empirycznych i sporządzenie dokumentacji zadania złożenie rozwiązania zadania i dokumentacji. Ponadto, wymagane jest sporządzenie dokumentacji technicznej programu. Ten etap należy wykonać i rozliczyć w listopadzie.

Uwagi:

  • Punktacja wykonania zadania: etap I - 15 punktów, etap II - 15 punktów, etap III - 70 pkt.
  • Każdy tydzień spóźnienia realizacji któregokolwiek etapu skutkuje odjęciem 9 punktów.
  • Wymagane:
    • dokumentacja kodu programu (szczegóły proszę uzgadniać z dr A. Jastrzębską),
    • sprawozdanie merytoryczne: nazwa zadania, opis zadania, metoda rozwiązania, opis danych testowych, opis wyników, wnioski.
  • Zachęcam Państwa do wykonania zadań przed wyznaczonymi terminami.

Oceny:

  • 51 - 60 punktów - dst
  • 61 - 70 punktów - dst+
  • 71 - 80 punktów - db
  • 81 - 90 punktów - db+
  • 91 - 100 punktów - bdb

Szczegółowy regulamin i harmonogram jest zamieszczony na stronie internetowej dr inż. Agnieszki Jastrzębskiej, współprowadzącej zajęcia laboratoryjne.



Wykład, realizacja - jesień 2015

  • 5 X 2015 (pn) Sprawy organizacyjne. Wiadomości wstępne - problem, zadanie problemu, algorytm, operacje elementarne, operacje dominujące, funkcja kosztu, złożoność czasowa pesymistyczna i średnia, złożoność pamięciowa, cdn.
  • 8 X 2015 (cz) Kryteria jednorodne i logarytmiczne wyznaczania kosztów, kiedy i jak stosować. Równoważność klas języków, problemów decyzyjnych i funkcji decyzyjnych. Klasy języków rekurencyjnych i rekurencyjnie przeliczalnych, problemów rozstrzygalnych i częściowo rozstrzygalnych, funkcji obliczalnych i częściowo obliczalnych. Języki uniwersalny i przekątniowy oraz ich dopełnienia, język kodów maszyn Turinga akceptujących niepuste języki.
  • 12 X 2015 (pn) Charakteryzacja klasy języków/problemów: rekurencyjne/rozstrzygalne, rekurencyjnie przeliczalne/częściowo rozstrzygalne i komplementarne do nich, przykłady języków z poszczególnych klas: Lu, Ld, Lnp, Lp, Lr, Lnr. Maszyny Turinga z wyrocznią, języki rekurencyjnie równoważne (równoważne w sposób rekurencyjnie przeliczalny), hierarchia pustości, rekurencyjna równoważność problemu akceptacji słowa przez maszynę Turinga i pierwszej klasy z hierarchii pustości z dowodem, rekurencyjne równoważność akceptowania przez maszynę Turinga wszystkich słów i drugiej klasy hierarchii pustości (bez dowodu).
  • 15 X 2015 (cz) Maszyny RAM, definicja modelu podstawowego; przykłady maszyn RAM: sprawdzenie parzystości liczby binarnej, sortowanie symboli w słowie binarnym, dodawanie liczb binarnych. Model okrojony i jego równoważność z modelem podstawowym
  • 19 X 2015 (pn) Równoważność klasy maszyn RAM i klasy maszyn Turinga, złożoność symulacji. Sprawdzian dopuszczający.
  • 22 X 2015 (cz) Funkcje pierwotnie rekursywne, definicja, całkowitość, obliczalność przez maszyny Turinga z własnością stopu, przykłady.
  • 26 X 2015 Funkcje pierwotnie rekursywne cd., operacja minimum ograniczonego, dzielenie i funkcje pokrewne, numeracje Cantora i Godla.(pn)
  • 29 X 2015 (cz) Operacja minimum nieograniczonego, funkcje regularne. Funkcje rekurencyjne i częściowo rekurencyjne. Rekurencyjność funkcji Ackermana. Hierarchia klas funkcji rekurencyjnych (ścisłe zawieranie). Obliczalność klas funkcji rekurencyjnych przez maszyny Turinga.
  • 2 XI 2015 (pn) Symulacja obliczeń klas maszyn Turinga przez klasy funkcji rekurencyjnych. Teza Churcha. Hierarchie Grzegorczyka i Ritchiego - informacja.
  • 5 XI 2015 (cz) Transformacja wielomianowa, definicja, przykład, dowód przechodniości, klasy problemów NP, coNP, EXP, P, NPC. Twierdzenie Cook'a, dowód (dokończenie na następnym wykładzie).
  • 9 XI 2015 (pn) Twierdzenie Cook'a, dowód (dokończenie). Twierdzenie Savitcha, dowód. Klasy problemów NP, coNP, EXP, P, NPC, P-space, Np-space, Relacje miedzy tymi problemami. Hierarchia wielomianowa problemów - informacja.
  • 19 XI 2015 (cz) Próby odpowiedzi na pytanie P=NP? Przykłady problemów NP zupełnych.
  • 26 XI 2015 (cz) przygotowanie do sprawdzianu końcowego.
  • 30 XI 2015 (pn) Sprawdzian końcowy.
  • 12 I 2016 (wt) 14.00, sala 329, sprawdzian końcowy, II termin.

Ćwiczenia, realizacja - jesień 2015

  • 5 X 2015. Prezentacja zadania laboratoryjnego. Kryteria jednorodne i logarytmiczne wyznaczania kosztów.
  • 12 X 2015. Charakteryzacja klasy języków/problemów: rekurencyjne/rozstrzygalne, rekurencyjnie przeliczalne/częściowo rozstrzygalne i komplementarne do nich, przykłady języków z poszczególnych klas: Lu, Ld, Lnp, Lp, Lr, Lnr. Analiza zadania laboratoryjnego w zakresie metodologii.
  • 19 X 2015. Równoważność klasy maszyn RAM i klasy maszyn Turinga, złożoność symulacji, dokończenie. Równoważność klas maszyn RAM z adresowaniem bezpośrednim i pośrednim.
  • 26 X 2015. Przykłady funkcji pierwotnie rekursywnych. Funkcja Ackermana - definicja i szkic dowodu, że nie jest pierwotnie rekursywana.
  • 2 XI 2015. Poprawa sprawdzianu dopuszczającego. Funkcje pierwotnie rekursywne - przykłady i dowody.
  • 9 XI 2015. Klasy problemów QL, NQL, NQLC, PLogSpace i NPLogSpace.
  • 23 XI 2015. Kontrola realizacji zadania laboratoryjnego
  • 15 XII 2015 (wt), 15.00, sala 329, sprawdzian dopuszczający, II termin.

Laboratoria, realizacja - jesień 2015

Etapy realizacji zadania laboratoryjnego:

  • Pierwszy etap realizacji zadania semestralnego obejmuje opracowanie i udokumentowanie metodologiczne zadania, powinien być wykonany i rozliczony w październiku. 
  • Drugi etap obejmuje oprogramowanie zadania i sporządzenie dokumentacji programu, należy wykonać i rozliczyć w listopadzie.
  • Trzeci etap obejmuje testy empiryczne oprogramowanych metod, dokumentację testów oraz integrację poszczególnych części dokumentacji, powinien być zrealizowany i rozliczony do połowy grudnia.

Uwagi:

  • Punktacja wykonania zadania: etapy I i II - po 25 pkt, etap III - 50 pkt.
  • Termin i sposób przedstawienia wyników poszczególnych etapów należy uzgodnić wcześniej z prowadzącymi zajęcia tak, by zdążyć w wyznaczonych terminach.
  • Każdy tydzień spóźnienia realizacji któregokolwiek etapu skutkuje odjęciem 7 punktów. Jedno spóźnienie w czasie realizacji dwóch pierwszych etapów nie jest karane.
  • Zachęcam Państwa do wykonania zadań przed wyznaczonymi terminami.

Oceny:

  • 51 - 60 punktów - dst
  • 61 - 70 punktów - dst+
  • 71 - 80 punktów - db
  • 81 - 90 punktów - db+
  • 91 - 100 punktów - bdb

Szczegółowy regulamin jest zamieszczony na stronie internetowej mgr Agnieszki Jastrzębskiej, współprowadzącej zajęcia laboratoryjne.


Wykład, realizacja - jesień 2014

  • 2 X 2014 (cz) Prezentacja zadania laboratoryjnego, cdn.
  • 6 X 2014 (pn) Wiadomości wstępne - problem, algorytm, operacje elementarne, operacje dominujące, funkcja kosztu, złożoność czasowa pesymistyczna i średnia, złożoność pamięciowa, cdn.
  • 9 X 2014 (cz) Wiadomości wstępne - zależność określenia rozmiaru od zakresu wartości, kryteria jednorodne i logarytmiczne, oszacowania asymptotyczne. Równoważność przestrzeni problemów decyzyjnych, języków i funkcji decyzyjnych. Modele obliczeń. Maszyny Turinga - powtórzenie: klasy języków rekurencyjnych i rekurencyjnie przeliczalnych, język uniwersalny, język przekątniowy i ich dopełnienia.
  • 13 X 2014 (pn) Charakteryzacja przestrzeni języków, języki rekurencyjnie przeliczalne i komplementarne do nich oraz nierekurencyjne. Maszyny Turinga z wyrocznią, hierarchia pustości, problem Posta (sformułowanie).
  • 16 X 2014 (cz) Maszyny RAM, definicja, proste programy, równoważność maszyn Turinga i maszyn RAM - szkic dowodu.
  • 20 X 2014 (pn) Klasa funkcji pierwotnie rekursywnych, definicja, całkowitość i obliczalność przez maszyny Turinga, przykłady.
  • 23 X 2014 (cz) Funkcje pierwotnie rekursywne, przykłady, kodowania Cantora i Godla.
  • 27 X 2014 (pn) Równoważność klas funkcji rekurencyjnych i częściowo rekurencyjnych oraz maszyn Turinga z własnością stopu i maszyn Turinga.
  • 30 X 2014 (cz) Wejściówka. Równoważność klas funkcji rekurencyjnych i częściowo rekurencyjnych oraz maszyn Turinga z własnością stopu i maszyn Turinga (cd).
  • 3 XI 2014 (pn) Hierarchie Grzegorczyka i Ritchiego, hipoteza Churcha. Transformacja wielomianowa, przechodniość transformacji wielomianowej. Klasy problemów NP, co-NP, P, Exp.
  • 13 XI 2014 (cz) Twierdzenie Cooka, dowód. Twierdzenie Savitcha, dowód.
  • 17 XI 2014 (pn) Próby odpowiedzi na pytanie P?=NP: p-izomorfizm, gęstość języków, klas NPI problemów, NP?=coNP. Klasy złożoności czasowej pamięciowej: P-space=NP-space, DLogk-space, DPolylog-space.
  • 20 XI 2014 (cz) Przygotowanie do sprawdzianu końcowego.
  • 24 XI 2014 (pn) Sprawdzian końcowy.
  • styczeń 2015 (miejsce i czas będą podane później w Ogłoszeniach) Sprawdzian końcowy - drugie podejście.

Ćwiczenia, realizacja - jesień 2014

  • 6 X 2014. Prezentacja zadania laboratoryjnego cd.
  • 13 X 2014. Charakteryzacja przestrzeni problemów/języków/funkcji, domkniętość klas języków rekurencyjnych i rekurencyjnie przeliczanych ze względu na operacje, przykłady języków rekurencyjnie przeliczalnych i nierekurencyjnych.
  • 20 X 2014. Równoważność maszyn Turinga i maszyn RAM.
  • 27 X 2014. Pierwotna rekurencyjność funkcji, przykłady.
  • 3 XI 2014. Redefinicja operacji minimum nieograniczonego dla funkcji częściowo rekurencyjnych. Schematy blokowe maszyn Turinga realizujących metody kompozycji funkcji. Interpretacje niedeterminizmu. Przykłady problemów klasy NP, problemy komplementarne.
  • 13 XI 2014. Zadanie laboratoryjne - uogólnienia.
  • 17 XI 2014. Wejściówka - analiza błędów.

Laboratoria, realizacja - jesień 2014

Etapy realizacji zadania laboratoryjnego:

  • Pierwszy etap realizacji zadania semestralnego należy wykonać w październiku. Pierwszy etap obejmuje oprogramowanie deterministycznego automatu skończonego jako klasyfikatora bez odrzucania elementów obcych, przygotowanie syntetycznych danych testowych, przeprowadzenie testów (dokumentacja nie jest wymagana).
  • Drugi etap realizacji zadania semestralnego należy wykonać w trzech pierwszych tygodniach listopada. Drugi etap obejmuje oprogramowanie automatu skończonego z ograniczonym niedeterminizmem oraz uwzględnienie odrzucania elementów obcych w obu typach automatu (detereministycznego i niedetereministycznego), uzupełnienie syntetycznych danych testowych, przeprowadzenie testów (dokumentacja nie jest wymagana).
  • Trzeci etap realizacji zadania semestralnego należy wykonać w listopadzie. Ten etap obejmuje oprogramowanie automatu rozmytego z uwzględnieniem klasyfikacji bez odrzucania i z odrzucaniem elementów obcych, przeprowadzenie testów (dokumentacja nie jest wymagana).
  • Czwarty etap realizacji zadania semestralnego do połowy grudnia. Ten etap obejmuje przygotowanie dokumentacji technicznej i merytorycznej do wszystkich poprzednich etapów.

Uwagi:

  • Punktacja wykonania zadania: etap I - 20 pkt, etapy II i III - 25 pkt, etap IV - 30 pkt.
  • Termin i sposób przedstawienia wyników poszczególnych etapów należy uzgodnić z prowadzącymi zajęcia tak, by zdążyć w wyznaczonych terminach.
  • Każdy tydzień spóźnienia realizacji któregokolwiek etapu skutkuje odjęciem 8 punktów. Pierwsze spóźnienie nie jest karany, pod warunkiem, że nie dotyczy ostatniego etapu.
  • Zachęcam Państwa do wykonania zadań przed wyznaczonymi terminami.

Zagadnienia 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 - jesień 2012

  • 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 praktycznej w bieżacym semestrze.
  • 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.