Matematyka Dyskretna krajka.pdf

MatematykaDyskretna

UniwersytetMariiCurieSkłodowskiej

Wydział Matematyki, Fizyki iInformatyki

InstytutInformatyki

Matematyka Dyskretna

AndrzejKrajka

Moim wspaniałym dzieciom

Asi i Tomkowi

Lublin 2011

Instytut Informatyki UMCS

Lublin 2011

Andrzej Krajka

Matematyka Dyskretna

Recenzent : Ryszard Smarzewski

Opracowanie techniczne: Marcin Denkowski

Projekt okładki: Agnieszka Kuśmierska

Praca współﬁnansowana ze środków Unii Europejskiej w ramach

Europejskiego Funduszu Społecznego

Publikacja bezpłatna dostępna online na stronach

Instytutu Informatyki UMCS: informatyka.umcs.lublin.pl.

Wydawca

Uniwersytet Marii CurieSkłodowskiejw Lublinie

Instytut Informatyki

pl. Marii CurieSkłodowskiej 1, 20031 Lublin

Redaktor serii: prof. dr hab. Paweł Mikołajczak

www: informatyka.umcs.lublin.pl

email: dyrii@hektor.umcs.lublin.pl

Druk

ESUS Agencja ReklamowoWydawnicza Tomasz Przybylak

ul. Ratajczaka 26/8

61815Poznań

www: www.esus.pl

ISBN: 9788362773053

Wstęp

Matematyka dyskretnajestto zbiorcza nazwaróżnych działówmatema

tyki, zajmujących się badaniem struktur nieciągłych czyli skończonych lub

co najwyżej przeliczalnych. Matematyka dyskretna stała się popularna w

ostatnich latach dzięki zastosowaniom winformatyce, która wsposób natu

ralnyzajmujesięjedyniestrukturamiskończonymi(skończonareprezentacja

liczb, skończona ilość operacji w jednostkach czasu komputera taktowanie

zegara).

Skrypt ten powstał na podstawie wykładów, które prowadziłem na kie

runkachinformatycznych Uniwersytetuim.MariiCurieSkłodowskiejwLu

blinie. Z założenia jest poszerzeniem wykładu o niektóre elementy, które z

powoduograniczeńczasowychniemogłybyćwsposóbkompletnywyłożone.

Tak więc niektóre twierdzenia, podawanena wykładzie bezdowodów, tutaj

są wprowadzone z dowodami i konieczną do tych dowodów teorią.

Nie zakładam jednak, że ta książka jest pełną monograﬁą wszystkich

działów matematyki dyskretnej. Ponieważ w planie zajęć studenci mają

takie przedmioty jak podstawy rachunku prawdopodobieństwa, wstęp do

logiki i teorii mnogości czy też elementy logiki i arytmetyki komputerów,

więc poważnie zostały okrojone, a nawet zlikwidowane, takie działy mate

matykidyskretnejjakalgebra,logika, teoriamnogości,rachunekprawdopo

dobieństwa ikombinatoryka. Cowięcej, ze względu na plan studiów,wtym

skrypciezakładam znajomość niektórych pojęć z tych działów (rozdział 7.1

należy traktować jako raczej przypomnienie a nie formalne wprowadzenie

prawdopodobieństwa). Z drugiej strony, ponieważ studenci na drugim roku

studiów mają przedmiot o nazwie teoria grafów, dlatego w ramach kursu

Matematyka Dyskretna teoria grafów została zredukowana do podstawo

wychpojęć.Traktujemyjątutajjakowprowadzeniedowspomnianegowyżej

przedmiotu,chociażitakwtymskrypciezagadnieniazwiązanezgrafamisą

znacznie bardziej rozbudowane w porównaniu z wykładem. Również duża

ilość przedmiotów takich jak podstawy programowania spowodowała usu

nięciezwykładuelementówdotyczącychsprawdzaniapoprawnościlogicznej

programów.

Tocozostałotogłównieproblemyzwiązanezrekurencjami,teorialiczb,

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: