Programowanie/Algorytmy/NS

Schematy Nassi Schneidermana (Schematy NS)

Schematy NS służą do zapisu algorytmów strukturalnych. Nadają się do projektowania algorytmów na kartkach papieru, ponieważ pozwalają łatwo dekomponować zadania programistyczne.

Przepływ wykonywania algorytmu następuje z góry na dół. Każda instrukcja jest zapisywana jako prostokąt. Najpierw cała kartka papieru jest jedną instrukcją, którą należy zdekomponować (rozłożyć na mniejsze podzadania). Każde podzadanie jest także konstrukcją strukturalną opisaną przy okazji języka IPL.

Należy pamiętać o starannym opisywaniu kartek, aby nie powstał bałagan. Na górze powinien być nagłówek opisujący schemat, na końcu zaś sekwencja: kreska-kropka-kreska (kod Morse'a litery K), oznaczająca koniec schematu.

kompozycja sekwencyjna w schematach Nassi Schneidermanna

Kompozycja sekwencyjna w schematach NS polega na umieszczeniu czynności późniejszych pod wcześniejszymi. Wykonywanie czynności odbywa się z góry na dół. Pojedyncza Instrukcja NS w formie prostokąta może być podzielona na sekwencję czynności prostszych poprzez podzielenie jej poziomymi kreskami. Zostało to zilustrowane rysunkiem poniżej.

Początkowo zadanie mogło obejmować napisanie całego programu (Użytkownik chce mieć program podlewania kwiatka). W tym celu projektant dokonuje dekompozycji na czynności prostsze. W rezultacie otrzymaliśmy zdekomponowany schemat. Przykład umieszczono poniżej.

kompozycja warunkowa w schematach Nassi Schneidermanna

Kompozycja warunkowa (alternatywa) polega na określeniu prawdziwości warunku i wykonania jednego z dwóch zadań. Na schematach NS jest to zobrazowane poprzez umieszczenie na górze klatki opisu warunku, natomiast na dole są dwia węższe podzadania, z których jedno zostanie wykonane.

Zadanie może być puste (program w danym przypadku nic nie robi). Oznaczane jest ono ukośnym przekreśleniem klatki. Szerokość podzadań może być dopasowana do przewidywanego rozmiaru na papierze.

Jeżeli podzadania nie mieszczą się na kartce, wówczas zamiast ich treści umieszcza się adres etykiety (np. E1) i podzadania pisze na oddzielnej kartce o nazwie opisanej tą etykietą. Pozwala to rozpisywać większe algorytmy na mniejsze podzadania (dekompozycję).

wybór wielokrotny w schematach Nassi Schneidermanna

Wybór wielokrotny jest rozwinięciem kompozycji warunkowej (zamiast warunku mogącego przyjmować dwie wartości możemy wybierać spośród wielu opcji). W rzeczywistych językach programowania jest realizowane jako zagnieżdżenie zwykłych kompozycji warunkowych (nie przyspieszy to obliczeń). Wybór wielokrotny pozwala czasami na lepsze zapisanie wyboru, kiedy jest więcej możliwości wyboru.

Przykładowa kompozycja wyboru wielokrotnego (z angielskiej Wikipedii) została przedstawiona poniżej. Zaproponowano także inne sposoby zapisu wyboru wielokrotnego.

kompozycja iteracyjna w schematach Nassi Schneidermanna

Diagramy Nassi Schneidermanna pozwalają na zapis pętli. Poniżej pokazano kompozycję algorytmiczną typu dopóki - dopóty. Wykonanie przebiega z góry na dół. Na początku następuje sprawdzenie prawdziwości warunku. Dopóki warunek jest prawdziwy, dopóki następuje wykonanie refrenu i ponowne sprawdzenie warunku. Refren może być dalej dekomponowany (rozkładany na instrukcje prostsze). Także Obliczanie warunku może być wykonywane w oddzielnym zadaniu.

Zauważmy, że jeżeli warunek będzie zawsze prawdziwy, wówczas pętla nie będzie mogła zostać zakończona. Bardzo ważną rzeczą jest zatem konieczność zapewnienia zakończenia działania pętli w skończonym czasie. Warunek musi w końcu przestać zwracać prawdę.

Rzeczywiste pętle zwykle są zwykle poprzedzone instrukcjami wstępnymi, które przygotowują dane do przetwarzania w pętli.

Inną ważną sprawą jest określenie sytuacji po zakończeniu wykonywania pętli. Można to opisywać komentarzem // Teraz już......

Poniżej pokazano pętlę słodzącą herbatę. Najpierw przygotowujemy się do słodzenia herbaty. Aby sprawdzić warunek, konieczne jest sprawdzenie smaku herbaty. Następnie przechodzimy do warunku. Dopóki herbata nie jest słodka, dopóty wykonuj refren. Refren polega na posłodzeniu herbaty i sprawdzeniu jej smaku w celu określenia prawdziwości warunku. Na końcu można powiedzieć, że herbata już jest słodka.

kompozycja równoległa w Schematach Nassi Schnedermanna

Schematy Nassi Schnerdermanna pozwalają wykonać wiele zadań równolegle. Wykonanie następuje również góry na dół.

Implementacja jest zależna od konkretnego narzędzia programistycznego pozwalającego programować równolegle. Obecnie wiele języków programowania pozwala na to.

Języki C i C++ w nowych standardach mają wsparcie dla tych funkcjonalności (wykorzystuje się też bibliotekę POSIX threads (pthreads) lub dodatek OpenMP). W kartach graficznych GPGPU możliwe jest równoległe uruchomienie dużej liczby prostych zadań (technologie CUDA, OpenCL), wymagają one jednak np. uprzedniego skopiowania danych do karty graficznej i jej zwrócenia po wykonaniu obliczeń.

Należy pamiętać, że aby kompozycja równoległa się zakończyła, konieczne jest zakończenie wszystkich jej podzadań.

Poniżej pokazano wykonanie równoległe czterech instrukcji.

literatura

Schematy NS zostały także opisane na angielskiej Wikipedii (Nassi Schneideman Diagram)