Egzamin z przedmiotu "Podstawy informatyki"

1. Pojęcie algorytmu.

2. Złożoność czasowa algorytmu

3. Częściowa poprawność algorytmu (programu)

4. Własności poprawnie sformułowanego algorytmu

5. Weryfikacja poprawności programu

6. Niezmiennik pętli

7. Problem „STOP-u”

8. Notacja „wielkie O ”

9. Własności notacji „wielkie O”

10. Klasy algorytmów

11. Złożoność asymptotyczna algorytmu

12. Znajdowanie złożoności asymptotycznej

13. Sposoby zapisu algorytmu

14. Pojęcie pseudo-kodu

15. Schemat blokowy zorientowany algorytmu

16. Schemat zwarty NS algorytmu

17. Instrukcja warunkowa

18. Pojęcie pętli

19. Instrukcja warunkowa

20. Instrukcja grupująca

21. Klasyfikacja algorytmów

22. Pojęcie rekurencji

23. Algorytm iteracyjny

1. Algorytm - to jednoznaczny przepis obliczenia w skończonym czasie pewnych danych wejściowych do pewnych danych wynikowych.

Algorytm Euklidesa

#include <stdio.h>

 

main()

{

int m, n;

 

printf("Podaj dwie liczby calkowite");

printf(" dodatnie m i n < ");

scanf("%d %d", &m, &n);

printf("NWD(%d,%d) = ", m, n);

 

while ( n != m)

if ( n > m)

n = n - m;

else

m = m - n;

printf("%d\n", m);

return 0;

}

2. Złożoność czasowa algorytmów - Przyjętą miarą złożoności czasowej jest liczba operacji podstawowych w zależności od rozmiaru wejścia. Pomiar rzeczywistego czasu zegarowego jest mało użyteczny ze względu na silną zależność od sposobu realizacji algorytmu, użytego kompilatora oraz maszyny na której algorytm wykonujemy. Dlatego w charakterze czasu wykonania rozpatruje się zwykle liczbę operacji podstawowych (dominujących). Operacjami podstawowymi mogą być na przykład: podstawienie, porównanie lub prosta operacja arytmetyczna.

3. Bardziej formalnie. Rozważać będziemy zatem następujące ważne własności algorytmów:

1. Dla danych d spełniających
   , jeżeli obliczenie algorytmu K dochodzi do punktu końcowego, to otrzymane wyniki spelniają
   .

2. Dla każdych danych d spełniających warunek
   obliczenie K nie jest przerwane.

3. Dla każdych danych d spełniających
   obliczenie K nie jest nieskończone.

• Warunek (1) nazywa się częściową poprawnością.

• Warunek (2) nazywa się określonością obliczeń.

• Warunek (3) nazywa się własnością stopu.

4.

5.

6. Proste algorytmy najczęściej nie wymagają szczegółowej formalnej analizy poprawności. Autor siada, projektuje algorytm i pisze program. Testuje go na komputerze, i po skończonej liczbie znalezionych i usuniętych błędów uznaje, że algorytm (program) jest poprawny.

Taka metoda nie zawsze jest właściwa. Po pierwsze projekt może być zły. Po drugie rozumowania ad hoc mogą mieć błąd pierworodny, trudny do wykrycia już w fazie testowania. Po trzecie testowanie nie jest jedyną możliwą metodą sprawdzania poprawności programu.

Zajmiemy sie najpierw metodami wykazywania częściowej poprawności algorytmu. Pewną wygodną i powszechnie stosowaną metodą wykazywania częściowej poprawności algorytmów jest metoda niezmienników.

Mówimy, że warunek g jest niezmiennikim instrukcji I w algorytmie K w wyróżnionym jej miejscu przy warunku wejściowym
, jeżeli dla każdego obliczenia K spełniającego warunek początkowy
, za każdym razem, gdy obliczenie dochodzi do wyróżnionego miejsca instrukcji I, bieżące wartości zmiennych spełniają warunek g.

#include <stdio.h>

 

main()

{

double x, y, z;

int n, m;

printf("Podaj rzeczywiste x i naturalne n: ");

scanf("%lf %d", &x, &n);

/* Zakladamy, ze dane sa poprawne. */

 

/* warunek alfa: n >= 0, x - liczba rzeczywista */

z=x;

y=1.;

m=n;

do{

/* Niezmiennik: x^n = y*z^m & m>=0 */

if ( (m % 2) == 1 )

y = y*z;

z = z*z;

m = m/2;

/* Niezmiennik: x^n = y*z^m & m>=0 */

}

while (m != 0);

/* warunek beta: y = x^n */

 

printf("%5.2f^%d = %10.2f\n", x, n, y);

 

return 0;

 

}

---