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

Spis treści

Karty przedmiotów typu O (obowiązkowych)

O3. Języki formalne i złożoność obliczeniowa

Wymagane przygotowanie studentów.

Program przedmiotu.

Literatura podstawowa

Literatura dodatkowa

O2.M Algorytmy i struktury danych (M)

Wymagane przygotowanie studentów.

Program przedmiotu:

Literatura podstawowa

Literatura uzupełniająca

O2.M Analiza numeryczna (opracował: prof. S. Lewanowicz)

Wymagane przygotowanie studentów.

Program przedmiotu:

Tematyka przedmiotu

O2.M Matematyka dyskretna (M)

Wymagane przygotowanie studentów

Program przedmiotu

Literatura

O2.M Programowanie (M)

Opis przedmiotu.

Wybrane zagadnienia:

Wymagania wstępne:

Literatura:

Karty przedmiotów I.2

Zaawansowane przedmioty teoretyczne I.2

Algorytmy grafowe

Tematyka przedmiotu

Zalecana literatura

Wymagane przygotowanie do przedmiotu

Algorytmy on-line

Program:

Literatura:

Algorytmy tekstowe

Tematyka przedmiotu.

Zalecana literatura:

Geometria obliczeniowa

Tematyka przedmiotu.

Zalecana literatura:

Wymagane przygotowanie do przedmiotu

Algorytmy rozproszone

Tematyka przedmiotu.

Zalecana literatura

Wymagane przygotowanie do przedmiotu

Kombinatoryka

Zalecana literatura

Wymagane przygotowanie do przedmiotu

Kryptografia

Cel zajęć:

Program:

Wymagania:

Literatura

Matematyczne metody grafiki komputerowej  (popracował prof. S. Lewanowicz)

Tematyka przedmiotu

Program wykładu:

Zalecana literatura

Wymagane przygotowanie do przedmiotu:

Optymalizacja kombinatoryczna

Tematyka przedmiotu.

Program wykładu

Zalecana literatura:

Wymagane przygotowanie do przedmiotu

Realistyczna grafika komputerowa (opracował dr A. Łukaszewski)

Tematyka przedmiotu.

Zalecana literatura:

Wymagane przygotowanie do przedmiotu

Analiza programów komputerowych

Tematyka przedmiotu.

Zalecana literatura:

Wymagane przygotowanie do przedmiotu:

Rachunek lambda

Program:

Literatura:

Wymagania wstępne:

Teoretyczne podstawy języków programowania

Tematyka przedmiotu.

Literatura.

Wymagania wstępne:

Modelowanie zjawisk przyrodniczych (opracował dr. A. Szustalewicz)

Metody translacji

Program

Systemy typów

Wybrane zagadnienia:

Literatura:

Wymagania wstępne:

Karty przedmiotów typu O (obowiązkowych)

O3. Języki formalne i złożoność obliczeniowa

Wymagane przygotowanie studentów.

Wiedza z zakresu przedmiotów Programowanie oraz Matematyka dyskretna.

Program przedmiotu.

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.

Literatura podstawowa

