Uniwersytet Opolski - Centralny System Uwierzytelniania
Strona główna

Teoretyczne podstawy informatyki

Informacje ogólne

Kod przedmiotu: 3.4.KRK.12SX.TPI
Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Teoretyczne podstawy informatyki
Jednostka: Instytut Informatyki
Grupy:
Punkty ECTS i inne: 5.00 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.
Język prowadzenia: polski
Rodzaj przedmiotu:

obowiązkowe

Skrócony opis:

Prezentacja podstawowych teoretycznych modeli obliczeń, ich możliwości i ograniczeń oraz wprowadzenie w podstawowe zagadnienia teorii złożoności obliczeniowej.

Pełny opis:

A. Problematyka wykładu / B. Problematyka konwersatorium (K) C. Problematyka laboratorium (L)

Pojęcie języka. Deterministyczne i niedeterministyczne automaty skończone. (L)

Wyrażenia i języki regularne. Gramatyki regularne, równoważność z automatami. (L)

Lemat o pompowaniu. Języki nieregularne. (K)

Gramatyki i języki bezkontekstowe, własności języków bezkontekstowych. Gramatyki języków programowania. Stosowane notacje. (L) Automaty ze stosem. Równoważność gramatyk bezkontekstowych i automatów ze stosem. (L)

Lemat o pompowaniu dla języków bezkontekstowych. (K)

Niedeterministyczna wielotaśmowa maszyna Turinga. Modele ograniczone maszyny Turinga. (L)

Maszyna uniwersalna. Obliczalność. Teza Churcha. Problem stopu. Problemy nierozstrzygalne. (K)

Pamięciowa i czasowa złożoność obliczeniowa. Problemy SAT i PRIME. Związki pomiędzy klasami złożoności. (K)

NP-zupełność. Przykład problemu obliczeniowo trudnego. (K)

Literatura:

M. Sipser, Wprowadzenie do teorii obliczeń, WNT, 2009.

Literatura uzupełniająca:

1. J.E. Hopcroft, R. Motwani, J.D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń, Wydawnictwo Naukowe PWN, Nowe wydanie, Warszawa 2005.

2. Ch. H. Papadimitriou, Złożoność obliczeniowa, WNT, 2002.

Efekty uczenia się:

Wiedza:

• Definiuje deterministyczne i niedeterministyczne automaty skończone.

• Definiuje zbiór wyrażeń regularnych nad ustalonym alfabetem.

• Definiuje automat ze stosem i gramatykę bezkontekstową.

• Zna własności domknięcia klasy języków regularnych i klasy języków bezkontekstowych na operacje regularne.

• Zna podstawowe warianty maszyn Turinga (jednotaśmowa, wielotaśmowa, niedeterministyczna).

• Zna pojęcie problemu nierozstrzygalnego.

• Definiuje problemy SAT i PRIMES.

• Definiuje złożoność obliczeniową problemu.

• Wymienia podstawowe klasy złożoności obliczeniowej.

Umiejętności:

• Konstruuje automat skończony i pisze wyrażenie regularne dla prostych języków regularnych.

• Przekształca niedeterministyczny automat skończony na automat deterministyczny.

• Konstruuje automat równoważny danemu wyrażeniu regularnemu.

• Konstruuje automat ze stosem i pisze gramatykę bezkontekstową dla prostych języków bezkontekstowych.

• Podaje przykłady języków, które nie są regularne lub nie są bezkontekstowe.

• Konstruuje jedno- i wielotaśmową maszynę Turinga.

• Podaje przykład problemu nierozstrzygalnego.

• Podaje przykład problemu NP-zupełnego.

• Potrafi zwięźle przedstawić pytanie „ czy P= NP ?”

Kompetencje społeczne (postawy):

• Zna ograniczenia własnej wiedzy i rozumie potrzebę dalszego kształcenia.

• Potrafi odpowiednio określić priorytety służące realizacji określonego zadania informatycznego (laboratorium).

• Postępuje etycznie w zakresie wykorzystania efektów pracy innych osób.

• Rozumie potrzebę popularnego przedstawiania laikom wybranych osiągnięć informatyki teoretycznej.

Metody i kryteria oceniania:

Forma i sposób zaliczenia oraz podst. kryteria oceny lub wymagania egzaminacyjne - na ogólnych zasadach określonych w programie kształcenia; w szczególności:

A. Sposób zaliczenia

• zaliczenie z oceną

B. Formy zaliczenia

• (L) zaliczenie z oceną: ustalenie oceny zaliczeniowej na podstawie ocen cząstkowych otrzymywanych w trakcie trwania semestru z pisemnych sprawdzianów;

• (K) zaliczenie z oceną: ustalenie oceny zaliczeniowej na podstawie aktywności na zajęciach i ocen z prac domowych;

• (W) zaliczenie z oceną: ustalenie oceny zaliczeniowej na podstawie obecności na zajęciach oraz ocen końcowych z laboratorium i konwersatorium;

C. Podstawowe kryteria

• (W), (L), (K) - uzyskanie pozytywnej oceny zaliczeniowej

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

Okres: 2023-10-01 - 2024-02-29
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Konwersatorium, 15 godzin więcej informacji
Laboratorium, 15 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Lidia Tendera
Prowadzący grup: Dariusz Marzec, Lidia Tendera
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Zaliczenie na ocenę
Konwersatorium - Zaliczenie na ocenę
Laboratorium - Zaliczenie na ocenę
Wykład - Zaliczenie na ocenę
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Opolski.
pl. Kopernika 11a, 45-040 Opole https://uni.opole.pl kontakt deklaracja dostępności mapa serwisu USOSweb 7.0.4.0-www3-4 (2024-07-15)