UNIWERSYTET ŁÓDZKI - Centralny System Uwierzytelniania

NA SKRÓTY
STUDENCI, PRACOWNICY
JEDNOSTKI ORGANIZACYJNE
PRZEDMIOTY
- Złożoność obliczeniowa algorytmów
STUDIA
AKADEMIKI
POMOC

Złożoność obliczeniowa algorytmów

Informacje ogólne

Kod przedmiotu:	1500-ILO5OA
Kod Erasmus / ISCED:	(brak danych) / (brak danych)
Nazwa przedmiotu:	Złożoność obliczeniowa algorytmów
Jednostka:	Wydział Fizyki i Informatyki Stosowanej
Grupy:
Punkty ECTS i inne:	0 LUB 3.00 (w zależności od programu) Podstawowe informacje o zasadach przyporządkowania punktów ECTS: roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS; tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h; 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się; tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS; nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta. zobacz reguły punktacji
Język prowadzenia:	(brak danych)
Forma studiów:	stacjonarne
Wymagania wstępne:	Student znalogikę matematyczną i teorię mnogości Student zna elementarne zagadnienia matematyki dyskretnej Student opanował podstawy algorytmówi struktur danych
Skrócony opis:	Celem zajęć jest zapoznanie studenta z naturą obliczeń, możliwościami i ograniczeniami współczesnych komputerów; prezentacja zadań obliczeniowych wymagających długiego czasu pracy komputera lub dużych zasobów pamięci
Pełny opis:	Celem zajęć jest zapoznanie studenta z naturą obliczeń, możliwościami i ograniczeniami współczesnych komputerów; prezentacja zadań obliczeniowych wymagających długiego czasu pracy komputera lub dużych zasobów pamięci
Efekty uczenia się:	Wiedza Student przywołuje przykłady problemów rozwiązywalnych i nierozwiązywalnych w sposób zautomatyzowany. Student definiuje złożoność czasową i pamięciową algorytmów. Student definiuje omawiane na zajęciach klasy złożoności oraz pojęcie problemu zupełnego w danej klasie. Umiejętności Student odróżnia problemy które mają jakiekolwiek rozwiązanie od tych dla których istnieją rozwiązania efektywne. Student określa złożoność czasową i pamięciową prostych programów. Student podaje przykłady problemów należących do omawianych klas złożoności a w szczególności problemów zupełnych w danej klasie. Kompetencje społeczne Student rozróżnia problemy rozwiązywalne i efektywnie rozwiązywalne.

Zajęcia w cyklu "Semestr zimowy 2023/2024" (zakończony)

