Politechnika
Warszawska

Katalog
ECTS

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. 2022/2023

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_U04, K_U05, K_U08, K_U14, K_U01, K_U02
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: