Aplikacje podstawy

zbiór poleceń zapisanych w określonym języku programowania zgodnie z obowiązującymi w tym języku regułami

Program

proces tworzenia i testowania programu

Programowanie

posiada ściśle zdefiniowane reguły syntaktyczne i semantyczne, które opisują, jak należy budować poprawnie wyrażenia

Język programowania

zarezerwowane słowa, które w danym języku programowania mają ściśle określone znaczenie i mogą zostać użyte tylko zgodnie z ich przeznaczeniem. Są nimi m.in. nazwy poleceń

Słowa kluczowe

ciąg instrukcji i deklaracji zapisany w języku programowania. Opisuje operację, jakie powinien wykonać komputer. Składa się z jednego lub kilku plików tekstowych (przetwarzany na kod maszynowy lub pośredni)

Kod źródłowy

program służący do tłumaczenia programu zapisanego w języku programowania z postaci źródłowej do postaci wynikowej (kompilatory - języki wysokiego poziomu, asemblery - języki symboliczne)

Translator

program służący do tłumaczenia kodu zapisanego w języku źródłowym na odpowiadający mu kod w języku wynikowym (kod maszynowy najczęściej)

Kompilator

program, który analizuje kod źródłowy instrukcja po instrukcji i każdy przeanalizowany fragment kodu wykonuje na bieżąco

Interpreter

wydzielony fragment programu komputerowego (ułatwia pracę, kompilowane osobno)

Moduł

urządzenie służące do łączenia przekomplikowanych modułów w jeden plik wykonalny

Linker (konsolidator)

proces polegający na połączeniu skomplikowanych modułów i utworzeniu pliku wynikowego (mogą być dołączone biblioteki)

Konsolidacja

program użytkowy, wykonywujący konkretne zadania i oferujący interfejs użytkownika

Aplikacja

program komputerowy, który pracuje na serwerze i komunikuje się z użytkownikiem poprzez sieć komputerową z wykorzystaniem przeglądarki internetowej

Aplikacja internetowa

niewielki program komputerowy, którego wykonanie jest możliwe tylko z poziomu innej aplikacji

Aplet

służy do tworzenia programów komputerowych, których zadaniem jest przetwarzanie danych, wykonywanie obliczeń i algorytmów (może zawierać konstrukcje składniowe)

Język programowania

zbiór reguł opisujących sposób definiowania struktur danych, rodzaje dostępnych słów kluczowych i symboli oraz zasad

Składnia

zbiór reguł definiujących znaczenie słów kluczowych i symboli ich funkcji w programie.

Semantyka

określają dostępne typy danych, ich właściwości oraz operacje, które mogą być wykonane na wartościach danego typu

Typy danych

przetwarzanie kodu źródłowego za pomocą preprocesora

Wstępne przetwarzanie kodu

sprawdzeniu, czy nie występują niedozwolone znaki, oraz na podzieleniu tekstu na jednostki odseparowane białymi znakami, analiza składni programu (analiza liniowa, skanowanie)

Analiza leksykalna

parser sprawdza kod źródłowy struktury składniowej i ustalenia, czy dane są poprawne składniowo, zgodność gramatyczna (hierarchiczna)

Analiza syntaktyczna (składniowa)

sprawdza poprawność programu na poziomie znaczenia poszczególnych instrukcji oraz programu jako całość, czy program może być skopmilowany

Analiza semantyczna (znaczeniowa)

sprawdzanie poprawności typów (w językach silnym typowaniem)

kontrola typów

sprawdzanie, czy instrukcje i wyrażenia mają sens w kontekście, w którym zostały użyte

kontrola poprawności instrukcji

sprawdzanie, czy nazwy jednoznacznie identyfikują funkcje, etykiety i inne konstrukcje języka programowania.

kontrola nazw

są czynności mające na celu przyspieszenie działania programu lub zmniejszenie jego objętości (analizy przepływu sterowania i przepływu danych)

Optymalizacja kodu wynikowego

W wyniku kompilacji na podstawie kodu źródłowego generowany jest kod języka niskiego poziomu, kod wykonywalny, lub kod w języku pośrednim

Generowanie kodu

program napisany w języku skryptowym, który jest wykonywany wewnątrz aplikacji.

Skrypt

język programowania służący do wykonywania wyspecjalizowanych czynności. tworzone z myślą o interakcji z użytkownikiem. Często są wykorzystywane do zadań administracyjnych, w stronach dynamicznych

Język skryptowy

zawierają definicje typowych operacji wykonywalnych w programach

biblioteki standardowe

Typowe biblioteki standardowe to:

Operacje na ciągach tekstowych, na typach danych oraz funkcje do zarządzania nimi, Obsługa wejścia-wyjścia, plików, wielowątkowości, zarządzanie pamięcią

dołączone do programu na etapie konsolidacji

Biblioteki statyczne

ładowane przez program na etapie wykonywania

Biblioteki dynamiczne

zestaw ścisłe określonych czynności, prowadzących do wykonania pewnego zadania. Określa sposób rozwiązania problemu

Algorytm

Zapis algorytmu w wybranym języku programowania

implementacją algorytmu

operacje, które należy wykonać, są zapisywane za pomocą zwykłego tekstu (wstępna faza)

Opis słowny

opis słowny, który może zawierać instrukcje z języka programowania

pseudokod

operacje które należy wykonać zapisane są w postaci numerowanego kroku

Lista kroków

reprezentacja graficzna algorytmu, może zostać przedstawione jako graf, wyróżnia się: korzeń, gałęzie, liście

Drzewo algorytmu

operacje, które należy wykonać, są przedstawiane w postaci graficznej z użyciem symboli

Schemat blokowy

algorytm powinien zwracać poprawne wyniki, odzwierciedlające rzeczywistość

poprawność

algorytm powinien przy takim samym zbiorze danych wejściowych zwracać takie same wyniki

Jednoznaczność

dla każdego zbioru poprawnych danych wejściowych algorytm powinien zwracać wyniki w skończonej liczbie kroków

Skończoność

algorytm powinien prowadzić do rozwiązania problemu w jak najmniejszej liczbie kroków

Efektywność

cechy algorytmów to:

Poprawność Jednoznaczność Skończoność Efektywność

Specyfikacja algorytmu powinna zawierać

podanie danych wejściowych; określenie wyniku, warunków jakie mają spełniać, podanie zmiennych pomocniczych

problem, który należy rozwiązać, jest dzielony na kilka mniejszych, a te znowu są dzielone aż do uzyskania problemów łatwych do rozwiązania.

Dziel i zwyciężaj

Problem, który należy rozwiązać jest dzielony na kilka mniejszych. Wyniki analizy cząstkowych problemów wykorzystuje się do rozwiązywania głównego problemu

Programowanie dynamiczne

nie jest przeprowadzana dokładna analiza problemu, tylko wybierane jest rozwiązanie, które w danym momencie wydaje się najskuteczniejsze

Metoda zachłanna

przeszukiwany jest zbiór danych aż do znalezienia rozwiązania. przeszukiwany jest zbiór danych aż do znalezienia rozwiązania. przeszukiwany jest zbiór danych aż do znalezienia rozwiązania.

Poszukiwanie i wyliczanie

na podstawie niepełnych danych tworzony jest algorytm, który działa w sposób najbardziej prawdopodobny

Heurystyka

Klasyfikacja algorytmów ze względu na sposób konstruowania algorytmu.

Dziel i zwyciężaj Programowanie dynamiczne Metoda zachłanna Poszukiwanie i wyliczanie Heurystyka

Klasyfikacja algorytmów ze względu na sposób wykonywania działań

Liniowy Warunkowy (z rozgałęzieniem) Z pętlą (cykliczne)

kolejne kroki w algorytmie wykonywane są w kolei jakiej zostały zapisane. Żaden krok nie może być pominięty ani powtórzony

Liniowy

Warunkowy (z rozgałęzieniem)

wykonywanie poleceń zależy od spełnienia lub niespełnienia określonego warunku

grupa poleceń jest powtarzana wielokrotnie.

Z pętlą (cykliczne)

Klasyfikacja algorytmów ze względu na sposób wykonywania operacji:

Sekwencyjne Inercyjne Rekrutacyjne

operacje w algorytmie są wykonywane w kolejności, w jakiej zostały opisane.

Sekwencyjne

niektóre kroki są powtarzane aż do spełniania wymaganego warunku.

Iteracyjne

formuła powtarzająca dane i odwołująca się do niej samej. Zakończenie wywoływania formuły następuje po spełnieniu warunku zakończenia

Rekurencyjne

Klasyfikacja algorytmów ze względu na obszar zastosowań.

Matematyczne Przeszukujące Porządkujące Rekurencyjne Szyfrujące

- program jest dzielony na fragmenty (procedury) wykonując ściśle określone operacje. Tworzone programy korzystają ze standardowych procedur wywoływanych podczas pracy programu.

Proceduralność

– procedury są wykonywane według kolejności ich wywołań. W danym momencie może być wykonywania tylko jedna procedura.

Praca sekwencyjna

pozwala na uruchomienie co najmniej dwóch procedur w tym samym czasie. Kolejne procedury wykonywane są sekwencyjnie, lecz kolejność ich wykonywania nie jest z góry określona.

Praca wielowątkowa

pozwala na uruchomienie wielu procedur w tym samym czasie

Praca równoległa

– procedura lub funkcja wywołuje sama z siebie aż do uzyskania ostatecznego wyniku.

Rekurencja

procedury i dane są definiowane jako klasa obiektów. Algorytmy mają znacznie drugorzędne. Programy są tworzone jako zbiory klas.

Obiektywność

decyzje dotyczące zachowania się algorytmu są podejmowane w sposób losowy. Działanie programu nie musi być poprawne, ale daje duże prawdopodobieństwo poprawności.

Algorytm probabilistyczny

Do najważniejszych technik implementacji algorytmów należy:

Proceduralność Praca sekwencyjna – Praca wielowątkowa Praca równoległa Rekurencja Obiektywność Algorytm probabilistyczny

ilość czasu potrzebnego do rozwiązania problemu w zależności od liczby danych wejściowych. (podawana w liczbie wykonanych operacji)

Złożoność czasowa algorytmu

operacją, której wykonanie wpływa bezpośrednio na czas wykonania całego algorytmu

Operacja dominująca

określa wielkość pamięci operacyjnej komputera, która jest potrzebna do przechowywania danych wejściowych, danych pośrednich oraz ostatecznych wyników obliczeń.

Złożoność pamięciowa algorytmu

określa zużycie zasobów dla najgorszego przypadku

złożoność: pesymistyczną

określa zużycie zasobów dla uśrednionych wszystkich możliwych przypadków lub dla typowych przypadkówv

złożoność oczekiwaną

określa zużycie zasobów dla najkorzystniejszego przypadku

optymistyczną złożoność

liczba wierzchołków pośrednich w drodze od korzenia do wybranego wierzchołka końcowego

Długość drogi

to największa długość drogi od korzenia do wierzchołka końcowego.

Wysokość drzewa

porządkowanie zbioru danych według określonych jego cech

Sortowanie liczb

algorytm szybkiego wyszukiwania elementu w zbiorze

Znajdowanie najmniejszego lub największego elementu w zbiorze