To tylko jedna z 15 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
ALGORYTM • sposób postępowania umożliwiający rozwiązanie zadania określonego typu • podany w postaci zestawu kolejnych czynności do wykonania • wykonawcą algorytmu może być człowiek lub urządzenie (np. komputer) STRUKTURA DANYCH • Zestaw powiązanych ze sobą danych wraz z mechanizmami określającymi sposob tworzenia, likwidowania i wykorzystania zdefiniowanego zestawu jako całości oraz poszczegolnych jego elementow. PROGRAM KOMPUTEROWY • zrozumiały dla komputera sposob zapisu algorytmu i opisu struktur danych • zapisywany przy użyciu języków programowania. EWOLUCJA METOD PROGRAMOWANIA • Programowanie w języku maszynowym - Programista posługuje się pojęciami charakterystycznymi dla systemu komputerowego, a nie dla dziedziny zastosowań (operuje rozkazami wchodzącymi w skład listy rozkazow procesora) - Rozkazy składające się na program programista zapisu w postaci binarnych kodow - Programista operuje bezpośrednio na komorkach pamięci operacyjnej. Odpowiedzialny jest za określenie sposobu binarnej reprezentacji informacji. • Programowanie w języku symbolicznym (asemblerze) - Programista posługuje się rozkazami pochodzącymi z listy rozkazow procesora (ale są one zapisywane w postaci instrukcji, a nie w postaci binarnych kodow). - Języki symboliczne wprowadziły zmiany w sposobie notacji programu, ale nie spowodowały zasadniczych zmian w zestawie pojęć wykorzystywanych do opisu algorytmow. - Pojawiła się możliwość przypisywania nazw komorkom pamięci (definiowanie zmiennych) • Programowanie w językach wysokiego poziomu I generacji - Pojawiła się możliwość stosowania instrukcji: podstawienia (przypisania), warunkowej, pętli (iteracji), skoku. - Przy opisie algorytmy następuje rezygnacja ze stosowania rozkazow z listy rozkazow procesora i pojawia się możliwość stosowania pojęć o znacznie większym stopniu ogolności. - Wprowadzenie mechanizmu deklarowania zmiennych - Ułatwione zostało operowanie na wartościach tekstowych - Pojawiła się możliwość korzystania ze złożonych typow danych (tablice, pliki) • Programowanie proceduralne - Możliwość definiowania podprogramow. - Zdefiniowanie nowego podprogramu pozwala na rozszerzenie zbioru instrukcji dostępnych w stosowanym języku programowania. - Mechanizm parametrow zwiększył uniwersalność definiowanych instrukcji. - Pojawiła się możliwość definiowania danych lokalnych (dostępnych tylko w podprogramie) oraz danych globalnych (dostępnych w całym programie) • Programowanie strukturalne - Zwiększenie liczby instrukcji sterujących (np.: rożne postaci pętli, instrukcji warunkowych, wyboru, podstawienia) -dzięki czemu można było wyeliminować instrukcję skoku bezwarunkowego - Podział programu na dwie części: opis struktur danych i opis algorytmu - Zwiększenie liczby dostępnych typow danych (tablice, rekordy, zbiory, pliki),
(…)
… dowodzenie poprawności algorytmu, testowanie programu)• błędy wykonania programu - ujawniające się w trakcie realizacji algorytmu zapisanego w postaci programu (ujawniające się w postaci wyjątkow)• błędy syntaktyczne - polegające na niezgodności tekstu programu z gramatyką języka programowania (wykrywane przez kompilator)
ZŁOŻONOŚĆ OBLICZENIOWA ALGORYTMU - ilość zasobow systemu komputerowego niezbędnych do jego realizacji. • Zasoby systemu komputerowego niezbędne do realizacji algorytmu: - czas pracy procesora (złożoność czasowa algorytmu), - pamięć operacyjna (złożoność pamięciowa algorytmu). • Złożoność obliczeniowa jest uzależniona od wielkości zadania. Oszacowanie czasu realizacji algorytmu • Analiza powyższych danych pozwala stwierdzić, że czas obliczeń uzależniony jest przede wszystkim od składnika: 0,000002…
…(n) jeśli istnieją stała rzeczywista c1 > 0, c2 > 0 i stała naturalna n0 takie, że nierowność c1 g(n) ≤ f(n) ≤ c2 g(n) zachodzi dla każdego n ≥ n0. • Zbior wszystkich funkcji spełniających to ograniczenie określany jest jako Θ(g(n)) • Θ(g(n)) = {f(n); istnieją dodatnie stałe c1, c2 i n0 takie, że 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) dla wszystkich n ≥ n0}
ŚREDNIA ZŁOŻONOŚĆ OBLICZENIOWA • Średnia złożoność…
…, w którym potomkowie węzłów występują w ściśle określonej kolejności (np. alfabetycznej)•drzewo etykietowane (drzewo, w którym węzły lub krawędzie mają przypisane nazwy i/lub wartości)•drzewo binarne(drzewo, w którym węzły mają co najwyżej dwóch potomków (potomek lewy oraz potomek prawy) IMPLEMENTACJE DRZEW:
wektorowa = implementacja rodzicielska, •elementy drzewa należy ponumerować kolejnymi liczbami całkowitymi…
… korzenia - wymaga sekwencyjnego przeglądania list potomków. Lcrs (leftmost-child, right-sibling)• węzły identyfikowane są przez etykiety, a nie indeksy • pozwala na stosunkowo proste poruszanie się po drzewie w obu kierunkach, • pozwala na realizację zaawansowanych operacji na drzewie (np. łączenie drzew).
Drzew binarnych każdy węzeł przechowuje referencje do lewego (LC - left child) oraz prawego (RC…
… współbieżności w języku java • wątki: - logicznie wyodrębnione sekwencje instrukcji realizowane w sposób pozornie równoległy; - wykorzystują mechanizm podziału czasu; - realizowane są w obrębie tej samej maszyny wirtualnej; • programowanie rozproszone (sieciowe): - komunikujące się ze sobą programy uruchamiane na różnych komputerach (i różnych maszynach wirtualnych);- programowanie rozproszone wykorzystuje…
... zobacz całą notatkę
Komentarze użytkowników (0)