Matematyka dyskretna W 322 adys 322 ...

Matematyka dyskretna W 322 adys 322 aw Skarbek, nauka, matematyka, matematyka dyskretna

[ Pobierz całość w formacie PDF ]
MatematykaDyskretna
Władysław Skarbek
Państwowa Wyższa Szkoła Informatyki i Zarządzania
Październik 2004 – Styczeń 2005
Spis treści
3
. . . . . . . . . . . . . . . . . . . . . . . . . 3
. . . . . . . . . . . . . . . . . . . . . . . . . 4
. . . . . . . . . . . . . . . . . . . . 5
. . . . . . . . . . . . . . . . . . . . . . . . . . . 6
. . . . . . . . . . . . . . . . . . . . . . . . 7
. . . . . . . . . . . . . . . . . . . . . 7
. . . . . . . . . . . . . 9
. . . . . . . . . . . . . . . . . . . . . . . . . 10
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
. . . . . . . . . . . . 15
. . . . . . . . . . . . . . . . . . . . . 16
. . . . . . . . . . . . . . . . . . . . . . . . . . . 17
. . . . . . . . . . . . . . . . . . . . . . . . . . . 18
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
. . . . . . . . . . . . . . . . . . . . . 20
21
. . . . . . . . . . . . . . . . . . . . 22
. . . . . . . . . . . . . . . . . . . . . . . 22
. . . . . . . . . . . . . . . . . . 23
. . . . . . . . . . . . . . . . . . . . 23
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
. . . . . . . . . . . . . . . . . . . 27
. . . . . . . . . . . . . . . . . . . . . . 29
. . . . . . . . . . . . . . . . . . . . . . . . . . . 30
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
. . . . . . . . . . . . . . . . . . . . . . . 31
. . . . . . . . . . . . . . . . . . . . . . 32
. . . . . . . . . . . . . . . . . 34
1
. . . . . . . . . . . . . . . . . . . . . . . 35
. . . . . . . . . . . . . . 36
. . . . . . . . . . . . . . . . . . . . . . . . . . . 36
. . . . . . . . . . . . . . . . . . . . . . . . 38
. . . . . . . . . . . . . . . . . . . . . . . . . 41
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
. . . . . . . . . . . . . . 45
. . . . . . . . . . . . 46
. . . . . . . . . . . . . . . . . 50
50
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
. . . . . . . . . . 55
. . . 58
. . . . . . . . . . . . . . . . . 60
. . . . . . . 61
. . . . . . . . . . . . . . . . 65
. . . . . . . . . . . . . . . . . . . . . . . 66
. . . . . . . . . . . . . . . 72
. . . . . . . . . . . . . . . . . 72
. . . . . . . . . . . . 75
. . . . . . . . . . . . . . . 75
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
. . . . . . . . . . . . . . . . . . . 77
. . . . . . . . . . . . . . . . . . 78
80
. . . . . . . . . . . . . . . . . . . . 81
. . . . . . . . 84
. . . . . . . . . . . . . . . . 85
. . . . . . . . . 86
. . . . . . . . . . . . . . . . 88
. . . . . . . . . . . . . . 90
. . . . . . . . . . . . . . . 91
. . . . . . . . . . . . . 93
. . . . . . . . . . . . . . . . . . . . . . . . 93
. . . . . . . . . . . . . . . . . . . . . . . . 94
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
. . . . . . . . . . . . . . . . . . . . . 98
. . . . . . . . . . . . . . . 99
. . . . . . . . . . . . . . 101
. . . . . . . . . . . . . . . . . . . . . . . . 102
. . . . . . . . . . . . . . . . 103
. . . . . . . . . . . . . . . . 104
2
Przedmowa
Matematykadyskretnawujęciutegowykładumanaceluwprowadzeniekoncep
cjimatematycznychleżącychupodstawtakichobszarówwiedzyinformatycznej
jak języki i techniki programowania, układy logiczne i arytmetyczne maszyn
cyfrowych oraz algorytmy szyfrowania danych.
Zaczynamyodpojęciazbioruiszeregupochodnychpojęćmnogościowych,które
ściśle wiążą się z koncepcję typu danych,atrybutu obiektu wsystemie informa
cyjnym, tabeli w relacyjnej bazie danych oraz instancji obiektu danego typu.
Kolejnym prezentowanym obszarem są algebry i ich związek z projektowaniem
jednostek arytmetycznych i logicznych w maszynach cyfrowych, z koncepcją
klasy obiektów i algebraicznymmodelem programukomputerowego.
Rozdział poświęcony schematom rekurencyjnym omawia indukcyjne techniki
definiowania obiektów matematycznych. Obejmuje on szereg przykładów za
stosowania koncepcji rekursji w przyrostowymdefiniowaniu złożonych struktur
danych i algorytmówdziałających na nich.
Wykład zamyka dyskusja zastosowań rachunku reszt w kryptografii. Przedsta
wionowybranealgorytmyszyfrowaniadanychwrazzichteoretycznymipodsta
wami.
1 Zbiory
•
Zbiór jest pojęciem pierwotnym
)
”ten typ tak ma”
•
Przykład zbioru: księgozbiór Polskiej Biblioteki Narodowej
•
Intuicje zbioru:
–
Zbiór to kolekcja, zestaw elementów
–
Specyficzna własność wyróżnia elementy
–
Elementy należą do pewnego uniwersum
–
Zbiór jest podzbiorem pewnego uniwersum
1.1 Zbiory a typy danych
•
Intuicje informatyczne:
–
Książka
to złożony typ danych
–
Konkretny egzemplarz
Pana Tadeusza
w księgozbiorze to instancja
typu
Książka
3
  –
