Programowanie
Zasady programowania strukturalnego
Programowanie wykorzystujące zbiór instrukcji i zasady algorytmów strukturalnych jest nazywane PROGRAMOWANIEM STRUKTURALNYM. Jego podstawowa cechą jest składanie konstrukcji strukturalnych z konstrukcji prostych. Programowanie strukturalne powoduje, że programy staja się przejrzyste czytelne i poprawne.
Algorytm jest strukturalny, jeżeli metoda kolejnych uściśleń zostanie on ostatecznie zapisany w postaci ciągu konstrukcji (sekwencja, rozgałęzienie, pętla, podprogram), które dadzą się zakodować za pomocą instrukcji (przypisania, wprowadzenia i wyprowadzenia danych, warunkowa, złożona itd.).
Nie każdy algorytm rozwijany metoda kolejnych uściśleń jest algorytmem strukturalnym. Algorytm jest strukturalny, jeżeli jego zapis w postaci schematu blokowego w wyniku kolejnych redukcji daje się przekształcić do jednego bloku.
Pojęcie zmiennej w językach programowania. Zasady używania zmiennych statycznych i dynamicznych. Pojęcie typu tablicowego i rekordowego.
Aby komputer mógł wykonywać zadania, program musi przetwarzać dane - czyli liczby, znaki które przedstawiają jakieś informacje. Niektóre dane są ustalone przed uruchomieniem programu i pozostają niezmienne przez cały czas działania programu - są to stałe. Dane, które mogą zmieniać się w trakcie działania programu nazywamy ZMIENNYMI.
ZMIENNA STATYCZNA - słowo statyczna oznacza, że zmienna pozostaje w jednym miejscu pamięci. Zmienne statyczne mają taki sam zasięg jak zmienne automatyczne, ale nie znikają, gdy zawierająca je funkcja zakończy działanie. Innymi słowy zmienne należące do klasy statycznej charakteryzuje zasięg blokowy i statyczny czas trwania.
Zdefiniowanie typu danych a następnie określenie specyfikacji zmiennych tego typu oznacza, że zakres wartości przyjmowanych przez te zmienne i jednocześnie wzorzec pamięciowy są ustalone raz na zawsze. Zmienne deklarowane w ten sposób to zmienne statyczne.
ZMIENNE DYNAMICZNE - są tworzone i usuwane podczas wykonywania programu. Innymi słowy pamięć potrzebna na zmienne dynamiczne jest przydzielana podczas działania programu a gdy przestaje być potrzebna może zostać zwolniona i przydzielona innej zmiennej.
TYP TABLICOWY - tablice służą do przechowywania ustalonej liczby elementów tego samego typu oznaczonych wspólną nazwą z bezpośrednim dostępem do każdego z elementów przy pomocy indeksu określającego położenie elementu w tablicy.
TYP TABLICOWY - jest typem strukturalnym składającym się ze skończonej liczby elementów tego samego typu (definiuje się go w sekcji definicji typów).
TYP REKORDOWY - Typ ten służ do łączenia danych różnych typów w pewną całość logiczną. Jest on typem strukturalnym o stałej strukturze zdefiniowanej według potrzeb użytkownika. Rekord składa się ze stałej liczby składowych zwanych polami.
Pojęcie pliku oraz zmiennej plikowej w języku Pascal. Podstawowe operacje na plikach. Pojęcie procedury oraz funkcji, sposoby przekazywania parametrów. Podobieństwa i różnice w rozwiązaniach w języku C i Pascal.
PLIK - jest obszarem, w którym przechowywane są dane. Pliki są zwykle zapisane w pamięci trwałej takiej jak HDD czy FDD (plik jest sekwencją małych fragmentów danych). Jest typem strukturalnym. Określa się go jako zbiór powiązanych elementów zapisanych na HDD czy pamięci zewnętrznej.
Deklaracja typu i zmiennej plikowej w języku Pascal:
Type
Typ_plikowy =File of element;
Var
Zmienna_plikowa1: Typ_plikowy;
Zmienna_plikowa2: File of element_inny;
Procedury i funkcje do operacji na plikach:
assign(zp, nazwa) - skojarzenie pliku z nazwą
rewrite(zp) -otwarcie do zapisu, utworzenie nowego pliku
reset(zp) - plik do odczytu
write(zp, dane) zapis/dodanie do pliku
read(zp, zmienna) - odczyt elementu z pliku
EOF(zp):Boolean -Sygnalizacja końca pliku
Closefile(zp) - zamykanie pliku
Filesize(zp):integer - liczba elementów pliku
Filepos(zp):longint - aktualne położenie wskaźnika pliku
Seek(zp, pozycja) - ustawienie wskaźnika na zadanej pozycji
Truncate(zp) - skrócenie długości pliku
PROCEDURA - Jest to pewien podprogram opatrzony własnym identyfikatorem (nazwą). Może posiadać własny blok deklarujący stałe i zmienne. Zawiera również ciąg instrukcji, które ma wykonać. Jest to więc zamknięty, zwarty blok instrukcji wykonujący określone działanie.
Parametry procedur mogą przekazywać dane z programu do procedury. Lub przekazywać do programu wyniki wyznaczone w procedurze. Procedura może przekazywać wiele wyników.
Dla wzorcowego języka PASCAL zdefiniowano 3 podstawowe sposoby przekazywania parametrów:
Wartość - Parametry formalne przekazywane przez wartość są traktowane jak zmienne lokalne, którym nadaje się wartość początkową, równą wartości parametru aktualnego, w chwili wywołania. Parametry przekazywane przez wartość nie mogą zmieniać swej wartości w treści procedury. Nawet, gdy czasem wykorzystuje się je w instrukcjach przypisujących im wartość w treści procedury, to nie wpływa to na wartość zmiennej programu, która była parametrem aktualnym.
Parametry przekazywane do podprogramu przez zmienną, są poprzedzane słowem var np.:
Procedure ZmianaWartosci(var wartosc : integer);
W przypadku tego typu wywołania, każdorazowa zmiana wartości zmiennej przekazywanej do podprogramu zostaje automatycznie uwzględniona w programie wywołującym ten podprogram.
Przekazywanie przez stałą. Parametr jest poprzedzany słowem kluczowym const, informuje to procedurę, iż nie może ona wpływać na wartość parametru, jakakolwiek próba zmiany wartości parametru skończy się błędem kompilatora. Przekazując parametry przez stałą, pozwalamy kompilatorowi na maksymalną optymalizację kodu.
Procedure ZmianaWartosci(const wartosc : integer);
W TURBO PASCALU stosuje się również:
parametry otwarte np. otwarte tablice
parametry amorficzne
parametry przekazywane przez zmienną nieokreślonego typu z wykorzystaniem zmiennych absolutnych.
FUNKCJE - Są bardzo podobne do procedur. To również podprogramy wykonujące określony ciąg instrukcji, opatrzone identyfikatorem, listą argumentów w nagłówku, blokiem begin end. Jednak funkcje pozwalają na zwracanie pewnych wartości. Możemy je przyrównywać do pewnych zmiennych czy spróbować wyświetlić.
Pojęcie algorytmu oraz sposoby prezentacji algorytmów.
ALGORYTM - jest pojęciem ogólnym związanym nie tylko z programowaniem i programem. Określa on sposób wykonania pewnego zadania, rozwiązania określonego problemu czy osiągnięcia zamierzonego celu.
ALGORYTM opracowany dla programu określa sposób przekształcenia danych wejściowych w dane wyjściowe zgodnie z celem- zadaniem algorytmu. Dla realizacji jednego celu można stosować wiele algorytmów.
Algorytm składa się z opisu:
Obiektów, na których wykonywane są działania
działań realizujących cel algorytmu
kolejności działania
Nieformalnie algorytm jest pewną ściśle określoną procedura obliczeniową, która dla właściwych danych wejściowych „produkuje” żądane dane wyjściowe zwane wynikiem działania algorytmu.
Pojęcie złożoności obliczeniowej. Przykłady zastosowań, podstawowe notacje asymptotyczne, przykłady algorytmów o różnej złożoności obliczeniowej.
ZŁOŻONOŚĆ OBLICZENIOWA ALGORYTMU definiuje się jako ilość zasobów komputerowych potrzebnych do jego wykonania. Podstawowymi zasobami rozważanymi w analizie algorytmów są czas działania i ilość zajmowanej pamięci.
Kiedy dla dostarczenia dostatecznie dużych danych wejściowych liczymy jedynie rząd wielkości czasu działania algorytmu wtedy zajmujemy się ASYMPTOTYCZNĄ złożonością algorytmów.
NOTACJA - W notacji używanej do opisu asymptotycznego czasu działania algorytmów korzysta się z funkcji których zbiorem jest zbiór liczb naturalnych N={1, 2, 3, ...}
Podstawowe notacje:
notacja O
notacja Ω
notacja ω
Złożoność asymptotyczna górna O:
log n - złożoność logarytmiczna( b. dobra)
n - złożoność liniowa - zależność ilości operacji od wzrostu ilości danych na wejściu jest wprost proporcjonalna
n log n - złożoność logarytmiczno liniowa (na ogół troszke gorsza od liniowej)
n2 - bardzo niekorzystna, gdyż dyskwalifikuje algorytm jeśli chodzi o zadania na większych danych
n3 - jeszcze gorzej
2n - taka złożoność prawie nigdy nie pozwala na sensowne wykorzystanie algorytmu
Problem sortowania. Sortowanie tablic, sortowanie list, sortowanie plików (sortowanie zewnętrzne) - algorytmy, złożoność obliczeniowa.
SORTOWANIE - Sortowaniem nazywamy proces ustawiania zbioru obiektów w określonym porządku. Sortowanie stosuje się w celu ułatwienia późniejszego wyszukiwania elementów sortowanego zbioru. Sortowanie dzielimy na dwie klasy:
sortowanie tablic (wewnętrzne)
sortowanie plików (zewnętrzne)
Wewnętrzne, ponieważ tablice są przechowywane w szybkiej o dostępie „swobodnym” „wewnętrznej” pamięci komputerów. Pliki zaś są zazwyczaj przechowywane w wolniejszych, lecz pojemniejszych pamięciach zewnętrznych.
SORTOWANIE TABLIC - Najważniejszym wymaganiem stawianym metodom sortowania tablic jest oszczędne korzystanie z dostępnej pamięci. Wynika stąd, że permutowanie obiektów powodujące ich uporządkowanie powinno być wykonywane w miejscu oraz że metody przenoszenia obiektów z tablicy do tablicy wynikowej są właściwie o wiele mniej interesujące. Ograniczając wybór metod do tych, które spełniają kryterium oszczędnego wykorzystania pamięci metody sortowania obiektów w miejscu można podzielić na:
sortowanie przez wstawianie
sortowanie przez wybieranie
sortowanie przez zamianę
Sortowanie bąbelkowe to prosta metoda sortowania, o złożoności czasowej O(n2) i pamięciowej O(1). Polega na porównywaniu dwóch kolejnych elementów i zamianie ich kolejności, jeżeli zaburza ona porządek, w jakim się sortuje tablicę. Sortowanie kończy się, gdy podczas kolejnego przejścia nie dokonano żadnej zmiany.
Sortowanie pozycyjne (ang. radix sort) to algorytm sortowania porządkujący stabilnie ciągi wartości (liczb, słów) względem konkretnych cyfr, znaków itp, kolejno od najmniej znaczących do najbardziej znaczących pozycji. Złożoność obliczeniowa jest równa O(d(n + k)), gdzie k to wielkość domeny cyfr, a d szerokość kluczy w cyfrach. Wymaga O(n + k) dodatkowej pamięci.
Sortowanie przez łączenie (mergsort) to metoda ekstensywna o zapotrzebowaniu na dodatkową pamięć równą pojemności tablicy posortowanej. Wydajnościowo bliska quicksort, statystycznie z nim przegrywa, dobra metoda dla sortowania zewnętrznego (plików).
- dla tablic: podziel tablice na odcinki jednoelementowe, scalaj element 1 z 2, 3 z 4 itd., umieszczając wynik w drugiej tablicy. Potem 2-elementowe odcinki scalaj w 4-elementowe (wersja podstawowa iteracyjna).
Analogicznie postępujemy dla plików, stosuje się dwa pliki wejściowe i jeden wyjściowy
Złożoność: czas wykonywania algorytmu sortowania przez łączenie jest logarytmiczno liniowo zależny od liczby danych wejściowych. T(n)=Θ(nlogn)
Sortowanie szybkie: Algorytm działa rekursywnie - wybieramy pewien element tablicy, tzw. element dzielący, po czym na początek tablicy przenosimy wszystkie elementy mniejsze od niego, na koniec wszystkie większe, a w powstałe między tymi obszarami puste miejsce trafia wybrany element. Potem sortujemy osobno początkową i końcową część tablicy. Rekursja kończy się, gdy kolejny fragment uzyskany z podziału zawiera pojedynczy element, jako że jednoelementowa podtablica jest oczywiście posortowana.
Jeśli przez l oznaczymy indeks pierwszego, a przez r - ostatniego elementu sortowanego fragmentu tablicy, zaś przez i - indeks elementu, na którym tablica została podzielona, to procedurę sortowania można (w dużym uproszczeniu) przedstawić w następujący sposób:
SORTOWANIE PLIKÓW - wymaga zastosowania algorytmu sortowania przez scalanie i przepisywanie podciągów uporządkowanych do plików wynikowych. Ponieważ algorytmy sortowania plików są dość skomplikowane dla plików, które w całości nie mieszczą się w pamięci operacyjnej tworzy się specjalną tablicę rekordów.
Dynamiczne struktury danych. Podstawowe rodzaje struktur (stos, kolejki, listy). Sposoby implementacji. Algorytmy wstawiania, usuwania, wyszukiwania.
STOS - Jest strukturą danych o kolejności odczytu odwrotnej do kolejności zapisu. W związku z tym, że nowe elementy dołącza się do stosu na początku i pobiera się je ze stosu również na początku wystarczy utrzymać w programie jeden wskaźnik wskazujący na szczyt stosu. Stos może być implementowany zarówno w statycznych jak i dynamicznych strukturach danych.
W przypadku stosu implementowanego w strukturze dynamicznej każdy element stosu oprócz danych wpisywanych na stos musi zawierać wskaźnik na następny element stosu.
Dwie podstawowe implementacje to:
tablicowa
dowiązaniowa
KOLEJKA - Struktura danych typu kolejka jest wykorzystywana do grupowania i obsługi elementów w kolejności dołączania ich do grupy. Kolejka jest lista o szczególnych własnościach:
nowe pozycje mogą być dodawane tylko na końcu kolejki
pozycje mogą być usuwane tylko z początku kolejki (przypomina to kolejkę po bilety do kina wchodzi się na końcu kolejki a wychodzi na początku po kupieniu biletu)
kolejka jest formą danych typu FIFO (first IN first OUT )
LISTA - Jest chyba najprostszym sposobem połączenia zmiennych dynamicznych. Lista to ciąg elementów tego samego typu ułożonych w ciąg jeden za drugim. Lista przechowywana jest na stercie.
Podstawowa ideą listy jest to, że każdy jej element stanowiący zmienną dynamiczną oprócz danych zawiera łącznik, który wskazuje gdzie znajduje się następny element listy. Każdy element może być do listy dołączony lub z niej usunięty bez zmiany położenia innych elementów listy w pamięci.
LISTA JEDNOKIERUNKOWA - Składa się z elementów, które oprócz danych elementu zawierają jeden łącznik wskazujący na następny element listy. Dostęp do elementów listy jest sekwencyjny przez przeglądanie ich w kolejności od pierwszego do ostatniego.
LISTA DWUKIERUNKOWA - Składa się z elementów, które oprócz danych elementu listy zawierają dwa łączniki jeden do następnego, a drugi do poprzedniego elementu listy. Dostęp do elementów listy dwukierunkowej jest także sekwencyjny. Przy pamiętaniu wskaźnika końca listy, lista może być przeglądana także w porządku odwrotnym od ostatniego elementu do pierwszego.
Podstawowe pojęcia i zasady programowania obiektowego na przykładzie wybranego języka programowania.
OBIEKT - abstrakcyjny byt, reprezentujący lub opisujący pewna rzecz czy pojecie w świecie rzeczywistym. Konkretny obiekt jest odróżnialny od innych obiektów, ma nazwę i określone granice.
Obiekt to:
abstrakcja pojęciowa lub informacyjna
struktura danych
konkretny obiekt materialny, istniejący rzeczywiście
Program obiektowy operuje na klasach/obiektach. Program stanowi rozwiązanie konkretnego problemu i jest realizowany za pomocą sekwencji wywołań metod poszczególnych klas/obiektów.
Podstawowe pojęcia:
Obiekt/klasa
Hermetyzacja
Dziedziczenie
Polimorfizm
KLASA - wzorzec dla obiektów, typ obiektów określa atrybuty obiektów i akcje, jakie są dopuszczalna w obiekcie tej klasy
HERMETYZACJA - proces ukrywania tych elementów abstrakcji(obiektu), które implementują jego strukturę i zachowanie, służy do ochrony przed bezpośrednim dostępem do danych zawartych w klasie/obiekcie.
DZIEDZICZENIE:
realizacja między klasami mówiąca o tym, że dana klasa(podklasa) współdzieli strukturę i zachowanie zdefiniowane w jednej lub wielu klasach (nadklasach)
podklasa najczęściej jest specjalizacja swojej nadklasy poprzez doprecyzowanie lub rozszerzenie odziedziczonej struktury i zachowania.
POLIMORFIZM - uogólnienie pewnych cech na poziomie drzewa dziedziczenia.
Techniki tworzenia i likwidacji obiektów w pamięci operacyjnej na przykładzie języka C++. Sposoby inicjacji wartości atrybutów.
Programowanie
7