9. Zasady projektowania algorytmów, pytania egzamin inżynierski AiR ARS


  1. Ogólne zasady projektowania algorytmów i programowania

Pracuj nad właściwie sformułowanym problemem

Dokładna analiza nawet małego zadania może prowadzić do ogromnych korzyści praktycznych:

Osoba zamawiająca program często próbuje narzucić programiście niewłaściwe rozwiązanie, dlatego analiza postawionego problemu i własny pomysł na jego rozwiązanie są bardzo istotne.

  1. Zbadaj przestrzeń rozwiązań

1) Programista nigdy nie powinien zabierać się do programowania pierwszego pomysłu algorytmu, tylko szukać innych, lepszych rozwiązań. Tworzenie prototypów lub projektów algorytmów pozwala na wybranie najlepszego rozwiązania (inne rozwiązania niekoniecznie są złe jednak dążymy do najlepszego efektu)

2) Problem, który wydaje się trudny, może mieć proste, nieoczekiwane

rozwiązanie. Należy porównywać średnią złożoność obliczeniową* różnych rozwiązań tego samego problemu, co w efekcie będzie prowadziło do przyspieszenia działania programu oraz zwiększenia zakresu danych wejściowych.

Najlepszym przykładem jest wyszukiwanie, gdzie znamy kilka metod, które w trudności implementacji są do siebie zbliżone, a w efektywności znacznie się różnią. (jednak lepsze rozwiązania posiadają czasem pewne ograniczenia na które nie możemy sobie w danym przypadku pozwolić).

* Przez złożoność obliczeniową algorytmów rozumiemy ilość zasobów niezbędnych do wykonania algorytmu. Przez zasoby rozumie się zwykle czas (złożoność czasowa) i zajętość pamięci operacyjnej (złożoność pamięciowa).

Czas działania algorytmu zależy od samego algorytmu oraz od szybkości działania komputera, rodzaju i wielkości danych.

Złożoność obliczeniowa stała - O(1)

Algorytm wykonuje stałą ilość operacji dominujących bez względu na rozmiar danych wejściowych.

Złożoność obliczeniowa liniowa - O(n)

Dla każdej danej algorytm wykonuje stałą ilość operacji dominujących. Czas wykonania jest proporcjonalny do liczby n danych wejściowych.

Złożoność obliczeniowa kwadratowa - O(n2)

Algorytm dla każdej danej wykonuje ilość operacji dominujących proporcjonalną do liczby wszystkich przetwarzanych danych. Czas wykonania jest proporcjonalny do kwadratu liczby Inne złożoności tego typu O(n3), O(n4)... noszą nazwę wielomianowych złożoności obliczeniowych.

Złożoność obliczeniowa logarytmiczna - O(log2n)

W algorytmie zadanie rozmiaru n da się sprowadzić do zadania rozmiaru n/2. Typowym przykładem jest wyszukiwanie binarne w zbiorze uporządkowanym. Sprawdzenie środkowego elementu pozwala określić, w której z dwóch połówek zbioru może znajdować się poszukiwany element.

Złożoność obliczeniowa liniowo logarytmiczna - O(n log2n)

Zadanie rozmiaru n daje się sprowadzić do dwóch podzadań rozmiaru n/2 plus pewna ilość operacji, których liczba jest proporcjonalna do ilości danych n. Tego typu złożoność obliczeniową posiadają dobre algorytmy sortujące

Złożoność obliczeniowa wykładnicza - O(2n), O(n!)

Złożoność obliczeniową O(2n) posiada algorytm, w którym wykonywana jest stała liczba operacji dla każdego podzbioru n danych wejściowych.

Złożoność obliczeniową O(n!) posiada algorytm, w którym wykonywana jest stała liczba operacji dla każdej permutacji n danych wejściowych.

Złożoność obliczeniowa wykładnicza jest bardzo niekorzystna, ponieważ czas wykonania rośnie szybko wraz ze wzrostem liczby danych wejściowych.

Porównanie klas złożoności obliczeniowych

Klasa złożoności
obliczeniowej O()

Nazwa klasy złożoności
obliczeniowej

Cechy algorytmu

O(1)

Stała

działa prawie natychmiast

O(log2n)

Logarytmiczna

niesamowicie szybki

O(n)

liniowa

szybki

O(nlog2n)

liniowo-logarytmiczna

dosyć szybki

O(n2)

kwadratowa

wolny dla dużych n

O(n3)

sześcienna

wolny dla większych n

O(2n), O(n!)

wykładnicza

nierealizowalny dla większych n

3) Korzystaj z oszacowań

  1. Przyjrzyj się danym

1) Stosuj odpowiednie do zadania struktury danych, uzyskując:

Na przykład przekształć powtarzający się kod w tablicę.

  1. Nie komplikuj - Podsumowanie

  1. Rozwiązuj problemy w tak prosty sposób jak to tylko możliwe, w przypadku gdy lepsze rozwiązanie jest zbędne i osiągnęliśmy wystarczającą efektywność algorytmu oraz zakres jego działania.

  1. Prosty kod jest niekiedy bezpieczniejszy, odporniejszy i efektywniejszy niż jego bardziej skomplikowany odpowiednik

  1. Jeżeli trzeba, idź na ustępstwa

  1. Podsumowując, optymalizuj kod (zarówno pod względem czasu wykonania jak i użycia pamięci) tylko wtedy, jeżeli koniecznie trzeba to zrobić; nie optymalizuj za wcześnie

  1. Główna celem projektowania algorytmów jest uzyskanie zadowalającej w danym przypadku efektywności programu, dlatego też staraj się zapewnić najwyższą jakość na najwyższym poziomie:



Wyszukiwarka

Podobne podstrony:
13. Techniki wspomagania decyzji II, pytania egzamin inżynierski AiR ARS
1. Zadania i metody automatycznej regulacji, pytania egzamin inżynierski AiR ARS
2. Sterowanie procesami - zadania, pytania egzamin inżynierski AiR ARS
14. Dokumenty elektroniczne, pytania egzamin inżynierski AiR ARS
18. Metody przybliżone rozwiązywania zadań optymalizacji dyskretnej I, pytania egzamin inżynierski A
16. Komputerowo zintegrowane wytwarzanie, pytania egzamin inżynierski AiR ARS
18. Metody przybliżone rozwiązywania zadań optymalizacji dyskretnej II, pytania egzamin inżynierski
zasady projektowania algorytmów
Pytania-egzamin, Inżynieria Środowiska [PW], sem 1, chemia
9 Zasady Projektowania Algorytmow
9 Zasady projektowania algorytmów II
9 Zasady projektowania algorytmów III
fizyka pytania egzaminacyjne, materiały air, fizyka dla elek, wykład 1
Pytania z egzaminu inżynierskiego
zagrozenia naturalne pytania2, egzamin inzynierski gig
PYTANIA EGZAMINACYJNE Z INŻYNIERII CHEMICZNEJ
Pytania z egzaminu z inżynierii chem, Inżynieria Chemiczna

więcej podobnych podstron