Teoria algorytmów i obliczeń

 

Wykład, realizacja - jesień 2024

  1. 3 X 2024. Sprawy organizacyjne. Opisanie zadania laboratoryjnego. Funkcje pierwotnie rekursywne, definicja, całkowitość. Przykłady funkcji pierwotnie rekursywnych: suma, iloczyn, potęga, silnia, ograniczona różnica, porównania, ograniczone suma i iloczyn, minimum ograniczone, dzielenie, reszta, dzielnik liczba dzielników, pierwszość, uzasadnienia pierwotnej rekursywności.
  2. 17 X 2024. Funkcje pierwotnie rekursywne: całkowitość, dowód; numeracja Cantora, dowód; numeracja Godla, szkic dowodu. Funkcja Ackermana, intuicja, definicja, własności, nieprzynależność do klasy funkcji pierwotnie rekursywnych.
  3. 24 X 2024. Hierarchia funkcji rekurencyjnych. Funkcja Ackermana - przynależność do klasy funkcji rekurencyjnych. Równoważność klasy funkcji rekurencyjnych (częściowo rekurencyjnych) i klasy maszyn Turinga z własnością stopu (klasy maszyn Turinga). Teza Churcha.
    - - - 31 X 2024. Wykład odwołany.
  4. 7 XI 2024. Podstawy teorii złożoności: problem, problem jako zbiór zadań, liczność zbioru zadań. Algorytm, operacje elementarne, operacje dominujące, funkcje złożoności czasowej i pamięciowej, ograniczenie dolne i górne oraz rząd funkcji. Rozmiar zadania. Algorytmy: złożoność czasowa pesymistyczna, złożoność pamięciowa. Rozmiar zadania problemu: wartość vs. długość zapisu, kryteria jednorone i logarytmiczne wyznaczania kosztów.

 

Ćwiczenia, realizacja - jesień 2024

Ćwiczenia prowadzi prof. Konstanty Junosza-Szaniawski

 

Laboratoria, realizacja - jesień 2024

Etapy realizacji zadania laboratoryjnego:

  • Etap wstępny realizacji zadania semestralnego obejmuje ustalenie składu zespołów i wybór projektu, terminem zaliczenia etapu wstępnego jest 15 października.
  • Pierwszy etap obejmuje przygotowanie dokumentacji algorytmów (opis, dowód poprawności, analiza złożoności). Termin oddania dokumentacji - nie później niż 5 listopada. Obecność obowiązkowa, zespół składa dokumentację w formacie pdf za pomocą poczty elektronicznej.
  • Drugi etap obejmuje oprogramowanie algorytmów i przygotowania przykładów. Termin realizacji tego etapu - nie później niż 27 listopada. Obecność obowiązkowa.
  • Trzeci etap obejmuje przygotowanie wersji końcowej programu, przeprowadzenie testów, przygotowanie sprawozdania z testów oraz przygotowanie pełnej wersji dokumentacji. Termin zaliczenia tego etapu - nie później niż 3 grudnia. Obecność obowiązkowa, zespół przekazuje wszystkie materiały za pomocą poczty elektronicznej.

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 laboratorium.
  • Nieobecność na którymkolwiek etapie to -20% z oceny etapu dla 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ą itp.), wówczas ocena danego etapu zostanie pomniejszona o 20%.

Uwaga:

  • Zespoły mogą uzgadniać indywidualny tryb zaliczania zajęć laboratoryjnych.

 

 

