Program studiów informatycznych na Uniwersytecie Wrocławskim (cz.2)
Studia stacjonarne II stopnia: 3-semestralne i 4-semestralne
Program przyjęty przez Radę Wydziału Matematyki i Informatyki w dniu 22 stycznia 2013 roku ze zmianami z 21 maja 2013 roku oparty na Kierunkowych Efektach Kształcenia dla kierunku informatyka przyjętych przez Senat Uniwersytetu Wrocławskiego w dniu 20 czerwca 2013 roku ze zmianami z maja 2013 roku
Karty przedmiotów typu O (obowiązkowych)
O3. Języki formalne i złożoność obliczeniowa
Wymagane przygotowanie studentów.
O2.M Algorytmy i struktury danych (M)
Wymagane przygotowanie studentów.
O2.M Analiza numeryczna (opracował: prof. S. Lewanowicz)
Wymagane przygotowanie studentów.
Wymagane przygotowanie studentów
Zaawansowane przedmioty teoretyczne I.2
Wymagane przygotowanie do przedmiotu
Wymagane przygotowanie do przedmiotu
Wymagane przygotowanie do przedmiotu
Wymagane przygotowanie do przedmiotu
Matematyczne metody grafiki komputerowej (popracował prof. S. Lewanowicz)
Wymagane przygotowanie do przedmiotu:
Wymagane przygotowanie do przedmiotu
Realistyczna grafika komputerowa (opracował dr A. Łukaszewski)
Wymagane przygotowanie do przedmiotu
Analiza programów komputerowych
Wymagane przygotowanie do przedmiotu:
Teoretyczne podstawy języków programowania
Modelowanie zjawisk przyrodniczych (opracował dr. A. Szustalewicz)
Wiedza z zakresu przedmiotów Programowanie oraz Matematyka dyskretna.
Program przedmiotu obejmuje zagadnienia związane z teorią języków formalnych (wykłady A1 - A8) w zakresie istotnym z punktu widzenia wykształcenia informatycznego, a także dostatecznym dla stworzenia zasobów naturalnych przykładów dla części B i C. Następnie przechodzi się do zagadnień związanych z pojęciami rozstrzygalności i nierozstrzygalności (wykłady R1 -- R8). Ostatnia część kursu poświęcona jest wybranym, elementarnym zagadnieniom złożoności obliczeniowej.
A1. Deterministyczny automat skończony. Języki regularne. Lemat o pompowaniu. Twierdzenie o indeksie.
A2. Niedeterminizm. Niedeterministyczny automat skończony. Determinizacja automatu.
A3. Wyrażenia regularne. Równoważność automatów skończonych i wyrażeń regularnych. Aspekty algorytmiczne: rozstrzyganie równoważności wyrażeń regularnych jest możliwe ale zagadkowo czasochłonne.
A4. Uwagi o automatach na obiektach innych niż słowa skończone: automaty na drzewach skończonych i na słowach nieskończonych.
A5. Gramatyki bezkontekstowe. Przykłady.
A6. Postać Chomsky'ego, lemat o pompowaniu i jego konsekwencje.
A7. Automaty ze stosem. Postać Greibach gramatyk bezkontekstowych. Równoważnośc gramatyk i automatów ze stosem.
A8. Własności zamkniętości klasy języków bezkontekstowych. Niemożliwość determinizacji.
R1. Zbiory rekurencyjne i rekurencyjnie przeliczalne. Funkcje rekurencyjne - częściowe i całkowite. Numeracja funkcji rekurencyjnych. Nierozstrzygalność problemu stopu.
R2. Pojęcie redukcji. Twierdzenie Rice'a. Uwagi o implikacjach tw. Rice'a dla możliwości automatycznej weryfikacji programów.
R3. Maszyna Turinga. Teza Churcha.
R4. Nierozstrzygalność problemu słów dla semiprocesów Thuego.
R5. Nierozstrzygalność problemu słów dla procesów Thuego (problemu słów w półgrupie).
R6. Nierozstrzygalność problemu odpowiedniości Posta, i przykłady nierozstrzygalnych problemów dotyczących gramatyk.
R7. Nierozstrzygalność teorii pierwszego rzędu liczb naturalnych z dodawaniem i mnożeniem (ewentualnie: z dodawaniem, mnożeniem i potęgowaniem). Uwagi o niemożliwości zaksjomatyzowania arytmetyki. Uwagi o dziesiątym problemie Hilberta.
R8. Nierozstrzygalność rachunku predykatów pierwszego rzędu.
C1. Klasa PTIME i PSPACE. Redukcje wielomianowe. Wielomianowa równoważność 3SAT i 3COL.
C2. Niedeterminizm i klasa NP. Przykłady. Przykłady języków z klasy co-NP, oraz z przecięcia NP i co-NP. Charakteryzacja NP jako klasy języków bedących projekcjami języków z P.
C3. NP zupełność. Twierdzenie Cook'a. Więcej przykładów problemów NP-zupełnych. Uwagi o SAT-solverach.
C4. PSPACE. Tw. Savitcha.
C5. Problemy PSPACE-zupełne: QBF i totalność wyrażeń regularnych. Wyjaśnienie zagadki z wykładu A3.
C6. Funkcje jednostronne. Uwagi o teoriozłożonościowych założeniach kryptografii z kluczem publicznym.
C7. Słaba wersja twierdzenia o hierarchii czasowej: różność EXPTIME i PTIME. Uwagi o
sposobach uogólnienia tej słabej wersji.
C8. Problemy wymagające dowodliwie czasu wykładniczego. Pebble games. Totalność wyrażeń regularnych
C9. Inne niż PTIME formalizacje intuicji ''łatwej obliczalności''. Uwagi o klasie FPT. Zrandomizowane algorytmy testowania pierwszości. Uwagi o komputerach kwantowych.
C10. Przykład problemu rozstrzygalnego ale nieelementarnego: totalność wyrażeń regularnych z dopełnieniem.
[1] Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, Projektowanie
i analiza algorytmów komputerowych, PWN, Warszawa 1983.
[2] Michael Sipser, Wprowadzenie do teorii obliczen, WNT Warszawa 2009.
[3] Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
Kompetencje. Przedmiot dotyczy jednego z głównych obszarów teorii informatyki. Oczekuje się, że osoba która go zaliczy, będzie miała świadomość wszechobecności, w sytuacjach związanych z praktyką informatyczną/algorytmiczną, podstawowych omawianych pojęć i zagadnień (takich jak automat skończony, problem rozstrzygalności, problem złożoności obliczeniowej, złożoność wielomianowa i złożoność NP, redukcja) a także będzie się umiała w praktyce sprawnie tymi pojęciami posługiwać. Ta zdolność do praktycznego posługiwania się stanowi priorytet, dlatego program przedmiotu nie obejmuje wielu zaawansowanych i specjalistycznych zagadnień, skupiając się na możliwie głębokim rozumieniu zagadnień elementarnych. Ponadto forma, w jakiej prowadzi się ćwiczenia tablicowe (w ramach których studenci prezentują na tablicy przygotowane przez siebie wcześniej rozwiązania zadań), przyczynia się do rozwoju kompetencji komunikacyjnych.
Macierz odniesienia. Odniesienie do kierunkowych obszarów kompetencji typowego przedmiotu z tej grupy jest następujące:
Kategoria kompetencji: kierunkowy kod efektu (stopień nasycenia) | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (+++) | wykładane w ramach przedmiotu treści obejmują zasadnicze pojęcia matematycznych podstaw informatyki, a przedstawiane w ramach przedmiotu twierdzenia są w pełni uzasadniane z użyciem ścisłych technik dowodowych; |
umiejętności teoretyczne: K_U01, K_U06 (+++) | przedmiot wymaga opanowania umiejętności samodzielnej analizy i klasyfikowania problemów obliczeniowych ze względu na zasoby obliczeniowe niezbędne do ich rozwiązywania |
wiedza specjalistyczna: K_W05 - K_W07 (++) | omawiane zagadnienia, z racji swej ogólności i wagi, stanowią punkt wyjścia dla różnych dziedzin informatycznych; w szczególności, omawiane pojęcia i poruszane problemy stanowią podstawę specjalistycznych dziedzin algorytmiki, w tym na przykład współczesnej kryptografii, przetwarzania danych, przetwarzania tekstów, a także, w części dotyczącej języków formalnych - teorii języków programowania. |
umiejętności specjalistyczne: K_U13 - K_U17 (++) | treści opanowywane w ramach przedmiotu, umiejętne stosowane w rozmaitych dziedzinach algorytmiki (tj. kryptografia, przetwarzanie danych czy tekstów) czy teorii języków programowania, pozwalają na rozwijanie zaawansowanych technik i konstrukcji w tych dziedzinach; przedmiot istotnie odnosi się do tych zastosowań; |
Formy zajęć.
Formy przekazywania wiedzy w ramach przedmiotu obejmują klasyczną postać wykładową oraz samodzielną pracę studentów w oparciu o materiały oraz ćwiczenia tablicowe. Formy utrwalania wiedzy i nabywania umiejętności mają formę ćwiczeń i repetytorium. W ramach ćwiczeń studenci prezentują wcześniej przez siebie przygotowana rozwiązania zadań problemowych. W ramach repetytorium jest czas na dodatkowe wyjaśnianie omawianych na wykładzie zagadnień i ćwiczenie rozwiązań typowych problemów.
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę prezentacji rozwiązań zadań problemowych w ramach ćwiczeń oraz rozwiązywanie takich zadań w czasie egzaminu. Egzamin ma formę pisemną i składa się z trzech części, po jednej dla każdej z poddziedzin składających się na program przedmiotu.
Parametry przedmiotu. Przedmiot odbywa się w wymiarze 60 godz. wykładu, 30 godz. ćwiczeń, 30 godz. repetytorium i kończy się egzaminem. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego i teoretycznego materiału oraz rozwiązania zadań problemowych szacuje się jak 2:1 w przypadku wykładów i ćwiczeń. W przypadku repetytorium nie zakłada się dodatkowej pracy własnej studenta. Przyjmuje się także, że dzięki ukierunkowaniu ćwiczeń i repetytorium na utrwalanie zdobywanej wiedzy i doskonalenie nabywanych umiejętności, regularna praca i przygotowywanie do tych zajęć zapewnia odpowiednie przygotowanie do egzaminu. Daje to sumaryczny czas pracy studenta 3*60 + 3 *30 + 30 = 300 godzin, w tym 120 godzin z udziałem nauczyciela akademickiego. Za zaliczenie przedmiotu student otrzymuje 9 punktów ECTS.
Wiedza z zakresu wykładów Programowanie oraz Matematyka dyskretna.
[1] Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, Projektowanie i analiza algorytmów komputerowych, PWN, Warszawa 1983.
[2] G. Brassard, P. Bratley, Algorithmics. Theory & practice, Prentice Hall, 1993.
31[3] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to algorithms, MIT Press, 1992.
[4] J. Kleinberg, E. Tardos, Algorithm Design, Addison Wesley, 2006.
[5] S. Baase„ A. von Gelder Computer Algorithms: Introduction to Design and Analysis, Addison-Wesley, 2000.
[6] L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT, Warszawa 1996.
[7] L. Banachowski, A. Kreczmar, W. Rytter, Analiza algorytmów i struktur danych, WNT, Warszawa 1989.
[8] S. E. Goodman, S. T. Hedetniemi, Introduction to the Design and Analysis of Algorithms, McGraw-Hill, 1977.
[9] D. H. Greene, D. E. Knuth, Mathematics for the Analysis of Algorithms, Birkhäuser, 1982.
[10] D. E. Knuth, Sztuka programowania, T. 1–3, WNT, 2003.
[11] Dexter C. Kozen, The Design and Analysis of Algorithms, Springer, 1992.
[12] M. Mitzenmacher, E. Upfal, Probability and Computing. Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
[13] R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
[14] T. Ottmann, P. Widmayer, Algorithmen und Datenstrukturen, Wissenschaftsverlag, 1993.
[15] E. M. Reingold, J. Deo, N. Nievergelt Algorytmy kombinatoryczne, PWN, Warszawa 1985.
[16] V. Vazirani, Approximation Algorithms, Springer, 2001.
Kompetencje. Przedmiot odwołuje się do matematycznych podstaw informatyki i obejmuje kluczowe, ogólne zagadnienia z teorii informatyki z zakresu algorytmiki i struktur danych stanowiące podstawę dla szeregu specjalistycznych dziedzin informatyki. Zawieraja treści z programu studiów informatycznych pierwszego stopnia rozszerzone do treści z programu studiów informatycznych drugiego stopnia. W wersji L (O.2L) od studentów wymagane jest poznanie:
W wersji M (O.2M) od studentów wymagana jest umiejętność pogłębionej analizy omawianych pojęć, szerszego zastosowania poznanych technik oraz wzbogacenie wykładanych treści o wiedzę dotyczącą kierunków rozwoju informatyki i badań w danej dziedzinie, w szczególności:
Macierz odniesienia.
Odniesienie do kierunkowych obszarów kompetencji przedmiotu z tej grupy jest następujące:
Kategoria kompetencji: kierunkowy kod efektu (stopień nasycenia) | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (+++) | wykładane w ramach przedmiotu treści: podstawowe techniki analizy problemów informatycznych oraz analizy i konstrukcji i algorytmów służących ich rozwiązaniu odwołują się istotnie do matematycznych podstaw informatyki i obejmują zaawansowane pojęcia teorii informatyki wymagając tym samym od studentów opanowania i ugruntowania wiedzy w tym zakresie; prezentowane zagadnienia algorytmiczne są analizowane dogłębnie ze względu na istotne aspekty, tj. model obliczeń, klasy złożoności czasowej i pamięciowej; w ramach przedmiotu prezentowane są wszystkie istotne pojęcia z zakresu algorytmiki i złożoności obliczeniowej; |
umiejętności teoretyczne: K_U01, K_U06 (+++) | przedmiot wymaga opanowania umiejętności konstrukcji algorytmów i struktur danych dla szerokiego spektrum problemów, z zastosowaniem zaawansowanych technik i konstrukcji algorytmicznych; analiza konstruowanych rozwiązań pozwala opanować umiejętność wnikliwej i wszechstronnej analizy algorytmów i struktur danych; |
wiedza specjalistyczna: K_W05 - K_W07 (++) | treści zawarte w przedmiocie stanowią podstawę szeregu dziedzin specjalistycznych i zastosowań informatyki; w ramach przedmiotu omawiane są rozwiązania algorytmiczne z zakresu algorytmów grafowych, przetwarzania danych (sortowania, porządkowania, wyboru, przetwarzania tekstów) i geometrii obliczeniowej; |
umiejętności specjalistyczne: K_U13 - K_U17 (++) | przedmiot pozwala opanować umiejętności stosowania pojęć i technik z danej dziedziny podstawowej w dziedzinach specjalistycznych i zastosowań informatyki, tj. algorytmy grafowe, przetwarzanie danych czy geometria obliczeniowa; studenci nabywają także umiejętność krytycznej analizy konstruowanych rozwiązań pod kątem ich zastosowania w konkretnej dziedzinie oraz poznają najnowsze rozwiązania w danym obszarze zastosowań algorytmiki. |
kompetencje praktyczne i zawodowe: K_U10-K_U11, K_W10-K_W12, K_K02-K_K04, K_K06-K_K07 (++) | przedmiot wymaga efektywnej implementacji wybranych problemów algorytmicznych z zastosowaniem poznanych technik i konstrukcji; pozwala to na rozwijanie umiejętności praktycznych; wykonywane zadania praktyczne stanowią trening umiejętności z zakresu planowania i organizacji działań, korzystania z narzędzi informatycznych i materiałów z poszanowaniem praw własności; |
Formy zajęć. Formy przekazywania wiedzy w ramach przedmiotu obejmują klasyczną formę wykładową oraz samodzielną pracę studentów w oparciu o materiały. Formy utrwalania wiedzy i nabywania umiejętności mają formę ćwiczeń z zadaniami problemowymi. Do przedmiotu jest prowadzona pracownia komputerowa.
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę prezentacji rozwiązań problemów w ramach ćwiczeń, rozwiązań zadań problemowych na sprawdzianach i w czasie egzaminu. Dodatkowo, poprzez zadania praktyczne w ramach pracowni, sprawdzane są praktyczne umiejętności konstrukcji efektywnych algorytmów i struktur danych.
Parametry przedmiotu. Zajęcia do przedmiotu mają formę wykładów, ćwiczeń i pracowni: 60 godz. wykładu, 30 godz. repetytorium, 30 godz. ćwiczeń i 30 godz. pracowni. Przedmiot kończy się egzaminem. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego i teoretycznego materiału oraz rozwiązania zadań problemowych szacuje się jak 2:1 w przypadku wykładu i ćwiczeń. Dla repetytorium nie przewiduje się dodatkowego czasu pracy studenta. Pracownia przewidziana do przedmiotu ma intensywny przebieg (jest przeprowadzana z pomocą automatycznego systemu sprawdzania), w związku z czym nakładu pracy własnej studenta szacuje się jak 2:1. Czas przygotowania do sprawdzianów i egzaminu, stanowiących immanentną część przedmiotu i związanego z nim procesu kształcenia, został wliczony w czas pracy studentów w przygotowanie do zajęć i systematyczne nabywanie wiedzy.
Całkowity nakład pracy studenta na przedmiot wynosi więc 3*60 + 3*30 + 30 + 3*30 = 390 godzin, w tym 120 godzin pracy z udziałem nauczyciela akademickiego i 90 godzin zajęć praktycznych. Wymiar punktowy przedmiotu jest sumarycznie szacowany na 13 punktów ECTS.
Nakład pracy na uzupełnienie przedmiotu na poziomie L do poziomu M, szacuje się jako nakład pracy na 15 godz. wykładu, 30 godz. ćwiczeń oraz 15 godz. pracowni. Różnica punktowa w stosunku do przedmiotu na poziomie L wynosi 4 ECTS.
Wiedza z zakresu wykładów analiza matematyczna oraz algebra.
Celem zajęć jest przedstawienie podstawowych metod i algorytmów rozwiązywania podstawowych zadań obliczeniowych. Omawiane zagadnienia mają wielorakie zastosowania m. in. w obliczeniach naukowych, wyszukiwaniu informacji i w grafice komputerowej.
Program wykładu zawiera następujące tematy:
· Arytmetyka komputerowa
· Rozwiązywanie równań nieliniowych
· Interpolacja wielomianowa w sensie Lagrange'a i Hermite'a. Interpolacja za pomocą funkcji sklejanych
· Aproksymacja funkcji - średniokwadratowa i jednostajna
· Kwadratury
· Rozwiązywanie układów równań liniowych. Metoda eliminacji Gaussa. Metody iteracyjne
Zalecana literatura
Kompetencje. Przedmiot wzbogaca matematyczne i algorytmiczne treści z programu studiów informatycznych I stopnia, rozszerzając je do zakresu z programu studiów informatycznych II stopnia. W wersji L (O.2L) od studentów wymagane jest opanowanie wiedzy i nabycie umiejętności w zakresie znajomości omawianych pojęć i technik, ich zrozumienia i zastosowania. W wersji M (O.2M) zakłada się, że studenci uzyskają umiejętność pogłębionej analizy omawianych pojęć, szerszego zastosowania poznanych technik oraz wzbogacenie wykładanych treści o wiedzę dotyczącą kierunków rozwoju obliczeń komputerowych i badań w dziedzinie analizy numerycznej.
Macierz odniesienia.
Odniesienie do kierunkowych obszarów kompetencji przedmiotu z tej grupy jest następujące:
Kategoria kompetencji: kierunkowy kod efektu (stopień nasycenia) | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (+++) | Prezentowany materiał teoretyczny i realizacje algorytmiczne obejmują najważniejsze zagadnienia analizy numerycznej; prezentowane twierdzenia i algorytmy są poparte precyzyjnymi dowodami poprawności i analizą złożoności obliczeniowej; |
umiejętności teoretyczne: K_U01, K_U06 (+++) | Wzorując się na standardowych rozwiązaniach prezentowanych na wykładzie studenci opracowują rozwiązania zbliżonych problemów i ich wersji praktycznych; prezentowane rozwiązania podlegają weryfikacji poprawności i skuteczności |
wiedza specjalistyczna: K_W05 - K_W07 (++) | Przedmiot daje podstawy teoretyczne nowych metod interpolacji i aproksymacji funkcji, całkowania numerycznego; wskazuje na ich zastosowania np. w konstrukcji krzywych Beziera i sklejanych, jak również ich wariantów i uogólnień |
umiejętności specjalistyczne: K_U13 - K_U17 (++) | Rozwiązania zagadnień praktycznych uzyskuje się stosując odpowiednio dobrany zestaw algorytmów rozwiązania modelowych problemów; elementem oceny jest konieczność samodzielnej implementacji wybranych rozwiązań, jak również opracowanie precyzyjnego raportu pisemnego |
kompetencje praktyczne i zawodowe: K_U10-K_U11, K_W10-K_W12, K_K02-K_K04, K_K06-K_K07 (++) | przedmiot wymaga samodzielnej implementacji wybranych rozwiązań, jak również opracowania precyzyjnego raportu pisemnego; realizowane w ten sposób zadania praktyczne i implementacyjne doskonalą umiejętności programistyczne oraz znajomość narzędzi informatycznych oraz stanowią trening umiejętności z zakresu planowania i organizacji działań oraz zasad etyki w działaniach informatyka; |
Formy zajęć. Formy przekazywania wiedzy w ramach przedmiotu obejmują klasyczną formę wykładową oraz samodzielną pracę studentów w oparciu o materiały. Formy utrwalania wiedzy i nabywania umiejętności mają formę repetytorium oraz ćwiczeń z zadaniami problemowymi. Do przedmiotu prowadzona jest pracownia wymagająca realizacji zadań implementacyjnych.
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę prezentacji rozwiązań problemów w ramach ćwiczeń, implementacji zadań programistycznych wraz z raportem pisemnym oraz rozwiązywania zadań problemowych w czasie egzaminu.
Parametry przedmiotu. Przedmiot odbywa się w wymiarze 60 godz. wykładu, 30 godz. ćwiczeń, 30 godz. repetytorium oraz 15 godz. pracowni, obejmującej samodzielne implementacje wybranych problemów. Przedmiot kończy się egzaminem. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego i teoretycznego materiału oraz rozwiązania zadań problemowych szacuje się jak 2:1 w przypadku wykładów, ćwiczeń i pracowni. W przypadku repetytorium nie zakłada się dodatkowego nakładu pracy studenta. Czas przygotowania do sprawdzianów i egzaminu został wliczony w czas pracy studentów związanej z przygotowaniem do zajęć i systematycznego nabywania wiedzy. Całkowity nakład pracy studenta wynosi zatem 3 * 60 + 3 * 30 + 3 * 15 + 30 = 345 godzin. Za zaliczenie przedmiotu student otrzymuje 12 punktów ECTS.
Nakład pracy na uzupełnienie przedmiotu na poziomie L do poziomu M, szacuje się jako nakład pracy na 15 godz. wykładu, 30 godz. ćwiczeń oraz 15 godz. pracowni. Różnica punktowa w stosunku do przedmiotu na poziomie L wynosi 4 ECTS.
Algebra, Analiza matematyczna, Wstęp do informatyki lub kurs ANSI C
Elementy Algebry i Teorii Liczb:
Funkcje
całkowitoliczbowe, arytmetyka modularna, operacje sufit i podłoga
zaokrąglania liczb rzeczywistych, algorytm mergesort. (2 godz.)
Asymptotyka funkcji liczbowych z uwzględnieniem zastosowań w szacowaniu złożoności czasowej algorytmów. (2 godz.)
Podzielność liczb, algorytm Euklidesa. (2 godz.)
Liczby Fibonacciego. (1 godz.)
Liczby
pierwsze i względnie pierwsze. Rozkład na czynniki. Funkcja Eulera.
Kwadraty łacińskie. Chińskie twierdzenie o resztach. Twierdzenie Eulera
(4 godz.)
Kombinatoryka:
Rozmieszczenia, permutacje, kombinacje, podziały (zbioru, liczby), Lemat Burnside'a. (4 godz.)
Metody generowania prostych obiektów kombinatorycznych. (2 godz.)
Przykłady prostych problemów definiowanych rekurencyjnie. (2 godz.)
Rozwiązywanie równań rekurencyjnych, funkcje tworzące. (4 godz.)
Liczby Catalana. (1 godz.)
Zasada włączania i wyłączania. (2 godz.)
Teoria grafów i zbiorów uporządkowanych:
Relacje porządku i równoważności i ich przykłady. (1 godz.)
Rozszerzenia liniowe zbiorów uporządkowanych - zastosowanie w konstrukcji algorytmów sortujących. (1 godz.)
Definicje i przykłady krat, krat rozdzielnych i Algebr Boole'a. (2 godz.)
Definicja i przykłady grafów, grafy pełne, dwudzielne skierowane, stopień wierzchołka. (2 godz.)
Drogi i cykle w grafach: grafy spójne i dwudzielne. (1 godz.)
Drzewa - równoważność różnych definicji. (1 godz.)
Komputerowa reprezentacja grafów. (1 godz.)
Metody BFS i DFS przeszukiwania grafów. (2 godz.)
Minimalne drzewa rozpinające - algorytmy Kruskala i Prima-Dijkstry. (2 godz.)
Przechodnie domkniecie: algorytmy Dijkstry i Warshalla. Złożoność problemu. (3 godz.)
Cykle i drogi Eulera. (1 godz.)
Cykle i drogi Hamiltona tw. Ore i wielomianowa redukcja problemu drogi do cyklu i odwrotnie. (2 godz.)
Grafy planarne. Tw. Kuratowskiego i wzór Eulera. (3 godz.)
Kolorowanie
grafów: zastosowanie - planowanie sesji egzaminacyjnej. Algorytm
sekwencyjny i twierdzenie o 5-kolorowaniu grafów planarnych. (2 godz.)
M.Ch.
Klin, R. Poesche, K. Rosenbaum, Algebra stosowana dla matematyków i
informatyków: grupy, grafy, kombinatoryka, WNT, Warszawa 1992.
R.L. Graham, D.E. Knuth, O. Patashnik, Matematyka konkretna, PWN, 1996.
J.L. Kulikowski, Zarys teorii grafów, PWN, Warszawa 1986.
W. Lipski, Kombinatoryka dla programistów, WNT, Warszawa 1982.
E.M. Reingold, J. Deo, N. Nievergelt, Algorytmy kombinatoryczne, PWN, Warszawa 1985.
K.A. Ross, Ch.B. Wright, Matematyka dyskretna, PWN, 1996.
M.M. Sysło, N. Deo, J. S. Kowalik, Algorytmy optymalizacji dyskretnej, PWN, Warszawa 1993.
R.J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa 1985.
M. Zakrzewski, T. Żak, Kombinatoryka, prawdopodobieństwo i zdrowy rozsądek, Quadrivium, Wrocław 1993
Kompetencje. Przedmiot obejmuje kluczowe treści matematyczne z zakresu algebry, kombinatoryki i teorii grafów niezbędne do zrozumienia zadadnień teorii algorytmów i stanowiące podstawę dla szeregu specjalistycznych dziedzin informatyki takich m.in. jak zagadnienia optymalizacji, kodowania i kryptografii. Zawieraja treści z programu studiów informatycznych I stopnia rozszerzone do treści z programu studiów informatycznych II stopnia. W wersji L (O.2L) od studentów wymagane jest poznanie:
W wersji M (O.2M) od studentów wymagana jest umiejętność pogłębionej analizy omawianych pojęć, szerszego zastosowania poznanych technik oraz wzbogacenie wykładanych treści o wiedzę dotyczącą kierunków rozwoju informatyki i badań w danej dziedzinie, w szczególności:
Macierz odniesienia.
Odniesienie do kierunkowych obszarów kompetencji przedmiotu z tej grupy jest następujące:
Kategoria kompetencji: kierunkowy kod efektu (stopień nasycenia) | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (+++) | wykładane w ramach przedmiotu treści odwołują się istotnie do matematycznych podstaw informatyki i obejmują zaawansowane pojęcia i techniki matematyczne; przedstawiane w ramach przedmiotu treści są w pełni uzasadniane z użyciem ścisłych technik dowodowych; |
umiejętności teoretyczne: K_U01, K_U06 (+++) | przedmiot wymaga opanowania umiejętności dowodzenia twierdzeń dla szerokiego spektrum problemów, z zastosowaniem zaawansowanych technik kombinatorycznych i algebraicznych; |
wiedza specjalistyczna: K_W05 - K_W07 (++) | treści zawarte w przedmiocie stanowią podstawę szeregu dziedzin specjalistycznych i zastosowań informatyki; w ramach przedmiotu omawiane są zagadnienia matematyczne związane z rozwiązywaniem zależności rekurencyjnych, algebry, kombinatoryki i teorii grafów; |
umiejętności specjalistyczne: K_U13 - K_U17 (++) | przedmiot pozwala opanować umiejętności stosowania pojęć i technik z danej dziedziny podstawowej w dziedzinach specjalistycznych i zastosowań informatyki, tj. algorytmy i struktury danych, kryptografia, algorytmy grafowe, przetwarzanie danych czy geometria obliczeniowa. |
Formy zajęć. Formy przekazywania wiedzy w ramach przedmiotu obejmują klasyczną formę wykładową oraz samodzielną pracę studentów w oparciu o materiały. Formy utrwalania wiedzy i nabywania umiejętności mają formę repetytorium i ćwiczeń z zadaniami problemowymi.
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę prezentacji rozwiązań problemów w ramach ćwiczeń oraz rozwiązań zadań problemowych na egzamine pisemnym.
Parametry przedmiotu. Zajęcia do przedmiotu mają formę wykładów, repetytorium i ćwiczeń: 45 godz. wykładu, 30 godz. repetytorium i 45 godz. ćwiczeń. Przedmiot kończy się egzaminem. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego i teoretycznego materiału oraz rozwiązania zadań problemowych szacuje się jak 2:1 w przypadku wykładów i ćwiczeń. Dla repetytorium nie zakłada się dodatkowego nakładu pracy studentów. Czas przygotowania do sprawdzianów i egzaminu, stanowiących immanentną część przedmiotu i związanego z nim procesu kształcenia, został wliczony w czas pracy studentów w przygotowanie do zajęć i systematyczne nabywanie wiedzy.
Całkowity nakład pracy studenta na przedmiot wynosi więc 3*45 + 30 + 3 *45 = 300 godzin, w tym 120 godzin pracy z udziałem nauczyciela akademickiego. Wymiar punktowy przedmiotu jest oszacowany na 9 punktów ECTS.
Nakład pracy na uzupełnienie przedmiotu na poziomie L do poziomu M, szacuje się jako nakład pracy na 15 godz. wykładu i 15 godz. ćwiczeń. Różnica punktowa w stosunku do przedmiotu na poziomie L wynosi 3 ECTS.
Celem wykładu jest przedstawienie studentom możliwie szerokiego kręgu zagadnień związanych z teorią języków programowania i jej zastosowaniami, ze szczególnym uwzględnieniem paradygmatów programowania imperatywnego i funkcyjnego oraz podstaw formalnych metod dowodzenia własności programów.
Logika dla informatyków, Wstęp do informatyki.
“Semantics with Applications: A Formal Introduction”, H. R. Nielson, F. Nielson
“The Formal Semantics of Programming Languages: An Introduction”, G. Winskel
“Semantics of Programming Languages”, A. Pitts
“Introduction to Lambda Calculus”, H. Barendregt, E. Barendsen
“Lecture Notes on Types”, A. Pitts
“Types and Programming Languages”, B. Pierce
Kompetencje. Przedmiot odwołuje się do matematycznych podstaw informatyki i obejmuje kluczowe, ogólne zagadnienia z teorii informatyki stanowiące podstawę dla teorii języków programowania oraz weryfikacji dedukcyjnej. Zawiera treści z programu studiów informatycznych I stopnia rozszerzone do treści z programu studiów informatycznych II stopnia. W wersji L (O.2L) od studentów wymagane jest opanowanie wiedzy i nabycie umiejętności w zakresie znajomości omawianych pojęć i technik, ich zrozumienia i zastosowania. W wersji M (O.2M) od studentów wymagana jest umiejętność pogłębionej analizy omawianych pojęć, w szczególności umiejętność samodzielnego opisania semantyki języka programowania w poznanych paradygmatach programowania i formalnego wnioskowania o własnościach programów napisanych w tym języku.
Macierz odniesienia.
Odniesienie do kierunkowych obszarów kompetencji przedmiotu z tej grupy jest następujące:
Kategoria kompetencji: kierunkowy kod efektu (stopień nasycenia) | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (+++) | wykładane w ramach przedmiotu treści odwołują się istotnie do matematycznych podstaw informatyki i obejmują klasyczne pojęcia i techniki z teorii języków programowania; przedstawiane w ramach przedmiotu treści są w pełni uzasadniane z użyciem ścisłych technik dowodowych; omawiane są m.in. dedukcyjne metody dowodzenia poprawności programów, formalne metody opisu semantyki; |
umiejętności teoretyczne: K_U01, K_U06 (+++) | przedmiot pozwala opanować umiejętność definiowania i analizowania języków programowania w różnych paradygmatach ze szczególnym uwzględnieniem paradygmatów imperatywnego i funkcyjnego; |
wiedza specjalistyczna: K_W05 - K_W07 (++) | treści zawarte w przedmiocie stanowią podstawę szeregu dziedzin specjalistycznych i zastosowań informatyki, m. in. w formalnym opisie i implementacji języków programowania oraz weryfikacji oprogramowania; |
umiejętności specjalistyczne: K_U13 - K_U17 (++) | przedmiot pozwala opanować umiejętności stosowania pojęć i technik z danej dziedziny podstawowej w dziedzinach specjalistycznych i zastosowań informatyki; studenci nabywają także umiejętność krytycznej analizy konstruowanych rozwiązań pod kątem konkretnych zastosowań, m. in. umiejętność doboru paradygmatu oraz języka programowania do implementacji algorytmów z dowolnej dziedziny; umiejętność formalnego opisu konkretnych konstrukcji językowych oraz prototypowej implementacji, umiejętność wnioskowania o poprawności i innych własnościach programów. |
Formy zajęć. Formy przekazywania wiedzy w ramach przedmiotu obejmują klasyczną formę wykładową oraz samodzielną pracę studentów w oparciu o materiały. Formy utrwalania wiedzy i nabywania umiejętności mają formę ćwiczeń z zadaniami problemowymi.
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę prezentacji rozwiązań problemów w ramach ćwiczeń, rozwiązań zadań problemowych na sprawdzianach i w czasie egzaminu. Ocena końcowa jest wyliczana jako średnia arytmetyczna oceny z ćwiczeń (ustalanej na podstawie aktywności na ćwiczeniach oraz wyników sprawdzianów) oraz oceny z egzaminu.
Efekt | Forma weryfikacji |
Wiedza teoretyczna | Ćwiczenia, sprawdziany oraz egzamin (sprawdzanie znajomości definicji, twierdzeń itp.) |
Umiejętności teoretyczne
| Ćwiczenia, sprawdziany oraz egzamin (sprawdzanie umiejętności wykorzystania poznanych narzędzi teoretycznych do rozwiązywania zadań problemowych |
Wiedza specjalistyczna
| Ćwiczenia, sprawdziany oraz egzamin (zadania problemowe dotyczące konstrukcji językowych w różnych paradygmatach programowania) |
Umiejętności specjalistyczne
| Ćwiczenia, sprawdziany oraz egzamin (zadania problemowe dotyczące analizy zagadnień występujących w różnych paradygmatach programowania) |
Parametry przedmiotu. Zajęcia do przedmiotu mają formę wykładów i ćwiczeń: 15 godz. wykładu i 15 godz. ćwiczeń. Przedmiot kończy się egzaminem. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego i teoretycznego materiału oraz rozwiązania zadań problemowych szacuje się jak 2:1 w przypadku wszystkich zajęć. Czas przygotowania do sprawdzianów i egzaminu, stanowiących immanentną część przedmiotu i związanego z nim procesu kształcenia, został wliczony w czas pracy studentów w przygotowanie do zajęć i systematyczne nabywanie wiedzy.
Całkowity nakład pracy studenta na przedmiot wynosi więc 90 godzin, w tym 30 godzin pracy z udziałem nauczyciela akademickiego. Wymiar punktowy na poziomie M przedmiotu jest szacowany na 3 punkty ECTS.
Program przedmiotu obejmuje zaawansowane aspekty algorytmów grafowych: efektywne implementacje klasycznych algorytmów, algorytmy dla ważnych podklas grafów, algorytmy dla grafów zmieniających się w czasie, algorytmy oparte na własnościach algebraicznych macierzy sąsiedztwa. Rozważane zagadnienia wybrane zostały na podstawie ich znaczenia dla rozwoju teorii oraz zastosowań w innych gałęziach informatyki oraz dziedzinach nauki. Wśród poruszanych tematów znajdują się:
Wymagana jest znajomość tematyki z zakresu algorytmów i struktur danych.
Kompetencje. Przedmiot zawiera specjalistyczne treści oparte na matematycznych podstawach informatyki i teorii informatyki. Treści te pokrywają w istotnym stopniu stan dziedziny z uwzględnieniem najnowszych osiągnięć i zastosowań praktycznych.
Macierz odniesienia. Odniesienie do kierunkowych obszarów kompetencji jest następujące:
Kategoria kompetencji: kierunkowe kody efektów (stopień nasycenia) | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (++) | Prezentowane algorytmy są konstrukcjami złożonymi, korzystającymi intensywnie z klasycznych technik informatycznych i aparatu matematycznego, w szczególności w zakresie matematyki dyskretnej i probalistyki. |
umiejętności teoretyczne: K_U01 - K_U06 (++) | Zadania rozwiązywane w ramach ćwiczeń wymagają, często głębokiej, analizy problemu, wyboru odpowiednich struktur danych i konstrukcji algorytmicznych na podstawie analizy ich efektywności obliczeniowej.
|
wiedza specjalistyczna: K_W05-07 (+++) | Wiele z prezentowanych tematów stanowi pole intensywnych badań naukowych. Studenci poznają najnowsze wyniki, obecny stan badań a także otwarte problemy, będące wyzwaniami dla współczesnej nauki. Wiele z nich ma bezpośrednie zastosowanie w innych gałęziach informatyki, jak przykładowo sieci komputerowe, analiza danych, baz danych, weryfikacja programów, itd… |
umiejętności specjalistyczne: K_U13-U17 (+++) | Studenci analizują poznawane algorytmy pod kątem ich poprawności oraz możliwości ich efektywnej implementacji. Problemy rozważane na ćwiczeniach uczą umiejętności wyabstrahowania z nich problemów grafowych. |
wiedza w zakresie zastosowań: K_W08-K_W09 (++) | Omawiane na wykładzie algorytmy grafowe mają bezpośrednie zastosowanie w wielu dziedzinach nauki i techniki (m.in. w sieciach komputerowych, analizie danych, bazach danych, weryfikacji programów). |
umiejętności w zakresie zastosowań: K_U05, K_U12 (++) | Poznanie prezentowanych algorytmów, rozwiązanie problemów rozważanych na ćwiczeniach oraz implementacja algorytmów w ramach prac domowych pozwalają nabyć umiejętności praktycznego stosowania algorytmów grafowych oraz użytych w nich technik do rozwiązywania wielu problemów, które mogą być modelowane problemami grafowymi. |
Formy zajęć. Formy przekazywania wiedzy w ramach przedmiotu obejmują klasyczną formę wykładową oraz samodzielną pracę studentów w oparciu o materiały. Formy utrwalania wiedzy i nabywania umiejętności obejmują ćwiczenia problemowe oraz zastosowania zdobytej wiedzy wykonywane w formie klasycznych ćwiczeń oraz efektywnych implementacji poznanych algorytmów.
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę prezentacji rozwiązań problemów w ramach ćwiczeń, implementacji algorytmów w ramach prac domowych, rozwiązań zadań problemowych na sprawdzianach i w czasie egzaminu.
Parametry przedmiotu. Przedmiot odbywa się w wymiarze 30 godz. wykładu oraz 30 godz. ćwiczeń i kończy się egzaminem. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego materiału oraz rozwiązania zadań problemowych szacuje się jak 1:1 w przypadku materiału wykładowego, 2:1 w przypadku zadań ćwiczeniowych, dodatkowo czas przygotowania i podejścia do egzaminu szacuje się jako 20 godzin. Za zaliczenie przedmiotu student otrzymuje 6 punktów ECTS.
Efekty dodatkowe.
Tematyka przedmiotu. W przypadku niektórych zagadnień informatycznych (routing w sieciach komputerowych, pamięć podręczna procesorów, buforowanie danych w Internecie, szeregowanie zadań) algorytm je rozwiazujący musi działać w sposób on-line i dokonywać decyzji bez wiedzy lub z częściową wiedzą o przyszłości. Na tym wykładzie zaprezentowane zostaną techniki i metody umożliwiające rozwiązywanie takich problemów optymalizacyjnych. Zaprezentowane zostaną rozwiązania przybliżone, dla których można dowodzić konkretnych gwarancji na temat jakości takich przybliżeń.
Kompetencje. Przedmiot zawiera specjalistyczne treści oparte na matematycznych podstawach informatyki i teorii informatyki. Treści te pokrywają w istotnym stopniu stan dziedziny z uwzględnieniem najnowszych osiągnięć i zastosowań praktycznych.
Macierz odniesienia. Odniesienie do kierunkowych obszarów kompetencji jest następujące:
Kategoria kompetencji: kierunkowe kody efektów (stopień nasycenia) | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (++) | Konstrukcja i analiza algorytmów on-line wykorzystuje zaawansowane techniki algorytmiczne wykorzystujące aparat matematyczny zarówno w konstrukcji, jak i analizie pojęć. |
umiejętności teoretyczne: K_U01 - K_U06 (++) | Analiza przeprowadzanych w ramach przedmiotu konstrukcji i rozumowań wymaga ścisłego stosowania aparatu matematycznego oraz wnikliwej analizy algorytmów. |
wiedza specjalistyczna: K_W05-07 (+++) | W ramach kursu studenci poznają klasyczne i najnowsze techniki umożliwiające rozwiązywanie najważniejszych problemów dziedziny. Wykład wprowadza pojęcia niezbędne do zrozumienia prac badawczych z dziedziny algorytmów on-line. |
umiejętności specjalistyczne: K_U13-U17 (+++) | Rozwiązania zagadnień praktycznych uzyskuje się stosując poznane na wykładzie techniki. Elementem oceny jest dobór odpowiednich poznanych narzędzi do nowych optymalizacyjnych problemów on-line. |
wiedza w zakresie zastosowań: K_W08-K_W09 (++) | Omawiane w ramach przedmiotu zagadnienia znajdują zastosowanie w wielu innych dziedzinach informatyki (np. w systemach operacyjnych, sieciach komputerowych, dynamicznych strukturach danych czy eksploracji terenu). |
umiejętności w zakresie zastosowań: K_U05, K_U12 (++) | Poznawane techniki on-line pozwalają rozwiązywać problemy optymalizacyjne z rozmaitych dziedzin. |
Formy zajęć. Formy przekazywania wiedzy w ramach przedmiotu obejmują klasyczną formę wykładową oraz samodzielną pracę studentów w oparciu o materiały. Formy utrwalania wiedzy i nabywania umiejętności obejmują ćwiczenia problemowe oraz zastosowania zdobytej wiedzy wykonywane w formie klasycznych ćwiczeń.
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę prezentacji rozwiązań problemów w ramach ćwiczeń i rozwiązań zadań problemowych w czasie egzaminu.
Parametry przedmiotu. Przedmiot odbywa się w wymiarze 30 godz. wykładu oraz 30 godz. ćwiczeń i kończy się egzaminem. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego materiału oraz rozwiązania zadań problemowych szacuje się jak 1:1 w przypadku materiału wykładowego, 2:1 w przypadku zadań ćwiczeniowych, dodatkowo czas przygotowania i podejścia do egzaminu szacuje się jako 20 godzin. Za zaliczenie przedmiotu student otrzymuje 6 punktów ECTS.
Przedmiot obejmuje klasyczne zagadnienia i nowe rozwiązania z dziedziny przetwarzania i przeszukiwania danych tekstowych. W dziedzinie tej znajdują się zarówno trudne i bazujące na zawansowanych konstrukcjach matematyczno-informatycznych rozwiązania, jak i prostsze koncepcyjnie, ale nadal bardzo pomysłowe i efektywne (także efektowne) konstrukcje algorytmiczne. Wśród poruszanych tematów znajdują się:
Wymagane przygotowanie do przedmiotu to znajomość tematyki z zakresu algorytmów i struktur danych.
Kompetencje. Przedmiot zawiera specjalistyczne treści oparte na matematycznych podstawach informatyki i teorii informatyki. Treści te pokrywają w istotnym stopniu stan dziedziny z uwzględnieniem najnowszych osiągnięć i zastosowań praktycznych.
Macierz odniesienia. Odniesienie do kierunkowych obszarów kompetencji jest następujące:
Kategoria kompetencji: kierunkowe kody efektów (stopień nasycenia) | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (++) | konstrukcja i analiza algorytmów teksowych odwołuje się do klasycznych technik informatycznych i wykorzystuje aparat matematyczny zarówno w konstrukcji, jak i analizie pojęć |
umiejętności teoretyczne: K_U01 - K_U06 (++) | analiza przeprowadzanych w ramach przedmiotu konstrukcji i rozumowań wymaga ścisłego stosowania aparatu matematycznego oraz wnikliwej analizy informatycznej |
wiedza specjalistyczna: K_W05-07 (+++) | w zakresie dziedziny algorytmów tekstowych studenci poznają klasyczne i najnowsze rozwiązania najważniejszych problemów: porównywania i przeszukiwania tekstów oraz konstrukcji struktur słownikowych; oprócz rozwiązan stricte informatycznych omawiane zagadnienie wiążą się z analizą danych genetycznych, zasobów internetowych, problamatyką kompresji i przetwarzaniu danych multimedialnych |
umiejętności specjalistyczne: K_U13-U17 (+++) | w zakresie dziedziny algorytmów tekstowych studenci analizują i stosują klasyczne i najnowsze rozwiązania najważniejszych problemów z dziedziny; |
wiedza w zakresie zastosowań: K_W08-K_W09 (++) | omawiane w ramach przedmiotu zagadnienia znajdują zastosowanie w innych dziedzinach informatyki (kompresja, wyszukiwarki Internetowe) oraz dziedzinach bardzie odległych, jak genetyka |
umiejętności w zakresie zastosowańi: K_U05, K_U12 (++) | odniesienie treści przedmiotu do innych dziedzin oraz analiza praktycznych rozwiązań problemów z tych dziedzin pozwalają nabyć umiejętności praktycznego stosowania informatyki w dziedzinach powiązanych z tematyka algorytmów tekstowych |
Formy zajęć. Formy przekazywania wiedzy w ramach przedmiotu obejmują klasyczną formę wykładową oraz samodzielną pracę studentów w oparciu o materiały. Formy utrwalania wiedzy i nabywania umiejętności obejmują ćwiczenia problemowe oraz zastosowania zdobytej wiedzy wykonywane w formie klasycznych ćwiczeń.
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę prezentacji rozwiązań problemów w ramach ćwiczeń, rozwiązań zadań problemowych na sprawdzianach i w czasie egzaminu.
Parametry przedmiotu. Przedmiot odbywa się w wymiarze 30 godz. wykładu oraz 30 godz. ćwiczeń i kończy się egzaminem. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego materiału oraz rozwiązania zadań problemowych szacuje się jak 1:1 w przypadku materiału wykładowego, 2:1 w przypadku zadań ćwiczeniowych, dodatkowo czas przygotowania i podejścia do egzaminu szacuje się jako 20 godzin. Oszacowanie całkowitego Za zaliczenie przedmiotu student otrzymuje 6 punktów ECTS.
Efekty dodatkowe.
Tematyka
przedmiotu obejmuje najważniejsze algorytmy i struktury danych używane w
dyskretnej geometrii, głównie w dwóch i trzech wymiarach. Rozważane
zagadnienia znajdują zastosowania w grafice komputerowej, geograficznych
systemach informacyjnych (GIS), robotyce, i in. Przy omawianiu
poszczególnych problemów i algorytmów prezentowane też są przykłady ich
zastosowań.
Wśród poruszanych tematów znajdą się:
Znajomość tematyki z zakresu algorytmów i struktury danych.
Kompetencje. Przedmiot zawiera treści oparte na matematycznych podstawach informatyki i teorii informatyki. Treści te pokrywają w istotnym stopniu stan dziedziny z uwzględnieniem najnowszych osiągnięć i zastosowań praktycznych.
Macierz odniesienia. Odniesienie do kierunkowych obszarów kompetencji jest następujące:
Kategoria kompetencji: kierunkowe kody efektów (stopień nasycenia) | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (++) | prezentowane rozwiązania algorytmiczne są poparte precyzyjnymi dowodami poprawności i analizą złożoności obliczeniowej, dolnymi granicami; materiał obejmuje najważniejsze zagadnienia geometrii obliczeniowej oraz kluczowe dla jej obszaru struktury danych i techniki algorytmiczne; |
umiejętności teoretyczne: K_U01 - K_U06 (++) | w oparciu o klasyczne rozwiązania prezentowane na wykładzie studenci opracowują rozwiązania szeregu problemów pokrewnych i praktycznych; prezentowane rozwiązania muszą być poparte formalną analizą złożoności i poprawności; |
wiedza specjalistyczna: K_W05-07 (+++) | przedmiot daje podstawy teoretyczne nowych trendów w geometrii obliczeniowej, w tym narzędzi analizy przestrzeni wielowymiarowych; program kładzie nacisk na powiązania z grafiką komputerową, systemami nawigacji, robotyką i in. działami informatyki |
umiejętności specjalistyczne: K_U13-U17 (+++) | w ramach przedmiotu dobiera się rozwiązania abstrakcyjnych problemów do zagadnień praktycznych, uwzględniając specyfikę zastosowań (skalowalność, rola poszczególnych parametrów, modelowanie); elementem oceny jest konieczność samodzielnej implementacji wybranych rozwiązań; |
wiedza w zakresie zastosowańi: K_W08-K_W09 (++) | w ramach samodzielnej pracy studenci implementują poznane algorytmy i zapoznają się z dostępnymi bibliotekami graficznymi (np. LEDA) |
umiejętności w zakresie zastosowań: K_U05, K_U12 (++) | materiał wykładu pokrywa szereg problemów o zastosowaniach w innych dziedzinach: nawigacja, robotyka, wizualizacja (p. wyżej); |
Formy zajęć. Formy przekazywania wiedzy w ramach przedmiotu obejmują klasyczną formę wykładową oraz samodzielną pracę studentów w oparciu o materiały. Formy utrwalania wiedzy i nabywania umiejętności obejmują ćwiczenia problemowe oraz zastosowania zdobytej wiedzy wykonywane w formie klasycznych ćwiczeń.
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę prezentacji rozwiązań problemów w ramach ćwiczeń, rozwiązań zadań problemowych na sprawdzianach i w czasie egzaminu.
Parametry przedmiotu. Przedmiot odbywa się w wymiarze 30 godz. wykładu, oraz 20 godz. ćwiczeń oraz 10 godz. przeznaczonych na pracownię, której bazę stanowią samodzielne implementacje wybranych problemów. Przedmiot kończy się egzaminem. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego materiału, rozwiązania zadań problemowych oraz implementacji algorytmów szacuje się jak 1:1 w przypadku materiału wykładowego, 2:1 w przypadku zadań ćwiczeniowych i 2,5:1 w przypadku zadań programistycznych. Dodatkowo czas przygotowania i podejścia do egzaminu szacuje się jako 20 godzin. Za zaliczenie przedmiotu student otrzymuje 6 punktów ECTS.
Dodatkowe uwagi.
Głównymi celami tego przedmiotu są zaznajomienie studentów z podstawowymi algorytmami i protokołami występującymi w obliczeniach rozproszonych oraz wykształcenie umiejętności konstrukcji i analizy takich algorytmów . Rozważane są modele synchroniczne i asynchroniczne, w których procesy komunikują się poprzez sieć. Zasadniczym rozważanym modelem komunikacji jest dwustronna wymiana komunikatów.
Następujące tematy są omawiane w ramach tego przedmiotu:
Znajomość tematyki z zakresu algorytmów i struktur danych.
Kompetencje. Przedmiot zawiera specjalistyczne treści oparte na matematycznych podstawach informatyki i teorii informatyki. Treści te pokrywają w istotnym stopniu stan dziedziny z uwzględnieniem najnowszych osiągnięć i zastosowań praktycznych.
Macierz odniesienia. Odniesienie do kierunkowych obszarów kompetencji jest następujące:
Kategoria kompetencji: kierunkowe kody efektów (stopień nasycenia) | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (++) | studenci poznają klasyczne, formalne techniki dowodzenia poprawności algorytmów rozproszonych oraz analizy ich złożoności; rozumie konieczność formalnego dowodzenia poprawności algorytmów i protokołów rozproszonych; potrafi przedstawić modele obliczeń synchronicznych i asynchronicznych; |
umiejętności teoretyczne: K_U01 - K_U06 (++) | w ramach przedmiotu studenci stosując aparat matematyczny analizują algorytmy rozproszone dowodząc ich poprawności oraz szacując ich złożoność; potrafią wskazać co najmniej jeden problem obliczeń rozproszonych, który nie ma rozwiązania algorytmicznego; |
wiedza specjalistyczna: K_W05-07 (+++) | studenci są w stanie zrozumieć pracę naukową dotyczącą algorytmów rozproszonych; potrafią przedstawić zastosowania algorytmów rozproszonych w realnych systemach komputerowych; |
umiejętności specjalistyczne: K_U13-U17 (+++) | student potrafi analizować problemy obliczeń rozproszonych oraz wybrać i zaadaptować odpowiedni dla problemu model obliczeń oraz algorytm rozproszony; potrafi zaprojektować i przeanalizować algorytm rozproszony dla wybranych zagadnień; |
wiedza w zakresie zastosowań: K_W08-K_W09 (++) | student zna zasady konstrukcji modeli obliczeń oraz algorytmów rozproszonych dla wybranych zagadnień; potrafi przedstawić wybrane algorytmy rozproszone stosowane w sieciach komputerowych i rozproszonych bazach danych; |
umiejętności w zakresie zastosowań: K_U05, K_U12 (++) | student poznaje możliwe zastosowania obliczeń rozproszonych i potrafi zastosować algorytmy rozproszone do rozwiązywania zadań w różnych dziedzinach. |
Formy zajęć. Formy przekazywania wiedzy w ramach przedmiotu obejmują klasyczną formę wykładową oraz samodzielną pracę studentów w oparciu o materiały. Formy utrwalania wiedzy i nabywania umiejętności obejmują ćwiczenia problemowe oraz zastosowania zdobytej wiedzy wykonywane w formie klasycznych ćwiczeń.
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę prezentacji rozwiązań problemów w ramach ćwiczeń, rozwiązań zadań problemowych na sprawdzianach i w czasie egzaminu.
Parametry przedmiotu. Przedmiot odbywa się w wymiarze 30 godz. wykładu oraz 30 godz. ćwiczeń i kończy się egzaminem. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego materiału oraz rozwiązania zadań problemowych szacuje się jak 1:1 w przypadku materiału wykładowego, 2:1 w przypadku zadań ćwiczeniowych, dodatkowo czas przygotowania i podejścia do egzaminu szacuje się jako 20 godzin. Oszacowanie całkowitego Za zaliczenie przedmiotu student otrzymuje 6 punktów ECTS.
Efekty dodatkowe.
Tematyka przedmiotu.
Przedmiot obejmuje klasyczne zagadnienia kombinatoryki niezawarte w programie Matematyki dyskretnej. Wśród poruszanych tematów znajdują się:
R.L. Graham, D.E. Knuth, O. Patashnik, Matematyka konkretna, PWN 1996.
W.Lipski, W.Marek, Analiza kombinatoryczna, PWN 1988.
Z.V.Mensikov i in., Analiza kombinatoryczna w zadaniach, PWN, Warszawa 1988.
Z.Pałka, A.Ruciński, Niekonstruktywne metody matematyki dyskretnej, PWN, Warszawa 1996.
M.Sysło, N.Deo, J.Kowalik, Algorytmy optymalizacji dyskretnej, PWN, Warszawa 1995.
Znajomość tematyki z zakresu matematyki dyskretnej.
Kompetencje. Przedmiot zawiera specjalistyczne treści oparte na matematycznych podstawach informatyki i teorii informatyki. Treści te pokrywają w istotnym stopniu stan dziedziny z uwzględnieniem najnowszych osiągnięć i zastosowań praktycznych.
Macierz odniesienia. Odniesienie do kierunkowych obszarów kompetencji jest następujące:
Kategoria kompetencji: kierunkowe kody efektów (stopień nasycenia) | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (++) | Poruszana tematyka jest często używana jako narzędzie do dowodzenia twierdzeń w dziedzinie informatyki teoretycznej. |
umiejętności teoretyczne: K_U01 - K_U06 (++) | analiza przeprowadzanych w ramach przedmiotu konstrukcji i rozumowań wymaga ścisłego stosowania aparatu matematycznego |
wiedza specjalistyczna: K_W05-07 (+++) | Używany materiał w dziedzinie kombinatoryki jest niezbędny do zrozumienia wielu nowych wyników z informatyki teoretycznej. |
umiejętności specjalistyczne: K_U13-U17 (+++) | Poruszana tematyka szczególnie w zakresie metody probabilistycznej jest niezbędna do zrozumienia niekonstruktywnych metod dowodzących istnienie separatorów i koncentratorów stanowiących ważne narzędzie w dowodzeniu istnienia efektywnych algorytmów. |
wiedza w zakresie zastosowań: K_W08-K_W09 (++) | wiedza nabyta przez studenta jest przydatna w rozwiązywaniu praktycznych problemów związanych z użyciem metod kombinatorycznych. |
umiejętności w zakresie zastosowań: K_U05, K_U12 (++) | poznane przez studentów metody i techniki są stosowane w rozwiązywaniu praktycznych problemów z różnych dziedzin; studenci poznają przykłady efektywnych zastosowań metod kombinatorycznych. |
Formy zajęć. Formy przekazywania wiedzy w ramach przedmiotu obejmują klasyczną formę wykładową oraz samodzielną pracę studentów w oparciu o materiały. Formy utrwalania wiedzy i nabywania umiejętności obejmują ćwiczenia problemowe oraz zastosowania zdobytej wiedzy wykonywane w formie klasycznych ćwiczeń.
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę prezentacji rozwiązań problemów w ramach ćwiczeń, rozwiązań zadań problemowych w czasie egzaminu.
Parametry przedmiotu. Przedmiot odbywa się w wymiarze 30 godz. wykładu oraz 30 godz. ćwiczeń i kończy się egzaminem. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego materiału oraz rozwiązania zadań problemowych szacuje się jak 1:1 w przypadku materiału wykładowego, 2:1 w przypadku zadań ćwiczeniowych, dodatkowo czas przygotowania i podejścia do egzaminu szacuje się jako 20 godzin. Oszacowanie całkowitego Za zaliczenie przedmiotu student otrzymuje 6 punktów ECTS.
Celem wykładu jest zapoznanie uczestników z nowoczesnymi metodami służącymi do ochrony prywatnosci danych elektronicznych, autentyfikacji użytkowników systemów komputerowych, zabezpieczaniu przed nieuprawnionymi modyfikacjami danych i innymi tego typu zastosowaniami opartymi na technikach kryptograficznych. Znaczenie tego typu metod ujawnia się szczególnie ostro w epoce powstawania globalnych sieci komputerowych, gdzie systemy operacyjne nie gwarantują już bezpieczeństwa.
Główny nacisk położony zostanie na prezentację metod albo obecnie stosowanych, bądź też wchodzących do praktyki. Niemniej jednak uczestnicy wykładu będą mieli okazję zapoznania się z materiałem teoretycznym będącym podstawa dla zrozumienia tych metod.
Uczestnicy zajęc przygotowani zostaną do pracy w zakresie projektowania i użytkowania systemów w zakresie problematyki bezpieczeństwa.
Matematyka dyskretna
Douglas Stinson, Kryptografia, WNT 2005
Kompetencje. Przedmiot zawiera specjalistyczne treści oparte na matematycznych podstawach informatyki i teorii informatyki. Treści te pokrywają w istotnym stopniu stan dziedziny z uwzględnieniem najnowszych osiągnięć i zastosowań praktycznych.
Macierz odniesienia. Odniesienie do kierunkowych obszarów kompetencji jest następujące:
Kategoria kompetencji: kierunkowe kody efektów (stopień nasycenia) | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (++) | Przedmiot objaśnia matematyczne podstawy kryptografii. Wprowadza on podstawowe matematyczne definicje związane z bezpieczeństwem algorytmów kryptograficznych.. |
umiejętności teoretyczne: K_U01 - K_U06 (++) | analiza przeprowadzanych w ramach przedmiotu konstrukcji i rozumowań wymaga ścisłego stosowania aparatu matematycznego oraz wnikliwej analizy informatycznej |
wiedza specjalistyczna: K_W05-07 (+++) | Kurs wprowadza podstawowe definicje i pojęcia niezbędne do zrozumienia prac badawczych w dziedzinie kryptografii. |
umiejętności specjalistyczne: K_U13-U17 (+++) | w zakresie dziedziny kryptografii studenci analizują i stosują klasyczne i najnowsze rozwiązania najważniejszych problemów z dziedziny; |
wiedza w zakresie zastosowań: K_W08-K_W09 (++) | omawiane w ramach przedmiotu zagadnienia znajdują szerokie zastosowania praktyczne, szczególnie związane z problemami transakcji finansowych i organizacji bezpiecznego przepływu informacji w firmach. |
umiejętności w zakresie zastosowań: K_U05, K_U12 (++) | studenci poznają zastosowania metod i technik kryptograficznych w organizacji przepływu danych i informacji; dla wybranych zagadnień potrafią zastosować odpowiedni protokół kryptograficzny. |
Formy zajęć. Formy przekazywania wiedzy w ramach przedmiotu obejmują klasyczną formę wykładową oraz samodzielną pracę studentów w oparciu o materiały. Formy utrwalania wiedzy i nabywania umiejętności obejmują ćwiczenia problemowe oraz zastosowania zdobytej wiedzy wykonywane w formie klasycznych ćwiczeń.
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę prezentacji rozwiązań problemów w ramach ćwiczeń, rozwiązań zadań problemowych na sprawdzianach i w czasie egzaminu.
Parametry przedmiotu. Przedmiot odbywa się w wymiarze 30 godz. wykładu oraz 30 godz. ćwiczeń i kończy się egzaminem. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego materiału oraz rozwiązania zadań problemowych szacuje się jak 1:1 w przypadku materiału wykładowego, 2:1 w przypadku zadań ćwiczeniowych, dodatkowo czas przygotowania i podejścia do egzaminu szacuje się jako 20 godzin. Oszacowanie całkowitego Za zaliczenie przedmiotu student otrzymuje 6 punktów ECTS.
Tematyka przedmiotu obejmuje przedstawienie podstawowych narzędzi matematycznych stosowanych w grafice komputerowej do opisu krzywych i powierzchni. Oprócz nowego ujęcia znanych metod, np. interpolacji funkcji jednej zmiennej za pomocą wielomianów lub funkcji sklejanych, omawiane są inne nowoczesne techniki modelowania krzywych. Szczegółowo dyskutuje się modelowanie powierzchni, w tym - efektywne algorytmy ich interpolacji i aproksymacji.
Znajomość tematyki z zakresu analizy matematycznej i analizy numerycznej.
Kompetencje. Przedmiot zawiera treści oparte na matematycznych podstawach informatyki. Treści te pokrywają w istotnym stopniu stan dziedziny z uwzględnieniem najnowszych osiągnięć i zastosowań praktycznych.
Macierz odniesienia. Odniesienie do kierunkowych obszarów kompetencji jest następujące:
Kategoria kompetencji: kierunkowe kody efektów (stopień nasycenia) | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (++) | prezentowane twierdzenia i algorytmy są poparte precyzyjnymi dowodami poprawności i analizą złożoności obliczeniowej; materiał obejmuje najważniejsze zagadnienia modelowania krzywych i powierzchni oraz nowoczesne algorytmy ich rozwiązania; |
umiejętności teoretyczne: K_U01 - K_U06 (++) | Wzorując się na standardowych rozwiązaniach prezentowanych na wykładzie studenci opracowują rozwiązania zbliżonych problemów i ich wersji praktycznych; prezentowane rozwiązania podlegają weryfikacji poprawności i skuteczności; |
wiedza specjalistyczna: K_W05-07 (+++) | przedmiot daje podstawy teoretyczne nowych metod matematycznych grafiki komputerowej; program podkreśla znaczenie krzywych oraz powierzchni Beziera i sklejanych, jak również ich wariantów i uogólnień; |
umiejętności specjalistyczne: K_U13-U17 (+++) | rozwiązania zagadnień praktycznych uzyskuje się stosując odpowiednio dobrane algorytmy rozwiązania modelowych problemów; elementem oceny jest konieczność samodzielnej implementacji wybranych rozwiązań; |
wiedza w zakresie zastosowań: K_W08-K_W09 (++) | w ramach samodzielnej pracy studenci implementują poznane techniki i metody |
umiejętności w zakresie zastosowań: K_U05, K_U12 (++) | materiał wykładu obejmuje problemy o zastosowaniach w innych dziedzinach: tomografia komputerowa, rozpoznawanie obrazów, robotyka |
Formy zajęć. Formy przekazywania wiedzy w ramach przedmiotu obejmują wykład, ćwiczenia oraz samodzielną pracę studentów z wykorzystaniem materiałów. Formy utrwalania wiedzy i nabywania umiejętności obejmują ćwiczenia problemowe oraz zastosowania zdobytej wiedzy wykonywane w formie klasycznych ćwiczeń.
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę prezentacji rozwiązań problemów w ramach ćwiczeń, rozwiązań zadań problemowych na sprawdzianach i w czasie egzaminu.
Parametry przedmiotu. Przedmiot odbywa się w wymiarze 30 godz. wykładu oraz 30 godz. ćwiczeń. W ramach ćwiczeń wymagana jest samodzielna implementacja wybranych problemów. Przedmiot kończy się egzaminem. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego materiału, rozwiązania zadań problemowych oraz implementacji algorytmów szacuje się jak 1:1 w wypadku materiału wykładowego, 2,5:1 w wypadku zadań ćwiczeniowych i programistycznych. Czas przygotowania do egzaminu szacuje się na 20 godzin. Za zaliczenie przedmiotu student otrzymuje 6 punktów ECTS.
Efekty dodatkowe.
Tematyka przedmiotu obejmuje teorię i algorytmy związane z problemami optymalizacyjnymi na dyskretnych strukturach. Wykorzystywane są tu techniki z kombinatoryki, programowania liniowego i teorii algorytmów .
Problem skojarzenia. Pojęcie skojarzenia występuje w różnych postaciach w bardzo wielu dziedzinach i ma zastosowanie w szeregu praktycznych i teoretycznych problemów takich jak:
Skojarzenia posiadają bardzo ciekawą i ładną strukturę, co doprowadziło do powstania bogatej teorii, która jest nieustannie rozwijana, ostatnio najprężniej w związku z zastosowaniami w ekonomii i teorii gier.
Matroidy. Przykładami
matroidów są drzewa rozpinające, zbiory liniowo niezależnych
kolumn macierzy, minimalny/maksymalny wagowo rozpinający podgraf, który
zawiera dokładnie jeden cykl. Pojęcie matroidu pozwala na konstrukcję
efektywnych algorytmów dla szerokiej klasy zagadnień.
T-joiny. Pojęcie T-joinów
jest wykorzystywane w rozwiązywaniu problemów grafowych, w tym analizy
cykli w grafie i wyznaczania optymalnych ścieżek.
Programowanie liniowe.
Przykłady innych problemów kombinatoryczno-optymalizacyjnych, w tym problem rozłącznych ścieżek.
Znajomość tematyki z zakresu algorytmów i struktur danych oraz matematyki dyskretnej.
Kategoria kompetencji: kierunkowe kody efektów (stopień nasycenia) | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (++) | konstrukcja i analiza algorytmów optymalizacji kombinatorycznej odwołuje się do klasycznych technik informatycznych i wykorzystuje aparat matematyczny zarówno w konstrukcji, jak i analizie pojęć; |
umiejętności teoretyczne: K_U01 - K_U06 (++) | analiza przeprowadzanych w ramach przedmiotu konstrukcji i rozumowań wymaga ścisłego stosowania aparatu matematycznego oraz wnikliwej analizy informatycznej |
wiedza specjalistyczna: K_W05-07 (+++) | w zakresie dziedziny optymalizacji kombinatorycznej studenci poznają klasyczne i najnowsze rozwiązania najważniejszych problemów: znajdowania skojarzenia o największym rozmiarze w grafach dwudzielnych i ogólnych, znajdowania skojarzenia najcięższego/najlżejszego w grafach z wagami na krawędziach, znajdowania optymalnego zbioru niezależnego w matroidzie, obliczania (optymalnej) interesekcji dwóch matroidów. |
umiejętności specjalistyczne: K_U13-U17 (+++) | w zakresie dziedziny optymalizacji kombinatorycznej studenci analizują i stosują klasyczne i najnowsze rozwiązania najważniejszych problemów z dziedziny; |
wiedza w zakresie zastosowań: K_W08-K_W09 (++) | omawiane w ramach przedmiotu zagadnienia znajdują zastosowanie w innych dziedzinach informatyki (kompresja, wyszukiwarki Internetowe) oraz dziedzinach bardzie odległych, jak genetyka |
umiejętności w zakresie zastosowań: K_U05, K_U12 (++) | odniesienie treści przedmiotu do innych dziedzin oraz analiza praktycznych rozwiązań problemów z tych dziedzin pozwalają nabyć umiejętności praktycznego stosowania informatyki w dziedzinach powiązanych z tematyka algorytmów tekstowych |
Formy zajęć. Formy przekazywania wiedzy w ramach przedmiotu obejmują klasyczną formę wykładową oraz samodzielną pracę studentów w oparciu o materiały. Formy utrwalania wiedzy i nabywania umiejętności obejmują ćwiczenia problemowe oraz zastosowania zdobytej wiedzy wykonywane w formie klasycznych ćwiczeń.
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę prezentacji rozwiązań problemów w ramach ćwiczeń, rozwiązań zadań problemowych na sprawdzianach i w czasie egzaminu.
Parametry przedmiotu. Przedmiot odbywa się w wymiarze 30 godz. wykładu oraz 30 godz. ćwiczeń i kończy się egzaminem. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego materiału oraz rozwiązania zadań problemowych szacuje się jak 1:1 w przypadku materiału wykładowego, 2:1 w przypadku zadań ćwiczeniowych, dodatkowo czas przygotowania i podejścia do egzaminu szacuje się jako 20 godzin. Oszacowanie całkowitego Za zaliczenie przedmiotu student otrzymuje 6 punktów ECTS.
Efekty dodatkowe.
Przedmiot obejmuje przegląd najważniejszych metod realistycznej syntezy obrazów. Opisywane metody można podzielić na dwa typy: metody Monte Carlo oparte na śledzeniu promieni i metody energetyczne „radiosity”. Wykład zawiera także opis metod mapowania obliczonego oświetlenia o wysokim zakresie dynamicznym do zakresu możliwego do wyświetlenia (algorytmy mapowania tonów). Wprowadzone są podstawy fizyczne transportu światła, które są konieczne do wyprowadzenie poprawnych algorytmów obliczających oświetlenie w fizycznych jednostkach.
Wśród poruszanych tematów znajdują się:
1. P.Shirley - Realistic Ray Tracing, A.K. Peters 2000
2. P.Dutre, P.Bekaert, K.Bala - Advanced Global Illumination, A.K. Peters 2003
3. P.Dutre - Global Illumination Compendium
4. H.W.Jensen - Realistic Image Synthesis Using Photon Mapping, A.K. Peters 2001
5. F.Sillion, C.Puech - Radiosity and Global Illumination, Morgan Kaufmann Publ. 1994
Znajomość tematyki z zakresu podstaw grafiki komputerowej, rachunku prawdopodobieństwa, analizy matematycznej oraz biegłość w programowaniu w języku C/C++.
Kompetencje. Przedmiot zawiera treści oparte na matematycznych podstawach informatyki i teorii informatyki. Treści te pokrywają w istotnym stopniu stan dziedziny z uwzględnieniem najnowszych osiągnięć i zastosowań praktycznych.
Macierz odniesienia. Odniesienie przedmiotu do kierunkowych obszarów kompetencji jest następujące:
Kategoria kompetencji: kierunkowe kody efektów (stopień nasycenia) | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (++) | prezentowane rozwiązania algorytmiczne są poparte precyzyjnymi wyprowadzeniami gwarantującymi poprawność obliczeń; materiał obejmuje najważniejsze zagadnienia syntezy obrazu oraz kluczowe struktury danych i techniki algorytmiczne przyspieszające obliczenia (np. śledzenie promieni) |
umiejętności teoretyczne: K_U01 - K_U06 (++) | w oparciu o klasyczne rozwiązania prezentowane na wykładzie studenci opracowują rozwiązania problemów pokrewnych i praktycznych; prezentowane rozwiązania muszą bazować na analizie złożoności i poprawności; |
wiedza specjalistyczna: K_W05-07 (+++) | przedmiot daje podstawy teoretyczne nowych metod syntezy obrazów w grafice komputerowej; omawiane są także przykładowe nowe algorytmy na podstawie prac z bieżących konferencji naukowych; omawiane są powiązania dziedziny m.in. ze statystyką (metody Monte Carlo) i metodami numerycznymi rozwiązywania układów równań liniowych (metoda radiosity) |
umiejętności specjalistyczne: K_U13-U17 (+++) | w ramach przedmiotu dobiera się rozwiązania problemów do zagadnień praktycznych, uwzględniając specyfikę zastosowań; elementem oceny jest konieczność samodzielnej implementacji wybranych rozwiązań; |
wiedza w zakresie zastosowań: K_W08-K_W09 (++) | studenci poznają dostępne biblioteki graficzne, mają świadomość znaczenia metod grafiki i wizualizacji w rozmaitych dziedzinach; |
umiejętności w zakresie zastosowań: K_U05, K_U12 (++) | studenci poznają sposoby stosowania metod zaawansowanej grafiki komputerowej w innych dziedzinach ; |
kompetencje praktyczne i zawodowe: K_U10-K_U11, K_W10-K_W12, K_K02-K_K04, K_K06-K_K07 (++) | studenci implementują poznane algorytmy i zapoznają się z dostępnymi bibliotekami graficznymi |
Formy zajęć. Formy przekazywania wiedzy w ramach przedmiotu obejmują klasyczną formę wykładową oraz pracownie programistyczną, której celem jest kierowanie samodzielną pracą studentów nad projektem będącym implementacją kolejnych etapów programu syntezy obrazów.
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę sprawdzania przedstawianych na pracowni programów, co pozwala na ocenę bieżącego rozumienia treści teoretycznych i wyjaśnianie na bieżąco wątpliwości/braków wiedzy. Dokładniejsza weryfikacja znajomości części teoretycznej odbywa się w czasie egzaminu.
Parametry przedmiotu. Przedmiot odbywa się w wymiarze 30 godz. wykładu, oraz 30 godz. przeznaczonych na pracownię, której bazę stanowi samodzielna implementacja projektu. Przedmiot kończy się egzaminem. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego materiału szacuje się jak 1:1 w przypadku materiału wykładowego, oraz 2:1 dla pracowni programistycznej. Dodatkowo czas przygotowania i podejścia do egzaminu szacuje się jako 20 godzin. Za zaliczenie przedmiotu student otrzymuje 6 punktów ECTS.
Dodatkowe uwagi.
Statyczna analiza programów komputerowych jest jednym z najważniejszych narzędzi, które są używane do znajdowania błędów, optymalizacji i znajdowania możliwości "włamów". Zanalizowanie niewielkiego programu jest stosunkowo łatwe, większe programy sprawiają już poważny problem, natomiast analiza wielkich programów wydawała się do niedawna poza zasięgiem dostępnych metod.
Wykład poświęcony jest przeglądowi algorytmów analizy programów, zaczynając od klasycznych metod takich jak analiza przepływu danych czy abstrakcyjna interpretacja.
Flemming Nielson, Hanne Riis Nielson, Chris Hankin: Principles of program analysis, Springer 2005
Wykład może wymagać sporej sprawności matematycznej, w szczególności od słuchaczy będzie się wymagać swobodnego posługiwania się pojęciami takimi jak semantyka języka czy twierdzenie o punkcie stałym.
Kompetencje. Przedmiot zawiera specjalistyczne treści oparte na matematycznych podstawach informatyki i teorii informatyki. Treści te pokrywają w istotnym stopniu stan dziedziny z uwzględnieniem najnowszych osiągnięć i zastosowań praktycznych.
Macierz odniesienia. Odniesienie do kierunkowych obszarów kompetencji jest następujące:
Kategoria kompetencji: kierunkowe kody efektów (stopień nasycenia) | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (++) | większość przedstawionych analiz istotnie korzysta z aparatu matematycznego (np teorii krat i punktów stałych) oraz informatycznego (np semantyka języków programowania) |
umiejętności teoretyczne: K_U01 - K_U06 (++) | podczas zajęć studenci będą konstruować skomplikowane analizy programów; większość tych analiz aproksymuje problemy nierozstrzygalne |
wiedza specjalistyczna: K_W05-07 (+++) | przedmiot daje podstawy teoretyczne do zrozumienia najnowszych osiągnięć analizy statycznej; omawiane są powiązania przedmiotu z konstrukcją kompilatorów i bezpieczeństwem systemów komputerowych |
umiejętności specjalistyczne: K_U13-U17 (+++) | podczas zajęć studenci nabywają umiejętność tworzenia nowych analiz i uzasadniania ich poprawności |
wiedza w zakresie zastosowań: K_W08-K_W09 (++) | w ramach przedmiotu studenci implementują poznane analizy i zapoznają się z istniejącymi narzędziami do tworzenia takich analiz |
umiejętności w zakresie zastosowań: K_U05, K_U12 (++) | poznane na zajęciach metody dają się wykorzystać w innych dziedzinach, takich jak konstrukcja kompilatorów czy analiza bezpieczeństwa systemów komputerowych |
Formy zajęć. Formy przekazywania wiedzy w ramach przedmiotu obejmują klasyczną formę wykładową oraz samodzielną pracę studentów w oparciu o materiały. Formy utrwalania wiedzy i nabywania umiejętności obejmują ćwiczenia problemowe oraz zastosowania zdobytej wiedzy wykonywane w formie klasycznych ćwiczeń.
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę prezentacji rozwiązań problemów w ramach ćwiczeń, rozwiązań zadań problemowych na sprawdzianach i w czasie egzaminu.
Parametry przedmiotu. Przedmiot odbywa się w wymiarze 30 godz. wykładu oraz oraz 24 godz. ćwiczeń oraz 6 godz. przeznaczonych na pracownię, której bazę stanowią samodzielne implementacje wybranych problemów. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego materiału oraz rozwiązania zadań problemowych szacuje się jak 1:1 w przypadku materiału wykładowego, 2:1 w przypadku zadań ćwiczeniowych, dodatkowo czas przygotowania i podejścia do egzaminu szacuje się jako 20 godzin. Oszacowanie całkowitego Za zaliczenie przedmiotu student otrzymuje 6 punktów ECTS.
Efekty dodatkowe.
Tematem przedmiotu jest wprowadzenie do rachunku lambda jako modelu obliczeń oraz prototypowego języka programowania. Jego celem jest pokazanie, w jaki sposób kształtowały się pojęcia, które dzisiaj są wykorzystywane w różnych językach programowania, a także ich
precyzyjne określenie i zdefiniowanie. Wykład zostanie uzupełniony o uwagi historyczne i teoretyczne.
Logika dla informatyków, Programowanie L.
Kompetencje. Przedmiot zawiera specjalistyczne treści oparte na matematycznych podstawach.
Macierz odniesienia.
Odniesienie do kierunkowych obszarów kompetencji jest następujące:
Kategoria kompetencji: kierunkowe kody efektów (stopień nasycenia) | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (++) | przedmiot przedstawia klasyczne wyniki dotyczące rachunku lambda używając aparatu matematycznego |
umiejętności teoretyczne: K_U01 - K_U06 (++) | analiza przeprowadzanych w ramach przedmiotu konstrukcji i rozumowań wymaga ścisłego stosowania aparatu matematycznego |
wiedza specjalistyczna: K_W05-07 (+++) | przedmiot daje podstawy teoretyczne do zrozumienia konstrukcji współczesnych języków programowania |
umiejętności specjalistyczne: K_U13-U17 (+++) | przedmiot dostarcza teoretycznych narzędzi pozwalających na projektowanie nowych języków programowania wyposażonych w określone konstrukcje |
Formy zajęć. Formy przekazywania wiedzy w ramach przedmiotu obejmują klasyczną formę wykładową oraz samodzielną pracę studentów w oparciu o materiały. Formy utrwalania wiedzy i nabywania umiejętności obejmują ćwiczenia problemowe oraz zastosowania zdobytej wiedzy wykonywane w formie klasycznych ćwiczeń.
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę prezentacji rozwiązań problemów w ramach ćwiczeń, rozwiązań zadań problemowych na sprawdzianach i w czasie egzaminu.
Parametry przedmiotu. Przedmiot odbywa się w wymiarze 30 godz. wykładu oraz 30 godz. ćwiczeń. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego materiału oraz rozwiązania zadań problemowych szacuje się jak 1:1 w przypadku materiału wykładowego, 2:1 w przypadku zadań ćwiczeniowych, dodatkowo czas przygotowania i podejścia do egzaminu szacuje się jako 20 godzin. Za zaliczenie przedmiotu student otrzymuje 6 punktów ECTS.
Wykład jest poświęcony formalnym podstawom różnych zagadnień dotyczących języków programowania. Programy i języki programowania będą rozpatrywane jako obiekty matematyczne, których własności mogą być ściśle formułowane i dowodzone. W ramach wykładów będą omawiane sposoby formalnego definiowania mechanizmów językowych, systemy typów, polimorfizm, podtypowanie, teoretyczne podstawy języków obiektowych.
Logika dla informatyków, Programowanie L, Programowanie funkcyjne.
Kompetencje. Przedmiot zawiera specjalistyczne treści oparte na matematycznych podstawach informatyki. Odniesienie do kierunkowych obszarów kompetencji jest następujące:
Kategoria kompetencji: kierunkowy kod efektu (stopień nasycenia) | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (++) | omawiane są zaawansowane zagadnienia z dziedziny teorii języków programowania z użyciem formalnych narzędzi do opisu języków i wnioskowania o ich własnościach (m. in. systemy dedukcji naturalnej) |
umiejętności teoretyczne: K_U01, K_U06 (++) | analiza przeprowadzanych w ramach przedmiotu konstrukcji i rozumowań wymaga ścisłego stosowania aparatu matematycznego i informatycznego |
wiedza specjalistyczna: K_W05 - K_W07 (+++) | przedmiot daje podstawy teoretyczne do analizy różnych konstrukcji występujących we współczesnych językach programowania w paradygmatach obiektowym i funkcyjnym |
umiejętności specjalistyczne: K_U13 - K_U17 (+++) | przedmiot dostarcza teoretycznych narzędzi pozwalających na analizę języków programowania w odniesieniu do omawianych własności i konstrukcji językowych |
wiedza z zakresu zastosowań: K_W08, K_W09 (++) | student poznaje konstrukcje i własności języków programowania używanych w praktyce programistycznej |
umiejętności z zakresu zastosowań: K_U05, K_U12 (++) | student potrafi analizować programy i błędy w ich konstrukcji w odniesieniu do poznanych własności języków (m. in. systemu typów) |
Formy zajęć. Formy przekazywania wiedzy w ramach przedmiotu obejmują klasyczną formę wykładową oraz samodzielną pracę studentów w oparciu o materiały. Formy utrwalania wiedzy i nabywania umiejętności obejmują ćwiczenia problemowe oraz zastosowania zdobytej wiedzy wykonywane w formie klasycznych ćwiczeń.
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę prezentacji rozwiązań problemów w ramach ćwiczeń, rozwiązań zadań problemowych na sprawdzianach i w czasie egzaminu.
Parametry przedmiotu. Przedmiot odbywa się w wymiarze 30 godz. wykładu oraz 30 godz. ćwiczeń. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego materiału oraz rozwiązania zadań problemowych szacuje się jak 1:1 w przypadku materiału wykładowego, 2:1 w przypadku zadań ćwiczeniowych, dodatkowo czas przygotowania i podejścia do egzaminu szacuje się jako 20 godzin. Za zaliczenie przedmiotu student otrzymuje 6 punktów ECTS.
Zaawansowane przedmioty I.2 (zastosowania)
Tematyka przedmiotu.
Popularne zjawiska fizyki otaczającej nas przyrody, jak ruch w polu grawitacyjnym, ruch drgający, model drapieżnika i ofiary są opisywane równaniami różniczkowymi. Przedmiot wprowadza słuchaczy do klasycznej teorii równań różniczkowych zwyczajnych oraz zapoznaje ich z metodami numerycznymi rozwiązywania takich równań – zagadnienia początkowe, brzegowe… Słuchacze poznają również piękny sposób modelowania przyrody za pomocą geometrii fraktalnej – płatek śniegu, paprotka Barnsley’a, żuczek Mandelbrota. Potrzebnymi i szeroko stosowanymi są grafika komputerowa, animacja obrazu, a także projekcje dostępnych filmów video. Bardzo wygodnym systemem do programowania jest łatwy i bogaty w grafikę MATLAB.
Wśród poruszanych tematów znajdują się:
· Klasyfikacja równań różniczkowych, równanie rodziny krzywych, ortogonalność krzywych,
· Podstawowe metody rozwiązywania równań różniczkowych pierwszego rzędu,
· Równania różniczkowe wyższych rzędów, twierdzenia o istnieniu i regularności rozwiązań,
· Pole kierunków, przestrzeń fazowa,
· Metody Rungego-Kutty, metody jawne, niejawne, błąd lokalny, błąd globalny,
· Sterowanie wielkością kroku, metody włożone,
· Przykłady zagadnień początkowych – wybór zagadnień do rozwiązywania na laboratorium
· Równania sztywne, obszary stabilności absolutnej metod,
· Zagadnienia brzegowe, schematy różnicowe, rząd aproksymacji schematu różnicowego, metoda przegnania, stabilność metody przegnania, metoda strzału,
· Twierdzenia o istnieniu i jednoznaczności rozwiązań zagadnień brzegowych, przykłady,
· Elementarne wprowadzenie do fraktali – generowanie fraktali, wymiarowość obiektu
Zalecana literatura:
Wymagane przygotowanie do przedmiotu to znajomość tematyki z zakresu algorytmów i struktury danych.
Kompetencje. Przedmiot zawiera treści oparte na matematycznych podstawach teorii równań różniczkowych zwyczajnych oraz na metodach numerycznych. Treści te pokrywają w istotnym stopniu stan dziedziny z uwzględnieniem najnowszych osiągnięć i zastosowań praktycznych. Odniesienie do kierunkowych obszarów kompetencji typowego przedmiotu z tej grupy jest następujące:
Kategoria kompetencji: kierunkowe kody efektów (stopień nasycenia) | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (++) | przedmiot wymaga znajomości wielu pojęć z analizy matematycznej i algebry, oraz umiejętności programowania komputera z szerokim użyciem grafiki. Jego materiał obejmuje podstawowe zagadnienia teorii równań różniczkowych zwyczajnych, a prezentowane rozwiązania teoretyczne będą poparte precyzyjnymi rozważaniami na temat regularności i jednoznaczności przebiegu rozwiązań rozpatrywanych zagadnień.. |
umiejętności teoretyczne: K_U01 - K_U06 (++) | w oparciu o klasyczne rozwiązania, prezentowane na wykładzie, studenci opracowują rozwiązania teoretyczne i numeryczne szeregu problemów wziętych z praktyki. |
wiedza specjalistyczna: K_W05-07 (+++) | przedmiot daje podstawy teoretyczne dla klasycznych i nowoczesnych trendów w rozwiązywaniu równań różniczkowych zwyczajnych, w tym podstawy dla narzędzi analizy przestrzeni wielowymiarowych; program kładzie nacisk na ilustrowanie rozwiązań grafiką komputerową, ułatwiającą zrozumienie przebiegów modelowanych zagadnień. |
umiejętności specjalistyczne: K_U13-U17 (+++) | w ramach przedmiotu dobiera się rozwiązania abstrakcyjnych problemów do zagadnień praktycznych, uwzględniając specyfikę zastosowań (skalowalność, rola poszczególnych parametrów, modelowanie); elementem oceny jest konieczność samodzielnej implementacji wybranych rozwiązań; |
wiedza w zakresie zastosowań: K_W08-K_W09 (++) | studenci poznają metody informatyczne i matematyczne znajdujące zastosowania w różnych dziedzinach; poznają techniki numeryczne i istniejące biblioteki algorytmów numerycznych. |
umiejętności w zakresie zastosowań: K_U05, K_U12 (++) | materiał wykładu dotyka szeregu problemów o zastosowaniach w innych dziedzinach informatyki – np. metoda bisekcji rozwiązywania równań algebraicznych przy rozwiązywaniu zagadnień brzegowych metodą strzałów. |
kompetencje praktyczne i zawodowe: K_U10-K_U11, K_W10-K_W12, K_K02-K_K04, K_K06-K_K07 (++) | w ramach samodzielnej pracy studenci implementują, modyfikują lub uzupełniają poznane algorytmy czy metody, korzystając z dostępnych w literaturze lub Internecie bibliotek metod i algorytmów numerycznych; doskonalą w ten sposób umiejętności praktyczne, znajomość narzędzi informatycznych oraz zasad wykorzystywania materiałów i narzędzi o różnych prawach licencyjnych; |
Formy zajęć. Formy przekazywania wiedzy w ramach przedmiotu obejmują klasyczną formę wykładową oraz samodzielną pracę studentów w oparciu o materiały. Formy utrwalania wiedzy i nabywania umiejętności obejmują ćwiczenia problemowe oraz zastosowania zdobytej wiedzy na laboratorium wykonywane w formie numerycznego rozwiązywania sformułowanych zagadnień..
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę prezentacji rozwiązań problemów w ramach ćwiczeń, rozwiązań zadań problemowych na sprawdzianach, na laboratorium i w czasie egzaminu.
Parametry przedmiotu. Przedmiot odbywa się w wymiarze 30 godz. wykładu, oraz 15 godz. ćwiczeń oraz 15 godz. przeznaczonych na laboratorium, którego bazę stanowią samodzielne implementacje wybranych problemów. Przedmiot kończy się egzaminem. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego materiału, rozwiązywania zadań problemowych oraz implementacji algorytmów szacuje się jak 1:1 w przypadku materiału wykładowego, 2:1 w przypadku zadań ćwiczeniowych i 2,5:1 w przypadku zadań programistycznych. Dodatkowo, czas przygotowania i podejścia do egzaminu szacuje się jako 20 godzin. Za zaliczenie przedmiotu student otrzymuje 6 punktów ECTS.
Dodatkowe uwagi.
Tematyka przedmiotu.
Wykład ma na celu zaznajomienie studentów ze strukturą kompilatorów, przedstawienie metod formalnych stosowanych przy ich konstrukcji oraz zapoznanie ze sprawdzonymi w praktyce rozwiązaniami wykorzystywanymi przy projektowaniu translatorów. W trakcie zajęć praktycznych studenci powinni posiąść praktyczne umiejętności realizacji podstawowych modułów translatorów.
Zalecana literatura
Kompetencje. Przedmiot zawiera treści oparte na matematycznych podstawach informatyki i teorii informatyki. Treści te są skoncentrowane na obszarze zastosowań określonym w tytule przedmiotu z uwzględnieniem zaawansowanych pojęć informatycznych i ich wykorzystaniu w danej dziedzinie. Odniesienie do kierunkowych obszarów kompetencji typowego przedmiotu z tej grupy jest następujące:
Kategoria kompetencji: kierunkowe kody efektów (stopień nasycenia) | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (++) | przedmiot wymaga znajomości pojęć z teorii informatyki oraz matematycznych podstaw informatyki do przedstawienia omawianych zastosowań; w szczególności z teorii języków formalnych |
umiejętności teoretyczne: K_U01 - K_U06 (++) | konstrukcja efektywnego kompilatora wymaga stosowania aparatu matematycznego oraz wnikliwej analizy informatycznej |
wiedza specjalistyczna: K_W05-07 (+++) | przedmiot daje zarówno podstawy teoretyczne jak i praktyczne techniki tworzenia kompilatorów i dzięki temu umożliwia zrozumienie najnowszych trendów w tej dziedzinie |
umiejętności specjalistyczne: K_U13-U17 (+++) | stworzenie własnego kompilatora wymaga dokładnego przeanalizowania problemu i zastosowania zaawansowanych modeli informatycznych; |
wiedza w zakresie zastosowań: K_W08-K_W09 (++) | w ramach przedmiotu studenci implementują własne kompilatory wybranych języków korzystając z najnowszych technologii i narzędzi, m.in. generatorów parserów ; |
umiejętności w zakresie zastosowań: K_U05, K_U12 (++) | materiał wykładu ma silne związki z innymi dziedzinami informatyki, np w językach formalnych, teorii automatów czy statycznej analizie programów |
kompetencje praktyczne i zawodowe: K_U10-K_U11, K_W10-K_W12, K_K02-K_K04, K_K06-K_K07 (++) | stworzenie własnego kompilatora pozwala nabyć i udoskonalić umiejętności praktycznego implementowania rozwiązań infromatycznych z wykorzystaniem narzędzi informatycznych; stopień skomplikowania i zaawansowania tworzonych rozwiązań informatycznych uświadamia znaczenie zasad pracy i jej organizacji oraz rozwijania przedsięwzięć informatycznych; stosowanie różnorodnych narzędzi informatycznych dostarcza wiedzy na temat praw własności i zasad etyki zawodowej informatyka; |
Formy zajęć. Formy przekazywania wiedzy w ramach przedmiotu obejmują klasyczną formę wykładową oraz samodzielną pracę studentów w oparciu o materiały. Formy utrwalania wiedzy i nabywania umiejętności obejmują ćwiczenia praktyczne oraz zajęcia ćwiczeniowo-laboratoryjne.
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę prezentacji rozwiązań zadań problemowych oraz praktycznych rozwiązań w ramach zajęć ćwiczeniowo-laboratoryjnych, oraz rozwiązań zadań problemowych na sprawdzianach i w czasie egzaminu.
Parametry przedmiotu. Przedmiot odbywa się w wymiarze 30 godz. wykładu oraz 30 godz. zajęć pomocnicznych w formie ćwiczeń i pracowni. Przedmiot kończy się egzaminem. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego materiału oraz rozwiązania zadań problemowych szacuje się jak 1:1 w przypadku materiału wykładowego, 2:1 w przypadku zadań ćwiczeniowych i laboratoryjnych, dodatkowo czas przygotowania i podejścia do egzaminu szacuje się jako 20 godzin. Za zaliczenie przedmiotu student otrzymuje 6 punktów ECTS.
Efekty dodatkowe.
Przedmiot ma na celu wprowadzenie do systemów typów znajdujących zastosowanie w projektowaniu i implementacji języków programowania funkcyjnego oraz obiektowego. Wykład oparty jest na klasycznym podręczniku Pierce'a "Types and Programming Languages", a zajęcia w ramach pracowni towarzyszącej wykładowi poświęcone są analizie i implementacji wybranych systemów typów.
Logika dla informatyków, Programowanie (M).
Kompetencje. Przedmiot zawiera treści oparte na matematycznych podstawach informatyki i teorii informatyki. Treści te są skoncentrowane na obszarze zastosowań określonym w tytule przedmiotu z uwzględnieniem zaawansowanych pojęć informatycznych i ich wykorzystaniu w danej dziedzinie. Odniesienie do kierunkowych obszarów kompetencji typowego przedmiotu z tej grupy jest następujące:
Kategoria kompetencji: kierunkowy kod efektu (stopień nasycenia | Uzasadnienie |
wiedza teoretyczna: K_W01 - K_W04 (++) | przedmiot wymaga znajomości pojęć z teorii informatyki oraz matematycznych podstaw informatyki do przedstawienia omawianych zastosowań; omawiane zagadnienia bazują na podstawach teorii języków programowania oraz jej związkach z logiką; |
umiejętności teoretyczne: K_U01, K_U06 (++) | analiza przedstawianych w ramach przedmiotu systemów typów wymaga stosowania aparatu matematycznego oraz wnikliwej analizy formalnej zagadnień informatycznych; |
wiedza specjalistyczna: K_W05 - K_W07 (+++) | przedmiot dotyczy specjalistycznej dziedziny, rozwijanej i stosowanej w konstrukcji systemów informatycznych i języków programowania; w ramach przedmiotu studenci poznają podstawowe i pojęcia i zagadnienia z dziedziny (pojęcia typu, podtypu, polimorfizmu); |
umiejętności specjalistyczne: K_U13 - K_U17 (+++) | studenci uczą się analizować i konstruować zaawansowane systemy typów; |
wiedza z zakresu zastosowań: K_W08, K_W09 (++) | systemów typów efektywnie wspierają zastosowania informatyki w różnych dziedzinach; studenci poznają różne systemy typów oraz ich aspekty istotne z punktu widzenia różnych dziedzin zastosowań; |
umiejętności z zakresu zastosowań: K_U05, K_U12 (++) | studenci implementują systemy typów uwzględniając aspekty praktyczne i różnych dziedzin zastosowań; |
kompetencje praktyczne i zawodowe: K_U10-K_U11, K_W10-K_W12, K_K02-K_K04, K_K06-K_K07 (++) | w ramach przedmiotu studenci projektują i tworzą zaawansowane systemy typów; tworzenie praktycznych rowiązań pozwala nabyć i udoskonalić umiejętności praktycznego implementowania rozwiązań informatycznych z wykorzystaniem narzędzi informatycznych; stopnień skomplikowania i zaawansowania tworzonych rozwiązań uświadamia znaczenie zasad pracy informatyka, pozwala doskonalić umiejętności organizacji pracy, współpracy, planowania i rozwijania przedsięwzięć informatycznych; stosowanie różnorodnych narzędzi informatycznych dostarcza wiedzy na temat praw własności i zasad etyki zawodowej informatyka. |
Formy zajęć. Formy przekazywania wiedzy w ramach przedmiotu obejmują klasyczną formę wykładową oraz samodzielną pracę studentów w oparciu o materiały. Formy utrwalania wiedzy i nabywania umiejętności obejmują ćwiczenia praktyczne oraz zajęcia ćwiczeniowo-laboratoryjne.
Weryfikacja efektów. Sprawdzenie osiąganych efektów ma formę prezentacji rozwiązań zadań problemowych, praktycznych rozwiązań w ramach zajęć ćwiczeniowo-laboratoryjnych, oraz rozwiązań zadań problemowych na sprawdzianach i w czasie egzaminu.
Parametry przedmiotu. Przedmiot odbywa się w wymiarze 30 godz. wykładu oraz 30 godz. zajęć pomocnicznych w formie ćwiczeń i pracowni. Przedmiot kończy się egzaminem. Wymiar pracy samodzielnej wymaganej do opanowania zaawansowanego materiału oraz rozwiązania zadań problemowych szacuje się jak 1:1 w przypadku materiału wykładowego, 2:1 w przypadku zadań ćwiczeniowych i laboratoryjnych, dodatkowo czas przygotowania i podejścia do egzaminu szacuje się jako 20 godzin. Za zaliczenie przedmiotu student otrzymuje 6 punktów ECTS.
Efekty dodatkowe.
[a]