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.
5. 21 XI 2024. Problemy, problemy decyzyjne, funkcje decyzyjne. Transformacja wielomianowa, definicja, przechodniość. Klasy problemów decyzyjnych: P, NP, coNP, NPC. Twierdzenie Cooka, dowód.
6. 28 XI 2024. Powtórzenie materiału, konsultacje, godziny dziekańskie.
7. 5 XII 2024. Charakteryzacja klasy problemów ze względu na złożoność pamięciową ich algorytmów, twierdzenie Savitcha, P-space=NP-space, hierarchia wielomianowa. (AJ)
8. 12 XII 2024. Równoważność klas problemów decyzyjnych, funkcji decyzyjnych, języków formalnych. Rozstrzygalność/obliczalność/rekurencyjność i pochodne tych pojęć. Próby dowodu problemu P?=NP.
9. 19 XII 2024. Powtórzenie materiału, konsultacje.

 

Ć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).