Zaprzyjaźnij się z algorytmami - Jacek Tomasiewicz | Ebook

E-Book - Produkt w wersji cyfrowej

Tytuł : Zaprzyjaźnij się z algorytmami

Autor: Jacek Tomasiewicz

Format pliku: pdf

Wydawnictwo: Wydawnictwo Naukowe PWN

Liczba stron: 164

Wyadnie: 1

Rok wydania: 2015

ISBN: 978-83-011-8466-7

język: polski

Opis:

Zaprzyjaźnij się z algorytmami. Przewodnik dla początkujących i średniozaawansowanych zawiera opis podstawowych i najważniejszych technik algorytmicznych i struktur danych, które zostały uporządkowane w osiemnastu rozdziałach. Do każdego tematu wyselekcjonowano zadania o zróżnicowanym poziomie trudności odpowiednie zarówno dla początkujących, jak i bardziej zaawansowanych uczniów. Książka jest również doskonałym materiałem dydaktycznym dla nauczycieli szkół gimnazjalnych i ponadgimnazjalnych.

Spis treści:

Wprowadzenie XI

Od autora XIII

1. Złożonosć czasowa 1

Porównanie różnych złożonosci czasowych 2

Limit czasu 3

Złożonosć pamięciowa 4

Ćwiczenie 4

Zadania treningowe 5

Żabka ⋆ 5

Chodnik ⋆ ⋆ 6

Tasma ⋆ ⋆ 7

Rozwiązania 8

2. Zliczanie elementów9

Ćwiczenie 10

Zadania treningowe 11

Permutacja ⋆ 11

Ropucha ⋆ ⋆ 12

Przyciski ⋆ 13

Rozwiązania 14

3. Sumy prefiksowe16

Ćwiczenie 17

Zadania treningowe 18

Długa tasma 18

Samochody ⋆ ⋆ 19

Chomiki ⋆ ⋆ ⋆ 20

Rozwiązania 21

4. Sortowanie22

Sposób 1: sortowanie przez wybieranie 22

Sposób 2: sortowanie przez zliczanie 23

Sposób 3: sortowanie przez scalanie 24

Funkcje sortujące 24

Ćwiczenie 25

Zadania treningowe 25

Iloczyn ⋆ 25

Gwozdzie ⋆ ⋆ 26

Tory kolejowe ⋆ ⋆ ⋆ 27

Rozwiązania 28

5. Stos i kolejka30

Stos 30

Kolejka 31

Ćwiczenie 32

Zadania treningowe 32

Nawiasy ⋆ ⋆ 32

Ryby ⋆ ⋆ ⋆ 33

Cukiernia ⋆ ⋆ ⋆ 34

Rozwiązania 35

6. Wyszukiwanie lidera37

Sprawdzenie kandydata 37

Rozwiązanie o złożonosci O(n2) 38

Rozwiązanie o złożonosci O(n log n) 38

Rozwiązanie o złożonosci O(n) 39

Ćwiczenie 40

Zadania treningowe 41

Dwie częsci ⋆ ⋆ 41

Bajtocka flaga ⋆ ⋆ ⋆ 42

Lider prefiksowy ⋆ ⋆ ⋆ 43

Rozwiązania 44

7. Spójny podciąg o maksymalnej sumie45

Rozwiązanie o złożonosci O(n3) 45

Rozwiązanie o złożonosci O(n2) 46

Rozwiązanie o złożonosci O(n) 46

Ćwiczenie 47

Zadania treningowe 49

Odchudzanie ⋆ 49

Bilet ⋆ ⋆ 49

Praca domowa ⋆ ⋆ ⋆ 51

Rozwiązania 51

8. Liczby pierwsze i złożone53

Liczenie dzielników 53

Test pierwszosci w czasie O(√n) 54

Ćwiczenie 54

Zadania treningowe 56

Obwód ⋆ 56

Szczyty ⋆ ⋆ 56

Flagi ⋆ ⋆ ⋆ ⋆ 57

Rozwiązania 58

9. Sito Eratostenesa61

Faktoryzacja 62

Ćwiczenie 63

Zadania treningowe 64

Tablica liczb ⋆ ⋆ 64

Liczby półpierwsze ⋆ ⋆ ⋆ 64

Liczby doskonałe ⋆ ⋆ ⋆ 65

Rozwiązania 66

10. Algorytm Euklidesa68

Najmniejsza wspólna wielokrotnosć 69

Ćwiczenie 69

Zadania treningowe 69

Mandarynki ⋆ 69

Wesoła małpka ⋆ ⋆ 70

Zbiór pierwszych ⋆ ⋆ ⋆ 71

Rozwiązania 72

11. Ciąg Fibonacciego73

Ćwiczenie 74

Zadania treningowe 74

Zajączek ⋆ ⋆ 74

Drabina ⋆ ⋆ ⋆ 75

