Algorytmy. Struktury danych i złożoność obliczeniowa

1. Wprowadzenie

1.1. Sterownie procesami deskryptorowymi
1.2. Układy różniczkowo-algebraiczne w teorii sterowania
1.3. Różniczkowo-algebraiczne równania Eulera-Lagrange'a
1.4. Właściwości i klasyfikacja układów deskryptorowych
1.5. Złożone procesy technologiczne
1.6. Przykłady procesów wielostadialnych
1.7. Nowe rezultaty

2. Wstępna analiza procesu

2.1. Motywacja
2.2. Analiza procesów jednoetapowych
2.3. Nowe rezultaty
2.4. Indeks procesu jednostadialnego
2.5. Analiza procesów wielostadialnych
2.6. Nowe rezultaty

3. Zadanie sterowania optymalnego a zadanie optymalizacji

3.1. Motywacja
3.2. Metoda strzałów i dwu-punktowe zagadnienie brzegowe
3.3. Metoda strzałów wielopunktowych
3.4. Parametryzacja funkcji sterującej
3.5. Bezpośrednia metoda strzałów
3.6. Podejście sekwencyjne
3.7. Rozwiązywanie równań deskryptorowych

4. Nowe algorytmy sterowania optymalnego

4.1. Pełna parametryzacja zdania sterowania
4.2. Zadanie optymalizacji z ograniczeniami ciągło-punktowymi
4.3. Podejście sekwencyjno-kolokacyjne
4.4. Konieczne warunki optymalności
4.5. Właściwości nowego algorytmu

5. Wyniki symulacji komputerowych

5.1. Sterowanie reaktorem kinetycznym
5.2. Lądowanie samolotu przerwane przez uskok wiatru

6. Podsumowanie

Książka Dawno temu był sobie algorytm wyjaśnia koncepcje informatyki poprzez znane historie i codzienne sytuacje.
Autor tłumaczy przetwarzanie informacji jako coś, co dzieje się poza komputerami,
a informatykę jako studium systematycznego rozwiązywania problemów. Martin Erwig pokazuje, że wiele codziennych czynności dotyczy rozwiązywania problemów. Na przykład poranne wstawanie: wstajemy z łóżka, bierzemy prysznic, ubieramy się, jemy śniadanie. Ta prosta codzienna rutyna rozwiązuje powtarzający się problem za pomocą serii dobrze zdefiniowanych kroków. W informatyce takie rutynowe działanie nazywamy algorytmem.
Książka wyjaśnia pojęcia z zakresu przetwarzania za pomocą przykładów z życia i popularnych opowieści. Na przykład Jaś i Małgosia wykonują algorytm powrotu z lasu do domu. Film Dzień świstaka ilustruje problem nierozwiązywalności; Sherlock Holmes manipuluje strukturami danych podczas rozwiązywania zagadek kryminalnych; magię w świecie Harry’ego Pottera można zrozumieć dzięki typom i abstrakcjom; natomiast Indiana Jones pokazuje złożoność wyszukiwania. Po drodze autor omawia reprezentacje i różne sposoby organizacji danych; trudne problemy; język, składnię i niejednoznaczność; struktury sterujące, pętle i problem stopu; różne rodzaje rekurencji; a także reguły znajdowania błędów w algorytmach.
Książka zdobyła nagrodę American Book Fest za najlepszą książkę w kategorii Edukacja / Nauka.

Jak już wiesz, struktura danych jest sposobem zorganizowania danych w pamięci komputera, co ma umożliwić szybkie wykonywanie zamierzonych operacji. Pamiętasz też, że algorytm jest sekwencją działań pozwalających na rozwiązanie problemu. Często warunkiem poprawnego działania algorytmu i pomyślnego rozwiązania problemu programistycznego jest trafny wybór struktury danych. To bardzo ważne zagadnienie. Nawet jeśli dobrze znasz wybrany język programowania, to aby pisać dobry kod, musisz nabrać biegłości w posługiwaniu się algorytmami i strukturami danych.

Dzięki tej książce nauczysz się rozwiązywać ambitne problemy algorytmiczne i projektować własne algorytmy. Materiałem do ćwiczeń są tu przykłady zaczerpnięte z konkursów programistycznych o światowej renomie. Dowiesz się, jak klasyfikować problemy, czym się kierować podczas wybierania struktury danych i jak dobierać odpowiednie algorytmy. Sprawdzisz także, w jaki sposób wybór struktury danych może wpłynąć na czas wykonywania algorytmów. Nauczysz się też używać takich metod jak rekurencja, programowanie dynamiczne czy wyszukiwanie binarne. Swoich sił spróbujesz w ramach samodzielnej pracy nad modyfikacją poszczególnych algorytmów. Zamieszczone tu szczegółowe analizy kodu pomogą Ci w zrozumieniu praktycznych aspektów stosowania algorytmów i struktur danych.

