Sylabus przedmiotu
Podstawy informatyki II
| Forma zajęć | Atrybuty formy | Godziny w semestrze | Godziny w tygodniu | Zaliczenie | Kompetencje | Waga | ||
|---|---|---|---|---|---|---|---|---|
| stacjonarne | niestacjonarne | stacjonarne | niestacjonarne | |||||
| Wykład | Forma mieszana, Kontakt bezpośredni: 100% | 30 | 18 | 2 | 1 | Zaliczenie na ocenę |
|
(50%)1 przez 2 |
| Laboratorium | Kontakt bezpośredni: 100% | 30 | 18 | 2 | 1 | Zaliczenie na ocenę |
|
(50%)1 przez 2 |
| Forma aktywności | Liczba godzin - stac. | Liczba godzin - niestac. |
|---|---|---|
| Analiza wskazanej literatury | 15 | 18 |
| Przygotowanie do egzaminu / zaliczenia | 5 | 5 |
| Przygotowanie pracy pisemnej, raportu, prezentacji, demonstracji, itp. | 15 | 24 |
| Przygotowanie projektu | 15 | 18 |
| Praca własna | 1 | 15 |
| SUMA | 51 | 80 |
Cele przedmiotu:
Celem przedmiotu jest przedstawienie teorii automatów i języków formalnych, złożoności obliczeniowej oraz klasyfikacji problemów ze względu na ich złożoność obliczeniową. Analiza metod radzenia sobie z problemami obliczeniowo trudnymi. Przedstawienie podstaw modelowania oprogramowania, w szczególności modelowania oprogramowania z zastosowaniem języka UML.
Wymagania wstępne:
Podstawy informatyki I
Zakres tematyczny
| Rodzaj zajęć | Opis | Godz. stac. | Godz. niestac. |
|---|---|---|---|
| Wykład | 1. Złożoność obliczeniowa: pamięciowa, czasowa. | 1 | 1 |
| Wykład | 2. Ograniczenia złożoności problemu; luka algorytmiczna. Wyznaczanie złożoności obliczeniowej - rzędy złożoności. | 3 | 2 |
| Wykład | 3. Rekurencja - twierdzenie o rekurencji uniwersalnej. | 1 | 1 |
| Wykład | 4. Słowa, języki, operacje na językach. Deterministyczne i niedeterministyczne automaty skończone. Równoważność automatów skończonych, języków i wyrażeń regularnych. | 4 | 2 |
| Wykład | 5. Wyrażenia regularne w praktyce programisty. | 2 | 1 |
| Wykład | 6. Gramatyki i języki bezkontekstowe. Gramatyki w postaci normalnej Chomsky’ego. Parsowanie. | 3 | 2 |
| Wykład | 7. Automaty ze stosem. Deterministyczne i niedeterministyczne maszyny Turinga. | 2 | 1 |
| Wykład | 8. Redukcje wielomianowe. Problemy NP-zupełne. Twierdzenie Cooka. | 3 | 2 |
| Wykład | 9. Projektowanie algorytmów dla problemów obliczeniowo trudnych. | 3 | 2 |
| Wykład | 10. Wstęp do modelowania oprogramowania. Modelowanie w projektowaniu oprogramowania. | 2 | 1 |
| Wykład | 11. Język UML: charakterystyka diagramów UML, diagramy klas i obiektów, diagramy przypadków użycia, definiowanie (spisywanie) przypadków użycia, diagramy akcji. | 3 | 1 |
| Wykład | 12. Modelowanie systemu informatycznego z wykorzystaniem języka UML. Modelowanie wybranych aspektów oprogramowania (np. wymagania systemowe, architektura rozwiązania, funkcjonalności projektowanego systemu, schemat wdrożenia) za pomocą wybranych diagramów UML. | 3 | 2 |
| Laboratorium | 1. Przedstawienie tematyki, harmonogramu i zasad zaliczenia laboratorium. | 1 | 1 |
| Laboratorium | 2. Słowa, języki, wyrażenia regularne i automaty deterministyczne. | 3 | 2 |
| Laboratorium | 3. Deterministyczne automaty skończone. Niedeterministyczne automaty skończone. Determinizacja i minimalizacja. | 4 | 2 |
| Laboratorium | 4. Projektowanie i implementacja parserów. | 4 | 3 |
| Laboratorium | 5. Wyrażenia regularne w praktyce programisty. | 3 | 1 |
| Laboratorium | 6. Projektowanie i implementacja algorytmów dla problemów obliczeniowo trudnych. | 4 | 2 |
| Laboratorium | 7. Automatów Moore’a i Mealy’ego. kodowanie sygnałów wejściowych i wyjściowych, kodowanie stanów, kodowanie tabeli przejść. | 3 | 2 |
| Laboratorium | 8. Modelowanie oprogramowania i zasady spisywania przypadków użycia. | 3 | 2 |
| Laboratorium | 9. Rysowanie i analiza diagramów przypadków użycia | 3 | 2 |
| Laboratorium | 10. Poprawa sprawdzianów. Podsumowanie i zaliczenie ćwiczeń. | 2 | 1 |
Metody dydaktyczne
| Opis |
|---|
| Wykład problemowy |
| Wykład konwencjonalny |
| Metoda przypadków |
| Demonstracja |
| Ćwiczenia laboratoryjne |
Warunki zaliczenia:
Ocena końcowa z przedmiotu stanowi średnią arytmetyczną wszystkich form zajęć. Każda z form zajęć musi być oceniona pozytywnie. Szczegółowe informacje zostaną przekazane na pierwszych zajęciach podczas prezentacji sylabusa.
Literatura podstawowa:
Literatura uzupełniająca:
| Symbole | Opis efektu | Metoda weryfikacji | Forma zajęć |
|---|---|---|---|
| Potrafi omówić kluczowe aspekty automatów i gramatyk. Potrafi rozwiązać wybrane problemy stosując formalizm automatów oraz gramatyk. |
|
|
|
| Posiada wiedzę dotyczącą złożoności obliczeniowej, oszacowania złożoności obliczeniowej algorytmu sekwencyjnego. |
|
|
|
| Potrafi rozwiązywać problemy uwzględniając dostępne techniki i środki. |
|
|
|
| Potrafi analizować poprawność algorytmu i oszacować jego złożoność obliczeniową |
|
|
|
| Potrafi opisać podstawy modelowania programu w oparciu o podstawowe diagramy języka UML. |
|
|