Algorytmy i struktury danych

1 opinia

Format:

mobi, epub, ibuk

DODAJ DO ABONAMENTU

WYBIERZ RODZAJ DOSTĘPU

41,30  59,00

Format: mobi, epub

 

Dostęp online przez myIBUK

WYBIERZ DŁUGOŚĆ DOSTĘPU

6,15

Wypożycz na 24h i opłać sms-em

41,3059,00

cena zawiera podatek VAT

ZAPŁAĆ SMS-EM

TA KSIĄŻKA JEST W ABONAMENCIE

Już od 19,90 zł miesięcznie za 5 ebooków!

WYBIERZ SWÓJ ABONAMENT

Jądrem informatyki jest algorytmika, a najważniejszym elementem procesu tworzenia dobrego programu komputerowego jest właściwy dobór algorytmów i struktur danych – szczególnie pod kątem ich wydajności.
Algorytmy i struktury danych są tematem jednego z podstawowych przedmiotów wykładanych na każdych studiach informatycznych. Książka została sprawdzona dydaktyczne na zajęciach prowadzonych ze studentami informatyki Uniwersytetu Warszawskiego, jak też wielu innych uczelni informatycznych w kraju.
Informacja o autorze/ redaktorze:
Autorzy są informatykami o uznanym w świecie dorobku naukowym, edukacyjnym i popularyzatorskim. W latach osiemdziesiątych XX wieku tworzyli podwaliny algorytmiki w Uniwersytecie Warszawskim. Mają na swoim koncie wiele znakomitych prac algorytmicznych opublikowanych w najlepszych wydawnictwach naukowych poświęconych informatyce teoretycznej.


Liczba stron292
WydawcaWydawnictwo Naukowe PWN
ISBN-13978-83-01-20148-7
Numer wydania1
Język publikacjipolski
Informacja o sprzedawcyePWN Sp. z o.o.

Ciekawe propozycje

