4130649704

Zaliczenie przedmiotu: zaliczenie ćwiczeń.

Literatura

1.    A. Białynicki-Birula; Algebra liniowa z geometrią. BM 48, PWN, 1976.

2.    A. I. Kostrykin, J. I. Manin; Algebra liniowa i geometria. PWN, 1993.

5.    Algebra liniowa 2 [ALN 832]

Specjalność    I+N+T+Z    Poziom    3    Status    O

L. godz. tyg.    2 W + 2 Ćw    L. pkt.    7    Socr. Codę    11.1

Algebry liniowe, izomorfizm algebr. Algebra endomorfizmów oraz algebra macierzy.

Przestrzeń sprzężona, przekształcenia sprzężone.

Podprzestrzenie niezmiennicze, wartości i wektory własne endomorfizmu, diagonalizowalność endomorfi-zmu, twierdzenie Jordana (informacyjnie).

Funkcjonał dwuliniowy i jego macierz, nieosobliwość funkcjonału dwuliniowego. Forma kwadratowa. Podprzestrzeń dwuliniowa i jej podprzestrzeń, przykłady. Prostopadłość, dopełnienie oraz uzupełnienie podprzestrzeni przestrzeni dwuliniowej.

Baza prostopadła, twierdzenie o istnieniu bazy prostopadłej, metody znajdowania bazy prostopadłej. Postać kanoniczna formy kwadratowej (metoda Lagrange’a oraz metoda Jacobiego).

Przestrzenie dwuliniowe nad ciałem liczb rzeczywistych, twierdzenie o bezwładności, sygnatura. Funkcjonał dodatnio, ujemnie określony, kryterium Sylvestera.

Izomorfizm przestrzeni dwuliniowych; symetrie, rozkład izometrii na symetrie.

Macierze ortogonalne, grupa ortogonalna. Endomorfizmy samosprzężone, twierdzenie spektralne. Zaliczenie przedmiotu: egzamin.

Literatura: zob. algebra liniowa 1.

3.    K. Szymiczek; Wykłady z algebry dwuliniowej. Skrypt UŚ. Nr 467, 1991.

6.    Algorytmy i struktury danych 1 [ASD 151]

Specjalność    I    Poziom    5    Status    O

L. godz. tyg.    2    W + 2 Ćw L. pkt.    5+1    Socr. Codę    11.0

1. Elementy analizy algorytmów: poprawność semantyczna, niezmienniki pętli, problem stopu; koszty realizacji algorytmów; rozmiar danych, złożoność czasowa i pamięciowa; typy złożoności: konieczna, wystarczająca, średnia; notacja asymptotyczna (O, 0, fi), rzędy wielkości funkcji: logarytmiczna, stała, liniowo-logarytmiczna, wielomianowa, wykładnicza.

2.    Rekurencja: algorytmy oparte na metodzie „dziel i zwyciężaj”; metody rozwiązywania rekurencji, twierdzenie o rekursji uniwersalnej (bez dowodu); podstawy programowania dynamicznego.

3.    Elementarne struktury danych: tablice, listy wiązane, grafy, drzewa; podstawowe własności matematyczne drzew binarnych.

4.    Abstrakcyjne struktury danych: stosy, kolejki FIFO, kolejki priorytetowe, słowniki; zastosowania powyższych struktur i metody ich implementacji; dokładne omówienie kopców i drzewa poszukiwań binarnych (drzew BST).

5.    Sortowanie: analiza wybranych algorytmów (sortowanie przez wstawianie, przez selekcję, przez scalanie, przez kopcowanie, szybkie); model drzew decyzyjnych i twierdzenia o dolnym ograniczeniu na czas działania dowolnego algorytmu sortującego za pomocą porównań; sortowanie w czasie liniowym: przez zliczanie, pozycyjne, kubełkowe.

6 Mieszanie (haszowanie): metody rozwiązywanie kolizji (metoda łańcuchowa, adresowanie otwarte); złożoność haszowania.

7.    Problem Union-Find: sumowanie zbiorów rozłącznych i jego zastosowania (algorytm Kruskala dla problemu minimalnego drzewa rozpinającego grafu).

Zaliczenie przedmiotu: egzamin.

Literatura:

1.    T. Cormen, C. Leiserson i R. Rivest, Wprowadzenie do Algorytmów, WNT, 2000 (wyd. 3).

2.    L. Banachowski, K. Diks i W. Rytter, Algorytmy i Struktury Danych, WNT, 2001 (wyd. 3).

3.    R. Sedgewick, Algorytmy w C++, ReadMe, 1999.

4 A. Drozdek, Struktury Danych w Języku C, WNT, 1996.