Teoretyczne podstawy informatyki
Informacje ogólne
Kod przedmiotu: | 1100-TI0LII |
Kod Erasmus / ISCED: | (brak danych) / (brak danych) |
Nazwa przedmiotu: | Teoretyczne podstawy informatyki |
Jednostka: | Wydział Matematyki i Informatyki |
Grupy: | |
Punkty ECTS i inne: |
0 LUB
6.00
LUB
5.00
(zmienne w czasie)
|
Język prowadzenia: | polski |
Forma zaliczenia: | egzamin |
Forma studiów: | stacjonarne |
Wymagania wstępne: | Znajomość rachunku zbiorów i rachunku zdań, indukcji matematycznej, pojęcie rekurencji. |
Skrócony opis: |
Celem przedmiotu jest zaznajomienie studenta z teoretycznymi podstawami informatyki. Przedstawione są teoretyczne modele komputerów: automaty skończone, automaty ze stosem i maszyny Turinga oraz równoważne im klasy języków i gramatyk formalnych. |
Efekty uczenia się: |
Po zakończonym kursie student: e1 przytacza i ilustruje podstawowe pojęcia dotyczące języków formalnych (działania na językach formalnych, gramatyki formalne, teoretyczne modele komputerów) e2 posługuje się różnymi metodami opisu języków regularnych e3 konstruuje deterministyczne automaty skończone akceptujące wskazane języki regularne e4 stosuje metody algorytmiczne z dowodu Twierdzenia Kleene’ego. e5 posługuje się gramatykami języków bezkontekstowych (w szczególności gramatykami w postaci normalnej Chomsky'ego, drzewami wyprowadzeń) e6 analizuje podstawowe modele teoretyczne komputerów e7 wymienia podstawowe twierdzenia dotyczące własności języków formalnych (teoriomnogościowe własności języków formalnych, Lematy o pompowaniu) e8 podaje zależności pomiędzy zbiorami języków formalnych w oparciu o klasyfikację Chomsky’ego e9 przeprowadza krytyczną analizę zadań Powyższe efekty kształcenia osiągane w ramach przedmiotu pozwalają na realizację kierunkowych efektów kształcenia, mających następujące oznaczenia w programie Informatyka I stopnia: 1100I-1A_W03, 1100Isd1A_W13. |
Zajęcia w cyklu "Semestr letni 2023/2024" (w trakcie)
Okres: | 2024-02-26 - 2024-09-30 |
Przejdź do planu
PN W
WT W
ŚR CZ CK
PT W
|
Typ zajęć: |
Ćwiczenia konwersatoryjne, 28 godzin
Wykład, 28 godzin
|
|
Koordynatorzy: | Aneta Tomaszewska | |
Prowadzący grup: | Aneta Tomaszewska, Justyna Walewska | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Ocena zgodna z regulaminem studiów
Ćwiczenia konwersatoryjne - Ocena zgodna z regulaminem studiów Wykład - Ocena zgodna z regulaminem studiów |
Zajęcia w cyklu "Semestr letni 2022/2023" (zakończony)
Okres: | 2023-02-20 - 2023-09-30 |
Przejdź do planu
PN W
WT ŚR CZ CK
PT CK
|
Typ zajęć: |
Ćwiczenia konwersatoryjne, 28 godzin
Wykład, 28 godzin
|
|
Koordynatorzy: | Aneta Tomaszewska | |
Prowadzący grup: | Szymon Brzostowski, Aneta Tomaszewska, Justyna Walewska | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Ocena zgodna z regulaminem studiów
Ćwiczenia konwersatoryjne - Ocena zgodna z regulaminem studiów Wykład - Ocena zgodna z regulaminem studiów |
Zajęcia w cyklu "Semestr letni 2021/2022" (zakończony)
Okres: | 2022-02-21 - 2022-09-30 |
Przejdź do planu
PN WT ŚR CZ W
CK
PT CK
|
Typ zajęć: |
Ćwiczenia konwersatoryjne, 28 godzin
Wykład, 28 godzin
|
|
Koordynatorzy: | Aneta Tomaszewska | |
Prowadzący grup: | Aneta Tomaszewska, Justyna Walewska | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Ocena zgodna z regulaminem studiów
Ćwiczenia konwersatoryjne - Ocena zgodna z regulaminem studiów Wykład - Ocena zgodna z regulaminem studiów |
|
Metody dydaktyczne: | wykład konwersatoryjny, prace w grupach, ćwiczenia praktyczne |
|
Sposoby i kryteria oceniania: | Ćwiczenia: Na ocenę z ćwiczeń składa się ocena aktywności, kartkówek oraz kolokwium sprawdzające efekty uczenia się z zakresu umiejętności e1-e6. Wykład: Wykład kończy się egzaminem weryfikującym efekty e1-2, e5-9. Egzamin składa się z dwóch części: I pisemnej (obowiązkowej) w postaci testu otwartego – 85% II ustnej (nieobowiązkowej) – 15% Na ocenę z przedmiotu składają się ocena z ćwiczeń (60%) i ocena z wykładu (40%). Skala ocen: 91% -100%: 5 (A), 81% -90%: 4+ (B), 71% -80%: 4 (C), 61% -70%: 3+ (D), 51% -60%: 3 (E). Przewidywany czas pracy własnej (w godzinach lekcyjnych): - przygotowanie do zajęć (praca bieżąca): 56 - przygotowanie do zaliczenia: 28 Student/ka weryfikuje efekty pracy własnej z Prowadzącymi zajęcia. |
|
Treści kształcenia: | 1. Problemy a języki formalne. 2. Języki regularne: wyrażenia regularne, automaty skończone, twierdzenie Kleene'ego, minimalizacja DAS, własności języków regularnych, lemat o pompowaniu dla jęz. regularnych, algorytmy decyzyjne dla języków regularnych. 3. Języki bezkontekstowe: gramatyki bezkontekstowe i regularne, postacie normalne gramatyk bezkontekstowych, własności języków bezkontekstowych, automaty ze stosem, jednoznaczność i determinizm języków bezkontekstowych . 4. Języki rekursywnie przeliczalne: maszyny Turinga, gramatyki frazowe. 5. Hierarchia Chomsky'ego języków formalnych. |
|
Literatura: |
[1]. Krasiński T. - Automaty i języki formalne; Wyd. UŁ 2007 [2]. Hopcroft J., Motwani R., Ullmann, J. - Wprowadzenie do teorii automatów, języków i obliczeń ; PWN 2005. [3]. Sipser M. - Wprowadzenie do teorii obliczeń. WNT 2009. [4]. Kozen D. - Automata and computability; Springer 1997. [5]. Cohen D. - Introduction to computer theory; Wiley 1991. [6]. Martin J.C. - Introduction to Languages and the Theory of Computation. McGraw Hill 1999 |
Zajęcia w cyklu "Semestr letni 2020/2021" (zakończony)
Okres: | 2021-03-08 - 2021-09-30 |
Przejdź do planu
PN WT ŚR W
CZ CK
CK
PT CK
|
Typ zajęć: |
Ćwiczenia konwersatoryjne, 28 godzin
Wykład, 28 godzin
|
|
Koordynatorzy: | Aneta Tomaszewska | |
Prowadzący grup: | Aneta Tomaszewska, Justyna Walewska | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Ocena zgodna z regulaminem studiów
Ćwiczenia konwersatoryjne - Ocena zgodna z regulaminem studiów Wykład - Ocena zgodna z regulaminem studiów |
|
Czy ECTS?: | T |
|
Metody dydaktyczne: | wykład konwersatoryjny, prace w grupach, ćwiczenia praktyczne |
|
Sposoby i kryteria oceniania: | Na ocenę z ćwiczeń składa się ocena aktywności, oceny z kartkówek oraz kolokwium sprawdzające efekty uczenia się z zakresu umiejętności e1-e6. Egzamin pozwala zweryfikować efekty uczenia się e1-2, e5-9. Egzamin w formie pisemnej może być dodatkowo uzupełniony odpowiedzią ustną. Na ocenę z przedmiotu składają się ocena z ćwiczeń (60% i ocena z wykładu (40%). |
|
Treści kształcenia: | 1. Problemy a języki formalne. 2. Języki regularne: wyrażenia regularne, automaty skończone, twierdzenie Kleene'ego, minimalizacja DAS, własności języków regularnych, lemat o pompowaniu dla jęz. regularnych, algorytmy decyzyjne dla języków regularnych. 3. Języki bezkontekstowe: gramatyki bezkontekstowe i regularne, postacie normalne gramatyk bezkontekstowych, własności języków bezkontekstowych, automaty ze stosem, jednoznaczność i determinizm języków bezkontekstowych . 4. Języki rekursywnie przeliczalne: maszyny Turinga, gramatyki frazowe. 5. Hierarchia Chomsky'ego języków formalnych. |
|
Literatura: |
[1]. Krasiński T. - Automaty i języki formalne; Wyd. UŁ 2007 [2]. Hopcroft J., Motwani R., Ullmann, J. - Wprowadzenie do teorii automatów, języków i obliczeń ; PWN 2005. [3]. Sipser M. - Wprowadzenie do teorii obliczeń. WNT 2009. [4]. Kozen D. - Automata and computability; Springer 1997. [5]. Cohen D. - Introduction to computer theory; Wiley 1991. [6]. Martin J.C. - Introduction to Languages and the Theory of Computation. McGraw Hill 1999 |
Zajęcia w cyklu "Semestr letni 2019/2020" (zakończony)
Okres: | 2020-02-24 - 2020-09-30 |
Przejdź do planu
PN WT W
ŚR CK
CK
CZ PT |
Typ zajęć: |
Ćwiczenia konwersatoryjne, 28 godzin
Wykład, 28 godzin
|
|
Koordynatorzy: | Aneta Tomaszewska | |
Prowadzący grup: | Aneta Tomaszewska, Justyna Walewska | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Ocena zgodna z regulaminem studiów
Ćwiczenia konwersatoryjne - Ocena zgodna z regulaminem studiów Wykład - Ocena zgodna z regulaminem studiów |
|
Czy ECTS?: | T |
|
Metody dydaktyczne: | wykład konwersatoryjny, prace w grupach, ćwiczenia praktyczne |
|
Sposoby i kryteria oceniania: | Na ocenę z ćwiczeń składa się ocena aktywności, oceny z kartkówek oraz kolokwium sprawdzające efekty kształcenia z zakresu umiejętności e1-e6. Egzamin pozwala zweryfikować efekty kształcenia e1-2, e5-9. Egzamin w formie pisemnej może być dodatkowo uzupełniony odpowiedzią ustną. Na ocenę z przedmiotu składają się ocena z ćwiczeń (60% i ocena z wykładu (40%). |
|
Treści kształcenia: | 1. Problemy a języki formalne. 2. Języki regularne: wyrażenia regularne, automaty skończone, twierdzenie Kleene'ego, minimalizacja DAS, własności języków regularnych, lemat o pompowaniu dla jęz. regularnych, algorytmy decyzyjne dla języków regularnych. 3. Języki bezkontekstowe: gramatyki bezkontekstowe i regularne, postacie normalne gramatyk bezkontekstowych, własności języków bezkontekstowych, automaty ze stosem, jednoznaczność i determinizm języków bezkontekstowych . 4. Języki rekursywnie przeliczalne: maszyny Turinga, gramatyki frazowe. 5. Hierarchia Chomsky'ego języków formalnych. |
|
Literatura: |
[1]. Krasiński T. - Automaty i języki formalne; Wyd. UŁ 2007 [2]. Hopcroft J., Motwani R., Ullmann, J. - Wprowadzenie do teorii automatów, języków i obliczeń ; PWN 2005. [3]. Sipser M. - Wprowadzenie do teorii obliczeń. WNT 2009. [4]. Kozen D. - Automata and computability; Springer 1997. [5]. Cohen D. - Introduction to computer theory; Wiley 1991. [6]. Martin J.C. - Introduction to Languages and the Theory of Computation. McGraw Hill 1999 |
Zajęcia w cyklu "Semestr letni 2018/2019" (zakończony)
Okres: | 2019-02-18 - 2019-09-30 |
Przejdź do planu
PN CK
W
CK
WT CK
ŚR W
CK
CZ PT |
Typ zajęć: |
Ćwiczenia konwersatoryjne, 28 godzin
Wykład, 28 godzin
|
|
Koordynatorzy: | Aneta Tomaszewska | |
Prowadzący grup: | Aneta Tomaszewska, Justyna Walewska | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Ocena zgodna z regulaminem studiów
Ćwiczenia konwersatoryjne - Ocena zgodna z regulaminem studiów Wykład - Ocena zgodna z regulaminem studiów |
|
Czy ECTS?: | T |
|
Metody dydaktyczne: | wykład konwersatoryjny, prace w grupach, ćwiczenia praktyczne |
|
Sposoby i kryteria oceniania: | Na ocenę z ćwiczeń składa się ocena aktywności, oceny z kartkówek oraz kolokwium sprawdzające efekty kształcenia z zakresu umiejętności e1-e6. Egzamin pozwala zweryfikować efekty kształcenia e1-2, e5-9. Egzamin w formie pisemnej może być dodatkowo uzupełniony odpowiedzią ustną. Na ocenę z przedmiotu składają się ocena z ćwiczeń (60% i ocena z wykładu (40%). |
|
Treści kształcenia: | 1. Problemy a języki formalne. 2. Języki regularne: wyrażenia regularne, automaty skończone, twierdzenie Kleene'ego, minimalizacja DAS, własności języków regularnych, lemat o pompowaniu dla jęz. regularnych, algorytmy decyzyjne dla języków regularnych. 3. Języki bezkontekstowe: gramatyki bezkontekstowe i regularne, postacie normalne gramatyk bezkontekstowych, własności języków bezkontekstowych, automaty ze stosem, jednoznaczność i determinizm języków bezkontekstowych . 4. Języki rekursywnie przeliczalne: maszyny Turinga, gramatyki frazowe. 5. Hierarchia Chomsky'ego języków formalnych. |
|
Literatura: |
[1]. Krasiński T. - Automaty i języki formalne; Wyd. UŁ 2007 [2]. Hopcroft J., Motwani R., Ullmann, J. - Wprowadzenie do teorii automatów, języków i obliczeń ; PWN 2005. [3]. Sipser M. - Wprowadzenie do teorii obliczeń. WNT 2009. [4]. Kozen D. - Automata and computability; Springer 1997. [5]. Cohen D. - Introduction to computer theory; Wiley 1991. [6]. Martin J.C. - Introduction to Languages and the Theory of Computation. McGraw Hill 1999 |
Zajęcia w cyklu "Semestr letni 2017/2018" (zakończony)
Okres: | 2018-02-19 - 2018-09-30 |
Przejdź do planu
PN WT W
ŚR CZ CK
PT CK
CK
CK
|
Typ zajęć: |
Ćwiczenia konwersatoryjne, 28 godzin
Wykład, 28 godzin
|
|
Koordynatorzy: | Aneta Tomaszewska | |
Prowadzący grup: | Aneta Tomaszewska, Justyna Walewska | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Ocena zgodna z regulaminem studiów
Ćwiczenia konwersatoryjne - Ocena zgodna z regulaminem studiów Wykład - Ocena zgodna z regulaminem studiów |
|
Czy ECTS?: | T |
|
Metody dydaktyczne: | wykład konwersatoryjny, prace w grupach, ćwiczenia praktyczne |
|
Sposoby i kryteria oceniania: | Na ocenę z ćwiczeń składa się ocena aktywności, oceny z kartkówek oraz kolokwium sprawdzające efekty kształcenia z zakresu umiejętności e1-e6. Egzamin pozwala zweryfikować efekty kształcenia e1-2, e5-9. Egzamin w formie pisemnej może być dodatkowo uzupełniony odpowiedzią ustną. Na ocenę z przedmiotu składają się ocena z ćwiczeń (60% i ocena z wykładu (40%). |
|
Treści kształcenia: | 1. Problemy a języki formalne. 2. Języki regularne: wyrażenia regularne, automaty skończone, twierdzenie Kleene'ego, minimalizacja DAS, własności języków regularnych, lemat o pompowaniu dla jęz. regularnych, algorytmy decyzyjne dla języków regularnych. 3. Języki bezkontekstowe: gramatyki bezkontekstowe i regularne, postacie normalne gramatyk bezkontekstowych, własności języków bezkontekstowych, automaty ze stosem, jednoznaczność i determinizm języków bezkontekstowych . 4. Języki rekursywnie przeliczalne: maszyny Turinga, gramatyki frazowe. 5. Hierarchia Chomsky'ego języków formalnych. |
|
Literatura: |
[1]. Krasiński T. - Automaty i języki formalne; Wyd. UŁ 2007 [2]. Hopcroft J., Motwani R., Ullmann, J. - Wprowadzenie do teorii automatów, języków i obliczeń ; PWN 2005. [3]. Sipser M. - Wprowadzenie do teorii obliczeń. WNT 2009. [4]. Kozen D. - Automata and computability; Springer 1997. [5]. Cohen D. - Introduction to computer theory; Wiley 1991. [6]. Martin J.C. - Introduction to Languages and the Theory of Computation. McGraw Hill 1999 |
Właścicielem praw autorskich jest UNIWERSYTET ŁÓDZKI.