Дискретная математика Анджей Шепетовский

Matematyka dyskretna

Wydawnictwo Uniwersytetu Gdańskiego

Autor: Andrzej Szepietowski

Jest to kolejne, poprawione, wydanie. Głównym celem przedstawionego wykładu jest przygotowanie do dalszego studiowania informatyki, a w szczególności do nauki projektowania algorytmów. Podręcznik zawiera podstawowe wiadomości z tzw. matematyki dyskretnej, czyli z arytmetyki, kombinatoryki, funkcji logicznych i teorii liczb. Zawiera także wiele przykładów algorytmów oraz zadania algorytmiczne do samodzielnego rozwiązania.

Spis treści

Przedmowa

1 Podstawowe poj˛ecia, oznaczenia

1.1 Sumy

1.2 Iloczyny

1.3 Zbiory

1.4 Różnica symetryczna zbiorów

1.5 Iloczyn kartezjański

1.6 Rodzina zbiorów

1.7 Grafy (nieskierowane)

1.8 Drzewa

1.9 Drzewa ukorzenione

1.10 Grafy skierowane

1.11 Słowa

1.12 Zaokrąglenia

1.13 Przedrostki

1.14 Notacja asymptotyczna

1.15 Wielomiany

1.15.1 Dzielenie wielomianów

1.15.2 Schemat Horna

1.15.3 Pierwiastki wielomianu

1.16 Zadania

2 Arytmetyka

2.1 System dziesiętny

2.2 System dwójkowy

2.3 Zwiększanie liczby o jeden

2.4 Porównywanie liczb

2.5 Operacje arytmetyczne w systemie dwójkowym

2.6 Zamiana systemu

2.7 Długo´s´c liczby

2.8 Du˙ze liczby

2.9 Ułamki

2.10 System szesnastkowy

2.11 Reprezentacja liczb w komputerze

2.11.1 Integer

2.11.2 Real

2.12 Wyra˙zenia arytmetyczne w j˛ezyku Pascal

2.13 Poszukiwania binarne (binary search)

2.13.1 Poszukiwanie pierwiastka

2.14 Zadania

2.15 Problemy

2.15.1 Uzupełnieniowy zapis liczb ujemnych

2.15.2 Liczby w postaci ósemkowej i szesnastkowej w j˛ezyku C

2.15.3 Sumy pot˛eg dwójki

2.15.4 Waga .

3 Kombinatoryka 55

3.1 Zasada podwójnego zliczania

3.2 Ciągi

3.3 Funkcje

3.4 Ciągi bez powtórzeń

3.5 Permutacje

3.6 Podzbiory

3.7 Podzbiory k-elementowe

3.8 Dwumian Newtona

3.9 Zasada szufladkowa Dirichleta

3.10 Zasada sumy

3.11 Zasada włączania i wyłączania

3.12 Przestawienia

3.13 Generowanie obiektów kombinatorycznych

3.13.1 Generowanie podzbiorów

3.13.2 Generowanie k-elementowych podzbiorów

3.13.3 Generowanie permutacji

3.14 Zadania

3.15 Problemy

3.15.1 Najkrótsze drogi

3.15.2 Rozmieszczanie przedmiotów w pudełkach

3.15.3 Wybór n przedmiotów k rozróżnialnych typów

3.15.4 Kombinacje z powtórzeniami

3.15.5 Permutacje z powtórzeniami

3.15.6 Podziały uporządkowane

3.15.7 Permutacje bez punktów stałych

3.15.8 Liczba surjekcji

3.15.9 Twierdzenie Ramseya

3.15.10 Twierdzenie Halla o różnych reprezentantach

4 Rachunek prawdopodobieństwa

4.1 Przestrzeń zdarzeń elementarnych

4.1.1 Zdarzenia

4.1.2 Dalsze przykłady przestrzeni zdarzeń elementarnych

4.2 Prawdopodobieństwo

4.2.1 Klasyczna definicja prawdopodobieństwa, rozkład jednostajny

4.2.2 Własności prawdopodobieństwa

4.3 Prawdopodobieństwo warunkowe

4.4 Zdarzenia niezależne

4.5 Prawdopodobieństwo całkowite

4.6 Schemat dwumianowy (Bernoulliego)

4.6.1 Rzut symetryczna˛moneta˛

4.6.2 Kolorowanie wierzchołków grafu

