Algorytmy. Almanach - George ...

[ Pobierz całość w formacie PDF ]
//-->Tytuł oryginału: Algorithms in a NutshellTłumaczenie: Zdzisław PłoskiISBN: 978-83-246-5847-3Authorized translation of the English edition of Algorithms in a Nutshell, ISBN 9780596516246© 2009 George Heineman; Gary Pollice; Stanley Selkow.This translation is published and sold by permission of O’Reilly Media, Inc., the owner of all rightsto publish and sell the same.Polish language edition published by Helion S.A.Copyright © 2010.All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means,electronic or mechanical, including photocopying, recording or by any information storage retrieval system,without permission from the Publisher.Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszechnianie całości lub fragmentuniniejszej publikacji w jakiejkolwiek postaci jest zabronione. Wykonywanie kopii metodąkserograficzną, fotograficzną, a także kopiowanie książki na nośniku filmowym, magnetycznymlub innym powoduje naruszenie praw autorskich niniejszej publikacji.Wszystkie znaki występujące w tekście są zastrzeżonymi znakami firmowymi bądź towarowymiich właścicieli.Autor oraz Wydawnictwo HELION dołożyli wszelkich starań, by zawarte w tej książce informacjebyły kompletne i rzetelne. Nie biorą jednakżadnejodpowiedzialności ani za ich wykorzystanie, ani zazwiązane z tym ewentualne naruszenie praw patentowych lub autorskich. Autor oraz WydawnictwoHELION nie ponoszą równieżżadnejodpowiedzialności za ewentualne szkody wynikłez wykorzystania informacji zawartych w książce.Wydawnictwo HELIONul. Kościuszki 1c, 44-100 GLIWICEtel. 32 231 22 19, 32 230 98 63e-mail:helion@helion.plWWW:(księgarnia internetowa, katalog książek)Drogi Czytelniku!Jeżeli chcesz ocenić tę książkę, zajrzyj pod adresMożesz tam wpisać swoje uwagi, spostrzeżenia, recenzję.Pliki z przykładami omawianymi w książce można znaleźć pod adresem:ftp://ftp.helion.pl/przyklady/algalm.zipPrinted in Poland.•Poleć książkę na Facebook.com•Kup w wersji papierowej•Oceń książkę•Księgarnia internetowa•Lubię to!»Nasza społecznośćSpis treściPrzedmowa ................................................................................................................................ 7Zasada: oddziel algorytm od rozwiązywanego problemuZasada: wprowadzaj tylko tyle matematyki, ile trzebaZasada: analizę matematyczną stosuj doświadczalnieOdbiorcyTreść książkiKonwencje stosowane w tej książceZastosowanie przykładów w kodziePodziękowaniaLiteratura899101111121313Część I ................................................................................................................151. Algorytmy są ważne ......................................................................................................17Postaraj się zrozumieć problemJeśli to konieczne, eksperymentujKwestia ubocznaNauka płynąca z opowiedzianej historiiLiteratura18192323252. Algorytmy w ujęciu matematycznym ..........................................................................27Rozmiar konkretnego problemuTempo rośnięcia funkcjiAnaliza przypadku najlepszego,średniegoi najgorszegoRodziny efektywnościMieszanka działańOperacje do pomiarów wzorcowychUwaga końcowaLiteratura272933374950525233. Wzorce i dziedziny .......................................................................................................53Wzorce — język komunikacjiForma wzorca pseudokoduForma projektowaForma oceny doświadczalnejDziedziny a algorytmyObliczenia zmiennopozycyjneRęczne przydzielanie pamięciWybór języka programowania5355575959606466Część II . ............................................................................................................ 694. Algorytmy sortowania ..................................................................................................71PrzeglądSortowanie przez wstawianieSortowanie medianoweSortowanie szybkieSortowanie przez wybieranieSortowanie przez kopcowanieSortowanie przez zliczanieSortowanie kubełkoweKryteria wyboru algorytmu sortowaniaLiteratura7177819198991041061111155. Wyszukiwanie . ............................................................................................................117PrzeglądWyszukiwanie sekwencyjneWyszukiwanie z haszowaniemPrzeszukiwanie drzewa binarnegoLiteratura1171181281401466. Algorytmy grafowe .................................................................................................... 147PrzeglądPrzeszukiwania w głąbPrzeszukiwanie wszerzNajkrótszaścieżkaz jednymźródłemNajkrótszaścieżkamiędzy wszystkimi paramiAlgorytmy minimalnego drzewa rozpinającegoLiteratura1471531601631741771804|Spis treści7. Znajdowanie dróg w AI ...............................................................................................181PrzeglądPrzeszukiwania wszerzA*SEARCHPorównanieAlgorytm minimaksAlgorytm AlfaBeta1811982012112142228. Algorytmy przepływu w sieciach . ............................................................................ 231PrzeglądPrzepływ maksymalnyDopasowanie obustronneUwagi na tematścieżekpowiększającychPrzepływ o minimalnym koszciePrzeładunekPrzydział zadańProgramowanie linioweLiteratura2312342432462492502522532549. Geometria obliczeniowa ............................................................................................255PrzeglądSkanowanie otoczki wypukłejZamiatanie prostąPytanie o najbliższych sąsiadówZapytania przedziałoweLiteratura255263272283294300Część III ............................................................................................................30110. Gdy wszystko inne zawodzi .......................................................................................303Wariacje na tematAlgorytmy aproksymacyjneAlgorytmy offlineAlgorytmy równoległeAlgorytmy losoweAlgorytmy, które mogą być złe, lecz z malejącym prawdopodobieństwemLiteratura303304304305305312315Spis treści|5 [ Pobierz całość w formacie PDF ]