Uniwersytet Mikołaja Kopernika w Toruniu - Centralny punkt logowaniaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Podstawy teorii obliczalności

Informacje ogólne

Kod przedmiotu: 1000-Z1PTO Kod Erasmus / ISCED: (brak danych) / (0613) Tworzenie i analiza oprogramowania i aplikacji
Nazwa przedmiotu: Podstawy teorii obliczalności
Jednostka: Wydział Matematyki i Informatyki
Grupy: Inf., I st., niestacjonarne, 3 rok, przedmioty obowiązkowe
Strona przedmiotu: https://plas.mat.umk.pl/moodle/course/view.php?id=151
Punkty ECTS i inne: 4.00
zobacz reguły punktacji
Język prowadzenia: polski
Wymagania wstępne:

Znajomość podstawowych pojęć algorytmiki, teorii mnogości oraz matematyki dyskretnej.

Całkowity nakład pracy studenta:

wykład – 20 godzin

ćwiczenia – 20 godzin

konsultacje z prowadzącymi zajęcia – 20 godzin

egzamin – 4 godziny

praca własna (rozwiązywanie zadań, studiowanie literatury) – 20 godzin

przygotowanie do egzaminu – 26 godzin

RAZEM: 110 godzin (4 punktów ECTS)


Efekty uczenia się - wiedza:

Student:

W1. Ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną w zakresie

programowania, algorytmów i złożoności, języków formalnych i automatów, języków i paradygmatów programowania (K_W02).

W2. Zna podstawowe metody projektowania, analizowania i programowania algorytmów (projektowanie strukturalne, rekurencja, złożoność obliczeniowa) (K_W04).

Efekty uczenia się - umiejętności:

Student:

U1. Potrafi zastosować wiedzę matematyczną do formułowania, analizowania i

rozwiązywania zadań informatycznych (K_U01).

U2. Potrafi pozyskiwać informacje z literatury, baz wiedzy, Internetu

oraz innych wiarygodnych źródeł, integrować je, dokonywać ich interpretacji oraz wyciągać wnioski i formułować opinie (K_U02).

U3. Projektuje, analizuje pod kątem poprawności i złożoności obliczeniowej oraz programuje algorytmy; wykorzystuje podstawowe techniki algorytmiczne i struktur danych (K_U07).

U4. Potrafi ocenić, na podstawowym poziomie, przydatność rutynowych metod i narzędzi informatycznych oraz wybrać i zastosować właściwą metodę i narzędzia do konkretnych zadań informatycznych (K_U23).


Efekty uczenia się - kompetencje społeczne:

Student:

K1. Myśli twórczo w celu udoskonalenia istniejących bądź stworzenia nowych rozwiązań.

K2. Jest nastawiony na jak najlepsze wykonanie zadania; dba o szczegóły; jest systematyczny.

K3. Skutecznie przekazuje innym swoje myśli w zrozumiały sposób; właściwie posługuje się terminologią fachową; potrafi nawiązać kontakt w obrębie swojej dziedziny i z osobą reprezentującą inną dziedzinę.

K4. Jest nastawiony na nieustanne zdobywanie nowej wiedzy, Umiejętności i doświadczeń; rozumie potrzebę ciągłego doskonalenia się i podnoszenia kompetencji zawodowych.

K5. W pełni samodzielnie realizuje uzgodnione cele, podejmując samodzielne i czasami trudne decyzje; potrafi samodzielnie wyszukiwać informacje w literaturze.

K6. Pracuje systematycznie i posiada umiejętność pozytywnego podejścia do trudności stojących na drodze do realizacji założonego celu; dotrzymuje terminów.


Metody dydaktyczne podające:

- wykład informacyjny (konwencjonalny)

Metody dydaktyczne poszukujące:

- ćwiczeniowa

Skrócony opis:

Celem przedmiotu jest przedstawienie podstawowych zagadnień teorii obliczalności, teorii złożoności obliczeniowej i lingwistyki matematycznej

Pełny opis:

1. Wyrażenia i języki regularne,

2. Automaty skończone

3. Twierdzenie Kleene’go

4. Lemat o pompowaniu dla języków regularnych

5. Gramatyki. Hierarchia Chomsky'ego

6. Automaty ze stosem

7. Maszyny licznikowe

8. Maszyny Turinga

9. Czasowa i pamięciowa złożoność obliczeniowa

10. Rozstrzygalność i nierozstrzygalność

Literatura:

• J. E. Hopcroft, J. D. Ullman, Wprowadzenie do teorii automatów, jezyków i obliczeń

• M. Sipser, Wprowadzenie do teorii obliczeń

• Kościelski, Teoria obliczeń. Wykłady z matematycznych podstaw informatyki.

• M. Foryś, W. Foryś, Teoria automatów i języków formalnych

• Blikle, Automaty i gramatyki

• S. Eilenberg, Automata, Languages and Machines

• Christos H. Papadimitriou, Złożoność obliczeniowa

• David Harel, Rzecz o istocie informatyki: algorytmika

Metody i kryteria oceniania:

Kryteria oceniania ćwiczeń:

Zaliczenie na ocenę na podstawie:

• wyników z kolokwiów (co najmniej 1) [W1,W2,U1,U3,U4,K1,K2,K3]

• wyników wejściówek [W1,W2,U1,U3,U4,K1,K2,K3,K4,K6]

• wyników uzyskanych za samodzielne wykonanie zadań domowych rozwiązywanych przez cały semestr [W1,W2,U1,U2,U3,U4,K1,K2,K3,K4,K5,K6]

• aktywności na zajęciach [W1,W2,U1,U3,U4,K1,K2,K3,K4,K5,K6] .

Dodatkowo na ocenę końcową składają się:

• systematyczność

• rozwiązywanie zadań dla chętnych

• obecność.

Dopuszczalny limit nieobecności na zajęciach – 2 razy.

Uwaga: Zwolnienie lekarskie należy dostarczyć w terminie 2 tygodni od nieobecności.

Zaliczenie wykładu: egzamin pisemny [W1,W2,U1,U2,U3,U4,K1,K2,K3,K4,K5,K6].

Zajęcia w cyklu "Rok akademicki 2017/18" (zakończony)

Okres: 2017-10-01 - 2018-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 20 godzin, 30 miejsc więcej informacji
Wykład, 20 godzin, 30 miejsc więcej informacji
Koordynatorzy: Kamila Barylska
Prowadzący grup: Kamila Barylska
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Rok akademicki 2018/19" (zakończony)

Okres: 2018-10-01 - 2019-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 20 godzin, 30 miejsc więcej informacji
Wykład, 20 godzin, 65 miejsc więcej informacji
Koordynatorzy: Kamila Barylska
Prowadzący grup: Kamila Barylska
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Rok akademicki 2019/20" (zakończony)

Okres: 2019-10-01 - 2020-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 20 godzin, 30 miejsc więcej informacji
Wykład, 20 godzin, 65 miejsc więcej informacji
Koordynatorzy: Kamila Barylska
Prowadzący grup: Kamila Barylska, Mariusz Kaniecki
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Wykład - Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.