Okres:	2023-10-01 - 2024-02-25	Wybrany podział planu: tygodniowy cykl przedmiotu Przejdź do planu PN LI WT ŚR W CZ PT
Typ zajęć:	Ćwiczenia informatyczne, 28 godzin więcej informacji Wykład, 14 godzin więcej informacji
Koordynatorzy:	Kordian Smoliński
Prowadzący grup:	Kordian Smoliński
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Przedmiot - Ocena zgodna z regulaminem studiów Ćwiczenia informatyczne - Ocena zgodna z regulaminem studiów Wykład - Ocena zgodna z regulaminem studiów
Informacje dodatkowe:	Uczestnictwo w zajęciach jest obowiązkowe.
Metody dydaktyczne:	Wykład 1 Metody podające \| Wykład informacyjny Laboratorium informatyczne lub pracownia fizyczna 1 Metody eksponujące \| Pokaz Metody podające \| Wykład konwersatoryjny Metody poszukujące \| Metoda ćwiczeniowa Metody poszukujące \| Metoda problemowa
Sposoby i kryteria oceniania:	OCENA KOŃCOWA Z PRZEDMIOTU jest ustalana zgodnie z algorytmem: Ocena z formy: "Wykład 1" ocena * 33.00 % + Ocena z formy: "Laboratorium informatyczne lub pracownia fizyczna 1" ocena * 67.00 % Dodatkowe warunki zaliczenia przedmiotu: Brak Ocena z formy "Wykład 1" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia: Test / quiz - 100.00% Ocena z formy "Wykład 1" ustalana jest na podstawie następującej skali: Poniżej 50.00% - ocena 2 50.00% i więcej - ocena 3 60.00% i więcej - ocena 3,5 70.00% i więcej - ocena 4 80.00% i więcej - ocena 4,5 90.00% i więcej - ocena 5 Dodatkowe warunki zaliczenia formy: Brak Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 1" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia: Zadanie / zadania praktyczne - 67.00% Aktywność na zajęciach - 33.00% Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 1" ustalana jest na podstawie następującej skali: Poniżej 50.00% - ocena 2 50.00% i więcej - ocena 3 60.00% i więcej - ocena 3,5 70.00% i więcej - ocena 4 80.00% i więcej - ocena 4,5 90.00% i więcej - ocena 5 Dodatkowe warunki zaliczenia formy: Brak
Treści kształcenia:	Wykład 1 Maszyna Turinga jako model obliczeń Teza Churcha-Turinga Złożoność czasowa i pamięciowa algorytmu Koszt jednostajny i koszt logarytmiczny Równoważność wielomianowa Probabilistyczna maszyna Turinga i niedeterministyczna maszyna Turinga Redukcje Klasy złożoności obliczeniowej Problemy NP-zupełne Laboratorium informatyczne lub pracownia fizyczna 1 Maszyna Turinga jako model obliczeń Teza Churcha-Turinga Złożoność czasowa i pamięciowa algorytmu Koszt jednostajny i koszt logarytmiczny Równoważność wielomianowa Probabilistyczna maszyna Turinga i niedeterministyczna maszyna Turinga Redukcje Klasy złożoności obliczeniowej Problemy NP-zupełne
Literatura:	Literatura podstawowa C. H. Papadimitriou, Złożoność obliczeniowa, Helion, Gliwice 2012. A. V. Aho, J. E. Hopcroft, J. D. Ullman, Projektowanie i analiza algorytmów, Helion, Gliwice 2003. Literatura dodatkowa I. Wegener, Complexity Theory, Springer, Berlin–Heidelberg 2005. Inne materiały dydaktyczne Notatki wykładowe

Zajęcia w cyklu "Semestr zimowy 2022/2023" (zakończony)

Okres:	2022-10-01 - 2023-02-19	Wybrany podział planu: tygodniowy cykl przedmiotu Przejdź do planu PN LI WT ŚR W CZ PT
Typ zajęć:	Ćwiczenia informatyczne, 28 godzin więcej informacji Wykład, 14 godzin więcej informacji
Koordynatorzy:	Kordian Smoliński
Prowadzący grup:	Kordian Smoliński, Zofia Stawska
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Przedmiot - Ocena zgodna z regulaminem studiów Ćwiczenia informatyczne - Ocena zgodna z regulaminem studiów Wykład - Ocena zgodna z regulaminem studiów
Informacje dodatkowe:	Uczestnictwo w zajęciach jest obowiązkowe.
Metody dydaktyczne:	Wykład 1 Metody podające \| Wykład informacyjny Laboratorium informatyczne lub pracownia fizyczna 1 Metody eksponujące \| Pokaz Metody podające \| Wykład konwersatoryjny Metody poszukujące \| Metoda ćwiczeniowa Metody poszukujące \| Metoda problemowa
Sposoby i kryteria oceniania:	OCENA KOŃCOWA Z PRZEDMIOTU jest ustalana zgodnie z algorytmem: Ocena z formy: "Wykład 1" ocena * 33.00 % + Ocena z formy: "Laboratorium informatyczne lub pracownia fizyczna 1" ocena * 67.00 % Dodatkowe warunki zaliczenia przedmiotu: Brak Ocena z formy "Wykład 1" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia: Test / quiz - 100.00% Ocena z formy "Wykład 1" ustalana jest na podstawie następującej skali: Poniżej 50.00% - ocena 2 50.00% i więcej - ocena 3 60.00% i więcej - ocena 3,5 70.00% i więcej - ocena 4 80.00% i więcej - ocena 4,5 90.00% i więcej - ocena 5 Dodatkowe warunki zaliczenia formy: Brak Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 1" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia: Zadanie / zadania praktyczne - 67.00% Aktywność na zajęciach - 33.00% Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 1" ustalana jest na podstawie następującej skali: Poniżej 50.00% - ocena 2 50.00% i więcej - ocena 3 60.00% i więcej - ocena 3,5 70.00% i więcej - ocena 4 80.00% i więcej - ocena 4,5 90.00% i więcej - ocena 5 Dodatkowe warunki zaliczenia formy: Brak
Treści kształcenia:	Wykład 1 Maszyna Turinga jako model obliczeń Teza Churcha-Turinga Złożoność czasowa i pamięciowa algorytmu Koszt jednostajny i koszt logarytmiczny Równoważność wielomianowa Probabilistyczna maszyna Turinga i niedeterministyczna maszyna Turinga Redukcje Klasy złożoności obliczeniowej Problemy NP-zupełne Laboratorium informatyczne lub pracownia fizyczna 1 Maszyna Turinga jako model obliczeń Teza Churcha-Turinga Złożoność czasowa i pamięciowa algorytmu Koszt jednostajny i koszt logarytmiczny Równoważność wielomianowa Probabilistyczna maszyna Turinga i niedeterministyczna maszyna Turinga Redukcje Klasy złożoności obliczeniowej Problemy NP-zupełne
Literatura:	Literatura podstawowa C. H. Papadimitriou, Złożoność obliczeniowa, Helion, Gliwice 2012. A. V. Aho, J. E. Hopcroft, J. D. Ullman, Projektowanie i analiza algorytmów, Helion, Gliwice 2003. Literatura dodatkowa I. Wegener, Complexity Theory, Springer, Berlin–Heidelberg 2005. Inne materiały dydaktyczne Notatki wykładowe

