Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Logika matematyczna
Tok studiów:
2019/2020
Kod:
IINF-1-303-n
Wydział:
Informatyki, Elektroniki i Telekomunikacji
Poziom studiów:
Studia I stopnia
Specjalność:
-
Kierunek:
Informatyka
Semestr:
3
Profil:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma studiów:
Niestacjonarne
Strona www:
 
Prowadzący moduł:
dr Mielczarek Dominik (dmielcza@wms.mat.agh.edu.pl)
Treści programowe zapewniające uzyskanie efektów uczenia się dla modułu zajęć

Opis efektów uczenia się dla modułu zajęć
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Powiązania z KEU Sposób weryfikacji i oceny efektów uczenia się osiągniętych przez studenta w ramach poszczególnych form zajęć i dla całego modułu zajęć
Wiedza: zna i rozumie
M_W001 zna podstawowe definicje i twierdzenia w zakresie klasycznego rachunku zdań i rachunku predykatów; INF1A_W01 Aktywność na zajęciach,
Egzamin,
Kolokwium
M_W002 rozumie potrzebę wprowadzenia formalizmu obliczeniowego, np. wykorzystującego maszyny Turinga bez stopu i ze stopem, abstrakcyjny język programowania (rachunek lambda) oraz formalizm funkcyjny; INF1A_W02, INF1A_W01 Aktywność na zajęciach,
Egzamin,
Kolokwium
Umiejętności: potrafi
M_U001 potrafi zweryfikować prawdziwość formuły rachunku zdań lub rachunku predykatów i potrafi zweryfikować, czy formuła rachunku zdań jest spełnialna; INF1A_U01 Aktywność na zajęciach,
Kolokwium
M_U002 umie ze zrozumieniem stosować indukcję matematyczną; INF1A_U01 Aktywność na zajęciach,
Kolokwium
M_U003 umie zaprojektować maszynę Turinga dla prostych problemów; INF1A_U01 Aktywność na zajęciach,
Kolokwium
Kompetencje społeczne: jest gotów do
M_K001 umie ocenić stopień zrozumienia przez siebie problemu, brakujące elementy rozumowania oraz stopień trudności problemów logiki matematycznej. INF1A_K01 Aktywność na zajęciach
Liczba godzin zajęć w ramach poszczególnych form zajęć:
SUMA (godz.)
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
32 16 16 0 0 0 0 0 0 0 0 0
Matryca kierunkowych efektów uczenia się w odniesieniu do form zajęć i sposobu zaliczenia, które pozwalają na ich uzyskanie
Kod MEU Student, który zaliczył moduł zajęć zna i rozumie/potrafi/jest gotów do Forma zajęć dydaktycznych
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Prace kontr. przejść.
Lektorat
Wiedza
M_W001 zna podstawowe definicje i twierdzenia w zakresie klasycznego rachunku zdań i rachunku predykatów; - - - - - - - - - - -
M_W002 rozumie potrzebę wprowadzenia formalizmu obliczeniowego, np. wykorzystującego maszyny Turinga bez stopu i ze stopem, abstrakcyjny język programowania (rachunek lambda) oraz formalizm funkcyjny; - - - - - - - - - - -
Umiejętności
M_U001 potrafi zweryfikować prawdziwość formuły rachunku zdań lub rachunku predykatów i potrafi zweryfikować, czy formuła rachunku zdań jest spełnialna; - - - - - - - - - - -
M_U002 umie ze zrozumieniem stosować indukcję matematyczną; - - - - - - - - - - -
M_U003 umie zaprojektować maszynę Turinga dla prostych problemów; - - - - - - - - - - -
Kompetencje społeczne
M_K001 umie ocenić stopień zrozumienia przez siebie problemu, brakujące elementy rozumowania oraz stopień trudności problemów logiki matematycznej. - - - - - - - - - - -
Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 149 godz
Punkty ECTS za moduł 5 ECTS
Udział w zajęciach dydaktycznych/praktyka 32 godz
Przygotowanie do zajęć 40 godz
Samodzielne studiowanie tematyki zajęć 75 godz
Egzamin lub kolokwium zaliczeniowe 2 godz
Szczegółowe treści kształcenia w ramach poszczególnych form zajęć (szczegółowy program wykładów i pozostałych zajęć)
Wykład (16h):

