Algorytmika praktyczna

• Kategorie:
  1. Ebooki i Audiobooki »
  2. Informatyka
• Język wydania: polski
• ISBN: 978-83-01-15821-7
• ISBN druku: 978-83-01-15817-0
• Liczba stron: 312
• Sposób dostarczenia produktu elektronicznego
  Produkty elektroniczne takie jak Ebooki czy Audiobooki są udostępniane online po uprzednim opłaceniu (PayU, BLIK) na stronie Twoje konto > Biblioteka.

  Pliki można pobrać zazwyczaj w ciągu kilku-kilkunastu minut po uzyskaniu poprawnej autoryzacji płatności, choć w przypadku niektórych publikacji elektronicznych czas oczekiwania może być nieco dłuższy.

  Sprzedaż terytorialna towarów elektronicznych jest regulowana wyłącznie ograniczeniami terytorialnymi licencji konkretnych produktów.
• Ważne informacje techniczne
• Minimalne wymagania sprzętowe:
  • procesor: architektura x86 1GHz lub odpowiedniki w pozostałych architekturach
  • Pamięć operacyjna: 512MB
  • Monitor i karta graficzna: zgodny ze standardem XGA, minimalna rozdzielczość 1024x768 16bit
  • Dysk twardy: dowolny obsługujący system operacyjny z minimalnie 100MB wolnego miejsca
  • Mysz lub inny manipulator + klawiatura
  • Karta sieciowa/modem: umożliwiająca dostęp do sieci Internet z prędkością 512kb/s
• Minimalne wymagania oprogramowania:
  • System Operacyjny: System MS Windows 95 i wyżej, Linux z X.ORG, MacOS 9 lub wyżej, najnowsze systemy mobilne: Android, iPhone, SymbianOS, Windows Mobile
  • Przeglądarka internetowa: Internet Explorer 7 lub wyżej, Opera 9 i wyżej, FireFox 2 i wyżej, Chrome 1.0 i wyżej, Safari 5
  • Przeglądarka z obsługą ciasteczek i włączoną obsługą JavaScript
  • Zalecany plugin Flash Player w wersji 10.0 lub wyżej.
• Informacja o formatach plików:
  • PDF - format polecany do czytania na laptopach oraz komputerach stacjonarnych.
  • EPUB - format pliku, który umożliwia czytanie książek elektronicznych na urządzeniach z mniejszymi ekranami (np. e-czytnik lub smartfon), dając możliwość dopasowania tekstu do wielkości urządzenia i preferencji użytkownika.
  • MOBI - format zapisu firmy Mobipocket, który można pobrać na dowolne urządzenie elektroniczne (np.e-czytnik Kindle) z zainstalowanym programem (np. MobiPocket Reader) pozwalającym czytać pliki MOBI.
  • Audiobooki w formacie MP3 - format pliku, przeznaczony do odsłuchu nagrań audio.
• Rodzaje zabezpieczeń plików:
  • Watermark - (znak wodny) to zaszyfrowana informacja o użytkowniku, który zakupił produkt. Dzięki temu łatwo jest zidentyfikować użytkownika, który rozpowszechnił produkt w sposób niezgodny z prawem.
  • Brak zabezpieczenia - część oferowanych w naszym sklepie plików nie posiada zabezpieczeń. Zazwyczaj tego typu pliki można pobierać ograniczoną ilość razy, określaną przez dostawcę publikacji elektronicznych. W przypadku zbyt dużej ilości pobrań plików na stronie WWW pojawia się stosowny komunikat.

  Więcej informacji o publikacjach elektronicznych

Słowo wstępne	9
Przedmowa	11
1. Algorytmy grafowe	15
	1.1. Reprezentacja grafu	16
	1.2. Przeszukiwanie grafu wszerz	20
	1.3. Przeszukiwanie grafu w głąb	25
	1.4. Silnie spójne składowe	31
	1.5. Sortowanie topologiczne	38
	1.6. Acykliczność	41
	1.7. Mosty, punkty artykulacji i dwuspójnie składowe	44
	1.8. Ścieżka i cykl Eulera	51
	1.9. Minimalne drzewo rozpinające	57
	1.10. Algorytm Dijkstry	60
	1.11. Algorytm Bellmana-Forda	65
	1.12. Maksymalny przepływ	67
		1.12.1. Maksymalny przepły wyznaczany metodą Dinica	68
		1.12.2. maksymalny przepływ dla krawędzi jednostkowych	72
		1.12.3. Najtańszy maksymalny przepływ dla krawędzi jednostkowych	74
	1.13. Maksymalne skojarzenie w grafie dwudzielnym	77
		1.13.1. Dwudzielność grafu	78
		1.13.2. Maksymalne skojarzenie w grafie dwudzielnym w czasie O (n(n+m))	81
		1.13.3. Maksymalne skojarzenie w grafie dwudzielnym w czasie O((n+m)n1/2)	83
		1.13.4. Najdroższe skojarzenie w grafie dwudzielnym	86
2. Geometria obliczeniowa na płaszczyźnie	91
	2.1. Odległość punktu od prostej	95
	2.2. Pole wielokąta	96
	2.3. Przynależność punktu do figury	98
	2.4. Punkty przecięcia	105
	2.5. Trzy punkty - okrąg	114
	2.6. Sortowanie kątowe	116
	2.7. Otoczka wypukła	120
	2.8. Para najbliższych punktów	123
3. Kombinatoryka	128
	3.1. Permutacje w kolejności antyleksykograficznej	128
	3.2. Permutacje - minimalna liczba transpozycji	130
	3.3. Permutacje - minimalna liczba transpozycji sąsiednich	132
	3.4. Wszystkie podzbiory zbioru	135
	3.5. Podzbiory k-elementowe w kolejności leksykograficznej	137
	3.6. Podziały zbioru z użyciem minimalnej liczby zmian	138
	3.7. Podziały liczby w kolejności antyleksykograficznej	140
4. Teoria liczb	142
	4.1. Współczynnik dwumianowy	142
	4.2. Największy wspólny dzielnik	144
	4.3. Odwrotność modularna	147
	4.4. Kongruencje	149
	4.5. Szybkie potęgowanie modularne	152
	4.6. Sito Eratostenesa	154
	4.7. Lista liczb pierwszych	155
	4.8. Test pierwszości	157
	4.9. Arytmetyka wielkich liczb	160
5. Struktury danych	178
	5.1. Struktura danych do reprezentacji zbiorów rozłącznych	178
	5.2. Drzewa wyszukiwań binarnych	182
		5.2.1. Drzewa maksimów	185
		5.2.2. Drzewa licznikowe	187
		5.2.3. Drzewa pozycyjne	189
		5.2.4. Drzewa pokryciowe	192
	5.3. Binarne drzewa statyczne dynamicznie alokowane	195
	5.4. Wzbogacane drzewa binarne	200
6. Algorytmy tekstowe	212
	6.1. Algorytm KMP	212
	6.2. Minimalny okres słowa	216
	6.3. KMP dla wielu wzorców (algorytm Aho-Corasick)	217
	6.4. Promienie palindromów w słowie	223
	6.5. Drzewa sufiksowe	226
		6.5.1. Liczba wystąpień wzorca w tekście	230
		6.5.2. Liczba różnych podsłów słowa	232
		6.5.3. Najdłuższe podsłowo występujące n razy	233
	6.6. Maksymalny leksykograficznie sufiks	234
	6.7. Równoważność cykliczna	235
	6.8. Minimalna leksykograficznie cykliczność słowa	237
7. Algebra liniowa	240
	7.1. Eliminacja Gaussa	240
		7.1.1. Eliminacja Gaussa w Z2	241
		7.1.2. Eliminacja Gaussa w Zp	244
	7.2. Programowanie liniowe	248
8. Elementy strategii podczas zawodów	253
	8.1. Szacowanie oczekiwanej złożoności czasowej	253
	8.2. Strategia pracy w drużynie	255
	8.3. Szablon	258
	8.4. Plik Makefile	259
	8.5. Parametry kompilacji programów	259
		8.5.1. Parametr - Weffc++	260
		8.5.2. Parametr - Wformat	262
		8.5.3. Parametr - Wshadow	263
		8.5.4. Parametr - Wsequence-point	264
		8.5.5. Parametr - Wunused	267
		8.5.6. Parametr - Wuninitialized	268
		8.5.7. Parametr Wfloat-equal	269
	8.6. Nieustanny time-limit	270
		8.6.1. Eliminacja dzielenia	271
		8.6.2. Wczytywanie danych wejściowych	271
		8.6.3. Wstawki asemblerowe i kompilacja z optymalizacjami	273
		8.6.4. Lepsze wykorzystanie pamięci podręcznej	274
		8.6.5. Przetwarzanie wstępne	275
Wskazówki do zadań	278
Dodatki	292
	A. Nagłówki stosowane w programach	292
	B. Nagłównki Eryka Kopczyńskiego na konkurs TopCoder	295
	C. Sposoby na sukces w zawodach	299
	D. Wykaz zadań na programowanie dynamiczne	304
	E. Wykaz zadań na programowanie zachłanne	305
	F. Wykaz przykładowych zadań	306
Literatura	307
Indeks	309