Zajęcia w cyklu "Semestr zimowy 2021/2022" (zakończony)

Okres:	2021-10-01 - 2022-01-23	Wybrany podział planu: tygodniowy cykl przedmiotu Przejdź do planu PN W LI WT ŚR CZ PT
Typ zajęć:	Ćwiczenia informatyczne, 28 godzin, 40 miejsc więcej informacji Wykład, 14 godzin, 40 miejsc więcej informacji
Koordynatorzy:	Kordian Smoliński
Prowadzący grup:	Kordian Smoliński, Zofia Stawska
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Przedmiot - Ocena zgodna z regulaminem studiów Ćwiczenia informatyczne - Ocena zgodna z regulaminem studiów Wykład - Ocena zgodna z regulaminem studiów
Informacje dodatkowe:	Uczestnictwo w zajęciach jest obowiązkowe.
Metody dydaktyczne:	Wykład 1 Metody podające \| Wykład informacyjny Laboratorium informatyczne lub pracownia fizyczna 1 Metody eksponujące \| Pokaz Metody podające \| Wykład konwersatoryjny Metody poszukujące \| Metoda ćwiczeniowa Metody poszukujące \| Metoda problemowa
Sposoby i kryteria oceniania:	OCENA KOŃCOWA Z PRZEDMIOTU jest ustalana zgodnie z algorytmem: Ocena z formy: "Wykład 1" ocena * 33.00 % + Ocena z formy: "Laboratorium informatyczne lub pracownia fizyczna 1" ocena * 67.00 % Dodatkowe warunki zaliczenia przedmiotu: Brak Ocena z formy "Wykład 1" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia: Test / quiz - 100.00% Ocena z formy "Wykład 1" ustalana jest na podstawie następującej skali: Poniżej 50.00% - ocena 2 50.00% i więcej - ocena 3 60.00% i więcej - ocena 3,5 70.00% i więcej - ocena 4 80.00% i więcej - ocena 4,5 90.00% i więcej - ocena 5 Dodatkowe warunki zaliczenia formy: Brak Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 1" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia: Zadanie / zadania praktyczne - 67.00% Aktywność na zajęciach - 33.00% Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 1" ustalana jest na podstawie następującej skali: Poniżej 50.00% - ocena 2 50.00% i więcej - ocena 3 60.00% i więcej - ocena 3,5 70.00% i więcej - ocena 4 80.00% i więcej - ocena 4,5 90.00% i więcej - ocena 5 Dodatkowe warunki zaliczenia formy: Brak
Treści kształcenia:	Wykład 1 Maszyna Turinga jako model obliczeń Teza Churcha-Turinga Złożoność czasowa i pamięciowa algorytmu Koszt jednostajny i koszt logarytmiczny Równoważność wielomianowa Probabilistyczna maszyna Turinga i niedeterministyczna maszyna Turinga Redukcje Klasy złożoności obliczeniowej Problemy NP-zupełne Laboratorium informatyczne lub pracownia fizyczna 1 Maszyna Turinga jako model obliczeń Teza Churcha-Turinga Złożoność czasowa i pamięciowa algorytmu Koszt jednostajny i koszt logarytmiczny Równoważność wielomianowa Probabilistyczna maszyna Turinga i niedeterministyczna maszyna Turinga Redukcje Klasy złożoności obliczeniowej Problemy NP-zupełne
Literatura:	Literatura podstawowa C. H. Papadimitriou, Złożoność obliczeniowa, Helion, Gliwice 2012. A. V. Aho, J. E. Hopcroft, J. D. Ullman, Projektowanie i analiza algorytmów, Helion, Gliwice 2003. Literatura dodatkowa I. Wegener, Complexity Theory, Springer, Berlin–Heidelberg 2005. Inne materiały dydaktyczne Notatki wykładowe

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

