Program studiów

Zasadniczym problemem informatyki jest tworzenie oprogramowania. Problem ten, stanowiący tło i uzasadnienie dla programu przedmiotu „Matematyka dyskretna”, może być przedstawiony następująco. Tworzenie oprogramowania rozpoczyna się od specyfikacji problemu, który może wystąpić w różnych dziedzinach zastosowań informatyki. Następnym krokiem jest opracowanie algorytmu stanowiącego rozwiązanie problemu i, wreszcie, zaimplementowanie tego algorytmu w wybranym języku programowania. Precyzyjne sformułowanie problemu, opracowanie algorytmu i programu wymaga użycia pojęć zrozumiałych dla ludzi i jednoznacznie interpretowanych przez komputer wykonujący program.<br/><br/>Zestaw tych pojęć zawiera się w działach matematyki określanych jako elementarna teoria mnogości oraz logika klasyczna, obejmująca rachunek zdań i rachunek kwantyfikatorów.<br/><br/>Tworzenie algorytmów polega na określeniu działań wykonywanych na pewnych strukturach danych. Określanie operacji, a także struktur danych, opiera się na wielu technikach, spośród których szczególnie szerokie zastosowania znajdują podejścia oparte o rekursję. Wiele praktycznych zagadnień jest formułowanych z wykorzystaniem pojęcia grafów, którym poświęca się sporą część zajęć. Mając ułożony algorytm i napisany program musimy mieć pewność, że program jest poprawny, czyli rozwiązuje wyspecyfikowany problem. Ponadto, nawet poprawny program może nie być zaakceptowany przez użytkownika z powodu jego złożoności obliczeniowej. Analiza problemów poprawności programów i złożoności obliczeniowej również wymaga pojęć i technik omawianych w ramach przedmiotu.<br/><br/>Główne zagadnienia objęte kursem to: elementarne pojęcia logiczne, pojęcie zbioru, definiowanie zbiorów, operacje na zbiorach, relacje i funkcje oraz ich właściwości, zliczanie zbiorów i funkcji, równoliczność zbiorów, języki formalne i gramatyki, język rachunku zdań i rachunku kwantyfikatorów, dowodzenie formuł, indukcja i rekursja strukturalna, rekursja w definiowaniu zbiorów i funkcji, grafy i ich właściwości, algorytmy grafowe, funkcje oceny złożoności algorytmów.