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

  • 2 X 2019 (ś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.
  • 3 X 2019 (cz) Opisanie zadania laboratoryjnego. Operacje dominujące. Jednorodne i logarytmiczne kryteria wyznaczania kosztu.
  • 9 X 2019 (śr) Wartość vs. logarytm z wartości jako rozmiar liczby, kryterium jednorodne vs. kryterium logarytmiczne, przykład. Maszyny RAM, definicja, model uproszczony, równoważność modeli podstawowego i uproszczonego, przykłady prostych maszyn RAM (programów).
  • 10 X 2019 (cz) Maszyny RAM, dalsze przykłady maszyn RAM, realizacja operacji arytmetycznych, złożoność obliczeniowa operacji arytmetycznych. Maszyny RAM z adresowaniem pośrednim. Równoważność klasy maszyn RAM z adresowaniem bezpośrednim i klasy maszyn Turinga.
  • 16 X 2019 (śr) Maszyny RAM, równoważność klas maszyn RAM z adresowaniem bezpośrednim i pośrednim oraz klasy maszyn Turinga, przykłady.
  • 17 X 2019 (cz) Funkcje pierwotnie rekursywne, definicja, przykłady: suma, iloczyn itd., ograniczona suma, ograniczony iloczyn, ograniczone minimum.
  • 23 X 2019(śr) Ograniczone minimum - dowód pierwotnej rekursywności. Właściwości funkcji pierwotnie rekursywnych: całkowite, obliczane przez maszyny Turinga z własnością stopu, dowody. Funkcje pierwotnie rekursywne cd., dzielenie, reszta z dzielenia, podzielnik, liczba podzielników, pierwszość, kodowanie/dekodowanie Cantora. Kodowanie/dekodowanie Godla.
  • 24 X 2019 (cz) Funkcja Ackermana, własności, szkic dowodu, że nie jest pierwotnie rekursywna. Rzut oka na hierarchię funkcji rekurencyjnych.
  • 7 XI 2019 (cz) Funkcja Ackermana, szkic dowodu, że jest rekurencyjna. Rzut oka na hierarchię funkcji rekurencyjnych, ścisłe zawieranie. Równoważność klas maszyn Turinga i klas funkcji rekurencyjnych, szkic dowodów.
  • 14 XI 2019 (cz) Bogactwo klasy funkcji pierwotnie rekursywnych: hierarchia Ritchiego, hierarchia Grzegorczyka - informacja, bogactwo klasy funkcji pierwotnie rekursywnych. Teoria złożoności: transformacja wielomianowa, przechodniość ternaformacji wielomianowej, klasy problemów P, NP, coNP.
  • 20 XI 2019 (śr) Problem SAT, twierdzenie Cook'a, dowód.
  • 21 XI 2019 (cz) Twierdzenie Savitcha, uzupełnienia. Klasy P-space i NP-space.
  • 4 XII 2019 (śr) Zagadnienia zaawansowane, uwagi o przedmiocie.

Ćwiczenia, realizacja - jesień 2019

Ćwiczenia prowadzi dr Michał Tuczyński

  • 2/8 X 2019 Domkniętość klas języków regularnych, bezkontekstowych, kontekstowych, rekurencyjnych, rekurencyjnie przeliczalnych ze względu na operacje sumy, przecięcia, dopełnienia, konkatenacji, gwiazdki Kleene'ego. Maszyny Turinga.
  • 9/15 X 2019 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.
  • 16/22 X 2019 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. Maszyny RAM.
  • 23/29 X 2019 Maszyny RAM, przykłady programów: konkatenacja zawartości rejestrów, kopiowanie odwróconej zawartości rejestru, suma i iloczyn liczb binarnych.
  • 30 X/5 XI 2019 Funkcje prymitywnie rekursywne, przykłady funkcji prymitywnie rekursywnych, ograniczone minimum, numeracja Cantora, numeracja Godla.
  • 6/12 XI 2019 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.
  • 19/20 XI 2019 Problemy decyzyjne i optymalizacyjne. Transformacja wielomianowa. Klasy P, NP, coNP, NPC. Przykłady problemów NP-zupełnych.

Laboratoria, realizacja - jesień 2019

Etapy realizacji zadania laboratoryjnego:

  • Etap wstępny realizacji zadania semestralnego obejmuje ustalenie składu zespołów i opracowanie koncepcji rozwiązania. Zaliczenie etapu jest w formie ustnej na zajęciach laboratoryjnych do 22 października.
  • Pierwszy etap obejmuje przygotowanie dokumentacji algorytmów (opis, analiza złożoności). Termin oddania dokumentacji - nie później niż na zajęciach 4/5 listopada. Obecność obowiązkowa, zespół przynosi wydrukowaną i zszytą dokumentację.
  • Drugi etap obejmuje oprogramowanie algorytmów i przygotowanie przykładów. Termin oddania programów i przykładów - nie później niż na zajęciach 18/19 listopada. Obecność obowiązkowa, zespół prezentuje program na komputerze w laboratorium.
  • Trzeci etap obejmuje przeprowadzenie testów i przygotowanie sprawozdania z testów. Termin zaliczenia tego etapu - nie później niż na zajęciach. 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 wstępny: -
  • Etap 1: 33% oceny
  • Etap 3: 33% oceny
  • Etap 4: 34% oceny

Uwagi:

  • Zespoły są zobowiązane uczestniczyć w zajęciach poszczególnych etapów zgodnie z planem zajęć. Jeśli w zespole są osoby z różnych grup laboratoryjnych, zespół uczestniczy w zajęciach grupy laboratoryjnej tej osoby, której zajęcia są najwcześniej. Obecność wszystkich jest obowiązkowa.
  • Etapy 1-3 muszą być wykonane co najmniej w połowie, żeby uzyskać zaliczenie.
  • Nieobecność na którymkolwiek etapie to -20% z oceny etapu osoby nieobecnej, spóźnienie zespołu to -20% oceny etapu każdej osoby z zespołu za każdy tydzień spóźnienia licząc od drugiego tygodniowego spóźnienia.
  • 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 20%.

 


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 etapie 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 (ćwiczeń) i zaliczenie części praktycznej, oba zaliczenia muszą być uzyskane  w bieżącym semestrze.
  • Wymagana jest obecność na zajeciach laboratoryjnych w celu kontroli realizacji zdania laboratoryjnego.
  • Zaliczenie części laboratoryjnej następuje na podstawie rozwiązania przydzielonego problemu w czasie semestru.
  • Zaliczenie części teoretycznej (ćwiczeń) według reguł obowiązujacych na ćwiczeniach.
  • Ocena z części teoretycznej (wykładu) jest ustalana na podstawie ustnego sprawdzianu.
  • Ocena z przedmiotu jest średnią ważoną z ocen z części teoretycznej (ćwiczeń i wykładu) i praktycznej zaokrągloną w kierunku oceny z części teoretycznej (ćwiczeń).
  • Ocena z przedmiotu jest ustalona za pomocą formuły: max{3, 3+(L-3)/4+(Ć-3)/4+(W-3)/2}, gdzie L, Ć i W są ocenami z laboratoriom, ćwiczeń i wykładu, L, Ć, W są w skali 2, 3, 3.5, 4, 4.5, 5 oraz L>2 i Ć>2.