4.6.3 Trzykrotny rzut niesymetryczna˛moneta˛

4.6.4 Ogólny schemat – n-krotny rzut niesymetryczna˛moneta˛

4.7 Zmienna losowa

4.7.1 Gęstość rozkładu prawdopodobieństwa zmiennej losowej

4.7.2 Dalsze przykłady zmiennych losowych

4.7.3 Rozkład jednopunktowy

4.7.4 Rozkład zero-jedynkowy

4.8 Łączny rozkład prawdopodobieństwa

4.8.1 Gęstość łącznego rozkładu

4.9 Niezależność zmiennych losowych

4.9.1 Własność niezależnych zmiennych losowych\

4.10 Rozkład dwumianowy (Bernoulliego)

4.11 Wartość oczekiwana, średnia

4.11.1 Własności wartości oczekiwanej

4.11.2 Wartość oczekiwana rozkładu jednopunktowego

4.11.3 Wartość oczekiwana rozkładu zero-jedynkowego

4.11.4 Wartość oczekiwana rozkładu dwumianowego

4.11.5 Wartość oczekiwana liczby różnokolorowych krawędzi

4.11.6 Własności wartości oczekiwanej, cd.

4.12 Nierówność Markowa

4.13 Wariancja

4.13.1 Wariancja rozkładu jednopunktowego

4.13.2 Wariancja rozkładu zero-jedynkowego

4.13.3 Wariancja rozkładu dwumianowego

4.13.4 Wariancja liczby różnokolorowych krawędzi

4.14 Nierówność Czebyszewa

4.15 Krańce rozkładu dwumianowego

4.16 Problem dnia urodzin

4.17 Algorytmy probabilistyczne

4.17.1 Algorytm z jednostronnym błędem

4.17.2 Algorytm sprawdzający mnożenie wielomianów

4.17.3 Algorytmy z błędem obustronnym

4.17.4 Algorytm kolorowania wierzchołków grafu

4.18 Zadania

4.19 Problemy

4.19.1 Niezależność zmiennych losowych

5 Funkcje boolowskie

5.1 Algebra Boole’a

5.1.1 Algebra podzbiorów

5.1.2 Alternatywa wykluczająca, xor

5.2 Wyrażenia boolowskie

5.2.1 Wyrażenia boolowskie w języku Pascal

5.3 Funkcje boolowskie

5.3.1 Funkcje boolowskie jednej zmiennej

5.3.2 Funkcje boolowskie dwóch zmiennych

5.3.3 Alternatywa i koniunkcja n zmiennych

5.3.4 Funkcja progowa

5.3.5 Postacie normalne funkcji boolowskich

5.4 Wielowartościowe funkcje boolowskie

5.5 Sieci boolowskie

5.5.1 Sieć dla alternatywy kilku zmiennych

.5.5.2 Sumator

5.6 Operacje boolowskie na wektorach

5.6.1 Reprezentacja zbioru

5.6.2 Operacje na wektorach w języku Pascal

5.6.3 Operacje na wektorach w języku C

5.6.4 Flagi

5.6.5 Reprezentacja ustawienia bierek w grze w szachy

5.6.6 Szyfrowanie w systemie one-pad

5.7 Funkcja parzysto´sci (parity)

5.8 Odciski, zabezpieczanie danych

5.9 Zadania

5.10 Problemy

5.10.1 Gra w kamienie

5.10.2 To˙zsamo´sci w algebrze podzbiorów

5.10.3 Sieci funkcji progowych i sortujących

5.10.4 Wspólne losowanie bitów

6 Teoria liczb 139

6.1 Dzielenie całkowitoliczbowe

6.2 Podzielność liczb

6.3 Relacja kongruencji

6.4 Klasy abstrakcji

6.5 Pierścień Zm

6.5.1 Pierścień Z5

6.5.2 Pierścień Z4

6.6 Największy wspólny dzielnik

6.7 Algorytm Euklidesa

6.7.1 Rozszerzony algorytm Euklidesa

6.8 Liczby pierwsze i względnie pierwsze

6.9 Rozkład liczb na czynniki pierwsze

6.10 Elementy odwracalne

6.11 Funkcja liniowa

6.12 Szyfry liniowe

6.13 Chińskie twierdzenie o resztach

6.14 Obliczenia na dużych liczbach

6.15 Szybkie potęgowanie

6.16 Pierwiastki kwadratowe

6.17 Funkcja Eulera

6.18 Małe twierdzenie Fermata

6.19 Szyfry RSA

6.20 Testy pierwszości

6.20.1 Test naiwny

6.20.2 Test Fermata

6.20.3 Test Millera-Rabina

6.20.4 Losowanie liczb pierwszych

6.21 Zadania

6.22 Problemy

6.22.1 Największy wspólny dzielnik

6.22.2 Najmniejsza wspólna wielokrotność

6.22.3 Liczby względnie pierwsze

6.22.4 Liczby pierwsze

6.22.5 Chińskie twierdzenie o resztach

6.22.6 System szyfrowania one-pad

6.22.7 Przestrzeń liniowa

6.22.8 Uogólnienie małego twierdzenia Fermata

6.22.9 Algorytm Euklidesa dla wielomianów

6.22.10 Wspólne losowanie liczby, gra w marynarza

7 Stosy, kolejki i drzewa

7.1 Listy

7.2 Stosy i kolejki

7.3 Implementacja stosu

7.4 Implementacja kolejki

7.5 Drzewa ukorzenione

7.6 Drzewa binarne

7.7 Drzewa wyrażeń arytmetycznych

7.8 Przeszukiwanie drzew binarnych

7.8.1 Przeszukiwanie drzewa w głąb

7.8.2 Przeszukiwanie drzewa wszerz

7.9 Drzewa decyzyjne

7.10 Drzewo gry

7.10.1 Algorytm waluacji drzewa gry

7.11 Zadania

7.12 Problemy

7.12.1 Szukanie fałszywej monetyi

8 Rekurencja 191

8.1 Wie˙ze Hanoi

8.2 Drzewo rekursji

8.3 Algorytm Euklidesa, wersja rekurencyjna

8.3.1 Rekurencyjne algorytmy przeszukiwania drzew

8.4 Drzewa poszukiwań binarnych

8.5 Funkcje rekurencyjne

8.6 Funkcja (ciąg) Fibonacciego

8.7 Algorytm sortowania przez scalanie

.8.8 Rozwiązywanie równań i nierówności rekurencyjnych

8.9 Metoda podstawiania

8.10 Metoda iteracyjna

8.11 Metoda rekurencji uniwersalnej

8.12 Funkcje tworzące

8.13 Zadania

8.14 Problemy

8.14.1 Wieże Hanoi

9 Grafy (nieskierowane)

9.1 Izomorfizm grafów

9.2 Drogi i cykle

9.3 Drzewa

9.4 Przeszukiwanie grafów w głąb

9.5 Algorytm przeszukiwania grafu wszerz

9.6 Liczenie składowych spójności

9.7 Drzewa spinające

9.8 Fundamentalny zbiór cykli

9.9 Minimalne drzewo spinające

9.10 Cykle i drogi Eulera

9.11 Drogi i cykle Hamiltona

9.12 Kolorowanie grafów

9.12.1 Kolorowanie z nawrotami

9.12.2 Kolorowanie grafu dwoma kolorami

9.12.3 Heurystyki kolorowania grafów

9.13 Hiperkostka

9.13.1 Rozgłaszanie wiadomości

9.13.2 Zbieranie informacji

9.13.3 Plotkowanie

9.14 Zadania

9.15 Problemy

9.15.1 Drzewa spinające

9.15.2 Skojarzenia

9.15.3 Minimalne drzewo spinające

9.15.4 Cykle Eulera

10 Grafy skierowane

10.1 Podstawowe definicje

10.2 Najkrótsze drogi w grafie

10.3 II etap

10.4 Algorytm Forda-Bellmana

10.5 Dodatnie długo´sci, algorytm Dijkstry

10.6 Najkrótsza droga w grafach acyklicznych

10.7 Zadania

10.8 Problemy

10.8.1 Spójność

10.8.2 Cykl Eulera w grafie skierowanym

10.8.3 Ciąg de Bruijna

Bibliografia

Skorowidz

ISBN: 978-83-7865-747-7

Rok wydania: 2018

Liczba stron: 252

Format: B5

Na każdą książkę wystawiamy paragon fiskalny lub fakturę VAT.

Książkę można odebrać osobiście w Gdańsku - Ujeścisko

Koszt dostawy jest stały bez względu na ilość zamawianych egzemplarzy!!!