Spis treści

  Przedmowa do nowego wydania     9
  Przedmowa do pierwszego wydania     11
  1 Podstawowe zasady analizy algorytmów     15
    1.1. Złożoność obliczeniowa     15
    1.2. Równania rekurencyjne     22
    1.3. Funkcje tworzące     23
    1.4. Poprawność semantyczna     24
    1.5. Podstawowe struktury danych     26
      1.5.1. Lista     27
      1.5.2. Zbiór     29
      1.5.3. Graf     30
      1.5.4. Notacja funkcyjna dla atrybutów obiektów     35
      1.5.5. Drzewo     35
    1.6. Eliminacja rekursji     38
    1.7. Koszt zamortyzowany operacji w strukturze danych     40
    1.8. Metody układania algorytmów     42
      1.8.1. Metoda „dziel i zwyciężaj”     42
      1.8.2. Programowanie dynamiczne     42
      1.8.3. Metoda zachłanna     43
      1.8.4. Inne metody     44
  Zadania     44
  2 Sortowanie     51
    2.1. Selectionsort – sortowanie przez selekcję     52
    2.2. Insertionsort – sortowanie przez wstawianie     53
    2.3. Quicksort – sortowanie szybkie     54
    2.4. Dolne ograniczenie na złożoność problemu sortowania     64
    2.5. Sortowanie pozycyjne     68
    2.6. Kolejki priorytetowe i algorytm heapsort     72
    2.7.. Drzewa turniejowe i zadania selekcji     79
    2.8. Szybkie algorytmy wyznaczania k-tego największego elementu w ciągu     84
    2.9. Scalanie ciągów uporządkowanych     87
    2.10. Sortowanie zewnętrzne     90
      2.10.1. Scalanie wielofazowe z 4 plikami     91
      2.10.2. Scalanie wielofazowe z 3 plikami     92
  Zadania     96
  3 Słowniki     100
    3.1. Implementacja listowa nieuporządkowana     101
    3.2. Implementacja listowa uporządkowana     101
    3.3. Drzewa poszukiwań binarnych     106
      3.3.1. Drzewa AVL     114
      3.3.2. Samoorganizujące się drzewa BST     118
    3.4. Mieszanie     121
      3.4.1. Wybór funkcji mieszającej     122
      3.4.2. Struktury danych stosowane do rozwiązywania problemu kolizji     122
    3.5. Wyszukiwanie pozycyjne     127
      3.5.1. Drzewa RST     127
      3.5.2. Drzewa TRIE     130
      3.5.3. Drzewa PATRICIA     132
    3.6. Wyszukiwanie zewnętrzne     135
      3.6.1. Pliki nieuporządkowane     135
      3.6.2. Pliki z funkcją mieszającą     136
      3.6.3. Sekwencyjne pliki indeksowane     136
      3.6.4. B-drzewo jako wielopoziomowy indeks rzadki     137
      3.6.5. B-drzewo jako wielopoziomowy indeks gęsty     136
  Zadania     139
  4 Złożone struktury danych dla zbiorów elementów     143
    4.1. Problem sumowania zbiorów rozłącznych     143
      4.1.1. Implementacja listowa     144
      4.1.2. Implementacja drzewowa     148
    4.2. Złączalne kolejki priorytetowe     155
  Zadania     162
  5 Algorytmy tekstowe     164
    5.1. Problem wyszukiwania wzorca     165
      5.1.1. Algorytm N („naiwny”)     165
      5.1.2. Algorytm KMP (Knutha-Morrisa-Pratta)     166
      5.1.3. Algorytm liniowy dla problemu wyszukiwania wzorca dwuwymiarowego, czyli algorytm Bakera     169
      5.1.4. Algorytm GS′ (wersja algorytmu Galila-Seiferasa dla pewnej klasy wzorców)     171
      5.1.5. Algorytm KMR (Karpa-Millera-Rosenberga)     172
      5.1.6. Algorytm KR (Karpa-Rabina)     174
      5.1.7. Algorytm BM (Boyera-Moore‘a)     175
      5.1.8. Algorytm FP (Fishera-Patersona)     178
    5.2. Drzewa sufiksowe i grafy podsłów     180
      5.2.1. Niezwarta reprezentacja drzewa sufiksowego     180
      5.2.2. Tworzenie drzewa sufiksowego     182
      5.2.3. Tworzenie grafu podsłów     187
    5.3. Inne algorytmy tekstowe     191
      5.3.1. Obliczanie najdłuższego wspólnego podsłowa     192
      5.3.2. Obliczanie najdłuższego wspólnego podciągu     192
      5.3.3. Wyszukiwanie słów podwójnych     192
      5.3.4. Wyszukiwanie słów symetrycznych     196
      5.3.5. Równoważność cykliczna     196
      5.3.6. Algorytm Huffmana     197
      5.3.7. Obliczanie leksykograficznie maksymalnego sufiksu     199
      5.3.8. Jednoznaczne kodowanie     201
      5.3.9. Liczenie liczby podsłów     202
  Zadania     202
  6 Algorytmy równoległe     207
    6.1. Równoległe obliczanie wyrażeń i prostych programów sekwencyjnych     209
    6.2. Sortowanie równoległe     223
  Zadania     226
  7 Algorytmy grafowe     229
    7.1. Spójne składowe     231
    7.2. Dwuspójne składowe     234
    7.3. Silnie spójne składowe i silna orientacja     241
    7.4. Cykle Eulera     247
    7.5. 5-kolorowanie grafów planarnych     250
    7.6. Najkrótsze ścieżki i minimalne drzewo rozpinające     255
  Zadania     257
  8 Algorytmy geometryczne     260
    8.1. Elementarne algorytmy geometryczne     261
    8.2. Problem przynależności     262
    8.3. Wypukła otoczka     265
    8.4. Metoda zamiatania     273
      8.4.1. Najmniej odległa para punktów     274
      8.4.2. Pary przecinających się odcinków     277
  Zadania     283
  Bibliografia     285
  Skorowidz     287
RozwińZwiń
W celu zapewnienia wysokiej jakości świadczonych przez nas usług, nasz portal internetowy wykorzystuje informacje przechowywane w przeglądarce internetowej w formie tzw. „cookies”. Poruszając się po naszej stronie internetowej wyrażasz zgodę na wykorzystywanie przez nas „cookies”. Informacje o przechowywaniu „cookies”, warunkach ich przechowywania i uzyskiwania dostępu do nich znajdują się w Regulaminie.

Nie pokazuj więcej tego powiadomienia