Oferta dydaktyczna Instytutu Informatyki

Poniższa lista przedstawia przedmioty, które są uczone w Instytucie Informatyki, niektóre z nich co roku, niektóre z mniejszą częstotliwością Każdy student Instytutu Informatyki studiuje wg indywidualnego toku studiów, wybierając (zgodnie z pewnymi zasadami) z tej listy swoje przedmioty.

Jeżeli zastanawiasz się nad studiami u nas, jeżeli chcesz wiedzieć, czy na Uniwersytecie można zostać inżynierem, jeżeli interesuje Cię 1000 zł stypendium miesięcznie - zapraszamy na naszą stronę główną

Matematyka dyskretna (M)

Nazwa angielska (title in English):
Prowadzący (lecturer): Grzegorz Stachowiak
Liczba punktów (ECTS): 9
Liczba punktów 2007 (ECTS since 2007): 9
Rodzaj (type): obowiązkowy
Rodzaj od 2007 (type since 2007): obowiązkowy.O2
Liczba godzin (hours in semester):
wykład:45
ćwiczenia:45
repetytorium:30
Egzamin (exam): tak
Możliwe zajęcia w języku angielskim (can be taught in English): nie
Przedmiot zostal uaktualniony na biezacy rok (updated): tak
Semestr (semester): zimowy

Wymagania (prerequisites)

Program (program)

Elementy Algebry i Teorii Liczb

  1. Funkcje całkowitoliczbowe, arytmetyka modularna, operacje sufit i podłoga zaokrąglania liczb rzeczywistych, algorytm mergesort. (2 godz.)
  2. Asymptotyka funkcji liczbowych z uwzględnieniem zastosowań w szacowaniu złożoności czasowej algorytmów. (2 godz.)
  3. Podzielność liczb, algorytm Euklidesa. (2 godz.)
  4. Liczby Fibonacciego. (1 godz.)
  5. 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

  1. Rozmieszczenia, permutacje, kombinacje, podziały (zbioru, liczby), Lemat Burnside'a. (4 godz.)
  2. Metody generowania prostych obiektów kombinatorycznych. (2 godz.)
  3. Przykłady prostych problemów definiowanych rekurencyjnie. (2 godz.)
  4. Rozwiązywanie równań rekurencyjnych, funkcje tworzące. (4 godz.)
  5. Liczby Catalana. (1 godz.)
  6. Zasada włączania i wyłączania. (2 godz.)

Teoria grafów i zbiorów uporządkowanych

  1. Relacje porządku i równoważności i ich przykłady. (1 godz.)
  2. Rozszerzenia liniowe zbiorów uporządkowanych - zastosowanie w konstrukcji algorytmów sortujących. (1 godz.)
  3. Definicje i przykłady krat, krat rozdzielnych i Algebr Boole'a. (2 godz.)
  4. Definicja i przykłady grafów, grafy pełne, dwudzielne skierowane, stopień wierzchołka. (2 godz.)
  5. Drogi i cykle w grafach: grafy spójne i dwudzielne. (1 godz.)
  6. Drzewa - równoważność różnych definicji. (1 godz.)
  7. Komputerowa reprezentacja grafów. (1 godz.)
  8. Metody BFS i DFS przeszukiwania grafów. (2 godz.)
  9. Minimalne drzewa rozpinające - algorytmy Kruskala i Prima-Dijkstry. (2 godz.)
  10. Przechodnie domkniecie: algorytmy Dijkstry i Warshalla. Złożoność problemu. (3 godz.)
  11. Cykle i drogi Eulera. (1 godz.)
  12. Cykle i drogi Hamiltona tw. Ore i wielomianowa redukcja problemu drogi do cyklu i odwrotnie. (2 godz.)
  13. Grafy planarne. Tw. Kuratowskiego i wzór Eulera. (3 godz.)
  14. Kolorowanie grafów: zastosowanie - planowanie sesji egzaminacyjnej. Algorytm sekwencyjny i twierdzenie o 5-kolorowaniu grafów planarnych. (2 godz.)

Literatura (references)

Jeżeli jesteś zainteresowany studiowaniem w naszym instytucie, zapraszamy na stronę poświęconą tegorocznej rekrutacji.

Nazwa użytkownika (user name):
Hasło (password):