Algorytmy_i_struktury_danych.pdf

(4929 KB) Pobierz

Projekt okładki i stron tytułowych:

Alicja Żarowska-Mazur

Wydawca:

Łukasz Łopuszański

Koordynator ds. redakcji:

Adam Kowalski

Redaktor:

Izabela Mika

Produkcja:

Anna Bączkowska

Skład wersji elektronicznej na zlecenie Wydawnictwa Naukowego PWN:

Kamil Raczyński /

konwersja.virtualo.pl

Książka, którą nabyłeś, jest dziełem twórcy i wydawcy. Prosimy, abyś przestrzegał praw, jakie im

przysługują. Jej zawartość możesz udostępnić nieodpłatnie osobom bliskim lub osobiście znanym.

Ale nie publikuj jej w internecie. Jeśli cytujesz jej fragmenty, nie zmieniaj ich treści i koniecznie

zaznacz, czyje to dzieło. A kopiując jej część, rób to jedynie na użytek osobisty.

Szanujmy cudzą własność i prawo Więcej na

www.legalnakultura.pl

Polska Izba Książki

Warszawa 1996, 2001

ISBN 978-83-01-20148-7

eBook został przygotowany na podstawie wydania papierowego z 2018 r., (wyd. I PWN) Warszawa

2018

Wydawnictwo Naukowe PWN SA 02-460 Warszawa, ul. Gottlieba Daimlera 2

tel. 22 69 54 321; faks 22 69 54 288

infolinia 801 33 33 88

e-mail:

pwn@pwn.com.pl; reklama@pwn.pl

www.pwn.pl

Spis treści

Przedmowa do nowego wydania

Przedmowa do pierwszego wydania

1. Podstawowe zasady analizy algorytmów

1.1. Złożoność obliczeniowa

1.2. Równania rekurencyjne

1.3. Funkcje tworzące

1.4. Poprawność semantyczna

1.5. Podstawowe struktury danych

1.5.1. Lista

1.5.2. Zbiór

1.5.3. Graf

1.5.4. Notacja funkcyjna dla atrybutów obiektów

1.5.5. Drzewo

1.6. Eliminacja rekursji

1.7. Koszt zamortyzowany operacji w strukturze danych

1.8. Metody układania algorytmów

1.8.1. Metoda „dziel i zwyciężaj”

1.8.2. Programowanie dynamiczne

1.8.3. Metoda zachłanna

1.8.4. Inne metody

Zadania

2. Sortowanie

2.1. Selectionsort – sortowanie przez selekcję

2.2. Insertionsort – sortowanie przez wstawianie

2.3. Quicksort – sortowanie szybkie

2.4. Dolne ograniczenie na złożoność problemu sortowania

2.5. Sortowanie pozycyjne

2.6. Kolejki priorytetowe i algorytm heapsort

2.7. Drzewa turniejowe i zadania selekcji

2.8. Szybkie algorytmy wyznaczania

k-tego

największego elementu w ciągu

2.9. Scalanie ciągów uporządkowanych

2.10. Sortowanie zewnętrzne

2.10.1. Scalanie wielofazowe z 4 plikami

2.10.2. Scalanie wielofazowe z 3 plikami

Zadania

3. Słowniki

3.1. Implementacja listowa nieuporządkowana

3.2. Implementacja listowa uporządkowana

3.3. Drzewa poszukiwań binarnych

3.3.1. Drzewa AVL

3.3.2. Samoorganizujące się drzewa BST

3.4. Mieszanie

3.4.1. Wybór funkcji mieszającej

3.4.2. Struktury danych stosowane do rozwiązywania problemu kolizji

3.5. Wyszukiwanie pozycyjne

3.5.1. Drzewa RST

3.5.2. Drzewa TRIE

3.5.3. Drzewa PATRICIA

3.6. Wyszukiwanie zewnętrzne

3.6.1. Pliki nieuporządkowane

3.6.2. Pliki z funkcją mieszającą

3.6.3. Sekwencyjne pliki indeksowane

3.6.4. B-drzewo jako wielopoziomowy indeks rzadki

3.6.5. B-drzewo jako wielopoziomowy indeks gęsty

Zadania

4. Złożone struktury danych dla zbiorów elementów

4.1. Problem sumowania zbiorów rozłącznych

4.1.1. Implementacja listowa

4.1.2. Implementacja drzewowa

4.2. Złączalne kolejki priorytetowe

Zadania

Plik z chomika:

mofffon

Algorytmy_i_struktury_danych.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: