Podstawy programowania

Algorytm - to skończony, uporządkowany ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego zadania.

Cechy algorytmu:

• Jednoznaczność (potrzebne dane, czynności i ich kolejność, oczekiwany wynik)
• Możliwość zastosowania do wielu podobnych zadań (klasa zadań rozwiązywanych za pomocą algorytmu)
• Poprawność - dla określonej klasy danych zawsze otrzymujemy wynik zgodny z oczekiwaniami np. największą z możliwych wartość wskaźnika podczas optymalizacji.
• Wykonalność - dla określonej klasy danych algorytm zawsze się kończy (własność stopu). Algorytm musi być wykonalny aby mógł być poprawny.
• Złożoność obliczeniowa (np. szukanie książki (w zbiorze n książek)
• Złożoność czasowa - czas najczęściej zależy od wymiarowości zadania. O czasie wykonania obliczeń decyduje niewielka część najczęściej wykonywanych operacji. Typowe zależności:
• Czas stały niezależny od wymiarowości
• Liniowa (n)
• Logarytmiczna (log2n)
• Liniowo-logarytmiczna (n * log2n)
• Kwadratowa (n2 )

• Złożoność pamięciowa – często istnieje wymienność, szybsze obliczenia kosztem większego zapotrzebowania na pamięć
• Złożoność pesymistyczna – n sprawdzeń
• Złożoność średnia – n/2 sprawdzeń
• Skończoność - Poprawie zaprojektowany algorytm powinien zatrzymać się po skończonej liczbie kroków (chyba, ze zbudujemy algorytm, który nie ma końca).

Algorytmiczne rozwiązywanie problemów

Komputer jest stosowany do rozwiązywania problemów zarówno przez profesjonalnych informatyków, którzy projektują i tworzą oprogramowanie, jak i przez tych, którzy stosują tylko technologię informacyjno-komunikacyjną, czyli nie wykraczają poza posługiwanie się gotowymi narzędziami informatycznymi. W obu przypadkach ma zastosowanie podejście do rozwiązywania problemów algorytmicznych, która polega na systematycznej pracy nad komputerowym rozwiązaniem problemu i obejmuje cały proces projektowania i otrzymania rozwiązania. Celem nadrzędnym tej metodologii jest otrzymanie dobrego rozwiązania, czyli takiego, które jest:

• zrozumiałe dla każdego, kto zna dziedzinę rozwiązywanego problemu i użyte narzędzia komputerowe,
• poprawne, czyli spełnia specyfikację problemu, a więc dokładny opis problemu,
• efektywne, czyli niepotrzebnie nie marnuje zasobów komputerowych, czasu i pamięci.

Ta metoda składa się z następujących sześciu etapów:

1. Opis i analiza sytuacji problemowej. Na podstawie opisu i analizy sytuacji problemowej należy w pełni zrozumieć, na czym polega problem, jakie są dane dla problemu i jakich oczekujemy wyników, oraz jakie są możliwe ograniczenia.

2. Sporządzenie specyfikacji problemu, czyli dokładnego opisu problemu na podstawie rezultatów etapu 1. Specyfikacja problemu zawiera:

• opis danych,
• opis wyników,
• opis relacji (powiązań, zależności) między danymi i wynikami.

Specyfikacja jest wykorzystana w następnym etapie jako specyfikacja tworzonego rozwiązania (np. programu).

3. Zaprojektowanie rozwiązania. Dla sporządzonej na poprzednim etapie specyfikacji problemu, jest projektowane rozwiązanie komputerowe (np. program), czyli wybierany odpowiedni algorytm i dobierane do niego struktury danych. Wybierane jest także środowisko komputerowe (np. język programowania), w którym będzie realizowane rozwiązanie na komputerze.

4. Komputerowa realizacja rozwiązania. Dla projektu rozwiązania, opracowanego na poprzednim etapie, jest budowane kompletne rozwiązanie komputerowe, np. w postaci programu w wybranym języku programowania. Następnie, testowana jest poprawność rozwiązania komputerowego i badana jego efektywność działania na różnych danych.

5. Testowanie rozwiązania. Ten etap jest poświęcony na systematyczną weryfikację poprawności rozwiązania i testowanie jego własności, w tym zgodności ze specyfikacją.

6. Prezentacja rozwiązania. Dla otrzymanego rozwiązania należy jeszcze opracować dokumentację i pomoc dla (innego) użytkownika. Cały proces rozwiązywania problemu kończy prezentacja innym zainteresowanym osobom (uczniom, nauczycielowi) sposobu otrzymania rozwiązania oraz samego rozwiązania wraz z dokumentacją.

Katalog uporządkowany

• Dla katalogu nieuporządkowanego nie znamy lepszego algorytmu wyszukiwania niż „pełny przegląd” (n)
• Dla katalogu uporządkowanego istnieje szybszy algorytm –„wyszukiwanie binarne” ((log2n)

Język programowania

Przeznaczenie: definiowanie algorytmów.

Wymagane cechy:

• Jednoznaczność
• Przejrzystość
• Zwarty zapis
• Precyzja.
• Czytelność

Język programowania służy do:

• Komunikowania się programisty z komputerem
• Komunikowania się programisty z innymi programistami
• Komunikowania się programisty z samym sobą.

Podstawowe elementy języka programowania

• Komentarze – uwagi pomagające zrozumieć opis algorytmu
• Deklaracje – używane biblioteki, przestrzeń nazw, opcje,…
• Zmienne – nazwa, typ (int, float, text)
• Stałe – dane używane w obliczeniach
• Struktury kontrolne (if, for, while,..)
• Procedury, funkcje, klasy

Zmienne i stałe

• Stała – pewna wartość używana podczas obliczeń np. 0.22 , ”abc”
• Zmienna – nazwana wielkość używana w obliczeniach, która może w trakcie obliczeń przyjmować różne wartości.
• Do przechowywania zmiennych rezerwuje się potrzebną ilość pamięci
• Podstawienie wartości na zmienną x=50 lub x=x+y
• Zmienne wykorzystujemy w wyrażeniach arytmetycznych i logicznych np.:

if (x <100 && x>40)

x=x+30;

Struktury kontrolne

Zmieniają kolejność wykonywania komend języka

• if ( x > 100 ) { x1 = x } else { x1 = x+x1 }
• for (i = 0; i < 10; i++) { a[i] = a[i+1];}
• do {i++;} while (i < 10);
• switch (s) { case ”a”: x=”b”; break; …
• goto et100;

Procedury i funkcje

Przeznaczenie: wygodne wydzielenie powtarzalnego fragmentu kodu np.:

int xy(int x, int y) {

… powtarzany fragment kodu

}

OPIS: int – typ zwracanego wyniku

xy – nazwa funkcji

x – przekazywany parametr

y – przekazywany parametr

Rekurencja

• Wywoływanie funkcji przez siebie, algorytm odwołuje się do samego siebie.
• Przydatny sposób do realizacji algorytmów dotyczących struktur wykazujących podobieństwo na różnych poziomach np. struktur hierarchicznych
• Realizacja z wykorzystaniem stosu – możliwe przepełnienie stosu "Stack overflow error."
• Przykładem rekurencji może być algorytm tzw. Wieża Hanoi, liczby Fibonacciego, algorytm Euklidesa i in;

Sortowanie danych

Jest bardzo wiele różnych algorytmów sortowania, a wszystkie różnią się znacznie czasem wykonywania I wymaganą pamięcią. Jedne działają szybko dla każdego rodzaju danych, inne bardzo zwalniają dla pewnych typów danych wejściowych. Wyróżniamy:

• Sortowanie przez wstawianie (insertionsort)
• Sortowanie przez wymianę/wybór (selectionsort)
• Sortowanie przez zliczanie (countingsort)
• Sortowanie szybkie (quicksort)
• Sortowanie stogowe (heapsort)
• Algorytm iteracyjny:
• Iteracja z określoną liczbą powtórzeń: wykonuj czynność A dokładnie N razy
• Iteracja warunkowa: wykonaj czynność A, dopóki jest spełniony warunek M

Klasy

• Wspólna definicja obiektów opisywanych tym samym zestawem atrybutów i funkcji
• Dziedziczenie –definiowanie nowej klasy na podstawie już zrealizowanej

Wyrażenia arytmetyczne i logiczne

W językach programowania można używać swobodnie złożonych wyrażeń arytmetycznych i logicznych

Semantyka i syntaktyka

W językach programowania ściśle określa się

• syntaktykę (gramatykę) – dopuszczalną budowę zdań języka (kolejność elementów, relacje między nimi,…)
• semantykę – znaczenie poszczególnych elementów języka (co spowoduje użycie pewnej konstrukcji językowej)

Notacja BNF (Backus-Naur form) – ścisłe definiowanie gramatyki języków programowania (bezkontekstowe)

Przykład:

<liczba_binarna> ::= <liczba_binarna> <cyfra>
<liczba_binarna> ::= <cyfra>
<cyfra> ::= 0 | 1

Języki proceduralne

• Biblioteki procedur podzielone na grupy funkcjonalne
• Wszystkie dane potrzebne do wykonania przekazywane jako parametry podczas wywołania procedury (funkcji)

Języki obiektowe

• Definiujemy klasę obiektów podając listę atrybutów określających obiekt oraz listę funkcji, za pomocą których można wpływać na działanie obiektu.
• Tworzymy egzemplarze obiektów (słowo kluczowe new) np. przyciski w okienku.
• Do atrybutów można odwoływać się poprzez nazwę obiektu i nawę atrybutu np. nazwa.atrybut
• Funkcje obiektu można uruchomić podając nazwę obiektu i nazwę funkcji np. nazwa.funkcja()

Języki programowania

• Assembler - język niskiego poziomu, operuje na rejestrach procesora i komórkach pamięci;
• Fortran - uniwersalny język do obliczeń inżynierskich. Obsługuje wyrażenia arytmetyczne, tablice, funkcje;
• Algol - Uniwersalny język algorytmiczny oparty na ściśle zdefiniowanej gramatyce (notacja BNF)
• Cobol - Common Business Oriented Language - Język przetwarzania danych biznesowych;
• PL-1 - Programming Language One, „wszystkomający” uniwersalny język programowania dla celów naukowych, inżynierskich i biznesowych
• C - do budowy jądra Unix'a
• Simula - rozszerzenie Algol'a
• Smalltalk - Pierwszy czysto obiektowy język programowania
• C++ jest rozszerzeniem obiektowym języka C (Bogaty ale dość złożony język, którym łatwo można zrobić wszystko włącznie z błędami)
• Java, C# - Podstawowe koncepcje przejęte z języka Smalltalk, składnia wzorowana na C++ ale starano się usunąć te elementy, które były przyczyną błędów programistycznych w C++, kompilowany do kodu bajtowego, dziedziczenie tylko od jednej klasy, posiada bogate biblioteki klas, uruchamianie w programach NetBeans, JBuilder/ Język C# wersja Microsoft, środowisko I biblioteki klas .NET I program Visual Studio;
• Prolog -
• Lisp -
• Perl, PHP - język skryptowy
• JavaScript -  język skryptowy

SŁOWNIK POJĘĆ / DEFINICJE:

Program - (ang. computer program) zbiór poleceń zapisany w kodzie maszynowym przeznaczony do wykonania przez komputer. Za jego pomocą maszyna ta może przetwarzać dane, rozwiązywać zadania i wykonywać wiele innych funkcji.

Programowanie - (ang. programming) proces tworzenia oprogramowania komputerowego, na który składają się takie etapy pracy jak: projektowanie programu, jego pisanie (programowanie właściwe), kompilacja, testowanie i aktualizowanie.

Słowa kluczowe - słowa zarezerwowane dla danego języka programowania, mające ściśle określone znaczenie, np. nazwy poleceń;

Kod źródłowy - (ang. code) określony, logiczny system zapisu stosowany do przedstawiania informacji. W informatyce pod pojęciem kod kryje się sposób przedstawiania danych jako liczb binarnych lub heksadecymalnych, aby były one zrozumiałe dla komputera.

Translator czyli interpretator - program służący do tłumaczenia kodu programu zapisanego w jęz. programowania z postaci źródłowej do postaci wynikowej. Wyróżniamy: kompilatory tłum. programy zapisane w jęz. wysokiego poziomu; asemblery tłum. programy zapisane w jęz. symbolicznym.

Kompilator - program służący do tłumaczenia kodu w jęz. źródłowym (w jęz. programowania) na odpowiadający mu kod w jęz. wynikowym (maszynowym).

Interpreter   program analizujacy kod źródłowy instrukcja po instrukcji i przedstawiający sprawdzony fragment kodu na bieżąco;

Moduł - to wydzielony fragment programu komp. Każdy moduł jest kompilowany osobno, co ułatwia pracę i analizę błędów.

Linker (konsolidator) - narzędzie do łączenia skompilowanych modułów w jeden plik wykonywalny;

Konsolidacja - proces łączenia skompilowanych modułów w jeden plik wykonywalny;

Aplikacja - ogólna nazwa programów użytkowych napisanych dla konkretnych zastosowań. Aplikacje przeznaczone są do uruchamiania na określonych typach komputerów, systemów operacyjnych.

Aplikacja internetowa (web application) - program pracujacy na serwerze i komunikujący się z userem poprzez sieć oraz przez przeglądarkę internetową

Aplet - niewielki program komputerowy który pracuje tylko w połączeniu z programem głównym, są to biblioteki np. aplety jęz. java, active-x uruchamiany na stronach internetowych;

Edytor - program umożliwiający obróbkę (edycję) danych pewnego rodzaju (np. edytor tekstowy, edytor dyskowy, edytor kodów źródłowych)

Parser - analizator składni. Program interpretujący dane wejściowe i dzielący tak, żeby były zrozumiałe dla następnych w kolejności mechanizmów przetwarzania m. in. kompilatora, języki skryptowe są wykonywane bezpośrednio przez parser.

Debbuger - procedura wyszukiwania błędów (ang. bug) krok po kroku w programach komputerowych. Służą do tego specjalne programy zwane debbuger'ami. Wspomagają programistów gdyż wyszukiwanie błędów jest bardzo żmudną i pracochłonną czynnością

Na koniec trochę przykładów algorytmów - gry: [WIEŻA HANOI] [GRA W ŻYCIE] [WISIELEC]

EdU 2015