Tenkonkretnyegzemplarznależydozbioruwszystkichinstancjitypu
Książka
–
Księgozbiór
to specyficzna
Kolekcja
–
Księgozbiór Biblioteki Narodowej to instancja typu
Księgozbiór
•
Wnioski:
–
Typ danych nie jest zbiorem
–
Typ danych
T
określa własność
instancja danych jest typu T
–
Własność
instancja danych jest typu T
definiuje zbiór wszystkich
instancji typu
T
Ćwiczenia
1. Podaj przykładowe atrybuty obiektu typu
Książka.
2. Typ
Kolekcja
jest generalizacją typu
Księgozbiór
. Jakich atrybutów typu
Księgozbiór
nie posiada
Kolekcja
?
3. Określtypdanych,któregozbiórwszystkichinstancjijestzbioremwszyst
kich danych osobowych studentów PWSIiP.
1.2 Elementy i podzbiory
•
∈
– przynależność, np.:
–
x
∈
X
–
x
jest elementem zbioru
X
–
y
∈
X
–
y
nie jest elementem zbioru
X
•
⊂
,
⊃
– podzbiór, nadzbiór, np.:
–
A
⊂
B
–
A
jest podzbiorem zbioru
B
–
B
⊃
A
–
B
jest nadzbiorem zbioru
A
•
,
– podzbiór, nadzbiór właściwy, np.:
–
A
B
–
A
jest podzbiorem właściwym zbioru
B
–
B
A
–
B
jest nadzbiorem właściwym zbioru
A
•
= – równość,
= – różność np.:
–
A
=
B
– zbiory
A
i
B
są identyczne
–
A
=
B
– zbiory
A
i
B
są różne
)
Skrót: wtt – wtedy i tylko wtedy
Ćwiczenia
Uzasadnij następujące własności inkluzji:
4
 1.
A
⊂
B
wtt
A
B
lub
A
=
B.
2. Jeśli
A
B,
to
A
=
B.
3.
A
⊂
A.
4. Jeśli
A
⊂
B
i
B
⊂
C,
to
A
⊂
C.
1.3 Definiowanie zbioru – notacja
•
∅
– zbiór pusty
•
{
,...,
}
– wyliczenie elementów zbioru, np.:
–
A
=
{
1
,
2
,
3
,
4
,
5
,
6
}
– zbiór składa się z liczb całkowitychod 1 do 6
–
B
=
{
1
,
2
,...,
12
}
– zbiór liczb naturalnych od 1 do 12
–
N ,
{
1
,
2
,
3
,...
}
– zbiór liczb naturalnych
–
Z ,
{
0
,
±
1
,
±
2
,
±
3
,...
}
– zbiór liczb całkowitych
•
{
x
:
W
(
x
)
}
– zbiór tych
x,
które spełniają warunek
W
(
x
)
,
np.:
–
ZP ,
{
x
:
x
∈
Z
,
2 dzieli
x
}
– zbiór liczb całkowitychparzystych
{
x
:
x
=
q
gdzie
q
∈
N
,p
∈
Z
}
– zbiór liczb wymiernych
–
R =
{
x
:
x
∈
Q lub jest granicą ciągu liczb wymiernych
}
– zbiór
liczb rzeczywistych
Ćwiczenia
1. Zapisz własność definicyjną zbioru liczb pierwszych.
2. Czy każda liczba rzeczywista o skończonym dziesiętnym zapisie pozycyj
nym jest liczbą wymierną ?
3. Podajprzykładliczbywymiernej,którejniemożnazapisaćskończonąlicz
bą cyfr dziesiętnych.
Zadania
1. Podaj przykład liczby wymiernej, która w zapisie dziesiętnym ma skoń
czoną liczbę cyfr, a w zapisie dwójkowym nie ma skończonego zapisu.
2. Dlaliczbyrzeczywistej
x
=0
,b
1
,b
2
,...
podajciągliczbwymiernychzbież
ny do
x.
5
–
Q
,
  [ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

mement.xlx.pl