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ą

Równania i nierówności liniowe

Nazwa angielska (title in English):
Prowadzący (lecturer): Antoni Kościelski
Liczba punktów (ECTS): 9
Liczba punktów 2007 (ECTS since 2007): 6
Rodzaj (type): zaawansowany
Rodzaj od 2007 (type since 2007): informatyczny.I2
Liczba godzin (hours in semester):
wykład:30
ćwiczenia: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)

Opis (description)

Równania i nierówności liniowe kojarzą się zwykle z zadaniem polegającym na rozwiązaniu danego układu. Rozwiązaniem takiego zadania jest zbiór wszystkich n-ek liczb spełniających rozważany układ. Często interesuje nas także problem niesprzeczności danego układu. Wtedy wystarczy, jeżeli udzielimy odpowiedzi na pytanie, czy jest chociaż jedna n-ka liczb spełniająca ten układ.

Zadania te mają różne własności w zależności np. od tego, czy rozwiązujemy dany układ w zbiorze liczb wymiernych, czy też w zbiorze liczb całkowitych lub naturalnych. Różnią się m.in. złożonością problemu. Problem niesprzeczności diofantycznych równań liniowych (a więc o rozwiązaniach naturalnych) jest NP-zupełny, a problem niesprzeczności równań o rozwiązaniach całkowitych jest wielomianowy. Niektóre problemy są silnie NP-zupełne, inne są pseudowielomianowe. Mają wiele zastosowań praktycznych, w tym technicznych i ekonomicznych. Redukują się do nich inne problemy. Mają również znaczenie teoretyczne.

Na wykładzie zostaną przedstawione podstawowe pojęcia ze złożoności obliczeniowej na przykładzie wspomnianych zadań. Zostaną też przedstawione algorytmy rozwiązujące równania liniowe i podobne zadania. Zajmiemy się złożonością samych zadań i rozwiązujących je algorytmów. Duża część wykładu zostanie oparta o bardzo dobrą książkę Schrijvera.

Wykład może zawierać podstawowe wiadomości z algebry liniowej, w tym informacje o matematycznych metodach rozwiązywania równań liniowych.

Program (program)

  1. Uzupełnienie wiadomości z algebry liniowej. Eliminacja Gaussa.
  2. Pojęcie złożoności czasowej. Klasy P i NP.
  3. NP-zupełność problemu niesprzeczności układu liniowych równań diofantycznych
  4. Wielomianowość zadania rozwiazania układu liniowych równań całkowitych.
  5. Wielomianowość problemu istnienia rozwiązania układu nierówności liniowych całkowitych o ograniczonej liczbie zmiennych.
  6. Metoda redukcji bazy.
  7. Złożoność algebraiczna. Związki z mnożeniem macierzy. Dolne granice na liczbę mnożeń.
  8. Programowanie liniowe.
  9. Metoda simpleks. Metoda elipsoid. Algorytm Karmarkara.

Inne zagadnienia, które mogą zostać omówione na wykładzie:

Algorytm Strassena mnożenia macierzy. Zaawasowane algorytmy mnożenia macierzy.

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