Uniwersytet Kardynała Stefana Wyszyńskiego w Warszawie - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Złożoność obliczeniowa

Informacje ogólne

Kod przedmiotu: WM-I-ZO Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Złożoność obliczeniowa
Jednostka: Wydział Matematyczno-Przyrodniczy. Szkoła Nauk Ścisłych
Grupy:
Strona przedmiotu: https://e.uksw.edu.pl/
Punkty ECTS i inne: 0 LUB 3.00 (w zależności od programu)
zobacz reguły punktacji
Język prowadzenia: polski
Dyscyplina naukowa, do której odnoszą się efekty uczenia się:

informatyka techniczna i telekomunikacja

Poziom przedmiotu:

średnio-zaawansowany

Symbol/Symbole kierunkowe efektów uczenia się:

I2_W01, I2_W11, I2_U01, I2_U06

Wymagania wstępne:

logika, algorytmy i struktury danych, matematyka dyskretna

Pełny opis:

Celem przedmiotu jest przekazanie wiedzy z zakresu podstaw złożoności obliczeniowej: maszyn abstrakcyjnych, modeli obliczeń oraz klas złożoności. Po zaliczeniu przedmiotu student powinien znać i rozumieć konsekwencje praktyczne przynależności problemu np. do klas P lub NP oraz różnic między algorytmem rozwiązującym dane zadanie a algorytmem heurystycznym lub aproksymacyjnym.

Efekty kształcenia i opis ECTS:

- zna i rozumie pojęcia problemów obliczeniowych i decyzyjnych, maszyn abstrakcyjnych, nierozstrzygalności, klas złożoności obliczeniowej oraz ich wzajemnych powiązań (I2_W01, I2_W11)

- potrafi skonstruować maszyny abstrakcyjne dla średnio skomplikowanych problemów decyzyjnych i obliczeniowych, potrafi analizować algorytmy pod kątem złożoności czasowej i pamięciowej, potrafi podać przykłady problemów należących do różnych klas złożoności (I2_U01, I2_U06)

szacunkowy nakład pracy studenta:

uczestnictwo w zajęciach 30 h

przygotowanie do zajęć 15 h

przygotowanie do weryfikacji 33 h

projekt 20 h

konsultacje z prowadzącym 2 h

Metody i kryteria oceniania:

Dla wszystkich efektów przyjmuje się następujące kryteria oceny we wszystkich formach weryfikacji:

ocena 5: osiągnięty w pełni (bez uchwytnych niedociągnięć)

ocena 4,5: osiągnięty niemal w pełni i nie są spełnione kryteria przyznania wyższej oceny

ocena 4: osiągnięty w znacznym stopniu i nie są spełnione kryteria przyznania wyższej oceny

ocena 3,5: osiągnięty w znacznym stopniu – z wyraźną przewagą pozytywów – i nie są spełnione kryteria przyznania wyższej oceny

ocena 3: osiągnięty dla większości przypadków objętych weryfikacją i nie są spełnione kryteria przyznania wyższej oceny

ocena 2: nie został osiągnięty dla większości przypadków objętych weryfikacją

Zajęcia w cyklu "Semestr zimowy 2019/20" (zakończony)

Okres: 2019-10-01 - 2020-01-31
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin więcej informacji
Wykład, 15 godzin więcej informacji
Koordynatorzy: Dorota Dąbrowska
Prowadzący grup: Dorota Dąbrowska
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzaminacyjny
E-Learning:

E-Learning (pełny kurs)

Typ przedmiotu:

obowiązkowy

Grupa przedmiotów ogólnouczenianych:

nie dotyczy

Wymagania wstępne:

Semantyka i weryfikacja programów

Zajęcia w cyklu "Semestr zimowy 2020/21" (zakończony)

Okres: 2020-10-01 - 2021-01-31
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 15 godzin więcej informacji
Wykład, 15 godzin więcej informacji
Koordynatorzy: Dorota Dąbrowska
Prowadzący grup: Dorota Dąbrowska
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzaminacyjny
E-Learning:

E-Learning (pełny kurs) z podziałem na grupy

Typ przedmiotu:

obowiązkowy

Grupa przedmiotów ogólnouczenianych:

nie dotyczy

Zajęcia w cyklu "Semestr zimowy 2021/22" (w trakcie)

Okres: 2021-10-01 - 2022-01-31
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Konwersatorium, 30 godzin więcej informacji
Koordynatorzy: Dorota Dąbrowska
Prowadzący grup: Dorota Dąbrowska
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzaminacyjny
E-Learning:

E-Learning (pełny kurs) z podziałem na grupy

Typ przedmiotu:

obowiązkowy

Grupa przedmiotów ogólnouczenianych:

nie dotyczy

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Kardynała Stefana Wyszyńskiego w Warszawie.