Wykład, realizacja - jesień 2023

  1. 5 X 2023. Sprawy organizacyjne. Opisanie zadania laboratoryjnego. Maszyny RAM z adresowaniem bezpośrednim, model uproszczony, przykłady maszyn RAM (programów).
  2. 12 X 2023. Maszyny RAM z adresowaniem pośrednim. Równoważność klas maszyn RAM z adresowaniem bezpośrednim, maszyn RAM z adresowaniem pośrednim i klas maszyn Turinga.
  3. 19 X 2023. Funkcje pierwotnie rekursywne, definicja, całkowitość. Przykłady funkcji pierwotnie rekursywnych: suma, iloczyn, potęga, silnia, ograniczona różnica, porównania, ograniczone suma i iloczyn, minimum ograniczone, dzielenie, reszta, dzielnik liczba dzielników, pierwszość, uzasadnienia pierwotnej rekursywności.
  4. 2 XI 2023. Funkcje pierwotnie rekursywne: całkowitość, dowód; numeracja Cantora, dowód; numeracja Godla, szkic dowodu. Funkcja Ackermana, intuicja, definicja, własności, nieprzynależność do klasy funkcji pierwotnie rekursywnych.
  5. 9 XI 2023. Funkcja Ackermana - przynależność do klasy funkcji rekurencyjnych. Hierarchie Grzegorczyka i R. Ritchie (informacja, niewymagana na zaliczenie). Teza Church'a. Równoważność klasy funkcji rekurencyjnych (częściowo rekurencyjnych) i klasy maszyn Turinga z własnością stopu (klasy maszyn Turinga). Teza Churcha.
  6. 16 XI 2023. Podstawy teorii złożoności: problem, problem jako zbiór zadań, liczność zbioru zadań. Algorytm, operacje elementarne, operacje dominujące, funkcje złożoności czasowej i pamięciowej, ograniczenie dolne i górne oraz rząd funkcji. Rozmiar zadania. Algorytmy: złożoność czasowa pesymistyczna, złożoność pamięciowa.
  7. 23 XI 2023. Rozmiar zadania problemu: wartość vs. długość zapisu, kryteria jednorone i logarytmiczne wyznaczania kosztów. Charakteryzacja przestrzeni problemów rozstrzygalnych: klasy problemów P, NP, co-NP. Transformacja wielomianowa. Klasa problemów NPC.
  8. 14 XII 2023. Twierdzenie Cook'a, twierdzenie Savitcha, studium literaturowe.
  9. 21 XII 2023. Twierdzenie Cook'a, twierdzenie Savitcha, uzupełnienia. Próby dowodu problemu P?=NP.
  10. 4 I 2024. Zaliczenie części teoretycznej.

 

Ćwiczenia, realizacja - jesień 2023

Ćwiczenia prowadzi dr hab. inż. M. Luckner

 

Laboratoria, realizacja - jesień 2023

Etapy realizacji zadania laboratoryjnego:

  • Etap wstępny realizacji zadania semestralnego obejmuje ustalenie składu zespołów i wybór projektu, terminem zaliczenia etapu wstępnego jest 16 października.
  • Pierwszy etap obejmuje przygotowanie dokumentacji algorytmów (opis, dowód poprawności, analiza złożoności). Termin oddania dokumentacji - nie później niż 7 listopada. Obecność obowiązkowa, zespół składa dokumentację w formacie pdf za pomocą poczty elektronicznej.
  • Drugi etap obejmuje oprogramowanie algorytmów i przygotowania przykładów. Termin realizacji tego etapu - nie później niż 28 listopada. Obecność obowiązkowa.
  • Trzeci etap obejmuje przygotowanie wersji końcowej programu, przeprowadzenie testów, przygotowanie sprawozdania z testów oraz przygotowanie pełnej wersji dokumentacji. Termin zaliczenia tego etapu - nie później niż 5 grudnia. Obecność obowiązkowa, zespół przekazuje wszystkie materiały za pomocą poczty elektronicznej.

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 laboratorium.
  • Nieobecność na którymkolwiek etapie to -20% z oceny etapu dla 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ą itp.), wówczas ocena danego etapu zostanie pomniejszona o 20%.

Uwaga:

  • Zespoły mogą uzgadniać indywidualny tryb zaliczania zajęć laboratoryjnych.

 

 

Wykład, realizacja - jesień 2022

  1. 6 X 2022, wykłady 1 i 2. Sprawy organizacyjne. Opisanie zadania laboratoryjnego.  Maszyny RAM, adresowanie bezpośrednie i pośrednie. Maszyna Turinga równoważna maszynie RAM z adresowaniem bezpośrednim.
  2. 13 X 2022, wykłady 3 i 4. Równoważność klas maszyn RAM z adresowaniem bezpośrednim, maszyn RAM z adresowaniem pośrednim i maszyn Turinga. Funkcje pierwotnie rekursywne, definicja, całkowitość. Przykłady funkcji pierwotnie rekursywnych: suma, iloczyn, potęga, silnia, ograniczona różnica, porównania, ograniczone suma i iloczyn.
  3. 27 X 2022, wykłady 5 i 6. Funkcje pierwotnie rekursywne cd., minimum ograniczone, dzielenie, reszta, dzielnik liczba dzielników, pierwszość, numeracje Cantora i Godla. Funkcja Ackermana, intuicja, definicja, własności, nieprzynależność do klasy funkcji pierwotnie rekursywnych.
  4. 3 XI 2022, wykłady 7 i 8. Funkcja Ackermana - przynależność do klasy funkcji rekurencyjnych. Hierarchie Grzegorczyka i R. Ritchie (informacja, niewymagana na zaliczenie). Teza Church'a. Równoważność klasy funkcji rekurencyjnych (częściowo rekurencyjnych) i klasy maszyn Turinga z własnością stopu (klasy maszyn Turinga).
  5. 10 XI 2022, wykłady 9 i 10. Teoria złożoności: problem, problem jako zbiór zadań, liczność zbioru zadań, algorytm, funkcje złożoności czasowej i pamięciowej, ograniczenie dolne i górne oraz rząd funkcji. Rozmiar zadania. Algorytmy: złożoność czasowa pesymistyczna, złożoność pamięciowa. Charakteryzacja przestrzeni problemów rozstrzygalnych: klasy problemów P, NP, co-NP. Transformacja wielomianowa. Klasa problemów NPC. Twierdzenie Cook'a (Cook-Levin).
  6. 24 XI 2022, wykłady 11 i 12. Złożoność pamięciowa, twierdzenie Savitcha, równość klas P-space i NP-space, klasy DlogSpace i PolylogSpace.
  7. 1 XII 2022, wykłady 13 i 14. Próby dowodu problemu P?=NP.
  8. 19 XII 2022. Zaliczenia.
  9. 12 I 2023. Zaliczenia poprawkowe.

 

Ćwiczenia, realizacja - jesień 2022

Ćwiczenia prowadzi dr inż. M. Luckner

 

Laboratoria, realizacja - jesień 2022

Etapy realizacji zadania laboratoryjnego:

  • Etap wstępny realizacji zadania semestralnego obejmuje ustalenie składu zespołów i wybór projektu, terminem zaliczenia etapu wstępnego jest 13 października.
  • Pierwszy etap obejmuje przygotowanie dokumentacji algorytmów (opis, dowód poprawności, analiza złożoności). Termin oddania dokumentacji - nie później niż 3 listopada. Obecność obowiązkowa, zespół składa dokumentację w formacie pdf za pomocą poczty elektronicznej.
  • Drugi etap obejmuje oprogramowanie algorytmów i przygotowania przykładów. Termin realizacji tego etapu - nie później niż 24 listopada. Obecność obowiązkowa.
  • Trzeci etap obejmuje przygotowanie wersji końcowej programu, przeprowadzenie testów, przygotowanie sprawozdania z testów oraz przygotowanie pełnej wersji dokumentacji. Termin zaliczenia tego etapu - nie później niż 8 grudnia. Obecność obowiązkowa, zespół przekazuje wszystkie materiały za pomocą poczty elektronicznej.

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 laboratorium.
  • Nieobecność na którymkolwiek etapie to -20% z oceny etapu dla 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ą itp.), wówczas ocena danego etapu zostanie pomniejszona o 20%.

Uwaga:

  • Zespoły mogą uzgadniać indywidualny tryb zaliczania zajęć laboratoryjnych.

 

 

Opis przedmiotu

 

Przedmiot Teoria algorytmów i obliczeń
Kierunek/Semestr Informatyka i systemy informacyjne/ sem VII
Rodzaj przedmiotu obowiązkowy
Odpowiedzialny prof. 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 z poprzedniego roku akademickiego

 

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 w czasie semestru przydzielonego problemu.
  • Zaliczenie części teoretycznej (ćwiczeń) według reguł obowiązujacych na ćwiczeniach.
  • Ocena z części teoretycznej (wykładu) jest ustalana na podstawie mieszanego (pisemnego/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ń i wykładu).