Wektory lub listy

Przyjrzyjmy się bliżej naszej liście pracowników. Taka lista może być postrzegana po prostu jako wiele elementów danych, które możemy zdecydować się zachować lub przechowywać w wielu zmiennych, powiedzmy X, Y, Z, . . . To oczywiście nie pozwoliłoby algorytmowi o stałym rozmiarze "przebiegać" przez listę, której długość może być różna, ponieważ każdy element na liście musiałby się odnosić w algorytmie za pomocą unikalnej nazwy. Dłuższe listy wymagałyby większej liczby nazw zmiennych, a tym samym dłuższych algorytmów. Potrzebujemy sposobu odwoływania się do wielu elementów w jednolity sposób. Potrzebujemy list zmiennych, które można "przejrzeć" lub uzyskać do nich dostęp w inny sposób, ale bez konieczności jawnego nazywania każdego z ich elementów. aby móc "wskazywać" na elementy na tych listach, odnosić się do "następnego" lub "poprzedniego" elementu i tak dalej. Do tych celów wykorzystujemy wektory, zwane również tablicami jednowymiarowymi. Jeśli zmienna jest jak pokój hotelowy, wektor można traktować jako cały korytarz lub piętro w hotelu. Pokoje 301, 302, . . . , 346 mogą być indywidualnymi "zmiennymi"; do każdego można się odwoływać osobno, ale w przeciwieństwie do prostego zbioru zmiennych, cały korytarz lub piętro ma również nazwę (powiedzmy "piętro 3"), a dostęp do znajdujących się w nim pomieszczeń można uzyskać za pomocą ich indeksu. 15. pokój wzdłuż tego korytarza to 315, a X pokój to 3X. Oznacza to, że możemy użyć zmiennej do indeksowania wektora. Zmiana wartości X może być wykorzystana do odniesienia się do zawartości różnych elementów w wektorze. Notacja stosowana w praktyce oddziela nazwę wektora od jego indeksu nawiasami; piszemy V[6] dla szóstego elementu wektora V i analogicznie V[X] dla elementu V, którego indeksem jest bieżąca wartość zmiennej X. Możemy nawet napisać V[X + 1], który odnosi się do element następujący po V[X] na liście. (Zauważ, że V[X + 1] i V[X] + 1 oznaczają dwie zupełnie różne rzeczy!)

W algorytmie bubblesort możemy na przykład użyć zmiennej X do sterowania pętlą wewnętrzną, a jednocześnie może ona podwoić się jako wskaźnik do wektora V sortowanych elementów. Oto jak może wyglądać wynikowa (bardziej zwięzła, a także bardziej precyzyjna) wersja algorytmu, gdzie "<" oznacza "jest mniejsze niż":


(1) wykonaj następujące N - 1 razy:
(1.1) X ← 1;
(1.2) podczas gdy X < N wykonaj następujące czynności:
(1.2.1) jeśli V[X + 1] < V[X] to je zamień;
(1.2.2) X ← X + 1.

Zachęcamy do zmodyfikowania tego algorytmu, uwzględniając wspomnianą wcześniej obserwację, tak aby przy każdym przejściu pętli zewnętrznej liczbę elementów sprawdzanych w pętli wewnętrznej można było zmniejszyć o 1. Wektory reprezentujące listy elementów mają wiele zastosowań. Książka telefoniczna to lista, podobnie jak słowniki, akta osobowe, opisy inwentarza, wymagania dotyczące kursów i tak dalej. W pewnym sensie wektor jako struktura danych jest ściśle powiązany z pętlą jako strukturą kontrolną. Przechodzenie przez wektor (w celu inspekcji, wyszukiwania, sumowania itp.) jest zwykle wykonywane za pomocą pojedynczej konstrukcji iteracyjnej. Tak jak pętla jest strukturą kontrolną opisującą długie procesy, tak wektor jest strukturą danych do reprezentowania długich list elementów danych. Istnieją również specjalne "indeksowane" wersje iteracyjnych konstrukcji sterujących, dostosowane do przechodzenia przez wektory. Na przykład możemy napisać:

dla X od 1 do 100 wykonaj następujące czynności

który jest podobny do:

wykonaj następujące 100 razy

z tym wyjątkiem, że w przypadku pierwszego możemy odnieść się bezpośrednio do X-tego elementu w wektorze w powtarzającym się segmencie, podczas gdy w przypadku drugiego nie możemy.

Zmienne, czyli małe pudełka

Pierwszymi obiektami zainteresowania są zmienne. Na przykład w algorytmie sumowania wynagrodzeń użyliśmy "zanotowanej liczby", która została najpierw zainicjowana na 0, a następnie użyta do akumulacji sumy wynagrodzeń pracowników. Właściwie używaliśmy zmiennej. Zmienna nie jest liczbą, słowem ani jakimś innym elementem danych. Może być raczej postrzegana jako małe pudełko lub komórka, w której można przechowywać pojedynczy przedmiot. Możemy nadać zmiennej nazwę, powiedzmy X, a następnie użyć instrukcji typu "wstaw 0 w X" lub "zwiększ zawartość X o 1.". Możemy również zadawać pytania dotyczące zawartości X, na przykład "czy X zawiera liczbę parzystą?" Zmienne są bardzo podobne do pokoi hotelowych; różne osoby mogą zajmować pokój w różnym czasie, a osobę znajdującą się w pokoju można określić frazą "mieszkańca pokoju 326". Termin "326" to nazwa pomieszczenia, podobnie jak X to nazwa zmiennej. To użycie słowa "zmienna" do oznaczenia komórki, która może zawierać różne wartości w różnym czasie, jest niepodobne do znaczenia zmiennej w matematyce, gdzie oznacza pojedynczą (zwykle nieznaną) wartość. W Części 3 omówimy paradygmat programowania funkcyjnego, który nie zajmuje się komórkami, ale bezpośrednio wartościami, jak w matematyce. Algorytmy zazwyczaj wykorzystują wiele zmiennych o różnych nazwach i do bardzo różnych celów. Na przykład w algorytmie sortowania bąbelkowego szczegółowa wersja może używać jednej zmiennej do zliczania, ile razy wykonywana jest pętla zewnętrzna, innej dla pętli wewnętrznej i trzeciej, aby pomóc w wymianie dwóch elementów na liście. Aby dokonać wymiany, jeden element jest na chwilę "wkładany do pudełka", drugi na swoje miejsce, a następnie "pudełkowy" element jest umieszczany na pierwotnym miejscu drugiego elementu. Bez użycia zmiennej wydaje się, że nie ma sposobu na zachowanie pierwszego elementu bez jego utraty. Ilustruje to użycie zmiennych jako pamięci lub przechowywania w algorytmie. Oczywiście fakt, że elementy są wymieniane wielokrotnie w jednym przebiegu sortowania bąbelkowego, nie oznacza, że potrzebujemy wielu zmiennych - za każdym razem można użyć tego samego "pudełka". Wynika to z faktu, że wszystkie wymiany w algorytmie sortowania pęcherzyków są rozłączne; żadna wymiana nie rozpoczyna się przed zakończeniem poprzedniej. W ten sposób zmienne można ponownie wykorzystać. Gdy w praktyce używa się zmiennych, wyrażenie "zawartość" jest zwykle pomijane i piszemy takie rzeczy jak X ← 0 (czytaj "X dostaje 0" lub "ustaw X na 0"), aby ustawić początkową wartość (czyli zawartość z) X na 0 i X ← X + 1 (odczytaj "X otrzymuje X + 1"), aby zwiększyć wartość X o 1. Ta ostatnia instrukcja, na przykład, mówi procesorowi, aby "odczytał" liczbę znalezioną w X , zwiększ go o jeden i zastąp go wynikiem.

Typy danych i struktury danych

Wiemy więc, jak wygląda algorytm i jak, biorąc pod uwagę dane wejściowe, procesor wykonuje proces, który opisuje algorytm. Jednak byliśmy dość niejasni co do obiektów manipulowanych przez algorytm. Mieliśmy listy, słowa i teksty, a także zabawne rzeczy, takie jak "zanotowane liczby", które wzrosły i "wskaźniki" które poczyniły postępy. Jeśli chcemy posunąć się do skrajności, możemy również powiedzieć, że mieliśmy mąkę, cukier, ciasta i mus czekoladowy, a także wieże, kołki i krążki. Obiekty te stanowiły nie tylko wejścia i wyjścia algorytmu, ale także akcesoria pośrednie, które zostały skonstruowane i używane w trakcie jego życia, takie jak liczniki ("zanotowane liczby") i wskaźniki. Dla wszystkich z nich używamy ogólnego terminu dane. Elementy danych występują w różnych odmianach lub mogą być różnego rodzaju. Niektóre z najczęstszych typów danych występujących w algorytmach wykonywanych przez komputery to różnego rodzaju liczby (całkowite, dziesiętne, binarne itd.) oraz słowa zapisane w różnych alfabetach. W rzeczywistości liczby mogą być również rozumiane jako słowa; Na przykład liczby całkowite dziesiętne to "słowa" w alfabecie składającym się z cyfr 0, 1, 2, . . . , 9 i liczby binarne używają alfabetu składającego się tylko z 0 i 1. Korzystne jest jednak trzymanie takich typów oddzielnie, nie tylko dla przejrzystości i porządku, ale także dlatego, że każdy typ dopuszcza własny specjalny zestaw dozwolonych operacji lub akcji. Wyliczanie samogłosek w liczbie nie ma większego sensu niż mnożenie dwóch wyrazów! I tak, naszym algorytmom trzeba będzie powiedzieć, jakimi obiektami mogą manipulować i jakie manipulacje są dozwolone. Manipulacja obejmuje nie tylko wykonywanie operacji, ale także zadawanie pytań, np. sprawdzanie, czy liczba jest parzysta lub czy dwa słowa zaczynają się na tę samą literę. Obserwacje te wydają się całkiem naturalne w świetle naszej dyskusji na temat operacji elementarnych w części 1 i emanują faktami dotyczącymi możliwości komputerów do manipulacji bitami. Tutaj przyjmujemy za pewnik podstawowe typy danych oraz operacje i testy z nimi związane. Interesuje nas to, w jaki sposób algorytmy mogą organizować, zapamiętywać, zmieniać i uzyskiwać dostęp do zbiorów danych. Podczas gdy struktury kontrolne służą do informowania procesora, dokąd powinien się udać, struktury danych i operacje na nich organizują elementy danych w sposób, który umożliwia mu robienie tego, co powinien zrobić, gdy się tam dostanie. Świat struktur danych jest tak samo bogaty w poziomy abstrakcji, jak świat struktur kontrolnych. W rzeczywistości przydatna sztuczka mentalna, która jest podstawą paradygmatu programowania obiektowego, pokazuje, że możemy się między nimi przełączać!

Ekspresyjna moc struktur kontrolnych

Czy możemy zrobić tylko z kilkoma prostymi strukturami kontrolnymi? Odpowiedź brzmi tak. Zidentyfikowano różne minimalne zestawy struktur kontrolnych, co oznacza, że w pewnych technicznych aspektach inne struktury kontrolne można zastąpić odpowiednimi kombinacjami tych ze zbioru minimalnego, tak że w praktyce są one jedyne potrzebne. Dobrze znany zestaw minimalny składa się z sekwencjonowania (a następnie), rozgałęzienia warunkowego (jeśli-to) i pewnego rodzaju konstrukcji pętli nieograniczonej (na przykład while-do). Nietrudno np. pokazać, że instrukcję w postaci "powtórz A, aż Q będzie prawdziwe", można zastąpić "zrób A, a potem, gdy Q jest fałszywe, wykonaj A", aby w obecności konstrukcje "podczas działania", które można wykonać bez konstrukcji "powtarzaj aż do". W podobnym duchu możliwe jest całkowite wyeliminowanie stwierdzeń "goto" z dowolnego algorytmu, kosztem jednak pewnego rozszerzenia algorytmu i zmiany jego pierwotnej struktury. Podobnie jest w ścisłym sensie, w którym wszystko, co można zrobić za pomocą podprogramów i rekurencji, można zrobić tylko za pomocą prostych pętli. Wykorzystanie tego wyniku do pozbycia się podprogramów danego algorytmu wiąże się jednak z dodaniem do algorytmu znacznej "maszyny" (w postaci nowych instrukcji elementarnych). Można wykazać, że jeśli taka maszyneria nie jest dozwolona, to podprogramy rekurencyjne są potężniejsze niż iteracja, tak że pewne rzeczy można zrobić tylko za pomocą tych pierwszych. Tematy te zostały tu poruszone tylko w sposób najbardziej powierzchowny, aby dać ci wyczucie istotnych kwestii, które cię interesują.

Rozwiązanie dla wież Hanoi

Przedstawiony tutaj algorytm realizuje zadanie przeniesienia N pierścieni z A do B przez C w następujący sposób. Najpierw sprawdza, czy N wynosi 1, w którym to przypadku po prostu przesuwa jeden pierścień, o który został poproszony, do miejsca docelowego (a dokładniej, wyświetla opis jednego ruchu, który wykona zadanie), i następnie wraca natychmiast. Jeśli N jest większe niż 1, najpierw przesuwa górne N-1 pierścieni z A do "dodatkowego" kołka C przy użyciu tej samej procedury rekurencyjnej; następnie podnosi jedyny pozostały pierścień w A, który musi być największym pierścieniem (dlaczego?) i przenosi go do miejsca docelowego, B; następnie, ponownie rekursywnie, przesuwa pierścienie N-1, które wcześniej "przechowywał" w C do ich ostatecznego miejsca przeznaczenia, B. Że ten algorytm przestrzega reguł gry jest trochę trudny do zauważenia, ale przy założeniu, że dwa procesy związane z pierścieniami N-1 zawierają tylko legalne ruchy, dość łatwo zauważyć, że tak samo jest z całym procesem przemieszczania pierścieni N. Oto algorytm. Jest napisany jako procedura rekurencyjna, której tytuł i parametry (jest ich cztery) mówią same za siebie:

podprogram przesuń N z X na Y za pomocą Z:
(1) jeśli N wynosi 1, to wypisz "przenieś X do Y";
(2) w przeciwnym razie (tj. jeśli N jest większe niż 1) wykonaj następujące czynności:
(2.1) wywołaj przeniesienie N ? 1 z X do Z używając Y ;
(2.2) wyjście "przesuń X do Y";
(2.3) wywołaj przeniesienie N ? 1 z Z do Y za pomocą X;
(3) powrót.

Aby zilustrować działanie tej procedury, która na pierwszy rzut oka może wyglądać dość śmiesznie, moglibyśmy spróbować uruchomić ją, gdy N wynosi 3; czyli symulowanie pracy procesora, gdy są trzy pierścienie. Należy to zrobić wykonując "główny algorytm" składający się z pojedynczej instrukcji: wywołaj ruch 3 z A do B za pomocą C. Symulację należy przeprowadzić ostrożnie, ponieważ nazwy parametrów X, Y i Z zaczynają się dość niewinnie, jako są A, B i C, ale zmieniają się za każdym razem, gdy procesor ponownie wejdzie w procedurę. Jakby, aby było bardziej zagmatwane, wznawiają swoje stare wartości, gdy "rozmowa" się kończy, a procesor wraca do miejsca, z którego pochodzi. Rysunek



pomaga zilustrować kolejność działań w tym przypadku. Zauważ, że procesor (i my też, jeśli rzeczywiście próbujemy symulować procedurę) musi teraz pamiętać nie tylko skąd pochodzi, aby powrócić do właściwego miejsca, ale także jakie wartości nazw parametrów były przed swoje nowe zadanie, aby prawidłowo wznowić pracę. Rysunek jest zorganizowany tak, aby odzwierciedlić głębokość rekurencji i odpowiedni sposób zmiany wartości parametrów. Strzałki reprezentują podróże procesora: strzałki w dół odpowiadają wywołaniom, strzałki w górę do powrotów, a strzałki poziome do prostego sekwencjonowania. Jak za dotknięciem czarodziejskiej różdżki okazuje się, że ostateczna sekwencja działań jest identyczna z tą, do której doszło wcześniej metodą prób i błędów. Jak się okazuje, problem Wież Hanoi dopuszcza inne rozwiązanie algorytmiczne, które wykorzystuje prostą iterację i w ogóle nie wywołuje wywołań podprogramów, i może być wykonane przez małe dziecko!

Rekurencja

Jednym z najbardziej użytecznych aspektów podprogramów, który dla wielu ludzi jest również jednym z najbardziej mylących, jest rekurencja. Rozumiemy przez to po prostu zdolność podprogramu lub procedury do wywołania samej siebie. Może to zabrzmieć absurdalnie, skoro jak, u licha, nasz procesor przybliża się do rozwiązania problemu, gdy w trakcie próby rozwiązania tego problemu mówi się, żeby zostawić wszystko i zacząć rozwiązywać ten sam problem od nowa? Poniższy przykład powinien nam pomóc w rozwiązaniu tego paradoksu i może pomóc, jeśli powiemy na początku, że rozwiązanie opiera się na tej samej właściwości algorytmów, o których mowa wcześniej: ten sam tekst (w tym przypadku podprogram rekurencyjny) może odpowiadać wielu częściom opisanego przez nią procesu. Konstrukcje iteracyjne są jednym ze sposobów mapowania długich procesów na krótkie teksty; podprogramy rekurencyjne to kolejny. Przykład opiera się na dość starożytnej zagadce znanej jako Wieże Hanoi, wywodzącej się od hinduskich kapłanów z wielkiej świątyni Benares. Załóżmy, że otrzymaliśmy trzy wieże, a żeby być bardziej skromnym, trzy kołki, A, B i C. Na pierwszym kołku, A, są trzy pierścienie ułożone w malejącym porządku wielkości, podczas gdy pozostałe są puste. Jesteśmy zainteresowani w przenoszeniu pierścieni z A do B, być może przy użyciu C w procesie. Zgodnie z zasadami gry, pierścienie należy przesuwać pojedynczo i w żadnym momencie nie można umieszczać większego pierścienia na mniejszym. Tę prostą zagadkę można rozwiązać w następujący sposób:

przenieś A do B;
przenieś A do C;
przenieś B do C;
przenieś A do B;
przenieś C do A;
przenieś C do B;
przenieś A do B.

Zanim przejdziemy dalej, powinniśmy najpierw przekonać się, że te siedem akcji naprawdę działa, a następnie powinniśmy wypróbować tę samą łamigłówkę z czterema, a nie trzema pierścieniami na kołku A (liczba kołków się nie zmienia). Umiarkowana ilość pracy powinna wystarczyć, aby odkryć sekwencję 15 akcji "przesuń X na Y", które rozwiązują wersję czteropierścieniową. Takie łamigłówki są intelektualnie trudne, a ci, którzy lubią łamigłówki, mogą chcieć rozważyć oryginalną hinduską wersję, która zawiera te same trzy kołki, ABC, ale z nie mniej niż 64 pierścieniami na A. Jak zobaczymy, wynalazcy układanki nie byli całkowicie oderwali się od rzeczywistości, gdy stwierdzili, że świat skończy się, gdy wszystkie 64 pierścienie zostaną prawidłowo ułożone na kołku B. Jednak nie mamy tutaj do czynienia z zagadkami, ale z algorytmiką, a w konsekwencji bardziej interesuje nas ogólny problem algorytmiczny związany z Wieżami Hanoi niż z tym czy innym konkretnym przypadkiem. Dane wejściowe to dodatnia liczba całkowita N, a pożądanym wynikiem jest lista działań "przenieś X do Y", które, jeśli zostaną wykonane, rozwiązują zagadkę obejmującą N pierścieni. Oczywiście rozwiązaniem tego problemu musi być algorytm, który działa dla każdego N, tworząc listę działań spełniających ograniczenia; w szczególności podążanie za nimi nigdy nie powoduje umieszczenia większego pierścienia na mniejszym. To jest problem, który naprawdę powinniśmy próbować rozwiązać, ponieważ gdy algorytm jest już dostępny, każdą instancję łamigłówki, niezależnie od tego, czy jest to wersja trzy-, cztero- czy 3078-pierścieniowa, można rozwiązać po prostu uruchamiając algorytm z żądaną liczbę dzwonków jako dane wejściowe. Jak to się robi? Odpowiedź jest prosta: dzięki magii rekurencji.

Cnoty podprogramów

Oczywiście podprogramy mogą być bardzo ekonomiczne, jeśli chodzi o rozmiar algorytmu. Nawet w tym prostym przykładzie pętla wyszukiwania jest napisana raz, ale jest używana dwa razy, podczas gdy bez niej algorytm musiałby oczywiście uwzględnić dwie szczegółowe wersje tej pętli. Ta ekonomia staje się znacznie ważniejsza dla złożonych algorytmów z wieloma podprogramami, które są wywoływane z różnych miejsc. Ponadto algorytm może zawierać podprogramy, które wywołują inne podprogramy i tak dalej. W ten sposób struktura algorytmiczna otrzymuje nowy wymiar; istnieją nie tylko zagnieżdżone pętle, ale zagnieżdżone podprogramy. Co więcej, pętle, instrukcje warunkowe, konstrukcje sekwencyjne, instrukcje "goto", a teraz podprogramy, mogą być przeplatane, dając algorytmy o rosnącej złożoności strukturalnej. Ekonomia to jednak nie jedyna zaleta podprogramów. Podprogram może być postrzegany jako "kawał" materiału algorytmicznego, pewnego rodzaju cegiełka, która po utworzeniu może być wykorzystana w innym fragmencie algorytmicznym przez pojedynczą instrukcję. To tak, jakby powiedzieć, że rozszerzyliśmy nasz repertuar dozwolonych instrukcji elementarnych. W przykładzie liczenia "pieniędzy", gdy procedura wyszukiwania jest już dostępna (a nawet wcześniej, o ile zdecydowano, że taka procedura zostanie ostatecznie napisana), instrukcja "call search-for 'abc' " jest dla każdego praktyczny cel, nowa podstawowa instrukcja. Tak więc podprogramy są jednym ze sposobów, w jaki możemy tworzyć własne abstrakcje, zgodnie z konkretnym problemem, który próbujemy rozwiązać. To bardzo potężny pomysł, ponieważ nie tylko skraca algorytmy, ale także czyni je przejrzystymi i dobrze zorganizowanymi. Przejrzystość i struktura, jak wielokrotnie podkreślano, mają ogromne znaczenie w algorytmice i wiele wysiłku poświęca się znalezieniu sposobów narzucenia ich projektantom algorytmów.

W ten sam sposób, w jaki użytkownik programu komputerowego zwykle nie wie nic o algorytmach, których używa, podprogram może być używany jako "czarna skrzynka", nie wiedząc, jak jest zaimplementowany. Wszystko, co użytkownik podprogramu musi wiedzieć, to co robi, ale nie jak to robi. To znacznie upraszcza problem, zmniejszając ilość szczegółów, o których należy pamiętać. Za pomocą podprogramów można stopniowo, krok po kroku, rozwijać złożony algorytm. Typowy problem algorytmiczny wymaga w pełni szczegółowego rozwiązania, które wykorzystuje tylko dozwolone czynności elementarne. Projektant może stopniowo dążyć do tego celu, najpierw opracowując algorytm wysokiego poziomu, który wykorzystuje "podstawowe" instrukcje, których nie ma w książce. W rzeczywistości są to wywołania podprogramów, które projektant ma na myśli, a które zostaną napisane później (lub być może wcześniej). Te podprogramy z kolei mogą korzystać z innych instrukcji, które, nie będąc wystarczająco elementarnymi, są ponownie uważane za wywołania podprogramów, które zostaną ostatecznie napisane. W pewnym momencie wszystkie podstawowe instrukcje są na wystarczająco niskim poziomie, aby znaleźć się wśród tych wyraźnie dozwolonych. Wtedy kończy się stopniowy proces rozwoju. Takie podejście daje początek albo projektowi "z góry na dół", który, jak już opisano, idzie od ogółu do konkretu, albo konstrukcji "od dołu do góry", w której przygotowuje się potrzebne podprogramy, a następnie projektuje bardziej ogólne procedury, które je nazywają, pracując w ten sposób od szczegółowych do ogólnych. Nie ma powszechnej zgody co do tego, które z nich jest lepszym podejściem do projektowania algorytmicznego. Powszechnie uważa się, że należy użyć jakiejś mieszanki. Wracając na chwilę do gastronomii, przygotowanie "mieszanki czekoladowej" może być dobrym kandydatem na podprogram w przepisie na mus czekoladowy z Części 1. To pozwoliłoby nam opisać przepis w następującym sposób, w którym każda z czterech instrukcji jest traktowana jako wywołanie podprogramu (lub raczej podprzepisu), którego tekst byłby następnie napisany osobno: (1) przygotować mieszankę czekoladową; (2) mieszanka do wytworzenia mieszanki czekoladowo-żółtkowej; (3) przygotować piankę z białek jaj; (4) wymieszaj oba, aby uzyskać mus. Warto zaznaczyć, że książka, z której zaczerpnięto przepis na mus, dość obszernie wykorzystuje podprogramy. Na przykład opisujemy szereg przepisów, których składniki zawierają pozycje takie jak Przepis na Słodkie Ciasto, Rogaliki czy Ciasto Francuskie, dla których użytkownik jest odsyłany do wcześniej podanych przepisów dedykowanych tym właśnie produktom. Można śmiało powiedzieć, że nie można przecenić mocy i elastyczności zapewnianych przez podprogramy