W książce między innymi:

algorytm przeszukiwania wszerz
algorytm Dijkstry
struktura zbiorów rozłącznych
kopce
tablice mieszające

Algorytmy: zmierzysz się z naprawdę trudnymi problemami!

O autorze książki

Dr Daniel Zingaro jest wielokrotnie nagradzanym wykładowcą Uniwersytetu Toronto. Głównym obszarem jego badań naukowych jest metodyka nauczania informatyki i sposób przyswajania tej dziedziny wiedzy. Słynie z niekonwencjonalnego i innowacyjnego podejścia do pracy ze studentami.

Spis treści:
1. Wprowadzenie do tematyki agentowej w Informatyce
2. Agent a dekompozycja algorytmu

2.1. Geneza agenta
2.2. Model algorytmu i problemy związane z jego dekompozycją
2.3. Dekompozycja inspirowana podziałem zbioru
2.4. Dekompozycja inspirowana pojęciem iloczynu kartezjańskiego
2.5. Zastosowanie iloczynu kartezjańskiego do zbioru U
2.6. System wieloagentowy jako rezultat dekompozycji algorytmu
2.7. Zastosowanie iloczynu kartezjańskiego w kategorii algorytmów
2.8. Podsumowanie - dekompozycja, agent, autonomia

3. M-agent

3.1. Wprowadzenie
3.2. Pojęcie agenta i koncepcja jego architektury
3.3. M-agent w systemie agentowym
3.4. Model oparty na architekturze M-agenta
3.5. Koncepcja profilu agenta i model agenta wieloprofilowego
3.6. Rozszerzenia i zastosowania koncepcji M-agenta

4. Równoważenie rozłożenia zasobów

4.1. Wprowadzenie
4.2. Agentowe środowisko równoważenia rozkładu zasobów
4.3. System agentowy
4.4. Informacja w systemie agentowym
4.5. Stabilizacja i skalowanie systemu wieloagentowego
4.6. Przykładowe wyniki badania równoważenia zasobów w strukturze wieloprocesorowej
4.7. Podsumowanie

5. Przykłady zastosowań systemów agentowych

5.1. Agenty w zarządzaniu współpracującymi robotami mobilnymi
5.2. Agent w systemach zorientowanych na usługi (SOA)
5.3. Agentowy system rozpoznawania nietypowych zachowań
5.4. Agenty w systemach ewolucyjnych
5.5. Agent w symulacji procesów dynamicznych

6. Zakończenie

Lista skrótów
1. Wprowadzenie
2. Dwumaszynowy problem przepływowy z minimalizacją sumy kosztów
3. Problem przepływowy z minimalizacją sumy kosztów spóźnień
4. Wzorce w cyklicznym problemie przepływowym
5. Bloki w problemach szeregowania z niepewnymi parametrami
6. Metoda hybrydowego algorytmu ewolucyjnego
7. Metoda lokalnych poszukiwań na ograniczonym obszarze
8. Zakończenie
Glosariusz
Indeks

Wyobraźmy sobie, że pewna kawiarnia pozbyła się całej konkurencji przez to, że oferuje darmową kawę, więc nie mamy innego wyboru niż umawiać się właśnie tam. Podczas gdy rozkoszujemy się miłymi rozmowami z przyjaciółmi, zamontowane w stołach podsłuchy i kamery dokładnie monitorują nasze konwersacje i rejestrują, z kim siedzimy. W pomieszczeniu jest także pełno sprzedawców, którzy płacą za naszą kawę, ale nieustannie nam przerywają, proponując zakup swoich produktów i usług. W istocie klientami kawiarni są ci sprzedawcy, a nie Ty i Twoi przyjaciele. Na takiej zasadzie funkcjonują media społecznościowe. Czy powinniśmy beztrosko oddać programom komputerowym prawo podejmowania za nas osobistych decyzji? Zdecydowanie nie. Inteligencja nie oznacza pokładania ślepej ufności w technologii, ale nie oznacza także przejawiania względem niej chorobliwej nieufności. Chodzi o to, by zdawać sobie sprawę z rzeczywistych możliwości AI i wiedzieć, co jest tylko chwytem marketingowym i artykułem techno-religijnej wiary. Chodzi także o zdolność zachowania kontroli nad urządzeniami. A przede wszystkim o to, żeby nie przestać myśleć w świecie, który próbuje myśleć za nas.