[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.

Literatura dodatkowa

[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.

O2.M Algorytmy i struktury danych (M)

Wymagane przygotowanie studentów.

Wiedza z zakresu wykładów Programowanie oraz Matematyka dyskretna.

Program przedmiotu:

  1. Przegląd metod projektowania efektywnych algorytmów: „dziel i zwyciężaj”, programowanie dynamiczne, metoda zachłanna. (4 godz.)
  2. Złożoność obliczeniowa algorytmu (pesymistyczna, oczekiwana, zamortyzowana). Przykłady analizy kosztu. (2 godz.)
  3. Dolne granice: modele i metody. Drzewa decyzyjne, liniowe drzewa decyzyjne, gry z adwersarzem, redukcje. (2 godz.)
  4. Sortowanie: Heapsort, Mergesort i Quicksort. Sortowanie w czasie liniowym: Countsort, Radixsort, Bucketsort. (6 godz.)
  5. Selekcja: algorytm Hoare’a i „magicznych piątek”. (2 godz.)
  6. Kolejki priorytetowe: kopce binarne, dwumianowe i Fibonacciego. Zastosowania w problemie najkrótszych ścieżek i minimalnego drzewa rozpinającego. (4 godz.)
  7. Scalanie. Drzewa turniejowe. Sortowanie zewnętrzne. (2 godz.)
  8. Słowniki. Drzewa BST, zrównoważone drzewa BST (AVL, 2-3-4-drzewa, drzewa czerwono-czarne). Optymalne drzewa wyszukiwań binarnych.Drzewa samoorganizujące się. Haszowanie. Słowniki statyczne. (8 godz.)
  9. Wyszukiwanie zewnętrzne — B-drzewa. (2 godz.)
  10. Problem sumowania zbiorów rozłącznych i jego zastosowania. (4 godz.)
  11. Algorytmy grafowe: DFS i jego zastosowania, przepływy w sieciach, skojarzenia. (4 godz.)
  12. Algorytmy tekstowe: Wyszukiwanie wzorca (algorytm Karpa-Rabina, Algorytm Knutha-Morrisa-Pratta). Drzewa sufiksowe (4 godz.)
  13. Geometria obliczeniowa. Lokalizacja punktu. Otoczka wypukła. Technika zamiatania. (4 godz.)
  14. Algorytmy algebraiczne i teorioliczbowe. FFT. Szybkie mnożenie liczb i wielomianów. (4 godz.)
  15. NP-zupełność. Algorytmy aproksymacyjne dla problemów obliczeniowo trudnych. Heurystyki dla problemów trudnych (algorytmy genetyczne, simulated annealing). (4 godz.)
  16. Modele obliczeń równoległych: PRAM, tablica procesorów, hiperkostka. Algorytmy równoległe. Klasa NC i problemy P-zupełne. (2 godz.)
  17. Specjalne modele obliczeń: sieci komparatorów, obwody logiczne. (2 godz.)
  18. Algorytmy randomizacyjne.Przykłady zastosowań randomizacji w geometrii obliczeniowej, algorytmach grafowych, algorytmach równoległych, konstrukcji struktur danych. (2 godz.)

Literatura podstawowa

[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.

Literatura uzupełniająca

[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.

O2.M Analiza numeryczna (opracował: prof. S. Lewanowicz)

Wymagane przygotowanie studentów.

Wiedza z zakresu wykładów analiza matematyczna oraz algebra.

Program przedmiotu:

Tematyka przedmiotu

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

  1. M. Dryja, J. i M. Jankowscy, Przegląd metod i algorytmów numerycznych, cz. 1 i 2, WNT, 1988.
  2. D. Kincaid, W. Cheney, Analiza numeryczna, WNT, 2005.
  3. J. Stoer, R. Bulirsch, Wstęp do analizy numerycznej, PWN, 1987.
  4. G. Dahlquist, A. Björck, Numerical Methods in Scientific Computing, Vol. I, SIAM, 2008.
  5. W. Gautschi, Numerical Analysis. An Introduction, Birkhäuser, 1997.
  6. G. Hämmerlin, K.-H. Hoffmann, Numerical Mathematics, Springer-Verlag, 1991.
  7. A. Quarteroni, R. Sacco, F. Saleri, Numerical Mathematics, Springer-Verlag, 2000.
  8. P. Deuflhard, A. Hohmann, Numerical Analysis in Modern Scientific Computing, Springer-Verlag, 2003.

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.

O2.M Matematyka dyskretna (M)

Wymagane przygotowanie studentów

Algebra, Analiza matematyczna, Wstęp do informatyki lub kurs ANSI C

Program przedmiotu

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.)

Literatura

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.

O2.M Programowanie (M)

Opis przedmiotu.

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.

Wybrane zagadnienia:        

  1. Definicje indukcyjne.
  2. Metody opisu semantyki języków programowania w paradygmacie imperatywnym.         Strukturalna semantyka operacyjna. Semantyka denotacyjna.         
  3. Logika Hoare'a i dedukcyjne dowodzenie poprawności programów.
  4. Podstawy rachunku lambda.         
  5. Rachunek lambda jako prototypowy język funkcyjny. Strategie redukcji.
  6. Rachunek lambda z typami prostymi. Polimorficzny rachunek lambda.

Wymagania wstępne:

Logika dla informatyków, Wstęp do informatyki.

Literatura:

“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.

Karty przedmiotów I.2

Zaawansowane przedmioty teoretyczne I.2

Algorytmy grafowe

Tematyka przedmiotu

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ę:

Zalecana literatura

  1. M.Golumbic, “Algorithmic Graph Theory and Perfect Graphs”
  2. S.Even, “Graph Algorithms”
  3. P.Sankowski, “Algebraic Graph Algorithms”
  4. M.Mucha, “Finding Maximum Matchings via Gaussian Elimination”
  5. J.P.Spinrad, “Efficient Graph Representations”

Wymagane przygotowanie do przedmiotu

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.

Algorytmy on-line

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ń.

Program:

Literatura:

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.

Algorytmy tekstowe

Tematyka przedmiotu.

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ę:

Zalecana literatura:

  1. M.Crochemore, W.Rytter, "Jewels of Stringology"
  2. ed. A.Apostolico, Z.Galil "Pattern Matching Algorithms"
  3. M.Crochemore, Ch.Handcart, T.Lecroq "Algorithms on Strings

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.

Geometria obliczeniowa

Tematyka przedmiotu.

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ę:

Zalecana literatura:

  1. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry, Algorithms and Applications, Third Edition, Springer, 2008.
  2. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Geometria obliczeniowa. Algorytmy i zastosowania, Wydawnictwo WNT, 2007.
  3. F.P. Preparata, M.I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, 1985.
  4. Josef O'Rourke, Computational Geometry in C, Cambridge University Press, 1994.
  5. H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987.

Wymagane przygotowanie do przedmiotu

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.

Algorytmy rozproszone

Tematyka przedmiotu.

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:

Zalecana literatura

  1. N. A. Lynch, Distributed Algorithms, Morgan-Kaufmann Publishers, 1996.
  2. G. Tel, Introduction to Distributed Algorithms, Cambridge University Press, 1994.
  3. H. Attiya, J. Welch, Distributed Computing, McGraw-Hill, 1998.

Wymagane przygotowanie do 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.

Kombinatoryka

Tematyka przedmiotu.

Przedmiot obejmuje klasyczne zagadnienia kombinatoryki niezawarte w programie Matematyki dyskretnej. Wśród poruszanych tematów znajdują się:

Zalecana literatura

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.

Wymagane przygotowanie do przedmiotu

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.

Kryptografia

Cel zajęć:

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.

Program:

Wymagania:

Matematyka dyskretna

Literatura

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.

Matematyczne metody grafiki komputerowej  (popracował prof. S. Lewanowicz)

Tematyka przedmiotu

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.

Program wykładu:

Zalecana literatura

  1. P. Dierckx, Curve and Surface Fitting with Splines, Clarendon Press, Oxford 1993.
  2. G. Farin, Curves and Surfaces for CAGD. A Practical Guide, Morgan-Kaufmann, 2002.
  3. J. D. Foley, A. van Dam, S. K. Feiner, J. F. Hughes, Computer Graphics. Principles and Practice, Addison-Wesley, Reading (Ma) 1992.
  4.  J. Hoschek, D. Lasser, Fundamentals of Computer Aided Geometric Design, AK Peters, Wellesley (Ma) 1993.
  5. P. Kiciak, Podstawy modelowania krzywych i powierzchni, wyd. II, WNT, Warszawa 2005. 

Wymagane przygotowanie do przedmiotu:  

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.

Optymalizacja kombinatoryczna

Tematyka przedmiotu.

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 .  

Program wykładu

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.

Zalecana literatura:

  1. Schrijver. Combinatorial Optimization.
  2. Lee. A First Course in Combinatorial Optimization.
  3. Cook, Cunningham, Pulleyblank, Schrijver. Combinatorial Optimization.
  4. Lawler. Combinatorial Optimization. Networks and Matroids.
  5. Papadimitriou, Steiglitz. Combinatorial Optimization.
  6. Lovasz, Pulleyblank. Matching theory.

Wymagane przygotowanie do przedmiotu

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.

Realistyczna grafika komputerowa (opracował dr A. Łukaszewski)

Tematyka przedmiotu.

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ę:

Zalecana literatura:

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

Wymagane przygotowanie do przedmiotu

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.

Analiza programów komputerowych

Tematyka przedmiotu.

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.

Zalecana literatura:

Flemming Nielson, Hanne Riis Nielson, Chris Hankin: Principles of program analysis, Springer 2005

Wymagane przygotowanie do przedmiotu: 

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. 

Rachunek lambda

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.

Program:

  1. Rachunek lambda - motywacja i historia.
  2. Formalna definicja rachunku lambda, relacje redukcji.
  3. Formalizacja pojęcia obliczalności za pomocą rachunku lambda, teza (Turinga-)Churcha, moc rachunku lambda.
  4. Własności relacji redukcji, twierdzenie Churcha-Rossera.
  5. Rachunek lambda z typami.
  6. Rozstrzygalność prostego systemu typów.
  7. Twierdzenie o silnej normalizacji.
  8. Związki rachunku lambda z logiką.
  9. Elementy semantyki.  
  10. Paradoks Kleene'ego-Rossera, modele dla rachunku lambda.

Literatura:

  1. H.P. Barendregt, The type free lambda calculus, in J. Barwise, Handbook of Mathematic Logic.
  2. H.P. Barendregt, E. Barendsen, Introduction to Lambda Calculus.
  3. H.P. Barendregt,  Lambda calculi with types, in: S. Abramsky, D.M. Gabbay and T.S.E. Maibaum (eds.), Handbook of Logic in Computer Science, (1992).
  4. A. Church, An unsolvable problem of elementary number theory, American Journal of Mathematics 58, (1936).
  5.  A. Church, A formulation of the simple theory of types, Journal of Symbolic Logic 5,  (1940).
  6. R. Loader, Notes on Simply Typed Lambda Calculus, (1998).
  7. John C. Reynolds, Theories of Programming Languages.

Wymagania wstępne:

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.

Teoretyczne podstawy języków programowania

Tematyka przedmiotu.

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.

Literatura.

  1. Abadi M., Cardelli L., A Theory of Objects. Springer-Verlag, 1996
  2. Bruce K.B., Foundations of Object-Oriented Languages. Types and Semantics. MIT Press, 2002.
  3. Castagna G., Object-Oriented Programming. A Unified Foundation. Birkhauser, 1997.
  4. Harper R., Practical Foundations for Programming Languages, Draft, 2012.
  5. Mitchell J.C., Foundations of Programming Languages. MIT Press, 1996.
  6. Mitchell J.C., Concepts in Programming Languages. Cambridge University Press, 2003.
  7. Pierce B., Types and Programming Languages. MIT Press, 2002.
  8. Reynolds J.C., Theories of Programming Languages. Cambridge University Press, 1998.

Wymagania wstępne:

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)

Modelowanie zjawisk przyrodniczych (opracował dr. A. Szustalewicz)

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:

  1. M. Calvo, D.J. Higham, J.I. Montijano and L. Randez, Stepsize selection for tolerance proportionality in explicit Runge–Kutta codes, Computational Mathematics 7 (1997) 361–382,
  2. M. Gewert, Z. Skoczylas, Równania różniczkowe zwyczajne, GiS, Wrocław 2010,
  3. E. Hairer, S. Norsett, G. Wanner, Solving ordinary differential equations I: nonstiff problems, Springer 2008,.
  4. D. Kincaid, W. Cheney, Analiza numeryczna, WNT, Warszawa 2009,
  5. A. Krupowicz, Metody numeryczne zagadnień początkowych równań różniczkych zwyczajnych, PWN, Warszawa 1986,
  6. N.M. Matwiejew, Metody całkowania równań różniczkowych zwyczajnych, PWN, Warszawa 1970,
  7. A. Palczewski, Równania różniczkowe zwyczajne, WNT, Warszawa 2004,
  8. B. Przeradzki, Teoria i praktyka równań różniczkowych zwyczajnych, podręcznik akademicki, WUŁ, Łódź 2003.

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.

Metody translacji

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.

Program

Zalecana literatura

  1. A.V. Aho, R. Sethi, J.D. Ullman, Compilers - Principles. Techniques, and Tools, Addison-Wesley, 1986.
  2. R. Wilhelm, D. Mauer, Compiler Design, Addison-Wesley, 1995.
  3. W.M. Waite, G. Goos, Konstrukcja kompilatorów, WNT, 1989.

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. 

Systemy typów

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.

Wybrane zagadnienia:

  1. Typy proste (rachunek lambda z typami prostymi, rozszerzenia, normalizacja)        
  2. Izomorfizm Curry'ego-Howarda
  3. Efekty         obliczeniowe w języku z typami prostymi (modyfikowalny stan, wyjątki, kontynuacje)
  4. Podtypowanie
  5. Typy iloczynowe i unijne
  6. Typy rekurencyjne
  7. Polimorfizm (rekonstrukcja typów, ML-polimorfizm, typy uniwersalne i egzystencjalne)
  8. Systemy typów wyższego rzędu (F-omega)
  9. Typy zależne

Literatura:

  1. Harper R., Type Systems for Programming Languages, Draft, 2000.        
  2. Pierce B., Types and Programming Languages, MIT Press, 2002.
  3. Pierce B. ed.,         Advanced Topics in Types and Programming Languages, MIT Press, 2005.
  4. M. H. Sorensen, P. Urzyczyn, Lectures on the Curry-Howard Isomorphism, Elsevier Science, 2006.

Wymagania wstępne:

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]

[a]tju:

ktora werjse parametrow chcial Jurek?


tju:

i ktora liczba godzin ? 300 jak w 3a pasuje lepiej.