Podprogramy lub procedury

Załóżmy, że otrzymujemy obszerny tekst i chcemy dowiedzieć się, jak chciwy jest jego autor, licząc zdania, które zawierają słowo "pieniądze". W takich przypadkach nie interesuje nas liczba wystąpień słowa "pieniądze", ale liczba zdań, w których występuje. Można zaprojektować algorytm, który będzie przechodził przez tekst w poszukiwaniu "pieniędzy". Po znalezieniu takiego zdarzenia biegnie naprzód, szukając końca zdania, które dla naszych celów przyjmuje się jako kropkę, po której następuje spacja; to jest ". " kombinacja. Po znalezieniu końca zdania algorytm dodaje 1 do licznika (czyli "zanotowanej liczby", jak w algorytmie sumowania wynagrodzeń), który został zainicjowany na 0 na początku. Następnie wznawia poszukiwanie "pieniędzy" od początku następnego zdania; to znaczy od litery następującej po kombinacji. Oczywiście algorytm musi cały czas zwracać uwagę na koniec tekstu, aby po jego osiągnięciu mógł wypisać wartość licznika. Algorytm przyjmuje postać zewnętrznej pętli, której zadaniem jest liczenie odpowiednich zdań. W tej pętli znajdują się dwa wyszukiwania, jedno dla "pieniądze", a drugie dla ". ", z których każda sama w sobie stanowi pętlę. Chodzi o to, że dwie wewnętrzne pętle są bardzo podobne; w rzeczywistości obaj robią dokładnie to samo - szukają sekwencji symboli w tekście. Obecność obu pętli w algorytmie wyraźnie działa, ale możemy zrobić to lepiej. Pomysł polega na napisaniu pętli wyszukiwania tylko raz, z parametrem, który z założenia zawiera konkretną kombinację poszukiwanych symboli. Ten segment algorytmiczny nazywa się podprogramem lub procedurą i jest aktywowany (lub wywoływany lub wywoływany) dwukrotnie w głównym algorytmie, raz z parametrem "pieniądze", a raz z ". " kombinacja. Tekst podprogramu jest dostarczany osobno i odnosi się on do zmiennego parametru poprzez nazwę, powiedzmy X. Podprogram zakłada, że wskazujemy jakieś miejsce w tekście wejściowym i może wyglądać następująco: podprogram szukaj X :

(1) wykonaj następujące czynności, aż wskażesz kombinację X lub dotrzesz do końca tekstu:
(1.1) przesunąć wskaźnik o jeden symbol w tekście;
(2) po osiągnięciu końca tekstu wyprowadź wartość licznika i zatrzymaj się;
(3) w przeciwnym razie wróć do głównego algorytmu.

Główna część algorytmu użyje podprogramu wyszukiwania dwukrotnie, za pomocą instrukcji w postaci "wywołaj wyszukiwanie pieniędzy" i "wywołaj wyszukiwanie". Porównaj rysunek 1 z rysunkiem 2, na którym schematycznie pokazano wersję z podprogramem.





Procesor, który działa, będzie teraz musiał być nieco bardziej wyrafinowany. Gdy zostaniesz poproszony o "wywołanie" podprogramu, zatrzyma to, co robił, zapamiętaj, gdzie to było, wybierz parametr(y), że tak powiem, i przejdzie do tekstu podprogramu. Następnie zrobi to, co każe mu podprogram, używając bieżącej wartości parametru, gdziekolwiek podprogram odwołuje się do tego parametru za pomocą swojej wewnętrznej nazwy (w naszym przykładzie X). Jeśli i kiedy podprogram każe mu powrócić, to właśnie to zrobi; mianowicie powróci do punktu następującego po "wezwaniu", które doprowadziło go w pierwszej kolejności do podprogramu, i stamtąd wznowi swoje obowiązki.

Diagramy dla algorytmów

Wizualne, diagramatyczne techniki są jednym ze sposobów przedstawiania przepływu sterowania algorytmem w jasny i czytelny sposób. Istnieją różne sposoby "rysowania" algorytmów, w przeciwieństwie do ich zapisywania. Jednym z najbardziej znanych jest zapisywanie podstawowych instrukcji w prostokątnych pudełkach, a testów w rombowych pudełkach i używanie strzałek do opisania, w jaki sposób procesor Runaround wykonuje algorytm. Powstałe obiekty nazywane są schematami blokowymi. Rysunek 1 przedstawia schemat blokowy zwykłego algorytmu sumowania wynagrodzeń,



a Rysunek 2 przedstawia schemat bardziej wyrafinowanej wersji, która obejmuje tylko pracowników zarabiających więcej niż ich bezpośredni przełożeni.



Zwróć uwagę na sposób, w jaki iteracja przedstawia się wizualnie jako cykl prostokątów, rombów i strzałek, a zagnieżdżone iteracje są wyświetlane jako cykle w cyklach. To wyjaśnia użycie terminu "pętla". Schematy blokowe na rysunkach 2 i 3 ilustrują również stosowność terminu "rozgałęzienie", który był powiązany z instrukcjami warunkowymi. Schematy blokowe mają również wady. Jednym z nich jest fakt, że trudniej jest zachęcić ludzi do przestrzegania niewielkiej liczby "dobrze uformowanych" struktur kontrolnych. Korzystając ze schematów blokowych, łatwo jest ulec pokusie użycia wielu "goto", ponieważ są one przedstawiane po prostu jako strzałki, takie jak te, które reprezentują pętle "while" lub instrukcje warunkowe. Tak więc to nadużywanie medium schematów blokowych spowodowało, że wielu badaczy zaleciło ich stosowanie z ostrożnością. Innym problemem jest fakt, że wiele rodzajów algorytmów po prostu nie nadaje się w naturalny sposób do graficznego, diagramowego odwzorowania oferowanego przez takie jak schematy blokowe. Powstałe artefakty będą często przypominać spaghetti, zmniejszając, a nie zwiększając, zdolność widza do zrozumienia, co naprawdę się dzieje. Niezależnie od powyższej dyskusji, w Części 14 zobaczymy, że istnieją języki diagramowe (nazwiemy je formalizmami wizualnymi), które są bardzo skuteczne, głównie w kontekście określania zachowania dużych i złożonych systemów. Problemem nie jest opisywanie obliczeń, jak robią to algorytmy, ale określenie reaktywnego i interaktywnego zachowania w czasie.

Instrukcja "Goto"

Jest jeszcze inna ważna instrukcja kontrolna, która jest ogólnie nazywana instrukcją goto. Ma ogólną postać "goto G", gdzie G zaznacza jakiś punkt w tekście algorytmu. W naszych przykładach moglibyśmy napisać, powiedzmy, "goto (1.2)", instrukcję, która powoduje, że procesor Runaround dosłownie przechodzi do wiersza (1.2) algorytmu i wznawia wykonywanie od tego miejsca. Konstrukcja ta jest kontrowersyjna z wielu powodów, z których najbardziej oczywisty ma charakter pragmatyczny. Algorytm, który zawiera wiele instrukcji "goto" kierujących sterowanie w tę i z powrotem w splątany sposób, szybko staje się bardzo trudny do zrozumienia. Przejrzystość, jak będziemy argumentować później, jest bardzo ważnym czynnikiem w projektowaniu algorytmicznym. Poza potencjalnym ograniczeniem naszej zdolności do zrozumienia algorytmu, istrukcje "goto" mogą również powodować trudności techniczne. Co się stanie, jeśli instrukcja "goto" skieruje procesor w sam środek pętli? Przykładem tego jest wstawienie instrukcji "goto (1.2.1)" między (1.1) a (1.2) do algorytmu sortowania bąbelkowego. Czy procesor ma wykonać (1.2.1) do (1.2.3), a następnie zatrzymać się, czy też należy wykonać je N-1 razy? Co się stanie, jeśli ta sama instrukcja pojawi się w sekwencji (1.2.1)-(1.2.3)? Problem ten ma swoje źródło w niejednoznaczności wynikającej z próby dopasowania tekstu algorytmu do zaleconego przez niego procesu. Oczywiście istnieje takie dopasowanie, ale ponieważ ustalone algorytmy mogą określać procesy o różnej długości, pojedynczy punkt w tekście algorytmu może być powiązany z wieloma punktami wykonywania odpowiedniego procesu. W związku z tym istrukcje "goto" są w pewnym sensie istotami z natury niejednoznacznymi, a wielu badaczy sprzeciwia się używaniu go swobodnie w algorytmach.

Sortowanie bąbelkowe: Przykład

Aby dokładniej zilustrować struktury kontrolne, przyjrzyjmy się algorytmowi sortowania. Sortowanie to jeden z najciekawszych tematów w algorytmice, z którym wiąże się w ten czy inny sposób wiele ważnych zmian. Dane wejściowe do problemu sortowania to nieuporządkowana lista elementów, powiedzmy liczb. Naszym zadaniem jest stworzenie listy posortowanej w porządku rosnącym. Problem można sformułować bardziej ogólnie, zastępując, powiedzmy, listami słów listy liczbowe, z zamiarem ich posortowania według ich leksykograficznej kolejności (tj. jak w słowniku lub książce telefonicznej). Zakłada się, że lista elementów poprzedzona jest jej długością N, a jedynym sposobem na uzyskanie informacji o wielkości tych elementów polega na wykonaniu porównań binarnych; to znaczy porównywać dwa elementy i działać zgodnie z wynikiem porównania. Jeden z wielu znanych algorytmów sortowania nazywa się sortowaniem bąbelkowym. W rzeczywistości sortowanie bąbelkowe jest uważane za zły algorytm sortowania z powodów wyjaśnionych w Części 6. Jest on tutaj używany tylko do zilustrowania struktur kontrolnych. Algorytm sortowania bąbelkowego opiera się na następującej obserwacji. Jeśli pomieszana lista jest przemierzana po kolei, po jednym elemencie na raz i gdy dwa sąsiednie elementy są w złej kolejności (to znaczy, że pierwszy jest większy niż drugi), są one wymieniane, to po zakończeniu przechodzenia , największy element jest na swoim miejscu; mianowicie na końcu listy. Rysunek (a) ilustruje takie przechodzenie dla prostej pięcioelementowej listy.



(Lista została sporządzona od dołu do góry: pierwszy element jest najniższy na rysunku. Strzałki pokazują tylko wymienione elementy, a nie te, które są porównywane.) Oczywiście, sortowanie może poprawić inne nieprawidłowe kolejności poza umieszczeniem maksymalnego elementu w jego ostateczna pozycja. Jednak rysunek (a) pokazuje, że jedno przejście niekoniecznie sortuje listę. Teraz drugie przejście doprowadzi drugi co do wielkości element do właściwego punktu spoczynku, przedostatniej pozycji na liście, jak widać na rysunku (b). Prowadzi to do algorytmu, który wykonuje N-1 takich przejść (dlaczego nie N?), co daje posortowaną listę. Nazwa "bubblesort" pochodzi od sposobu, w jaki duże elementy "wyskakują" na górę listy w miarę postępu algorytmu, zamieniając miejsca na mniejsze elementy, które są przesuwane niżej. Przed bardziej szczegółowym opisem algorytmu należy zauważyć, że drugie przechodzenie nie musi sięgać do ostatniego elementu, ponieważ w momencie rozpoczęcia drugiego przemierzania ostatnia pozycja na liście zawiera już prawowitego dzierżawcę - największy element na liście. Podobnie, trzecie przejście nie musi iść dalej niż pierwsze N-2 elementy. Oznacza to, że bardziej wydajny algorytm przemierzyłby tylko pierwsze N elementów w pierwszym przejściu, pierwsze N-1 w drugim, N-2 w trzecim itd. Powrócimy do algorytmu sortowania pęcherzyków i to ulepszenie Część 6, ale na razie wystarczy wersja nieulepszona. Algorytm brzmi następująco:

(1) wykonaj następujące N - 1 razy:
(1.1) wskazać na pierwszy element;
(1.2) wykonaj następujące N - 1 razy:
(1.2.1) porównać wskazany element z następnym elementem;
(1.2.2) jeśli porównywane elementy są w złej kolejności, wymienić je;
(1.2.3) wskazuje na następny element.

Zwróć uwagę, jak jest tutaj używane wcięcie dwupoziomowe. Pierwsza "następna", w linii (1), obejmuje wszystkie linie zaczynające się od 1, a druga, w linii (1.2), obejmuje te zaczynające się od 1.2. W ten sposób wyraźnie widać zagnieżdżony charakter konstrukcji pętli. Główne kroki podejmowane przez algorytm na ośmiopunktowej liście są zilustrowane na rysunku 2.2, gdzie sytuacja jest przedstawiona tuż przed każdym wykonaniem punktu (1.2).



