Teoria algorytmów i obliczeń

 

Wykład, realizacja - jesień 2025

1. 2 X 2025. 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.
2. 9 X 2025. Przykłady funkcji pierwotnie rekursywnych: dzielenie, reszta, dzielnik liczba dzielników, pierwszość, numeracja Cantora, numeracja Godla. Funkcja Ackermana, intuicja, definicja, własności, uzasadnienia pierwotnej rekursywności.
3. 16 X 2025. Funkcja Ackermana, nieprzynależność do klasy funkcji pierwotnie rekursywnych. 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).
4. 23 X 2025. Teza Churcha. 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. 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ń 2025

Ćwiczenia prowadzi mgr Adam Mata

 

Laboratoria, realizacja - jesień 2025

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 14 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ż 4 listopada. Zespół składa dokumentację w formacie pdf za pomocą poczty elektronicznej lub na pendrive.
• Drugi etap obejmuje oprogramowanie algorytmów i przygotowania przykładów. Termin realizacji tego etapu - nie później niż 26 listopada. Testy będą przeprowadzone na komputerach wydziałowych bez zainstalowanych kompilatorów. Obecność całego zespołu 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ż 2 grudnia. Zespół składa materiały za pomocą poczty elektronicznej lub na pendrive. Obecność całego zespołu obowiązkowa.

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ń 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.
10. 9 I 2025. Zaliczenia.

 

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

 

 

 

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