Spotkanie ⋆ ⋆ ⋆ ⋆ 76

Rozwiązania 77

12. Wyszukiwanie binarne79

Intuicja 79

Implementacja 80

Wyszukiwanie binarne po wyniku 81

Ćwiczenie 81

Zadania treningowe 82

Promień ⋆ ⋆ 82

Deski ⋆ ⋆ ⋆ 82

Tort ⋆ ⋆ ⋆ ⋆ 83

Rozwiązania 85

13. Gąsienica87

Przykład użycia 87

Ćwiczenie 88

Zadania treningowe 89

Smakołyki ⋆ ⋆ 89

Wycinek ⋆ ⋆ ⋆ 90

Temperatura ⋆ ⋆ ⋆ ⋆ 90

Rozwiązania 92

14. Programowanie zachłanne94

Problem wydawania reszty 94

Dowodzenie poprawnosci 95

Ćwiczenie 95

Zadania treningowe 96

Sznurki ⋆ ⋆ 96

Bracia ⋆ ⋆ ⋆ 97

Szklanki ⋆ ⋆ ⋆ 98

Rozwiązania 99

15. Programowanie dynamiczne101

Problem wydawania reszty 101

Ćwiczenie 103

Zadania treningowe 104

Pionek ⋆ 104

Wybrzeże ⋆ ⋆ ⋆ 105

Ładny ciąg ⋆ ⋆ ⋆ 106

Rozwiązania 107

16. Drzewa binarne110

Pełne drzewo binarne 111

Reprezentacja drzew binarnych 111

Binarne drzewa wyszukiwania (BST) 112

Ćwiczenie 112

Zadania treningowe 113

Drzewko binarne ⋆ 113

Nieskończone drzewko ⋆ ⋆ 114

Drzewko ⋆ ⋆ ⋆ 115

Rozwiązania 116

17. Kolejka priorytetowa119

Kopiec binarny 119

Wstawienie elementu do kopca O(log n) 120

Usunięcie elementu maksymalnego O(log n) 121

Tworzenie nowego kopca z listy elementów O(n) 122

Ćwiczenie 123

Zadania treningowe 124

Emeryci ⋆ ⋆ 124

Bilety ⋆ ⋆ ⋆ 124

Tamy ⋆ ⋆ ⋆ ⋆ 125

Rozwiązania 127

18. Algorytmy grafowe BFS i DFS128

Rodzaje grafów 129

Reprezentacja grafu 130

DFS, czyli przeszukiwanie grafu w głąb 132

BFS, czyli przeszukiwanie grafu wszerz 133

Ćwiczenie 134

Zadania treningowe 134

Lista kontaktów ⋆ ⋆ 134

Las ⋆ ⋆ ⋆ 135

Wyprawa króla ⋆ ⋆ ⋆ ⋆ 136

Rozwiązania 137

A. Kolejne tematy139

Algorytm Dijkstry 139

Srednica drzewa 139

Zbiory rozłączne 139

Algorytm Prima i Kruskala 139

Sortowanie topologiczne 140

Drzewo licznikowe 140

Szybkie potęgowanie 140

Koszt zamortyzowany 140

Najdłuższy rosnący podciąg 140

Teoria gier 140

Algorytm Knutha–Morrisa–Pratta 141

Haszowanie tekstów 141

Algorytm Karpa–Millera–Rosenberga 141

Szukanie palindromów i algorytm Manachera 141

Najdłuższy wspólny podciąg 141

Programowanie dynamiczne na drzewach 141

Podstawy geometrii obliczeniowej 142

Sortowanie kątowe 142

Otoczka wypukła 142

Para najmniej i najbardziej oddalonych punktów 142

Maski bitowe 142

Najniższy wspólny przodek 142

Silnie spójne składowe 143

Mosty i punkty artykulacji 143

Cykl Eulera 143

Przepływy i skojarzenia 143

B. STL144

Para elementów 144

Wektor 145

Kolejka 148

Kolejka priorytetowa 149

Minimum, maksimum i zamiana 150

Sortowanie 150

Permutacje 151

Mieszanie 152

Wskazniki w C++ 152

Iteratory 153

Wyszukiwanie binarne 154

Lista 154

Zbiór i multizbiór 155

Mapa 156

Bibliografia 157

Skorowidz 158

Opinie i komentarze 161

----

Ważne informacje o produkcie:

E-BOOK - PRODUKT W WERSJI CYFROWEJ

Plik pobierzesz na swoim koncie Allegro w zakładce ‘’Moja półka’’.

Musisz posiadać konto w Allegro, aby dokonać zakupu e-booka.

E-booka przeczytasz na: czytniku (Kindle, PocketBook, Onyx, Kobo i inne), smartfonie, tablecie lub komputerze. Informacja o formacie e-book zamieszczona jest w opisie aukcji.

E-book zostanie zabezpieczony za pomocą znaku wodnego i nie posiada DRM