Elementy pojawiające się nad linią znajdują się w swoich ostatecznych pozycjach. Zauważ, że w tym konkretnym przykładzie dwa ostatnie przejścia (nie pokazane) są zbędne; lista jest sortowana po pięciu, a nie siedmiu przejściach. Należy jednak zauważyć, że jeśli na przykład najmniejszy element jest ostatnim na oryginalnej liście (czyli na górze na naszych ilustracjach), to w rzeczywistości konieczne są wszystkie przejścia N - 1, ponieważ elementy, które mają być " bulgotać" (elbbubed? …) sprawiają więcej kłopotów niż te, które "bulgotają".

Łączenie struktur kontrolnych

Algorytm może zawierać wiele konstrukcji przepływu sterowania w nietrywialnych kombinacjach. Sekwencjonowanie, rozgałęzianie i iteracje mogą być przeplatane i zagnieżdżane w sobie. Na przykład algorytmy mogą zawierać zagnieżdżone iteracje, częściej nazywane zagnieżdżonymi pętlami. Pętla wewnątrz pętli może przybrać formę "zrób A dokładnie N razy", gdzie samo A jest, powiedzmy, postacią "powtórz B do C". Procesor realizujący taki segment musi dość ciężko pracować; za każdym razem, gdy wykonuje A, za każdym razem, gdy przechodzi pętla zewnętrzna, pętla wewnętrzna musi być przemierzana wielokrotnie, aż C stanie się prawdziwe. Tutaj zewnętrzna pętla jest ograniczona, a wewnętrzna warunkowa, ale możliwe są również inne kombinacje. Część A zewnętrznej pętli może zawierać wiele dalszych segmentów, z których każdy może z kolei wykorzystywać dodatkowe konstrukcje sekwencjonowania, rozgałęziania i iteracji, to samo dotyczy pętli wewnętrznej. Tym samym nie ma ograniczeń co do potencjalnej złożoności algorytmów. Rozważmy prosty przykład potęgi iteracji zagnieżdżonych. Załóżmy, że problemem było zsumowanie wynagrodzeń, ale nie wszystkich pracowników, tylko tych, którzy zarabiają więcej niż ich bezpośredni przełożeni. Oczywiście zakłada się, że (poza prawdziwym "szefem") w kartotece pracownika znajduje się nazwisko przełożonego tego pracownika. Algorytm rozwiązujący ten problem może być skonstruowany tak, aby pętla zewnętrzna przebiegała w dół listy, jak poprzednio, ale dla każdego pracownika "wskazanego" pętla wewnętrzna przeszukuje listę w celu znalezienia rekordu bezpośredniego przełożonego tego pracownika. Po znalezieniu menedżera stosuje się konstrukcję warunkową, aby określić, czy wynagrodzenie pracownika powinno być gromadzone w "zanotowanej liczbie", co wymaga porównania dwóch wynagrodzeń. Po wykonaniu tej "wewnętrznej" czynności pętla zewnętrzna wznawia kontrolę i przechodzi do następnego pracownika, którego menedżer jest następnie poszukiwany, aż do osiągnięcia końca listy.

Struktury kontrolne

Sterowanie sekwencją jest zwykle realizowane za pomocą różnych kombinacji instrukcji zwanych strukturami przepływu sterowania lub po prostu strukturami sterowania. Nawet przepis na mus czekoladowy zawiera kilka typowych, takich jak:

•  Sekwencjonowanie bezpośrednie, w formie "zrób A, a potem B" lub "zrób A, a potem B". (Każdy średnik lub kropka w przepisie kryje w sobie frazę "a potem", na przykład "delikatnie złóż czekoladę; [a następnie] lekko podgrzej…")

•  Rozgałęzienie warunkowe w postaci "jeśli Q, to zrób A, w przeciwnym razie wykonaj B" lub po prostu "jeśli Q, to zrób A", gdzie Q jest pewnym warunkiem. (Na przykład w przepisie "w razie potrzeby lekko podgrzej, aby rozpuścić czekoladę" lub "w razie potrzeby podawaj z bitą śmietaną").

Tak się składa, że te dwie konstrukcje sterujące, sekwencjonowanie i rozgałęzianie, nie wyjaśniają, w jaki sposób algorytm o stałej - może nawet krótkiej - długości może opisywać procesy, które mogą rosnąć coraz dłużej, w zależności od konkretnego wejścia. Algorytm zawierający tylko sekwencjonowanie i rozgałęzianie może zalecić procesy tylko o pewnej ograniczonej długości, ponieważ żadna część takiego algorytmu nie jest nigdy wykonywana więcej niż raz. Konstrukty sterujące, które są odpowiedzialne za przepisywanie coraz dłuższych procesów, są rzeczywiście ukryte nawet w przepisie na mus, ale są znacznie bardziej wyraźne w algorytmach, które radzą sobie z wieloma danymi wejściowymi o różnych rozmiarach, takimi jak algorytm sumowania wynagrodzeń. Są one ogólnie nazywane iteracjami lub konstrukcjami zapętlonymi i występują w wielu odmianach. Oto dwa:

•  Ograniczona iteracja w formie ogólnej "zrób A dokładnie N razy", gdzie N jest liczbą.
•  Iteracja warunkowa, czasami nazywana iteracją nieograniczoną, w postaci "powtórz A do Q" lub "gdy Q do A", gdzie Q jest warunkiem. (Na przykład w przepisie "ubijaj białka do uzyskania piany").

Opisując algorytm sumowania wynagrodzeń dość nieprecyzyjnie podchodziliśmy do sposobu realizacji głównej części algorytmu; powiedzieliśmy "przejdź przez listę, dodając pensję każdego pracownika do zanotowanej liczby", a następnie "po osiągnięciu końca listy wygeneruj odnotowany numer jako wynik". Powinniśmy naprawdę użyć konstrukcji iteracyjnej, która nie tylko precyzuje zadanie procesora przechodzącego przez listę, ale także sygnalizuje koniec listy. Załóżmy zatem, że dane wejściowe do problemu obejmują nie tylko listę pracowników, ale także jej długość; to jest całkowita liczba pracowników, oznaczona literą N. Teraz można użyć ograniczonej konstrukcji iteracyjnej, dając następujący algorytm:

(1) zanotuj 0; aby wskazać pierwszą pensję na liście;
(2) wykonaj następujące N - 1 razy:
     (2.1) dodać wskazaną pensję do zaznaczonego numeru;
     (2.2) wskazać następną pensję;
(3) dodać wskazaną pensję do zaznaczonego numeru;
(4) wygeneruj odnotowaną liczbę jako dane wyjściowe.

Wyrażenie "następujące" w punkcie (2) odnosi się do segmentu składającego się z podrozdziałów (2.1) i (2.2). Ta konwencja, w połączeniu z wcięciem tekstu, aby podkreślić "zagnieżdżony" charakter (2.1) i (2.2), będzie swobodnie używana w sequelu. Zachęcamy do szukania powodu używania N - 1 i dodawania końcowej pensji oddzielnie, zamiast po prostu używać N, a następnie tworzyć wyniki i zatrzymywać się. Zauważ, że algorytm zawodzi, jeśli lista jest pusta (to znaczy, jeśli N wynosi 0), ponieważ druga część klauzuli (1) nie ma sensu. Jeśli dane wejściowe nie zawierają N, całkowitej liczby pracowników, musimy użyć warunkowej iteracji, która wymaga od nas podania sposobu, w jaki algorytm może wykryć, kiedy dotarł do końca listy. Wynikowy algorytm wyglądałby bardzo podobnie do podanej wersji, ale używałby formy "powtórz następujące do osiągnięcia końca listy" w klauzuli (2). Powinieneś spróbować spisać pełny algorytm dla tego przypadku. Zwróć uwagę, jak konstrukcje iteracyjne umożliwiają krótkiej części tekstu algorytmu przypisanie bardzo długich procesów, których długość jest podyktowana wielkością danych wejściowych - w tym przypadku długością listy pracowników. Iteracja jest zatem kluczem do pozornego paradoksu jednego, ustalonego algorytmu wykonującego zadania o coraz dłuższym czasie trwania.

Wiemy już, że algorytmy zawierają starannie dobrane instrukcje elementarne, które określają podstawowe czynności do wykonania. Nie omawialiśmy jeszcze rozmieszczenia tych instrukcji w algorytmie, który umożliwia człowiekowi lub komputerowi ustalenie dokładnej kolejności czynności, które należy wykonać. Nie omawialiśmy też przedmiotów, którymi manipulują te działania. Algorytm może być traktowany jako wykonywany przez małego robota lub procesor (który może być odpowiednio nazwany Runaround). Procesor otrzymuje rozkazy biegania dookoła robiąc to i tamto, gdzie "to i tamto" są podstawowymi działaniami algorytmu. W algorytmie sumowania wynagrodzeń z poprzedniej części, małemu Runaroundowi kazano zanotować 0, a następnie zacząć przeglądać listę pracowników, znajdować pensje i dodawać je do zanotowanej liczby. Powinno być dość oczywiste, że kolejność wykonywania podstawowych czynności jest kluczowa. Niezwykle ważne jest nie tylko to, aby podstawowe instrukcje algorytmu były jasne i jednoznaczne, ale to samo powinno dotyczyć mechanizmu sterującego kolejnością wykonywania tych instrukcji. Algorytm musi zatem zawierać instrukcje sterujące, aby "pchać" procesor w tym lub innym kierunku, mówiąc mu, co ma robić na każdym kroku i kiedy przestać i powiedzieć "jestem jednym".

Wstęp i przegląd historyczny, czyli o co w tym wszystkim chodzi?

Komputery to niesamowite maszyny. Wydają się być w stanie zrobić wszystko. Latają samolotami i statkami kosmicznymi, kontrolują elektrownie i niebezpieczne zakłady chemiczne. Firmy nie mogą już działać bez nich, a coraz więcej skomplikowanych procedur medycznych nie może być wykonywanych pod ich nieobecność. Służą prawnikom i sędziom, którzy szukają precedensów sądowych w dziesiątkach udokumentowanych procesów, a także pomagają naukowcom w wykonywaniu niezwykle skomplikowanych i wymagających obliczeń matematycznych. Przekierowują i kontrolują miliony połączeń telefonicznych w sieciach obejmujących kontynenty. Wykonują zadania z niezwykłą precyzją - od czytania map i składu po graficzną obróbkę obrazu i projektowanie układów scalonych. . Mogą odciążyć nas od wielu nudnych obowiązków, takich jak skrupulatne śledzenie wydatków domowych, a jednocześnie zapewnić nam urozmaiconą rozrywkę, np. gry komputerowe lub skomputeryzowana muzyka. Co więcej, dzisiejsze komputery ciężko pracują, pomagając zaprojektować jeszcze potężniejsze komputery jutra. Tym bardziej niezwykłe jest to, że komputer cyfrowy - nawet ten najnowocześniejszy i najbardziej skomplikowany - może być traktowany jako po prostu duża kolekcja przełączników. Te przełączniki lub bity, jak się je nazywa, nie są "odwracane" przez użytkownika, ale są specjalnymi, wewnętrznymi przełącznikami, które są "odwracane" przez sam komputer. Każdy bit może znajdować się w jednej z dwóch pozycji lub, inaczej mówiąc, może przyjmować jedną z dwóch wartości, 0 lub 1. Zazwyczaj wartość bitu jest określona przez pewną charakterystykę elektroniczną, na przykład, czy dany punkt ma ładunek dodatni lub ujemny. Komputer może bezpośrednio wykonać tylko niewielką liczbę niezwykle trywialnych operacji, takich jak odwracanie, zerowanie lub testowanie. Odwracanie zmienia wartość bitu, zerowanie zapewnia, że bit kończy się na pozycji 0, a testowanie robi jedną rzecz, jeśli bit jest już na pozycji 0, a drugą, jeśli tak nie jest.



Komputery mogą różnić się wielkością (zgodnie z liczbą dostępnych bitów), rodzajami podstawowych operacji, które mogą wykonywać, szybkością wykonywania tych operacji, fizycznym nośnikiem zawierającym bity i ich wewnętrzną organizacją, oraz znacząco, w ich otoczeniu zewnętrznym. Ta ostatnia pozycja oznacza, że dwa komputery, które poza tym mają podobne funkcje, mogą wydawać się obserwatorowi bardzo różne: jeden może przypominać telewizor z klawiaturą, a drugi może być schowany pod pokrętłami i pokrętłami automatycznej dziewiarki. Jednak wygląd zewnętrzny ma znaczenie peryferyjne w porównaniu z bitami i ich wewnętrznym rozmieszczeniem. To właśnie bity "wyczuwają" zewnętrzne bodźce przychodzące ze świata zewnętrznego za pomocą przycisków, dźwigni, klawiszy na klawiaturze, elektronicznych linii komunikacyjnych, a nawet mikrofonów i kamer. To właśnie bity "decydują" o tym, jak reagować na te bodźce i odpowiednio reagować, kierując inne bodźce na zewnątrz za pomocą wyświetlaczy, ekranów, drukarek, głośników, brzęczyków, dźwigni i korb. Jak robią to komputery? Co takiego przekształca tak trywialne operacje na bitach w niewiarygodne wyczyny, jakich dokonują komputery? Odpowiedź tkwi w głównych pojęciach : procesie i algorytmie, który go określa i powoduje, że ma miejsce.

Trochę gastronomii

Wyobraź sobie kuchnię, zawierającą zapas składników, szereg przyborów do pieczenia, piekarnik i (człowieka) piekarza. Pieczenie pysznego ciasta rodzynkowego to proces, który ze składników przeprowadza piekarz za pomocą piekarnika, a przede wszystkim zgodnie z przepisem. Składniki są danymi wejściowymi do procesu, ciasto jest jego wyjściem, a przepis jest algorytmem. Innymi słowy, algorytm określa czynności, które składają się na proces. Receptury lub algorytmy odnoszące się do zestawu omawianych procesów są ogólnie nazywane oprogramowaniem, podczas gdy przybory i piekarnik reprezentują to, co ogólnie nazywa się sprzętem. Piekarz w tym przypadku można uznać za część sprzętu.



Podobnie jak w przypadku operacji bitowych, konstelacja piekarz/piekarnik/przybory ma bardzo ograniczone możliwości bezpośrednie. Ten sprzęt do pieczenia ciast może nalewać, mieszać, rozsmarowywać, kapać, rozpalać piekarnik, otwierać drzwi piekarnika, mierzyć czas lub mierzyć ilości, ale nie może bezpośrednio piec ciast. To przepisy - te magiczne recepty, które zamieniają ograniczone możliwości sprzętu kuchennego w ciasta - a nie piekarniki czy piekarnie, są tematem tego tekstu. Przepisy, jak już wspomniano, nazywane są tutaj algorytmami, podczas gdy dziedzina badań nad ludźmi, wiedzy i ekspertyzy, która dotyczy algorytmów, będzie nazywana algorytmiką. Narysowana tu analogia została wykonana możliwie jak najdokładniej: przepis, który jest w pewnym sensie bytem abstrakcyjnym, jest algorytmem; formalna pisemna wersja przepisu, taka jak ta znaleziona w książce kucharskiej, jest analogiczna do programu komputerowego. Oprogramowanie w rzeczywistości odnosi się bardziej do programów - precyzyjnych reprezentacji algorytmów napisanych w specjalnych językach odczytywanych przez komputer - niż do samych algorytmów. Jednak dopóki nie omówimy języków programowania, to rozróżnienie jest dość nieistotne. Konfrontujemy algorytmy, gdziekolwiek się udamy. Wiele codziennych procesów rządzi się algorytmami: wymiana przebitej opony, budowanie szafki zrób to sam, robienie na drutach swetra, dzielenie liczb, sprawdzanie numeru telefonu, aktualizowanie listy wydatków czy wypełnianie deklaracji podatkowej. Niektóre z nich (na przykład podział) mogą być w naszych umysłach bardziej bezpośrednio powiązane z komputerami, niż inne (na przykład budowa szaf), ale tutaj nas to dotyczy mniej. Chociaż komputery mają fundamentalne znaczenie dla tematu, w ogóle nie będziemy koncentrować się na ich fizycznych aspektach. To właśnie ich duchem zajmujemy się; z przepisami, które sprawiają, że działają zgodnie z ich algorytmami.

Algorytmika a informatyka

Algorytmika to coś więcej niż dziedzina informatyki. Jest to rdzeń informatyki i, uczciwie, można powiedzieć, że ma znaczenie dla większości nauki, biznesu i technologii. Sama natura algorytmiki sprawia, że jest ona szczególnie przydatna w tych dyscyplinach, które czerpią korzyści z wykorzystania komputerów, a te szybko stają się przytłaczającą większością. Wiadomo, że ludzie pytają: "Czym naprawdę jest informatyka? Dlaczego nie mamy nauki o łodziach podwodnych, nauki o zmywarkach ani nauki o telefonach?" Można argumentować, że telefony i zmywarki są tak samo ważne dla współczesnego życia jak komputery; może bardziej. Nieco bardziej skoncentrowanym pytaniem jest, czy informatyka obejmuje takie klasyczne dyscypliny, jak matematyka, fizyka, neurologia, elektrotechnika, językoznawstwo, logika i filozofia. My nie próbujemy odpowiedzieć na te pytania. Mamy jednak nadzieję, że domyślnie przekażemy coś z wyjątkowości i uniwersalności algorytmiki, a co za tym idzie, coś z wagi informatyki jako autonomicznej, choć młodej, dziedziny studiów. Ponieważ komputery mogłyby ograniczać ogólność algorytmiki, niektórzy uważają nieunikniony związek między nimi za niefortunny. W rzeczywistości określenie dziedziny "informatyka", jak powiedział ktoś kiedyś, jest jak odnoszenie się do chirurgii jako "nauki o nożach". Tak czy inaczej, jasne jest, że algorytmika nigdy nie rozwinęłaby się w taki sposób, jak bez tego łącza. Jednak ogólnie przyjmuje się, że termin "informatyka" jest mylący i że coś takiego jak "informatyka", "nauka o procesach" lub "nauka dyskretna" może być lepsze. Ponownie twierdzimy tylko, że nasza tematyka, algorytmika, stanowi podstawę informatyki, a nie ją zastępuje. Niektóre z tematów, które poruszamy w sequelu, takie jak istnienie problemów, których komputery nie mogą rozwiązać, mają implikacje filozoficzne, nie tylko na granicach wspaniałych maszyn, które jesteśmy w stanie zbudować, ale także na naszych własnych granicach jako śmiertelników o skończonej masie i skończonej żywotności. Pomimo głębokiej natury takich implikacji, w tej książce nacisk kładzie się na bardziej pragmatyczny cel, jakim jest zdobycie dogłębnego zrozumienia podstaw procesów wykonywanych maszynowo oraz receptur lub algorytmów, które nimi rządzą.

Trochę historii

Przyjrzyjmy się teraz kilku ważnym kamieniom milowym w rozwoju komputerów i informatyki, głównie po to, aby zilustrować, że jako uporządkowana dyscyplina naukowa jest to niezwykle młoda dziedzina. Gdzieś pomiędzy 400 a 300 rokiem p.n.e. wielki grecki matematyk Euklides wynalazł algorytm znajdowania największego wspólnego dzielnika (nwd) dwóch dodatnich liczb całkowitych. gcd X i Y jest największą liczbą całkowitą, która dokładnie dzieli X i Y . Na przykład gcd 80 i 32 wynosi 16. Szczegóły samego algorytmu nie mają tutaj znaczenia, ale algorytm Euklidesa, jak się go nazywa, jest uważany za pierwszy nietrywialny algorytm, jaki kiedykolwiek opracowano. Słowo algorytm wywodzi się od nazwiska perskiego matematyka Mohammeda al-Chuarizmi, który żył w IX wieku i któremu przypisuje się dostarczanie szczegółowych zasad dodawania, odejmowania, mnożenia i dzielenia zwykłych liczb dziesiętnych. Napisana po łacinie nazwa przekształciła się w Algorismus, od którego algorytm jest tylko małym krokiem. Najwyraźniej Euklides i al-Chuarizmi byli algorytmistami par excellence. Przechodząc od oprogramowania do sprzętu, jedną z pierwszych maszyn, które przeprowadzały proces kontrolowany przez coś, co można by nazwać algorytmem, było krosno tkackie wynalezione w 1801 roku przez Francuza Josepha Jacquarda. Utkany wzór wyznaczały karty z dziurkami w różnych miejscach. Otwory te, wyczuwane przez specjalny mechanizm, sterowały doborem nici i innymi czynnościami maszyny. Interesujące jest to, że krosno Jacquard nie miało nic wspólnego z wąską konotacją numeryczną terminu "obliczenia". Jedną z najważniejszych i najbardziej barwnych postaci w historii informatyki był Charles Babbage. Ten angielski matematyk, po częściowym zbudowaniu w 1833 r. maszyny zwanej "silnikiem różnicowym" do oceny pewnych wzorów matematycznych, wymyślił i zaplanował niezwykłą maszynę, którą nazwał "silnikiem analitycznym". W przeciwieństwie do silnika różnicowego, który został zaprojektowany do realizacji określonego zadania, silnik analityczny miał być zdolny do wykonywania algorytmów lub programów, zakodowanych przez użytkownika jako dziurki w kartach. Gdyby skonstruowano silnik analityczny, byłby to matematyczny odpowiednik krosna Jacquarda, które w rzeczywistości było jego inspiracją. Nie trzeba dodawać, że maszyna Babbage'a była z natury mechaniczna, oparta na dźwigniach, zębatkach i przekładniach, a nie na elektronice i krzemie. Niemniej idee obecne w jego projekcie silnika analitycznego stanowią podstawę wewnętrznej struktury i działania współczesnych komputerów. Powszechnie uważa się, że Babbage żył na długo przed swoim czasem, a jego pomysły nie zostały docenione znacznie później. Ada Byron, hrabina Lovelace, była programistką Babbage'a. Jest jedną z najciekawszych postaci w historii informatyki, której przypisuje się położenie podwalin pod programowanie ponad sto lat przed pojawieniem się pierwszego działającego komputera. Amerykański inżynier Herman Hollerith wynalazł maszynę, również opartą na kartach dziurkowanych, która została wykorzystana przez Amerykańskie Biuro Spisu Ludności (American Census Bureau) do spisu ludności z 1890 roku. Jednak pierwsze komputery ogólnego przeznaczenia zbudowano dopiero w latach 40. XX wieku, częściowo jako odpowiedź na potrzeby obliczeniowe fizyków i astronomów, a częściowo jako naturalny wynik dostępności odpowiednich urządzeń elektromechanicznych i elektronicznych. Jak na ironię, pomogła też druga wojna światowa, z jej działalnością polegającą na budowaniu bomb i łamaniu kodów. Niektóre z kluczowych postaci w tym przełomowym i ekscytującym okresie to Anglik Alan Turing, Amerykanie Howard Aiken, John Mauchly, J. Presper Eckert i Herman Goldstine oraz słynny niemiecko-amerykański matematyk John von Neumann. Wracając do oprogramowania i algorytmiki, połowa lat 30. była świadkiem jednych z najbardziej fundamentalnych prac nad teorią algorytmów, przynoszących wyniki dotyczące możliwości i ograniczeń algorytmów wykonywanych maszynowo. Godne uwagi jest to, że praca ta, której fragmenty zostaną opisane w dalszej części , poprzedzała rzeczywistą materializację komputera. Niemniej jednak ma uniwersalne i trwałe znaczenie. Niektóre z kluczowych postaci, wszyscy matematycy, to znowu Alan Turing, Niemiec Kurt G?del, Rosjanin Andrjej A. Markov i Amerykanie Alonzo Church, Emil Post i Stephen Kleene. Lata pięćdziesiąte i sześćdziesiąte były świadkami daleko idących i szybkich postępów technologicznych w projektowaniu i budowie komputerów. Można to przypisać z jednej strony nadejściem ery badań jądrowych i eksploracji kosmosu, a z drugiej boomowi dużych firm i banków oraz zróżnicowanej działalności rządowej. Precyzyjne przewidywanie różnych zjawisk jądrowych wymagało bardzo dużej mocy obliczeniowej, podobnie jak planowanie i symulacja misji kosmicznych. Eksploracja kosmosu wymagała również postępów w komunikacji wspomaganej komputerowo, ułatwiającej niezawodną analizę i filtrowanie, a nawet ulepszanie danych przesyłanych do i z satelitów i statków kosmicznych. Działalność biznesowa, bankowa i rządowa wymagała komputerów, które pomagałyby w przechowywaniu, manipulowaniu i wyszukiwaniu informacji dotyczących bardzo dużej liczby osób, pozycji inwentarzowych, danych fiskalnych i tak dalej. Interesujące dowody na znaczenie rozwoju technologicznego zorientowanego na maszyny w tym okresie można znaleźć w nazwach największej na świecie firmy komputerowej, IBM, i jednej z największych na świecie profesjonalnych organizacji związanych z komputerami, ACM. Pierwsza powstała około 1920 r., druga pod koniec lat 40. XX wieku. W obu przypadkach "M" pochodzi od słowa "machine": International Business Machines i Association for Computing Machinery. (IBM wyewoluował z firmy utworzonej w 1896 r. przez wspomnianego Hermana Holleritha, aby produkować jego maszyny do tabulacji). Uznanie informatyki jako niezależnej dyscypliny akademickiej nastąpiło w połowie lat 60., kiedy kilka uniwersytetów utworzyło wydziały informatyki. W 1968 roku ACM opublikowała cieszącą się szerokim uznaniem rekomendację dotyczącą programu nauczania przedmiotów z informatyki, która stanowi podstawę większości aktualnych programów studiów z zakresu informatyki na poziomie licencjackim. Ten program jest okresowo aktualizowany. Dziś prawie każda instytucja akademicka posiada wydział informatyki lub grupę informatyczną w ramach wydziału matematyki lub elektrotechniki. Lata 60. pokazały ponowne zainteresowanie pracami z lat 30. nad algorytmiką i od tego czasu ta dziedzina jest przedmiotem szeroko zakrojonych i dalekosiężnych badań. Nie będziemy się więcej rozwodzić nad obecną sytuacją technologiczną: komputery są po prostu wszędzie. Używamy ich do surfowania po Internecie, co oznacza, że używamy ich do odbierania i dostarczania informacji, czytania, słuchania i oglądania oraz oczywiście przeglądania i kupowania. Istnieją komputery stacjonarne, laptopy i komputery wielkości dłoni, więc nigdy nie musimy ich bez nich obejść, a szybko zmniejszająca się przepaść między telefonami komórkowymi a komputerami zwiastuje erę komputerów do noszenia. Prawie każde nowoczesne urządzenie jest sterowane przez komputer, a na przykład jeden nowoczesny samochód zawiera ich dziesiątki. Dzieci proszą o komputery osobiste na urodziny i otrzymują je; studenci informatyki na większości uczelni muszą posiadać własne komputery do odrabiania prac domowych; i nie ma działalności przemysłowej, naukowej czy handlowej, która nie jest w sposób zasadniczy wspomagana przez komputery.

Dziwna dychotomia

Pomimo tego wszystkiego (lub prawdopodobnie w wyniku tego) opinia publiczna jest dziwnie podzielona, jeśli chodzi o umiejętność obsługi komputera. Wciąż są tacy, którzy nie wiedzą absolutnie nic o komputerach, a także członkowie stale rosnącej klasy informatyków. Poczynając od 10-letnich właścicieli komputerów osobistych, ta powiększająca się grupa osób korzystających na co dzień z komputerów obejmuje menedżerów, inżynierów, bankierów, techników i oczywiście profesjonalnych programistów, analityków systemowych i członków samego przemysłu komputerowego. Dlaczego to dziwne? Otóż, oto nauka, o której niektórzy ludzie nic nie wiedzą, ale o której szybko rosnąca liczba ludzi najwyraźniej wie wszystko! Tak się jednak składa, że naprawdę niezwykłym zjawiskiem jest to, że duże i ważne części informatyki nie są wystarczająco znane nie tylko członkom pierwszej grupy, ale także członkom drugiej grupy. Jednym z celów jest próba naświetlenia ważnego aspektu rewolucji komputerowej poprzez przedstawienie podstawowych pojęć, wyników i trendów leżących u podstaw nauki o obliczeniach. Skierowany jest zarówno do nowicjusza, jak i eksperta. Czytelnik bez wiedzy o komputerach (miejmy nadzieję) dowie się tutaj o ich "duchu" i sposobie myślenia, który zmusza ich do pracy, szukając gdzie indziej materiałów dotyczących ich "ciała". Czytelnik znający się na komputerach, który może uznać, że pierwsze kilka rozdziałów jest raczej powolne, (mamy nadzieję) będzie mógł się wiele nauczyć od późniejszych.

Niektóre ograniczenia komputerów

Zanim rozpoczniemy naszą trasę, skontrastujmy pierwszy akapit tej części z niektórymi wyczynami, których obecne komputery nie są jeszcze w stanie wykonać. Powrócimy do tych kontrastów w ostatniej części, który dotyczy relacji między komputerami a ludzką inteligencją. Obecnie komputery są w stanie przeanalizować na miejscu ogromną ilość danych pochodzących z wielu zdjęć rentgenowskich mózgu pacjenta, zrobionych pod stopniowo rosnącymi kątami. Analizowane dane są następnie wykorzystywane przez komputer do wygenerowania przekrojowego obrazu mózgu, dostarczającego informacji o strukturze tkanek mózgu, umożliwiając w ten sposób precyzyjne zlokalizowanie takich nieprawidłowości jak guzy czy nadmiar płynów. W przeciwieństwie do tego, żaden obecnie dostępny komputer nie jest w stanie przeanalizować pojedynczego, zwykłego obrazu twarzy tego samego pacjenta i określić jego wieku z marginesem błędu, powiedzmy, wynoszącym pięć lat. Jednak większość 12-letnich dzieci może! Jeszcze bardziej uderzająca jest zdolność rocznego dziecka do rozpoznawania twarzy matki na zdjęciu, którego nigdy wcześniej nie widziała, wyczyn, którego komputery nie są w stanie naśladować (i to nie tylko dlatego, że nie mają matek...) . Komputery są w stanie sterować w najbardziej precyzyjny i efektywny sposób, jaki można sobie wyobrazić, niezwykle wyrafinowanymi robotami przemysłowymi używanymi do konstruowania skomplikowanych części maszyn składających się z setek komponentów. W przeciwieństwie do tego, dzisiejsze najbardziej zaawansowane komputery nie są w stanie pokierować robotem, aby skonstruował ptasie gniazdo ze stosu gałązek, czego może dokonać każdy 12-miesięczny ptak! Dzisiejsze komputery potrafią grać w szachy na poziomie międzynarodowego arcymistrza, a tym samym mogą pokonać ogromną większość ludzkich graczy. Jednak przy bardzo nieznacznej zmianie zasad gry (na przykład poprzez umożliwienie skoczkowi dwóch ruchów naraz lub ograniczenie ruchów hetmana do pięciu pól), najlepsze z tych komputerów nie będą w stanie się przystosować bez przeprogramowania. lub zrekonstruowane przez ludzi. W przeciwieństwie do tego, 12-letni szachista amator będzie w stanie rozegrać całkiem dobrą partię z nowymi zasadami w bardzo krótkim czasie, a wraz z doświadczeniem stanie się coraz lepszy. Jak wspomniano, te różnice są związane z różnicą między inteligencją ludzką a skomputeryzowaną. Będziemy w lepszej pozycji do dalszego omówienia tych kwestii w rozdziale 15, po tym, jak dowiemy się więcej o algorytmach i ich właściwościach.

Przepis

Oto przepis na mus czekoladowy zaczerpnięty z francuskiej kuchni Sinclaira i Malinowskiego. Składniki - to znaczy wkłady - obejmują 8 uncji półsłodkich kawałków czekolady, 2 łyżki wody, 14 filiżanek cukru pudru, 6 oddzielnych jajek i tak dalej. Daje od sześciu do ośmiu porcji pysznego musu z czekoladą. Oto przepis lub algorytm. Rozpuść czekoladę i 2 łyżki wody w podwójnym bojlerze. Po roztopieniu dodaj cukier puder; dodawać po trochu masło. Odłożyć na bok. Ubijaj żółtka do gęstej i cytrynowej barwy, około 5 minut. Delikatnie zawinąć w czekoladę. W razie potrzeby lekko podgrzej, aby rozpuścić czekoladę. Dodaj rum i wanilię. Białka ubić do uzyskania piany. Ubij 2 łyżki cukru; ubijaj, aż uformują się sztywne szczyty. Delikatnie złóż białka w mieszankę czekoladowo-żółtkową. Wlać do poszczególnych porcji dań. Schłodź co najmniej 4 godziny. W razie potrzeby podawać z bitą śmietaną. Robi od 6 do 8 porcji. Jest to "oprogramowanie" związane z przygotowaniem musu; jest to algorytm, który kontroluje proces wytwarzania musu ze składników. Sam proces jest wykonywany przez "sprzęt", w tym przypadku osobę przygotowującą mus, wraz z różnymi przyborami: podwójnym bojlerem, urządzeniem grzewczym, trzepaczką, łyżkami, minutnikiem i tak dalej.

Poziomy szczegółowości

Przyjrzyjmy się bliżej najbardziej elementarnym instrukcjom zawartym w tym przepisie. Rozważ instrukcję "domieszaj cukier puder". Dlaczego przepis nie mówi "weź trochę cukru pudru, wlej go do roztopionej czekolady, wmieszaj, weź trochę więcej, wlej, wymieszaj, . . .? A dokładniej, dlaczego nie jest napisane "weź 2365 ziaren cukru pudru, wlej je do roztopionej czekolady, weź łyżkę i mieszaj okrężnymi ruchami, . . .? Lub, by być jeszcze bardziej precyzyjnym, dlaczego nie "przesunąć ręką w kierunku składników pod kątem 14?, z przybliżoną prędkością 18 cali na sekundę,…?" Odpowiedź jest oczywiście oczywista. Sprzęt wie, jak wymieszać cukier puder z rozpuszczoną czekoladą i nie wymaga dalszych szczegółów. A co powiesz na odwrócenie sprawy i pytanie, czy to możliwe, że sprzęt wie, jak przygotować mieszankę czekolady z cukrem i masłem? W takim przypadku całą pierwszą część przepisu można by zastąpić prostą instrukcją "przygotuj mieszankę czekoladową". Doprowadzając to do skrajności, może sprzęt wie, jak przygotować mus czekoladowy. Umożliwiłoby to zastąpienie całego przepisu "przygotuj mus czekoladowy". Przy takim poziomie wiedzy o sprzęcie, pojedyncza linijka instrukcji jest idealnym przepisem na uzyskanie musu z czekolady; ten krótki przepis jest jasny, nie zawiera błędów i gwarantuje uzyskanie pożądanych wyników. Takie eksperymenty myślowe jasno pokazują, że poziom szczegółowości jest bardzo ważny, jeśli chodzi o podstawowe instrukcje algorytmu. Musi być dostosowany do konkretnych możliwości sprzętu, a także powinien być dostosowany do poziomu zrozumienia potencjalnego czytelnika lub użytkownika algorytmu. Rozważmy inny przykład poznany na początku naszego życia, który jest nieco bliższy obliczeniom - uporządkowane mnożenie liczb. Załóżmy, że zostaniemy poproszeni o pomnożenie 528 przez 46. Dokładnie wiemy, co robić. Pomnożymy 8 przez 6, otrzymując 48, zapisujemy cyfrę jednostki wyniku 8 i pamiętamy cyfrę dziesiątek 4; następnie mnożymy 2 przez 6 i dodajemy 4, otrzymując 16; zapisujemy cyfrę jednostek 6 po lewej stronie 8 i pamiętamy cyfrę dziesiątek 1; i tak dalej. Tutaj można zadać te same pytania. Dlaczego "mnożyć 8 przez 6?" Dlaczego nie "sprawdzić wpisu znajdującego się w ósmym wierszu i szóstej kolumnie tabliczki mnożenia" lub "dodać 6 do siebie 8 razy"? Podobnie, dlaczego nie możemy rozwiązać całego problemu za jednym pociągnięciem za pomocą prostego i satysfakcjonującego algorytmu "pomnóż dwie liczby?" To ostatnie pytanie jest dość subtelne: dlaczego możemy bezpośrednio pomnożyć 8 przez 6, ale nie 528 przez 46? Ponownie, jasne jest, że poziom szczegółowości jest kluczową cechą naszej akceptacji algorytmu mnożenia. Zakładamy, że odpowiedni sprzęt (w tym przypadku my sami) jest w stanie wykonać 8 razy 6, ale nie 528 razy 46, i że możemy to zrobić w naszych głowach, a przynajmniej znamy jakiś inny sposób, aby nie trzeba było nam mówić, jak sprawdzić wynik w tabeli. Te przykłady pokazują potrzebę uzgodnienia na samym początku podstawowych działań, które algorytm uważa za zdolny do przepisania. Bez tego nie ma sensu szukać algorytmów do czegokolwiek. Co więcej, różne problemy są naturalnie związane z różnymi rodzajami podstawowych działań. Przepisy wymagają mieszania, mieszania, nalewania i podgrzewania; mnożenie liczb pociąga za sobą dodawanie, mnożenie cyfr i, co ważne, zapamiętywanie cyfry; wyszukanie numeru telefonu może wymagać odwrócenia strony, przesunięcia palcem w dół listy i porównania podanego nazwiska z tym, na które wskazujemy. W precyzyjnych rodzajach algorytmów, które będziemy omawiać, te podstawowe instrukcje muszą być sformułowane jasno i precyzyjnie. Nie możemy zaakceptować rzeczy takich jak "ubijanie białek do uzyskania piany", ponieważ wyobrażenie jednej osoby na pianę może być zupełnie niepodobne do innej! Instrukcje muszą być odpowiednio odróżnialne od nieinstrukcyjnych, takich jak "robi 6 do 8 porcji". Zwroty rozmyte, takie jak "około 5 minut", nie mają miejsca w algorytmie przystosowanym do wykonywania przez komputer, jak ma to miejsce w przypadku niejasności, takich jak "podawaj z bitą śmietaną, jeśli chcesz". (Czy to faktyczna porcja, czy dodanie bitej śmietany, zależy od pragnień danej osoby?) Przepisy na mus, w przeciwieństwie do algorytmów, które będą nas interesować, zbyt wiele rzeczy uznają za oczywiste, z których najważniejsza czyli fakt, że człowiek jest częścią sprzętu. Nie możemy polegać na tego rodzaju luksusie, dlatego musimy być znacznie bardziej wymagający. Ogólna jakość algorytmu zależy przede wszystkim od wyboru dozwolonych działań podstawowych i ich adekwatności do danej sprawy.

Abstrakcja

Wcześniej stwierdzono, że prawdziwe komputery mogą wykonywać tylko niezwykle proste operacje na niezwykle prostych obiektach. Może się to wydawać sprzeczne z obecną dyskusją, w której zaleca się projektowanie różnych algorytmów przy użyciu podstawowych działań o różnym poziomie szczegółowości. Jednak analogia jest nadal aktualna. Uczniowi szefa kuchni może być konieczne podanie przepisu na mus czekoladowy, ale po kilku latach przygotowania musu wystarczy instrukcja "przygotuj mus czekoladowy". Mówimy, że pojęcia takie jak "mus czekoladowy", "beza cytrynowa" i "krem bawarski" są na wyższym poziomie abstrakcji niż operacje takie jak "mieszanie", "mieszanie" i "przelewanie" stosowane w przepisach na ich przygotowanie. W ten sam sposób, dzięki odpowiedniemu programowaniu, komputer może rozpoznawać abstrakcje wyższego poziomu, takie jak liczby, tekst i obrazy. Podobnie jak w gotowaniu, w komputerze istnieje wiele poziomów abstrakcji, z których każdy jest odpowiedni do opisywania różnych rodzajów algorytmów. Na przykład ten sam komputer jest postrzegany inaczej przez 12-latka grającego w grę komputerową, przez jego siostrę, która surfuje po Internecie, przez ojca, który używa arkusza kalkulacyjnego do obliczania ocen uczniów, a przez matkę. kto pisze program zarządzania testem skuteczności nowej szczepionki. Żadne z nich nie zna ani nawet nie dba o bity, które naprawdę składają się na proces obliczeniowy, którego używają. Ten proces abstrahowania od szczegółów w celu dostrzeżenia wspólnych wzorców w pozostałej części jest sednem prawie każdego ludzkiego przedsięwzięcia. Na przykład czytanie książki ma wpływ na mózg, który składa się z kilku odrębnych regionów, z których każdy składa się z neuronów i innych komórek. Komórki te zbudowane są ze złożonych cząsteczek, które zbudowane są z atomów, które z kolei zbudowane są z bardziej elementarnych cząstek. Wszystkie te różne poziomy abstrakcji odnoszą się do tego, co dzieje się w twoim mózgu, ale nie można ich wszystkich rozpatrywać łącznie. W rzeczywistości należą one do różnych dziedzin nauki: fizyki cząstek elementarnych, chemii, biologii molekularnej, neurobiologii i psychologii. Psycholog przeprowadzający eksperymenty z krótkotrwałą retencją pamięci będzie rozpraszany tylko przez myślenie o związkach między atomami i cząsteczkami w mózgu. To samo dotyczy informatyki. Gdybyśmy byli zmuszeni do myślenia na poziomie bitowym przez cały czas, komputer nie byłby przydatny. Zamiast tego możemy na przykład pomyśleć o grupie bitów (zwykle osiem bitów lub "bajt") jako oznaczającej znak. Możemy teraz rozważyć sekwencje bajtów do oznaczania słów angielskich, sekwencje słów i znaki interpunkcyjne do oznaczania zdań itd. do akapitów, rozdziałów i książek. Dla każdego z tych poziomów istnieją algorytmy. Na przykład sprawdzanie pisowni dotyczy słów, ale nie znaków, justowanie do lewej dotyczy akapitów, a tworzenie spisu treści dotyczy książek. W każdym przypadku możemy opisać algorytm, całkowicie ignorując fragmenty składające się na słowa, akapity lub całe książki. W miarę rozwoju, będziemy omawiać środki techniczne, które pozwalają nam tworzyć takie abstrakcje. Tymczasem opiszemy każdy algorytm na odpowiednim dla niego poziomie abstrakcji.

Krótkie algorytmy dla długich procesów

Załóżmy, że otrzymujemy listę akt personalnych, po jednym dla każdego pracownika w określonej firmie, z których każda zawiera imię i nazwisko pracownika, dane osobowe oraz wynagrodzenie. Interesuje nas łączna suma wszystkich wynagrodzeń wszystkich pracowników. Oto algorytm wykonania tego zadania:

(1) zanotuj cyfrę 0;
(2) przejdź przez listę, dodając wynagrodzenie każdego pracownika do zanotowanej liczby;
(3) po dojściu do końca listy, wygeneruj odnotowaną liczbę jako wynik.

Zanim przejdziemy dalej, powinniśmy najpierw przekonać się, że ten prosty algorytm spełnia swoje zadanie. "Zanotowana" liczba, którą można uznać za zapamiętaną lub zapisaną na kartce papieru, zaczyna się od wartości zero. Po dokonaniu doliczenia w ust. 2 dla pierwszego pracownika, liczba ta faktycznie przyjmuje wartość wynagrodzenia tego pracownika. Po drugim pracowniku jego wartość jest sumą wynagrodzeń pierwszych dwóch pracowników. Ostatecznie jego wartość jest wyraźnie sumą wszystkich wynagrodzeń.



Interesujące jest to, że tekst tego algorytmu jest krótki i ma stałą długość, ale proces, który opisuje i kontroluje, zmienia się wraz z długością listy pracowników i może być bardzo, bardzo długi. Dwie firmy, pierwsza z jednym pracownikiem, a druga z milionem, mogą wprowadzić swoją listę pracowników do tego samego algorytmu, a problem sumowania wynagrodzeń zostanie rozwiązany dla każdej z nich równie dobrze. Oczywiście w przypadku pierwszej firmy proces ten nie potrwa długo, natomiast w przypadku drugiej będzie to dość długi czas. Algorytm jest jednak ustalony. Nie tylko tekst algorytmu jest krótki i ma stałą wielkość, ale zarówno mała jak i duża firma potrzebuje tylko jednej zanotowanej liczby, aby wykonać zadanie, dzięki czemu ilość "przyborów" jest tutaj również mała i stała. Oczywiście potencjalna wartość podanej liczby będzie prawdopodobnie musiała być większa dla większych firm, ale cały czas będzie tylko jedna liczba

Problem algorytmiczny

I tak mamy ustalony algorytm określający wiele procesów o różnej długości, dokładny czas trwania i charakter procesu w zależności od danych wejściowych do algorytmu. Rzeczywiście, nawet prosty przykład sumowania wynagrodzeń pokazuje różne możliwe dane wejściowe: firmy jednoosobowe, firmy liczące milion osób, firmy, w których część pensji wynosi zero lub te, w których wszystkie pensje są równe. Czasami algorytm musi również działać z dziwacznymi danymi wejściowymi, takimi jak firmy bez pracowników lub takie, które zatrudniają ludzi otrzymujących ujemne pensje (czyli pracowników, którzy płacą firmie za przyjemność pracy dla niej). W rzeczywistości algorytm wynagrodzeń powinien działać zadowalająco dla nieskończonej liczby wejść. Istnieje nieskończona liczba całkowicie akceptowalnych list pracowników, a algorytm powinien być w stanie zsumować pensje w dowolnej z nich, gdy zostanie podany jako dane wejściowe. Ta kwestia nieskończenie wielu potencjalnych danych wejściowych nie do końca pasuje do analogii przepisu, ponieważ chociaż przepis powinien działać doskonale bez względu na to, ile razy jest używany, jego składniki są zwykle opisywane jako ustalone w ilości, a zatem w istocie przepis ma tylko jeden potencjalny wkład (przynajmniej w ilościach; oczywiście cząsteczki i atomy będą za każdym razem inne). Jednak przepis na mus czekoladowy mógł być ogólny; to znaczy, jego lista składników mogła brzmieć coś w stylu "X uncji kawałków czekolady, X/4 łyżek wody, X/32 filiżanki cukru pudru itp.", a jego ostatnia linia mogła brzmieć "sprawia, że 3X/4 do X porcji." Byłoby to bardziej zgodne z prawdziwym pojęciem algorytmu. W obecnej formie przepis jest algorytmem o nieco banalnym charakterze, ponieważ jest dostosowany do jednego konkretnego zestawu składników. Może być przeprowadzana (lub, w terminologii algorytmicznej, może być uruchamiana lub wykonywana) kilka razy, ale z zasadniczo tymi samymi danymi wejściowymi, ponieważ jedna filiżanka mąki jest uważana za dokładnie taką samą jak każda inna. Same dane wejściowe muszą być zgodne z przeznaczeniem algorytmu. Oznacza to na przykład, że lista bestsellerów New York Times nie byłaby akceptowana jako dane wejściowe do algorytmu sumowania wynagrodzeń, podobnie jak masło orzechowe i galaretka nie byłyby akceptowane jako składniki przepisu na mus. Pociąga to za sobą pewien rodzaj specyfikacji dozwolonych wejść. Ktoś musi dokładnie określić, które listy pracowników są legalne, a które nie; gdzie dokładnie na liście znajduje się wynagrodzenie; czy jest podana odręcznie (na przykład 32 000 USD), czy może w jakiejś skróconej formie (na przykład 32 000 USD); gdzie kończy się rekord pracownika, a zaczyna kolejny i tak dalej. Mówiąc najogólniej, przepisy lub algorytmy są rozwiązaniami na pewno rodzaje problemów, zwanych problemami obliczeniowymi lub algorytmicznymi. W przykładzie płacowym problem można sprecyzować w postaci prośby o numer reprezentujący sumę wynagrodzeń z listy pracowników organizacji. Lista ta może mieć różną długość, ale musi być ułożona w określony sposób. Problem taki można postrzegać jako poszukiwanie zawartości "czarnej skrzynki", która jest określona przez precyzyjną definicję legalnych danych wejściowych i precyzyjną definicję wymaganych wyników jako funkcji tych danych wejściowych; czyli sposób, w jaki każde wyjście zależy od wejścia.



Problem algorytmiczny został rozwiązany po znalezieniu odpowiedniego algorytmu. Czarna skrzynka została wtedy faktycznie zaopatrzona w zawartość; to "działa" zgodnie z tym algorytmem. Innymi słowy, czarna skrzynka może wytworzyć odpowiednie dane wyjściowe z dowolnego legalnego wkładu, wykonując proces, który jest określony i zarządzany przez ten algorytm. Słowo "dowolny" w poprzednim zdaniu jest bardzo ważne. Nie interesują nas rozwiązania, które nie działają dla wszystkich podanych wejść. Łatwo jest znaleźć rozwiązanie, które działa dobrze tylko w przypadku niektórych legalnych danych wejściowych. Jako skrajny przykład trywialny algorytm:

(1) wyprodukuj 0 jako wyjście.

bardzo dobrze sprawdza się w przypadku kilku interesujących list pracowników: tych bez pracowników, tych, w których każdy zarabia 0,00 zł (lub ich wielokrotności), a także tych z listą płac, która odzwierciedla idealną równowagę między pensją dodatnią a ujemną. Później zajmiemy się takimi zagadnieniami, jak wydajność i praktyczność algorytmów. Tutaj stawiamy minimalny wymóg, że algorytm faktycznie rozwiązuje problem, nawet jeśli może to zrobić nieefektywnie. Oczywiście sam problem może określać wymagane zachowanie potencjalnego algorytmu na niepożądanych danych wejściowych, ale wtedy te dane wejściowe, chociaż niepożądane, są nadal legalne. Na przykład problem sumowania wynagrodzeń mógłby zawierać wymóg, aby w przypadku pracownika, którego rekord nie zawierał numeru w obszarze wynagrodzeń, ale powiedzmy znak zapytania lub inne bezsensowne dane, algorytm powinien dodać nazwisko tego pracownika do specjalnej listy, która zostanie przekazana do biura płac do dalszych działań. Taka niekonwencjonalna lista pracowników jest jednak legalna; po prostu nie jest traktowana w standardowy sposób, ale jest traktowana w specjalny sposób, który pasuje do jego nienormalnej natury. W związku z tym trzymanie nielegalnych danych wejściowych oddzielnie jest odpowiedzialnością problemu algorytmicznego, podczas gdy traktowanie specjalnych klas nietypowych lub niepożądanych danych wejściowych jest odpowiedzialnością samego algorytmu.

Granice podstawowych działań

Jest jeszcze jedna ważna sprawa, którą musimy się w tym miejscu poruszyć, dotycząca wykonania podstawowych czynności lub operacji, zaleconych przez algorytm. Oczywistym jest, że każda z tych czynności musi być wykonana w skończonym czasie, inaczej oczywiście algorytm nigdy się nie skończy. Tak więc nieskończenie długie działania są złe. Działania, które mogą zająć nieskończenie małą ilość czasu, są również zakazane, co nie wymaga uzasadnienia. Jest nie do pomyślenia, aby maszyna kiedykolwiek była w stanie wykonywać czynności w coraz krótszym czasie. Na przykład prędkość światła zawsze byłaby ograniczeniem prędkości każdej maszyny. Podobne ograniczenia zasobów (czyli narzędzi) wykorzystywanych do wykonywania podstawowych czynności również muszą być narzucone, ale nie będziemy tu omawiać przyczyn. Jasne jest, że te założenia dotyczące podstawowych działań rzeczywiście obowiązują w przypadku prawdziwych komputerów. Na przykład podstawowe akcje manipulacji bitami są precyzyjne i jednoznaczne oraz zajmują ograniczoną ilość czasu i zasobów. Tak więc, zgodnie z obietnicą, opisana tu teoria algorytmiki będzie miała bezpośrednie zastosowanie do problemów przeznaczonych do rozwiązania komputerowego.

Problem i jego rozwiązanie: podsumowanie

Podsumowując, problem algorytmiczny składa się z:

1. scharakteryzowanego legalnego, możliwie nieskończonego zbioru potencjalnych zbiorów wejściowych, oraz
2. specyfikację pożądanych wyjść jako funkcję wejść.

Zakłada się, że z góry podany jest również opis dozwolonych akcji podstawowych lub konfiguracja sprzętowa wraz z jej wbudowanymi akcjami podstawowymi. Rozwiązaniem problemu algorytmicznego jest algorytm składający się z elementarnych instrukcji zalecających działania z uzgodnionego zbioru. Algorytm ten, gdy jest wykonywany dla dowolnego dozwolonego zestawu danych wejściowych, rozwiązuje problem, wytwarzając wymagane dane wyjściowe.

Ważne jest, aby rozpoznać znaczne trudności związane z zadowalającym rozwiązywaniem problemów algorytmicznych. Zaczynając od przepisu na mus, a następnie podając prosty algorytm sumowania, popełniono pewną niesprawiedliwość, ponieważ mogłoby się wydawać, że sprawy są łatwe. Nic nie jest dalsze od prawdy. W praktyce problemy algorytmiczne mogą być niezwykle złożone, a ich pomyślne rozwiązanie może zająć lata pracy. Co gorsza, jak zobaczymy dalej, wiele problemów nie daje zadowalających rozwiązań, podczas gdy inne w ogóle nie dopuszczają żadnych rozwiązań. W przypadku wielu problemów status, jeśli chodzi o dobre rozwiązania algorytmiczne, jest jeszcze nieznany, mimo intensywnej pracy wielu utalentowanych ludzi. Oczywiście nie będziemy w stanie zilustrować zagadnień poruszanych tu zbyt obszernymi i złożonymi przykładami, ale możemy wyczuć trudność w projektowaniu algorytmów, myśląc o następujących (nieformalnie opisanych) problemach algorytmicznych. W pierwszym zadaniu dane wejściowe to legalna pozycja w szachach (czyli opis sytuacji osiągniętej w pewnym momencie podczas partii szachów), podczas gdy dane wyjściowe to najlepszy ruch dla białych (czyli opis ruchu, który maksymalizuje szanse białych na wygranie meczu). Drugi problem dotyczy dystrybucji gazet. Załóżmy, że 20 000 gazet ma zostać rozprowadzonych do 1000 lokalizacji w 100 miastach przy użyciu 50 ciężarówek. Dane wejściowe zawierają odległości drogowe między miastami i lokalizacjami w każdym mieście, liczbę dokumentów wymaganych w każdej lokalizacji, obecną lokalizację każdej ciężarówki, zdolność każdej ciężarówki do przewozu gazet, a także pojemność benzyny i przebieg -wydajność galonów i szczegóły dotyczące dostępnych kierowców, w tym ich aktualne miejsce pobytu. Wynikiem ma być lista, dopasowująca kierowców do ciężarówek i zawierająca szczegółowe trasy dla każdej z ciężarówek, aby zminimalizować całkowitą liczbę przejechanych mil. W rzeczywistości problem wymaga algorytmu, który działa dla dowolnej liczby gazet, lokalizacji, miast i ciężarówek, tak aby ich liczba również się różniła i stanowiła część danych wejściowych. Zanim będziemy mogli omówić kwestie poprawności i skuteczności, czy też głębsze pytania dotyczące natury lub samego istnienia rozwiązań pewnych problemów algorytmicznych, musimy dowiedzieć się więcej o budowie algorytmów i strukturze obiektów, którymi manipulują.

• Kluczowe Idee
• Przed startem …
• Podstawowe Zachowania
• Badania Użytkowników
• Granice naszych umysłów
• Architektura informacji
• Projektowanie zachowań
• Zasady projektowania wizualnego
• Szkielety i prototypy
• Psychologia użyteczności
• Treść
• Moment Prawdy
• Dane dla projektantów
• Znajdź pracę, ty brudny hipisie

Po przestudiowaniu Części X powinieneś być w stanie:

•  Wyjaśnić podstawy reagowania na katastrofy.
•  Opisać proces reagowania na włamania w przypadku poważnych incydentów.
•  Opisać względy prawne.
•  Wyjaśnić konieczność tworzenia kopii zapasowych.
•  Opisać funkcje i rodzaje systemów wykrywania włamań (IDS).
•  Wyjaśnić znaczenie edukacji, certyfikacji i świadomości.
•  Opisać planowanie ciągłości działania.
•  Wymienić zalety centrów danych.
•  Poznać proces odzyskiwania po awarii IT.

Po przestudiowaniu Części IX powinieneś być w stanie:

•  Wyjaśnić konieczność tworzenia kopii zapasowej.
•  Opisać zakres i metody tworzenia kopii zapasowych.
•  Opisać różne poziomy RAID (nadmiarowa tablica niezależnych dysków).
•  Wyjaśnićpotrzebę zasad przechowywania danych.
•  Wyjaśnić zabezpieczenia bazy danych.
•  Wyjaśnić potrzebę kontroli dostępu do bazy danych, audytu i szyfrowania.
•  Opisać różnicę między wyciekiem danych a kradzieżą danych.
•  Wyjaśnić usuwanie, niszczenie i usuwanie danych.
•  Wyjaśnić zarządzanie prawami cyfrowymi (DRM) i sposób, w jaki może zapobiegać utracie danych

Po przestudiowaniu Części VIII powinieneś być w stanie:

•  Wyjaśnić, dlaczego atakujący coraz częściej skupiają się na aplikacjach.
•  Wymienić główne kroki w zabezpieczaniu aplikacji.
•  Dowiedzieć się, jak zabezpieczyć serwisy WWW i usługi e-commerce.
•  Opisać luki w przeglądarkach internetowych.
•  Wyjaśnić proces zabezpieczania poczty e-mail.
•  Wyjaśnić, jak zabezpieczyć Voice over IP (VoIP).
•  Opisać zagrożenia związane z usługą Skype VoIP.
•  Opisać, jak zabezpieczyć inne aplikacje użytkownika.
•  Dowiedzieć się, jak zabezpieczyć aplikacje nadzorcze TCP/IP.

Po przestudiowaniu Części VII powinieneś być w stanie:

• Zdefiniować elementy hartowania hosta, podstawy bezpieczeństwa i obrazy oraz administrację systemami.
•  Poznać ważne systemy operacyjne serwerów.
•  Opisać luki w zabezpieczeniach i poprawki.
•  Wyjaśnić jak zarządzać użytkownikami i grupami.
•  Wyjaśnić, jak zarządzać uprawnieniami.
• Poznać zabezpieczenia komputerów klienckich z systemem Windows, w tym scentralizowane zarządzanie bezpieczeństwem komputerów.
•  Wyjaśnić, jak tworzyć silne hasła.
•  Opisać, jak testować pod kątem luk w zabezpieczeniach.

Po przestudiowaniu Części VI powinieneś być w stanie:

•  Ogólnie zdefiniować firewalle (podstawowe działanie, architektura, problem przeciążenia).
•  Opisać, jak działa statyczne filtrowanie pakietów.
•  Wyjaśnić stanową inspekcję pakietów (SPI) dla głównych zapór granicznych.
•  Opisać, jak działa translacja adresów sieciowych (NAT).
•  Wyjaśnić zapory proxy aplikacji i filtrowanie treści w zaporach SPI.
•  Rozróżnić systemy wykrywania włamań (IDS) i systemy zapobiegania włamaniom (IPS).
•  Opisać filtrowanie antywirusowe.
•  Zdefiniować architektury zapory.
•  Opisać zarządzanie firewallem (definiowanie polityk, wdrażanie polityk, odczytywanie plików dziennika).
•  Opisać niektóre trudne problemy związane z zaporami ogniowymi

Po przestudiowaniu Części V powinieneś być w stanie:

•  Zdefiniować podstawową terminologię kontroli dostępu.
•  Opisać budynek fizyczny i zabezpieczenia komputerowe.
•  Wyjaśnić hasła wielokrotnego użytku.
•  Wyjaśnić, jak działają karty dostępu i tokeny.
•  Opisać uwierzytelnianie biometryczne, w tym weryfikację i identyfikację.
•  Wyjaśnić uprawnienia.
•  Wyjaśnić audyt.
•  Opisać, jak działają centralne serwery uwierzytelniania.
•  Opisać, jak działają serwery katalogowe.
•  Zdefiniować pełne zarządzanie tożsamością

Po przestudiowaniu Części IV powinieneś być w stanie:

•  Opisać cele tworzenia bezpiecznych sieci.
• Wyjaśnić, jak działają ataki typu "odmowa usługi".
• Wyjaśnić, jak działa zatrucie ARP.
• Dowiedzieć się, dlaczego kontrola dostępu jest ważna dla sieci.
• Wyjaśnić, jak zabezpieczyć sieci Ethernet.
• Opisać standardy bezpieczeństwa sieci bezprzewodowej (WLAN).
• Opisać potencjalne ataki na sieci bezprzewodowe.

Po przestudiowaniu Części III powinieneś być w stanie:

•  Wyjaśnić pojęcie kryptografii.
•  Opisać szyfrowanie kluczem symetrycznym i znaczenie długości klucza.
•  Wyjaśnić etap negocjacji.
•  Wyjaśnić wstępne uwierzytelnianie, w tym MS-CHAP.
•  Opisać kluczowanie, w tym szyfrowanie kluczem publicznym.
•  Wyjaśnić, jak działają podpisy elektroniczne, w tym podpisy cyfrowe, certyfikaty cyfrowe i kody uwierzytelniania wiadomości z haszowanym kluczem (HMAC).
•  Opisać szyfrowanie kluczem publicznym do uwierzytelniania.
•  Opisać bezpieczeństwo kwantowe.
•  Wyjaśnić systemy kryptograficzne, w tym VPN, SSL i IPsec.

Po przestudiowaniu Części II powinieneś być w stanie:

•  Uzasadnić potrzebę formalnych procesów zarządzania.
•  Wyjaśnić cykl zarządzania bezpieczeństwem planuj, chroń i zareaguj.
•  Opisać przepisy i regulacje dotyczące zgodności.
•  Opisać kwestie bezpieczeństwa organizacji.
•  Opisać analizę ryzyka.
•  Opisać techniczną infrastrukturę bezpieczeństwa.
•  Wyjaśnić implementację sterowaną polityką.
•  Poznać ramy zarządzania.

Po przestudiowaniu Części I powinieneś być w stanie:

•  Zdefiniować termin środowisko zagrożenia.
•  Używać podstawowej terminologii bezpieczeństwa.
•  Opisać zagrożenia ze strony pracowników i byłych pracowników.
•  Opisać zagrożenia ze strony twórców złośliwego oprogramowania.
•  Opisać tradycyjnych zewnętrznych hakerów i ich ataki, w tym procesy włamań, socjotechnikę, i ataki typu "odmowa usługi".
•  Wiedzieć, że przestępcy stali się dziś dominującymi napastnikami, opisz rodzaje ataków, których dokonują, i omówić ich metody współpracy.
•  Rozróżniać cyberwojnę od cyberterroryzmu.

IV Rewolucja Przemysłowa

"Czwarta rewolucja przemysłowa : uogólniająca koncepcja odnosząca się do pojęcia "rewolucji przemysłowej" w związku ze współczesnym wzajemnym wykorzystywaniem automatyzacji, przetwarzania i wymiany danych oraz technik wytwórczych."  (Wikipedia)