Wladysław Skarbek - Matematyka dyskretna.pdf

(819 KB) Pobierz
3932558 UNPDF
MatematykaDyskretna
Władysław Skarbek
Państwowa Wyższa Szkoła Informatyki i Zarządzania
Październik 2004 – Styczeń 2005
Spis treści
1.1 Zbiory a typy danych . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Elementy i podzbiory . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Definiowanie zbioru – notacja . . . . . . . . . . . . . . . . . . . . 5
1.4 Paradoks Russela . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Operacje mnogościowe . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6 Arytmetyczne typy danych . . . . . . . . . . . . . . . . . . . . . 7
1.8 Produkt kartezjański . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.9 Relacje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.10 Funkcje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.12 Generalizacja typów danych . . . . . . . . . . . . . . . . . . . . . 16
1.13 Atrybuty i cechy . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.14 Tabela relacyjna . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.15 Ciągi i macierze . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.16 Diagramy relacyjne w UML . . . . . . . . . . . . . . . . . . . . . 20
2.1 Intuicje informacyjne algebry . . . . . . . . . . . . . . . . . . . . 22
2.2 Definicja algebry ogólnej . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.1 Algebry a klasy obiektów . . . . . . . . . . . . . . . . . . 23
2.2.2 Diagramy klas w UML . . . . . . . . . . . . . . . . . . . . 23
2.3 Algebra Boole’a . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4 Układy zupełne funkcji Boole’a . . . . . . . . . . . . . . . . . . . 27
2.5 Własności algebry Boole’a . . . . . . . . . . . . . . . . . . . . . . 29
2.6 Mapa Karnaugh . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.7 Rachunek zdań . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.7.1 Spójniki logiczne . . . . . . . . . . . . . . . . . . . . . . . 31
2.7.2 Wyrażenia logiczne . . . . . . . . . . . . . . . . . . . . . . 32
2.7.3 Wyrażenia logiczne a zbiory . . . . . . . . . . . . . . . . . 34
1
2.7.4 Łamigłówka króla . . . . . . . . . . . . . . . . . . . . . . . 35
2.8 Rachunek predykatów i kwantyfikatorów . . . . . . . . . . . . . . 36
2.8.1 Predykaty . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.8.2 Kwantyfikatory . . . . . . . . . . . . . . . . . . . . . . . . 38
2.9 Homomorfizm algebr . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.10 Rachunek reszt . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.11 Arytmetyka cyfrowa w stałym przecinku . . . . . . . . . . . . . . 45
2.12.1 Wzorce bitowe w IEEE 754 . . . . . . . . . . . . . . . . . 50
3.1 Wieże Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.4 Klasyczna indukcja matematyczna . . . . . . . . . . . . . . . . . 60
3.4.2 Obliczanie sum metodą różnic . . . . . . . . . . . . . . . . 65
3.5 Równania rekurencyjne . . . . . . . . . . . . . . . . . . . . . . . 66
3.6 Zliczanie obiektów kombinatorycznych . . . . . . . . . . . . . . . 72
3.6.1 Współczynniki dwumienne . . . . . . . . . . . . . . . . . 72
3.6.3 Zasada włączania i wyłączania . . . . . . . . . . . . . . . 75
3.6.4 Podziały . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.6.5 Zbiory z powtórzeniami . . . . . . . . . . . . . . . . . . . 77
3.6.6 Zliczanie drzew binarnych . . . . . . . . . . . . . . . . . . 78
4.1 Podzielność liczb całkowitych . . . . . . . . . . . . . . . . . . . . 81
4.1.2 Algorytm Euklidesa dla NWP . . . . . . . . . . . . . . . . 85
4.1.4 Przykład – rozlewanie płynów . . . . . . . . . . . . . . . . 88
4.1.5 Liczby pierwsze – wprowadzenie . . . . . . . . . . . . . . 90
4.1.6 Faktoryzacja na liczby pierwsze . . . . . . . . . . . . . . . 91
4.1.7 Liczby pierwsze – sito Eratostenesa . . . . . . . . . . . . . 93
4.1.8 Liczby Mersena . . . . . . . . . . . . . . . . . . . . . . . . 93
4.1.9 Liczby Fermata . . . . . . . . . . . . . . . . . . . . . . . . 94
4.2 Algebra reszt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.2.1 Równania w resztach . . . . . . . . . . . . . . . . . . . . . 98
4.2.2 Chińskie twierdzenie o resztach . . . . . . . . . . . . . . . 99
4.2.3 Twierdzenia Fermata o resztach . . . . . . . . . . . . . . 101
4.2.4 Funkcja Eulera . . . . . . . . . . . . . . . . . . . . . . . . 102
4.2.5 Twierdzenie Eulera o resztach . . . . . . . . . . . . . . . . 103
4.2.6 Szyfrowanie – algorytm RSA . . . . . . . . . . . . . . . . 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 ,
3932558.001.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin