Nazwa przedmiotu:
Teoria algorytmów i obliczeń
Koordynator przedmiotu:
Prof. dr hab. inż. Władysław Homenda, Dr Michał Tuczyński
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Informatyka i Systemy Informacyjne
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
1120-IN000-ISP-0474
Semestr nominalny:
7 / rok ak. 2023/2024
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
1. godziny kontaktowe - 60 h; w tym a) obecność na wykładach – 30 h b) obecność na ćwiczeniach – 15 h c) obecność na laboratoriach – 15 h 2. praca własna studenta – 60 h, w tym a) zapoznanie z literaturą – 10 h b) przygotowanie do ćwiczeń – 10 h c) przygotowanie do sprawdzianów pisemnych – 10 h d) przygotowanie problemów laboratoryjnych –30 h Razem 120 h, co odpowiada 4 pkt. ECTS
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
1. obecność na wykładach – 30 h 2. obecność na ćwiczeniach – 15 h 3. obecność na laboratoriach – 15 h Razem 60 h, co odpowiada 2 pkt. ECTS
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
1. obecność na laboratoriach – 15 h 2. przygotowanie do sprawdzianów pisemnych – 10 h 3. przygotowanie problemów laboratoryjnych – 30 h Razem 55 h, co odpowiada 2 pkt. ECTS
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia15h
  • Laboratorium15h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Teoria automatów i języków formalnych Algorytmy i struktury danych
Limit liczby studentów:
Ćwiczenia – 30 os/grupa Laboratoria (ćwiczenia komputerowe) – 15-24 os/grupa
Cel przedmiotu:
Celem przedmiotu jest przekazanie wiedzy z teorii algorytmów, złożoności, rozstrzygalności, charakteryzacji klas problemów. Po ukończeniu kursu studenci powinni posiadać wiedzę i umiejętności sformułowane w tabeli efektów uczenia się.
Treści kształcenia:
Wykład: prowadzony metodą tradycyjną, treści omawiane w sali i zapisywane kredą na tablicy bez korzystania z nowoczesnych technik typu prezentacje. Taki przekaz umożliwia efektywne opanowanie przekazywanych treści. Ćwiczenia: podobnie jak wykład prowadzone są w sposób tradycyjny. Na ćwiczeniach uzupełniane są pomniejsze treści wykładu, rozwiązywane są problemy praktyczne dotyczące treści wykładu, a także powtarzane są trudniejsze kwestie z wykładu, np. powtarzane są trudne dowody fundamentalnych twierdzeń. Na ćwiczeniach zagadnienia są rozwiązywane na tablicy głównie przez studentów z pomocą prowadzącego. Laboratorium: polega na opracowaniu i oprogramowaniu algorytmu (dokładnego lub aproksymacyjnego) rozwiązania nietrywialnych problemów teorii złożoności oraz przygotowania raportu. Studenci pracują w zespołach 2-3-4 osobowych, wyznaczane są trzy terminy wykonania zadania laboratoryjnego, w tym termin złożenia pełnego projektu (programu i dokumentacji).
Metody oceny:
Do zaliczenia przedmiotu wymagane jest: - zaliczenie części teoretycznej i praktycznej w bieżącym semestrze, - zaliczenie części teoretycznej na podstawie dwóch kolokwiów, - zaliczenie części laboratoryjnej na podstawie rozwiązania przydzielonego problemu w czasie semestru; wymagana jest obecność na zajęciach laboratoryjnych w celu kontroli realizacji zdania laboratoryjnego, - ocena końcowa jest średnią z części teoretycznej i praktycznej.
Egzamin:
nie
Literatura:
1. J.E. Hopcroft, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, WNT. 2. A.V. Aho, J.E. Hopcroft, J.D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Company. 3. W. Homenda, Elementy lingwistyki matematycznej i teorii automatów, WPW. 4. P.B. Bovet, P. Crescenzi, Introduction to the theory of complexity, Prentice Hall. 5. M.B. Moret, The theory of computation, Addison-Wesley Publishing Company. 6. C.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa. 7. A. Yasuhara, Recursive function theory and logic, Academic Press. 8. F. Hennie, Introduction to computability, Addison-Wesley.
Witryna www przedmiotu:
Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Charakterystyka W01
Zna teoretyczne modele obliczeniowe: maszyny Turinga, gramatyki nieograniczone, maszyny RAM, funkcje rekurencyjne, jest świadomy uniwersalności modeli obliczeń i pojęcia obliczalności
Weryfikacja: aktywny udział w ćwiczeniach, sprawdzian pisemny
Powiązane charakterystyki kierunkowe: K_W01, K_W07
Powiązane charakterystyki obszarowe:
Charakterystyka W02
Zna podstawowe pojęcia teorii obliczalności: rozstrzygalność, częściowa rozstrzygalność, komplementarność częściowej rozstrzygalności, nierozstrzygalność
Weryfikacja: aktywny udział w ćwiczeniach, sprawdzian pisemny
Powiązane charakterystyki kierunkowe: K_W04, K_W08
Powiązane charakterystyki obszarowe:
Charakterystyka W03
Zna podstawowe pojęcia teorii złożoności: problemy jako przeliczalne zbiory zadań, algorytmy i ich złożoność, sposoby określania rozmiarów zadań, kryteria wyznaczania złożoności, równoważność klas problemów, języków i funkcji naturalnych
Weryfikacja: sprawdzian pisemny
Powiązane charakterystyki kierunkowe: K_W04, K_W08, K_W10
Powiązane charakterystyki obszarowe:

Profil ogólnoakademicki - umiejętności

Charakterystyka U01
Potrafi podać i uzasadnić charakterystykę przestrzeni problemów ze względu na ich rozstrzygalność, potrafi uzasadnić jakościową równoważność wybranych modeli obliczeń
Weryfikacja: aktywny udział w ćwiczeniach, sprawdzian pisemny, ocena rozwiązania problemu w ramach laboratorium
Powiązane charakterystyki kierunkowe: K_U01, K_U02, K_U04, K_U05, K_U08, K_U14
Powiązane charakterystyki obszarowe:
Charakterystyka U02
Potrafi skonstruować algorytmy rozwiązania prostych problemów w różnych modelach obliczeń, potrafi uzasadnić jakościową równoważność modeli obliczeniowych, potrafi uzasadnić ilościową równoważność wybranych modeli obliczeń
Weryfikacja: aktywny udział w ćwiczeniach, sprawdzian pisemny,
Powiązane charakterystyki kierunkowe: K_U01, K_U02, K_U04, K_U09, K_U11
Powiązane charakterystyki obszarowe:
Charakterystyka U03
Potrafi podać i uzasadnić charakterystykę przestrzeni problemów rozstrzygalnych ze względu na złożoność algorytmów rozwiązania problemów: klasy P, NP, coNP, NPC, Pspace, NPspace, relacje między tymi klasami
Weryfikacja: sprawdzian pisemny, ocena rozwiązania problemu w ramach laboratorium
Powiązane charakterystyki kierunkowe: K_U01, K_U09, K_U11, K_U14, K_U23
Powiązane charakterystyki obszarowe:

Profil ogólnoakademicki - kompetencje społeczne

Charakterystyka K01
Jest w stanie w sposób prosty wyjaśnić podstawowe zagadnienia teorii obliczalności, praktyczne ograniczenia metod obliczeniowych i teoretyczne granice obliczalności
Weryfikacja: udział w dyskusji
Powiązane charakterystyki kierunkowe: K_K01, K_K02, K_K04, K_K05
Powiązane charakterystyki obszarowe: