Ma 13 stron. Porusza takie kwestie jak: budowa algorytmów, konstrukcja algorytmu sortowania bąbelkowego, schemat blokowy, rekurencja, typy danych, statyczne i dynamiczne struktury danych, typy list, drzewo binarne, kompilacja, interpretacja, metody algorytmiczne.
Wymień o opisz struktury sterujące stosowane do budowy algorytmów.
Podstawowe struktury sterujące to:
bezpośrednie następstwo - wykonaj instrukcję A, potem instrukcję B, potem instrukcję C, itd.
wybór warunkowy - jeśli warunek Q jest spełniony wykonaj instrukcję A, jeśli nie to wykonaj instrukcję B.
iteracja ograniczona - wykonaj instrukcję A dokładnie N razy.
iteracja warunkowa „dopóki” - dopóki warunek Q jest spełniony wykonuj instrukcję A.
Iteracja warunkowa „aż do” - wykonuj instrukcję A dopóki warunek Q jest spełniony.
Jaka jest konstrukcja algorytmu sortowania bąbelkowego?
Sortowanie bąbelkowe polega na przestawianiu sąsiednich par elementów stojących w niewłaściwej kolejności. Istotne jest iż ciąg elementów przeglądany jest zawsze w tym samym kierunku, a przeglądanie to trwa dopóki mogą się w nim pojawić elementy w nieodpowiedniej kolejności.
Zapis słowny algorytmu sortowania bąbelkowego:
wykonaj co następuje N-1 razy;
wskaż na pierwszy element;
wykonaj co następuje N-1 razy;
porównaj ze sobą wskazany element i element następny;
jeśli elementy stoją w złej kolejności to zamień je miejscami;
wskaż na następny element;
Narysuj schemat blokowy: wyboru warunkowego, iteracji warunkowych typu: „dopóki” i „aż do”.
Schematy znajdują się na załączonym dodatku.
Zapisz słownie i naszkicuj schemat blokowy algorytmu sumowania wektora (jednowymiarowej tablicy) - n elementowego. Wykorzystaj zmienną indeksującą i znajomość długości wektora.
Zapis słowny algorytmu sumowania n -elementowego wektora:
zanotuj na boku liczbę zero;
wskaż na pierwszy element wektora;
wykonaj co następuje n-1 razy;
dodaj wartość wskazanego elementu do liczby zanotowanej na boku;
wskaż na kolejny element wektora;
dodaj wartość wskazanego elementu do liczby na boku;
wypisz wartość liczby na boku;
Schemat blokowy algorytmu w załączonym dodatku.
Jakie korzyści przynosi stosowanie procedur (podprogramów) w algorytmach?
Zalety stosowania procedur są następujące:
oszczędność tekstu
znacznie większa przejrzystość i czytelność struktury algorytmu
znacznie większa kontrola nad poprawnością algorytmu
uproszczenie we wprowadzaniu poprawek i usuwaniu błędów
możliwość programowania analitycznego i syntetycznego
Na czym polega rekurencja i jak można ją wykorzystać w konstruowaniu algorytmów?
Rekurencja - to zdolność podprogramu (procedury) do wywoływania samej siebie. Przykładem zastosowania procedury rekurencyjnej jest algorytm przenoszenia krążków znany z Wież Hanoi. Tam aby wykonać pewne przeniesienie należy przy okazji wykonać inne, czyli wywołać tę samą procedurę wewnątrz procedury wywoływanej na początku.
(…)
… wysokiego poziomu na program w języku niższego poziomu. Programy napisane w językach kompilowanych np.: w C, C++ są o wiele szybsze niż identyczne programy zapisane w językach interpretowanych.
Interpretacja - jest to proces tłumaczenia poszczególnych komend z języka wysokiego poziomu na kod maszynowy zrozumiały dla maszyny, w czasie ich wykonywania. Ta translacja wykonywana jest za każdym razem…
…
wywołaj SORTUJ listę L1
wywołaj SORTUJ listę L2
scal posortowane listy L1 i L2 w jedną posortowaną liste L (etap iteracyjny)
wróć do poziomu wywołania
Na czym polega metoda algorytmiczna zwana „programowaniem dynamicznym”?
Metoda algorytmiczna zwana „programowaniem dynamicznym” opiera się o zasadę optymalności Bellmana, która mówi: „jeśli znamy najlepszą drogę przejścia z punktu początkowego do punktu…
….
Jeżeli mamy pewność, że szanse wystąpienia najgorszego wypadku są znikome, a dany algorytm ma zadowalającą złożoność średniego przypadku można zastanowić się nad jego zastosowaniem w danym programie. Jaki problem nazywamy zamkniętym z punktu widzenia złożoności obliczeniowej?
Problemy zamknięte, to problemy dla których ustanowione dolne i górne ograniczenia złożoności czasowej schodzą się do tego samego…
... zobacz całą notatkę
Komentarze użytkowników (0)