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. |
|---|---|---|
| Przygotowanie do zajęć | 15 | 24 |
| Analiza wskazanej literatury | 15 | 18 |
| Przygotowanie do egzaminu / zaliczenia | 5 | 5 |
| Przygotowanie pracy pisemnej, raportu, prezentacji, demonstracji, itp. | 15 | 24 |
| Przygotowanie projektu | 15 | 18 |
| SUMA | 65 | 89 |
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:
bardzo dobry 5.0 student/ka zna, rozumie i wyjaśnia zakładane efekty uczenia się i potrafi je zastosować w praktyce w stopniu bardzo dobrym dobry plus 4.5 student/ka zna, rozumie i wyjaśnia zakładane efekty uczenia się i potrafi je zastosować w praktyce w stopniu ponad dobrym dobry 4.0 student/ka zna, rozumie i wyjaśnia zakładane efekty uczenia się i potrafi je zastosować w praktyce w stopniu dobrym dostateczny plus 3.5 student/ka zna, rozumie i wyjaśnia zakładane efekty uczenia się i potrafi je zastosować w praktyce w stopniu dość dobrym dostateczny 3.0 student/ka zna, rozumie i wyjaśnia zakładane efekty uczenia się i potrafi je zastosować w praktyce w stopniu dostatecznym zaliczone zal student/ka zna, rozumie i wyjaśnia zakładane efekty uczenia się i potrafi je zastosować w praktyce niezaliczone nzal student/ka nie zna, nie rozumie i nie wyjaśnia zakładanych efektów uczenia się i nie potrafi ich zastosować w praktyce
Literatura podstawowa: Feliks Kurp, Algorytmy. Struktury danych i złożoność obliczeniowa, Helion 2022. Robert Sedgewick, Kevin Wayne, Algorytmy. Wydanie IV, Helion 2012. Michał Śmiałek, Kamil Rybiński, Inżynieria oprogramowania w praktyce. Od wymagań do kodu z językiem UML, Helion 2023 Philippe Baumann, Patrick Grassle, Henriette Baumann, UML 2.0 in Action: A project-based tutorial. A detailed and practical book and eBook walk-through showing how to apply UML to real world development projects, Packt Publishing 2015.
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. |
|
|