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: | |||
| 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 |
 
 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 |
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 |
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 |
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.