WYKŁADY

Klasyczny rachunek zdań w ujęciu semantycznym. Kwantyfikatory. Tautologie klasyczneo rachunku zdań, metody dowodzenia twierdzeń. Zasada indukcji matematycznej. Postacie normalne formuł: dysjunkcyjna i koniunkcyjna. Problem spełnialności.

Maszyna z dostępem swobodnym (RAM).

Maszyna Turinga. Techniki upraszczające konstrukcję maszyn Turinga. Modyfikacje maszyn Turinga. Zbiory przeliczalne i zbiory mocy continuum. Języki przeliczalnie rekurencyjne i rekurencyjne.

Problemy rozstrzygalne i nierozstrzygalne. Twierdzenie Churcha-Kleene’ego o równoważności formalizmów obliczeniowych: maszyn Turinga, rachunku lambda i funkcji rekurencyjnych.

Ćwiczenia audytoryjne (16h):

Rozwiązywanie zadań ilustrujących treść wykładów.

Pozostałe informacje
Metody i techniki kształcenia:
  • Wykład: Treści prezentowane na wykładzie są przekazywane w formie prezentacji multimedialnej w połączeniu z klasycznym wykładem tablicowym wzbogaconymi o pokazy odnoszące się do prezentowanych zagadnień.
  • Ćwiczenia audytoryjne: Podczas zajęć audytoryjnych studenci na tablicy rozwiązują zadane wcześniej problemy. Prowadzący na bieżąco dokonuje stosowanych wyjaśnień i moderuje dyskusję z grupą nad danym problemem.
Warunki i sposób zaliczenia poszczególnych form zajęć, w tym zasady zaliczeń poprawkowych, a także warunki dopuszczenia do egzaminu:

Zasady udziału w zajęciach:
  • Wykład:
    – Obecność obowiązkowa: Nie
    – Zasady udziału w zajęciach: Studenci uczestniczą w zajęciach poznając kolejne treści nauczania zgodnie z syllabusem przedmiotu. Studenci winni na bieżąco zadawać pytania i wyjaśniać wątpliwości. Rejestracja audiowizualna wykładu wymaga zgody prowadzącego.
  • Ćwiczenia audytoryjne:
    – Obecność obowiązkowa: Tak
    – Zasady udziału w zajęciach: Studenci przystępując do ćwiczeń są zobowiązani do przygotowania się w zakresie wskazanym każdorazowo przez prowadzącego (np. w formie zestawów zadań). Ocena pracy studenta może bazować na wypowiedziach ustnych lub pisemnych w formie kolokwium, co zgodnie z regulaminem studiów AGH przekłada się na ocenę końcową z tej formy zajęć.
Sposób obliczania oceny końcowej:

Ocena końcowa (OK) jest średnią ważoną ocen z egzaminu (E) i zaliczenia ćwiczeń audytoryjnych (A):
OK = 2/3 x E + 1/3 x A ,
gdzie E jest średnią arytmetyczną ocen uzyskanych na egzaminie w kolejnych terminach, A jest średnią arytmetyczną ocen zaliczenia ćwiczeń w kolejnych terminach. Uzyskanie pozytywnej oceny końcowej następuje po uzyskaniu pozytywnego wyniku z egzaminu poprzedzonego pozytywnym zaliczeniem ćwiczeń.
Warunkiem przystąpienia do egzaminu jest wcześniejsze uzyskanie zaliczenia z ćwiczeń. Warunkiem ubiegania się o zaliczenie ćwiczeń jest 80% obecności na ćwiczeniach.

Sposób i tryb wyrównywania zaległości powstałych wskutek nieobecności studenta na zajęciach:

Wymagania wstępne i dodatkowe, z uwzględnieniem sekwencyjności modułów :

Brak wymagań wstępnych.

Zalecana literatura i pomoce naukowe:

1. M. Ben-Ari, Logika matematyczna w informatyce, Warszawa 2005
2. J. Hopcroft, J. Ullman, Projektowanie i analiza algorytmów, Helion, 2003.
3. A. Aho, J. Hopcroft, J. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, PWN, 2003.
4. G. Boolos, R. Jeffrey, Computability and Logic, Cambridge Univ. Press, 1980.

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

Nie podano dodatkowych publikacji

Informacje dodatkowe:

Brak