Okres:	2020-10-01 - 2021-02-07	Wybrany podział planu: tygodniowy cykl przedmiotu Przejdź do planu PN W WT LI ŚR W LI LI CZ PT
Typ zajęć:	Ćwiczenia informatyczne, 28 godzin, 40 miejsc więcej informacji Wykład, 14 godzin, 40 miejsc więcej informacji
Koordynatorzy:	Kordian Smoliński
Prowadzący grup:	Kordian Smoliński, Zofia Stawska
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Przedmiot - Ocena zgodna z regulaminem studiów Ćwiczenia informatyczne - Ocena zgodna z regulaminem studiów Wykład - Ocena zgodna z regulaminem studiów
Informacje dodatkowe:	Uczestnictwo w zajęciach jest obowiązkowe.
Metody dydaktyczne:	Wykład 1 Metody podające \| Wykład informacyjny Laboratorium informatyczne lub pracownia fizyczna 1 Metody eksponujące \| Pokaz Metody podające \| Wykład konwersatoryjny Metody poszukujące \| Metoda ćwiczeniowa Metody poszukujące \| Metoda problemowa
Sposoby i kryteria oceniania:	OCENA KOŃCOWA Z PRZEDMIOTU jest ustalana zgodnie z algorytmem: Ocena z formy: "Wykład 1" ocena * 33.00 % + Ocena z formy: "Laboratorium informatyczne lub pracownia fizyczna 1" ocena * 67.00 % Dodatkowe warunki zaliczenia przedmiotu: Brak Ocena z formy "Wykład 1" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia: Test / quiz - 100.00% Ocena z formy "Wykład 1" ustalana jest na podstawie następującej skali: Poniżej 50.00% - ocena 2 50.00% i więcej - ocena 3 60.00% i więcej - ocena 3,5 70.00% i więcej - ocena 4 80.00% i więcej - ocena 4,5 90.00% i więcej - ocena 5 Dodatkowe warunki zaliczenia formy: Brak Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 1" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia: Zadanie / zadania praktyczne - 67.00% Aktywność na zajęciach - 33.00% Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 1" ustalana jest na podstawie następującej skali: Poniżej 50.00% - ocena 2 50.00% i więcej - ocena 3 60.00% i więcej - ocena 3,5 70.00% i więcej - ocena 4 80.00% i więcej - ocena 4,5 90.00% i więcej - ocena 5 Dodatkowe warunki zaliczenia formy: Brak
Treści kształcenia:	Wykład 1 Maszyna Turinga jako model obliczeń Teza Churcha-Turinga Złożoność czasowa i pamięciowa algorytmu Koszt jednostajny i koszt logarytmiczny Równoważność wielomianowa Probabilistyczna maszyna Turinga i niedeterministyczna maszyna Turinga Redukcje Klasy złożoności obliczeniowej Problemy NP-zupełne Laboratorium informatyczne lub pracownia fizyczna 1 Maszyna Turinga jako model obliczeń Teza Churcha-Turinga Złożoność czasowa i pamięciowa algorytmu Koszt jednostajny i koszt logarytmiczny Równoważność wielomianowa Probabilistyczna maszyna Turinga i niedeterministyczna maszyna Turinga Redukcje Klasy złożoności obliczeniowej Problemy NP-zupełne
Literatura:	Literatura podstawowa C. H. Papadimitriou, Złożoność obliczeniowa, Helion, Gliwice 2012. A. V. Aho, J. E. Hopcroft, J. D. Ullman, Projektowanie i analiza algorytmów, Helion, Gliwice 2003. Literatura dodatkowa I. Wegener, Complexity Theory, Springer, Berlin–Heidelberg 2005. Inne materiały dydaktyczne Notatki wykładowe

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

Okres:	2019-10-01 - 2020-02-23	Wybrany podział planu: tygodniowy cykl przedmiotu Przejdź do planu PN WT ŚR W LI CZ PT LI
Typ zajęć:	Ćwiczenia informatyczne, 28 godzin więcej informacji Wykład, 14 godzin więcej informacji
Koordynatorzy:	Kordian Smoliński
Prowadzący grup:	Kordian Smoliński, Zofia Stawska
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Przedmiot - Ocena zgodna z regulaminem studiów Ćwiczenia informatyczne - Ocena zgodna z regulaminem studiów Wykład - Ocena zgodna z regulaminem studiów
Informacje dodatkowe:	Uczestnictwo w zajęciach jest obowiązkowe.
Metody dydaktyczne:	Wykład 1 Metody podające \| Wykład informacyjny Laboratorium informatyczne lub pracownia fizyczna 1 Metody eksponujące \| Pokaz Metody podające \| Wykład konwersatoryjny Metody poszukujące \| Metoda ćwiczeniowa Metody poszukujące \| Metoda problemowa
Sposoby i kryteria oceniania:	OCENA KOŃCOWA Z PRZEDMIOTU jest ustalana zgodnie z algorytmem: Ocena z formy: "Wykład 1" ocena * 33.00 % + Ocena z formy: "Laboratorium informatyczne lub pracownia fizyczna 1" ocena * 67.00 % Dodatkowe warunki zaliczenia przedmiotu: Brak Ocena z formy "Wykład 1" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia: Test / quiz - 100.00% Ocena z formy "Wykład 1" ustalana jest na podstawie następującej skali: Poniżej 50.00% - ocena 2 50.00% i więcej - ocena 3 60.00% i więcej - ocena 3,5 70.00% i więcej - ocena 4 80.00% i więcej - ocena 4,5 90.00% i więcej - ocena 5 Dodatkowe warunki zaliczenia formy: Brak Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 1" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia: Zadanie / zadania praktyczne - 67.00% Aktywność na zajęciach - 33.00% Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 1" ustalana jest na podstawie następującej skali: Poniżej 50.00% - ocena 2 50.00% i więcej - ocena 3 60.00% i więcej - ocena 3,5 70.00% i więcej - ocena 4 80.00% i więcej - ocena 4,5 90.00% i więcej - ocena 5 Dodatkowe warunki zaliczenia formy: Brak
Treści kształcenia:	Wykład 1 Maszyna Turinga jako model obliczeń Teza Churcha-Turinga Złożoność czasowa i pamięciowa algorytmu Koszt jednostajny i koszt logarytmiczny Równoważność wielomianowa Probabilistyczna maszyna Turinga i niedeterministyczna maszyna Turinga Redukcje Klasy złożoności obliczeniowej Problemy NP-zupełne Laboratorium informatyczne lub pracownia fizyczna 1 Maszyna Turinga jako model obliczeń Teza Churcha-Turinga Złożoność czasowa i pamięciowa algorytmu Koszt jednostajny i koszt logarytmiczny Równoważność wielomianowa Probabilistyczna maszyna Turinga i niedeterministyczna maszyna Turinga Redukcje Klasy złożoności obliczeniowej Problemy NP-zupełne
Literatura:	Literatura podstawowa C. H. Papadimitriou, Złożoność obliczeniowa, Helion, Gliwice 2012. A. V. Aho, J. E. Hopcroft, J. D. Ullman, Projektowanie i analiza algorytmów, Helion, Gliwice 2003. Literatura dodatkowa I. Wegener, Complexity Theory, Springer, Berlin–Heidelberg 2005. Inne materiały dydaktyczne Notatki wykładowe

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

