Wydział Matematyki, Informatyki i Mechaniki
Magisterskie Studia Uzupełniające na kierunku informatyka
Wymagania stawiane kandydatom
Kandydaci na MSUI powinni posiadać wiedzę z podstawowych działów matematyki i informatyki w następującym zakresie:
Matematyka:
- Algebra liniowa
- Liczby zespolone.
- Układy równań liniowych.
- Przestrzenie wektorowe i przekształcenia liniowe. Macierze.
- Wektory własne i wartości własne przekształcenia liniowego.
- Wyznaczniki i ich zastosowania.
- Postacie kanoniczne macierzy.
- Analiza
- Liczby rzeczywiste, kresy zbiorów.
- Granica ciagu liczb rzeczywistych. Granica funkcji w punkcie i ciagłość funkcji.
- Rachunek różniczkowy funkcji jednej zmiennej: pochodna funkcji w punkcie. Obliczanie pochodnych - podstawowe wzory. Twierdzenie o wartości średniej. Reguła de l'Hospitala. Wyznaczanie ekstremów funkcji jednej zmiennej. Pochodne wyższych rzędów, wzór Taylora. Badanie przebiegu funkcji.
- Szeregi liczbowe. Zbieżność, zbieżność bezwzględna, podstawowe kryteria zbieżności. Szeregi potęgowe.
- Rachunek całkowy funkcji jednej zmiennej: całka nieoznaczona, całka Riemanna. Całkowanie przez części i przez podstawianie. Twierdzenie o wartości średniej. Całki niewłaściwe.
- Wstęp do matematyki
- Podstawowe pojęcia teoriomnogościowe i operacje na zbiorach: przecięcie, dopełnienie, iloczyn kartezjański, relacje, funkcje, relacje równoważności.
- Moce zbiorów: zbiory skończone i nieskończone, równoliczność, porównywanie mocy zbiorów, tw. Cantora-Bernsteina, zbiory przeliczalne, tw. Cantora i zbiory mocy continuum.
- Częściowe porządki: elementy minimalne, najmniejsze, kresy, pojęcie kraty i kraty zupelnej, porządek liniowy, dualizacja, przykłady ważnych porządków (liczby naturalne, zbiory skończonych i nieskończonych słów, skończone i nieskończone drzewa).
- Indukcja matematyczna.
- Struktury algebraiczne: kongruencje, algebry ilorazowe, algebry wolne, algebry Boole'a, filtry, ideały, grupy, półgrupy. Izomorfizm, automorfizm, homomorfizm.
- Matematyka dyskretna
- Przykłady problemów definiowanych rekurencyjnie (wieże Hanoi), rozwiązywanie równań rekurencyjnych metodą rozwinięcia do sumy.
- Proste funkcje całkowitoliczbowe i ich własności. Równania rekurencyjne. Operacja modulo. Asymptotyka funkcji liczbowych.
- Elementy teorii liczb: NWD, NWW, liczby pierwsze i względnie pierwsze, faktoryzacja i funkcja Eulera.
- Elementy kombinatoryki: podstawowe obiekty kombinatoryczne (funkcje, rozmieszczenia, permutacje, kombinacje) i metody ich zliczania, własności permutacji, współczynniki dwumianowe, zasada włączeń i wyłączeń.
- Funkcje tworzące i rozwiązywanie równań rekurencyjnych.
- Logika
- Składnia i semantyka rachunku zdań i rachunku predykatów. Pojęcie spełniania i prawdziwości formuły.
- Dowodzenie twierdzeń. Systemy dowodzenia. Twierdzenie o pełności dla rachunku zdań i rachunku predykatów.
- Niesprzeczność i spełnialność zbioru formuł. Teorie pierwszego rzędu, pojęcie zupełności i rozstrzygalności.
- Metoda rezolucji dowodzenia twierdzeń.
- Metody numeryczne
- Arytmetyka zmiennopozycyjna. Uwarunkowanie zadania, numeryczna stabilność i poprawność algorytmów.
- Interpolacja: interpolacja Lagrange'a, algorytm różnic dzielonych, informacja o interpolacji Hermite'a.
- Kwadratury: rząd, kwadratury interpolacyjne, dobór węzłów (kwadratury Newtona-Cotesa, Gaussa).
- Rozwiązywanie układów równań liniowych: uwarunkowanie, metoda eliminacji Gaussa.
- Informacja o metodach bisekcji, Newtona i siecznych rozwiązywania równań nieliniowych.
Informatyka:
- Wstęp do programowania
- Intuicyjne pojęcie algorytmu. Przykłady algorytmów znanych ze szkoly (algorytm Euklidesa, Hornera, rozwiązywania równania kwadratowego, itp.).
- Reprezentacja liczb w układzie binarnym. Rachunek stałopozycyjny i zmiennopozycyjny (pojęcie zakresu, nadmiaru, niedomiaru, błędu zaokrągleń).
- Zmienne i wyrażenia. Typ zmiennej. Wartościowanie zmiennych. Wyrażenia arytmetyczne i logiczne.
- Instrukcje. Przykłady zapisu algorytmów.
- Podstawowe typy danych.
- Funkcje i procedury. Sposoby przekazywania parametrów (przez wartość i przez zmienną).
- Informacje o specyfikacji zadania algorytmicznego. Poprawność algorytmu. Metoda niezmienników.
- Złożoność obliczeniowa algorytmu: koszt czasowy i pamięciowy.
- Techniki programowania
- Rekurencja i jej zastosowania. Dowodzenie poprawności algorytmów rekurencyjnych.
- Abstrakcyjne typy danych (zbiór, stos, kolejka). Specyfikacja i realizacja.
- Typy wskaźnikowe. Zastosowanie typow wskaźnikowych do realizacji dynamicznych struktur danych (listy, drzewa).
- Metody konstruowania algorytmów: "dziel i zwyciężaj", programowanie z nawrotami, programowanie dynamiczne, programowanie zachłanne.
- Algorytmy i struktury danych
- Podstawowe rodzaje analizy złożoności (najgorszego przypadku, kosztu oczekiwanego, kosztu zamortyzowanego).
- Sortowanie i selekcja. Złożoność problemu a złożoność algorytmu na przykładzie sortowania. Heapsort i Quicksort. Sortowanie w czasie liniowym (Countsort, Radixsort, Bucketsort). Selekcja. Kolejki priorytetowe.
- Wyszukiwanie i problem słownika. Statyczny problem słownika (wyszukiwanie binarne). Drzewiaste realizacje słownika. Drzewa zrównoważone (AVL, czerwono-czarne). Haszowanie. Wyszukiwanie zewnętrzne (B-drzewa).
Literatura
- K.A. Ross, C. Wright, "Matematyka dyskretna"
- L. Banachowski, K. Diks, W. Rytter, "Algorytmy i struktury danych"
- L. Banachowksi, A. Kreczmar, "Elementy analizy algorytmów"
- N. Wirth, "Algorytmy + struktury danych = programy"
- J. M. Jankowscy, "Metody numeryczne"
- K. Kuratowski, "Analiza matematyczna"
- J. Tiuryn, "Logika dla informatyków"
- H. Rasiowa, "Wstęp do matematyki współczesnej"
- A. Białynicki-Birula, "Algebra liniowa"