Władysław Skarbek - Matematyka Dyskretna , Nauka
[ 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 ] |