Okres:	2018-10-01 - 2019-02-10	Wybrany podział planu: tygodniowy cykl przedmiotu Przejdź do planu PN WT ŚR W CZ LI PT
Typ zajęć:	Ćwiczenia informatyczne, 28 godzin więcej informacji Wykład, 14 godzin więcej informacji
Koordynatorzy:	Kordian Smoliński
Prowadzący grup:	Kordian Smoliński, Zofia Stawska
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Przedmiot - Ocena zgodna z regulaminem studiów Ćwiczenia informatyczne - Ocena zgodna z regulaminem studiów Wykład - Ocena zgodna z regulaminem studiów
Informacje dodatkowe:	Uczestnictwo w zajęciach jest obowiązkowe.
Metody dydaktyczne:	Wykład 1 Metody podające \| Wykład informacyjny Laboratorium informatyczne lub pracownia fizyczna 1 Metody eksponujące \| Pokaz Metody podające \| Wykład konwersatoryjny Metody poszukujące \| Metoda ćwiczeniowa Metody poszukujące \| Metoda problemowa
Sposoby i kryteria oceniania:	OCENA KOŃCOWA Z PRZEDMIOTU jest ustalana zgodnie z algorytmem: Ocena z formy: "Wykład 1" ocena * 33.00 % + Ocena z formy: "Laboratorium informatyczne lub pracownia fizyczna 1" ocena * 67.00 % Dodatkowe warunki zaliczenia przedmiotu: Brak Ocena z formy "Wykład 1" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia: Test / quiz - 100.00% Ocena z formy "Wykład 1" ustalana jest na podstawie następującej skali: Poniżej 50.00% - ocena 2 50.00% i więcej - ocena 3 60.00% i więcej - ocena 3,5 70.00% i więcej - ocena 4 80.00% i więcej - ocena 4,5 90.00% i więcej - ocena 5 Dodatkowe warunki zaliczenia formy: Brak Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 1" ustalana jest w oparciu o wyniki nastepujących składników zaliczenia: Zadanie / zadania praktyczne - 67.00% Aktywność na zajęciach - 33.00% Ocena z formy "Laboratorium informatyczne lub pracownia fizyczna 1" ustalana jest na podstawie następującej skali: Poniżej 50.00% - ocena 2 50.00% i więcej - ocena 3 60.00% i więcej - ocena 3,5 70.00% i więcej - ocena 4 80.00% i więcej - ocena 4,5 90.00% i więcej - ocena 5 Dodatkowe warunki zaliczenia formy: Brak
Treści kształcenia:	Wykład 1 Maszyna Turinga jako model obliczeń Teza Churcha-Turinga Złożoność czasowa i pamięciowa algorytmu Koszt jednostajny i koszt logarytmiczny Równoważność wielomianowa Probabilistyczna maszyna Turinga i niedeterministyczna maszyna Turinga Redukcje Klasy złożoności obliczeniowej Problemy NP-zupełne Laboratorium informatyczne lub pracownia fizyczna 1 Maszyna Turinga jako model obliczeń Teza Churcha-Turinga Złożoność czasowa i pamięciowa algorytmu Koszt jednostajny i koszt logarytmiczny Równoważność wielomianowa Probabilistyczna maszyna Turinga i niedeterministyczna maszyna Turinga Redukcje Klasy złożoności obliczeniowej Problemy NP-zupełne
Literatura:	Literatura podstawowa C. H. Papadimitriou, Złożoność obliczeniowa, Helion, Gliwice 2012. A. V. Aho, J. E. Hopcroft, J. D. Ullman, Projektowanie i analiza algorytmów, Helion, Gliwice 2003. Literatura dodatkowa I. Wegener, Complexity Theory, Springer, Berlin–Heidelberg 2005. Inne materiały dydaktyczne Notatki wykładowe

Zajęcia w cyklu "Semestr zimowy 2017/2018" (zakończony)

Okres:	2017-10-01 - 2018-02-09	Wybrany podział planu: tygodniowy cykl przedmiotu Przejdź do planu PN W LI WT ŚR CZ PT
Typ zajęć:	Ćwiczenia informatyczne, 30 godzin więcej informacji Wykład, 15 godzin więcej informacji
Koordynatorzy:	Kordian Smoliński
Prowadzący grup:	Kordian Smoliński
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Przedmiot - Ocena zgodna z regulaminem studiów Ćwiczenia informatyczne - Ocena zgodna z regulaminem studiów Wykład - Ocena zgodna z regulaminem studiów

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest UNIWERSYTET ŁÓDZKI.