Wykład z 16-10-2007

Programowanie (w znaczeniu szerszym) - jednoznaczne formułowanie zadań oraz sposobu ich rozwiązania za pomocą komputera prowadzącego do szeregu czynności.

Czynności składające się na proces programowania:

• Sformułowanie problemu

• Określenie metody rozwiązywania

• Dyskusja warunków istnienia rozwiązania

• Utworzenie siedzi działań

• Kodowanie algorytmu w wybranym języku programowania

• Uruchomienie testowe

• Opracowanie dokumentacji

Programowanie (w znaczeniu węższym) to kodowanie algorytmu w wybranym języku programowania.

Algorytm - zbiór reguł postępowania (przepis) mający na celu w skończonej liczbie kroków przetworzenie informacji wejściowych (danych) na informacje wyjściowe (wyniki).

Problemy związanie z opracowaniem algorytmu:

• Raz opracowany algorytm dla danego problemu może służyć do rozwiązania wszystkich problemów tej samej klasy, dla której został opracowany, różniących się jedynie doborem konkretnych danych wejściowych

• Zawsze przy opracowaniu algorytmu zakłada się pewien poziom szczegółowości na którym formułuje się algorytm

• Przed opracowaniem algorytmu powinniśmy stwierdzić czy zadanie posiada rozwiązanie i czy rozwiązanie jest jednoznaczne

• Algorytm powinien uwzględnić wszystkie możliwe warianty przebiegu

Kodowanie algorytmu w języku programowania:

Jako ograniczenia zawężające możliwość wyboru języka przyjmuje się m.in. :

• Klasę problemu

• Kwalifikacje programisty

• Dostępność translatora języka

Cechy dobrego programu:

• Poprawny - testowanie może wykazać obecność pomyłki, nigdy nie może wykazać nieobecności błędu

• Przystosowalny - modularna budowa

• Odporny - na błędy użytkownika

• Stabilny - nie załamuje się w przypadku prostego błędu danych wyjściowych

System programowania (środowisko programistyczne):

• Język programowania

• Translator

Język programowania - zbiór symboli oraz reguł syntaktycznych i semantycznych (znaczeniowych) stosowanych w trakcie definiowania sposobu przetwarzania określonego zadania.

Elementy języka programowania:

• Alfabet - zbiór dopuszczalnych symboli z których będą tworzone słowa, zdania w tym języku

• Składnia (syntaktyka) - reguły tworzenia poprawnych słów i zdań (tzw. instrukcji) tego języka

• Reguły znaczeniowe (semantyka) - interpretują znaczenie poszczególnych zdań i konstrukcji języka

Translacja - proces tłumaczenia programu źródłowego na wynikowy :

• Kompilacja

• Interpretacja

Kompilator - analizuje program napisany w określonym języku programowania (program źródłowy) i tłumaczy go na równoważny funkcjonalnie program w języku wewnętrznym (program wynikowy).

Interpretator - pobiera kolejne instrukcje programu, sprawdza ich poprawność, rozpoznaje jaką czynność należy wykonać i wykonuje ją. Oznacza to, że każde uruchomienie programu wymaga jego tłumaczenia.

Programy interpretowane działają bardzo wolno w porównaniu z programami kompilowanymi. Zaletą jest możliwość wykonania tylko fragmentu programu, łatwe lokalizowanie.

Testowanie

W praktyce testowanie programu na wszystkich możliwych danych teoretycznych jest niemożliwe.

Najczęściej stosuje się test:

• Funkcjonalny

• Wg oceny użytkownika

• Wg struktury programu

Systemy programowania poza translatorem obejmują:

• Edytory do zapisu programu źródłowego

• Narzędzia do testowania i uruchamiania programów (debbugery) pozwalające wykryć i usuwać błędy zawarte w programach

• Biblioteki specjalizowanych procedur które można włączyć do pisanych programów, narzędzia wspomagające użytkownika (nauka języka, podpowiedzi kontekstowe).

Translator - program tłumaczący, pozwalający „przetłumaczyć”, przekształcić kod programu napisany w języku zrozumiałym dla programisty (tzw. program źródłowy) w kod maszynowy czyli postać programu wykonalną na danym sprzęcie.

Nauka o algorytmach:

• Algorytmika jest dziedziną wiedzy zajmującą się badaniem algorytmów

• W informatyce jest ona nieodłącznie związana z algorytmami przetwarzania struktur danych

Potoczne rozumienie pojęcia „algorytm”:

• Potocznie algorytm jest rozumiany jako przepis na wykonanie jakiegoś zestawu czynności, prowadzących do osiągnięcia oczekiwanego i z góry określonego celu

• Mówi się również, że algorytm jest pewną ściśle określoną procedurą obliczeniową która dla zestawu danych wejściowych produkuje żądane dane wyjściowe

Pojęcie dziedziny algorytmu:

• Każdy algorytm działa na zbiorze obiektów (np. liczb), wraz z operacjami pierwotnymi, które można wykonać na tym zbiorze obiektów

• Układ obiektów wraz z operacjami będących podstawą dla określonego algorytmu nazywamy dziedziną algorytmiczną

Sposoby zapisu algorytmów:

Algorytm powinien przedstawiać kolejne jego kroki. Do zapisu tych kroków mogą być stosowane zapisy werbalne i formalne, np.:

• Graficzne (schematy blokowe)

• Formalne specyfikacje programów (VDM, CS)

• Zapisy w postaci pseudokodów

• Implementacje programów w dowolnym języku programowania

I generacja:

Kod maszynowy - czyli ciąg zer i jedynek stanowiący binarny zapis funkcji procesora wraz z ich parametrami.

II generacja:

Języki zwane asemblerami lub językami adresów symbolicznych, są językami niskiego poziomu. Funkcje procesora są w nich kodowane za pomocą tzw. mnemoników czyli krótkich i prostych poleceń będących dokładnym odpowiednikiem procedur które może wykonać procesor.

Asemblery jako języki niskiego poziomu słabo nadają się do tworzenia rozbudowanego oprogramowania użytkowego, dlatego stosuje się je głównie do tworzenia elementów oprogramowania systemowego zwłaszcza tych, w których najważniejsza jest szybkość działania i zgodność ze sprzętem komputerowym. Program napisany w języku asemblera musi zostać przetłumaczony na język maszynowy.

III generacja:

To języki wysokiego poziomu, których poszczególne instrukcje odpowiadają ciągom wielu rozkazów wewnętrznych komputera. Oferują one dla programistów takie udogodnienia, jak np. proceduralność czyli możliwość jednokrotnego zaprogramowania rozbudowanych procedur, a następnie wielokrotnego odwoływania się do nich w programie.

Wśród języków wysokiego poziomu wyróżnia się języki:

• Do zastosowań numerycznych np. FORTRAN

• Do przetwarzania danych ekonomicznych np. COBOL

• Do symulacji procesów np. SIMULA

• Uniwersalne - PASCAL czy BASIC

• Tworzenia systemów ekspertowych np. PROLOG

IV generacja:

Zaawansowane technologicznie systemy programowania które jakby ukrywają przed programistą stopień skomplikowania tworzonych aplikacji, umożliwiając mu koncentrowanie się na aspektach merytorycznych.

Wykład z 30-10-2007

Algorytm (cechy):

• Posiada dane wejściowe

• Jest precyzyjnie zdefiniowany

• Jest zbieżny

• Zwraca pewien wynik (niekoniecznie numeryczny)

Własności:

• Adekwatność - czy algorytm realizuje obliczenia zgodnie z przyjętym celem realizacji obliczeń

• Własności stopu - zostały zdefiniowane kryteria zatrzymywania wykonywania algorytmu w warunkach poprawnego i niepoprawnego zakończenia obliczeń

• Jednoznaczność - algorytm jest zapisywany w sposób na tyle precyzyjny że jego wykonywanie jest prawie automatycznym powtarzaniem kolejnych kroków

• Powtarzalność - każde wykonanie algorytmu przebiega według tego samego schematu

• Złożoność obliczeniowa - nakład czasu lub zasobów maszyny realizującej algorytm, niezbędny dla jego prawidłowego wykonania

Opis algorytmu:

Opis danych:

• Typ numeryczny - dane mogą mieć tylko wartości liczbowe (liczby całkowite - byte, short, int, long; liczby rzeczywiste - float, double)

• Typ znakowy (char) - dane mogą przybrać wartość łańcucha znaków

• Typ logiczny - dana przyjmuje 2 wartości (prawda/fałsz)

• Data (date)

• Obiekt (object)

Opis działań na danych (działania różnorodne, rodzaje działań) :

• Liniowe (sekwencyjne) - składają się z ciągu instrukcji które wykonywane są jedna po drugiej w kolejności jaka wynika z ich następstwa

• Nieliniowe - mają rozbudowaną strukturę, często występują w nim instrukcje, których wykonanie uzależnione jest od pewnego warunku. Oprócz sekwencji mogą zawierać selekcję i iterację.

Metody zapisu:

• Schematy blokowe

• Schematy Nassi-Schneidermana

• Pseudokod

• Języki programowania

Schemat blokowy - graficzny zapis przedstawiający opis i kolejność wykonywania czynności realizujących danych algorytm. Operacje przedstawione są pomocą skrzynek/bloków.

Skrzynka graniczna - początek lub koniec algorytmu

Skrzynka operacyjna - różne działania

Skrzynka wejścia/wyjścia - wprowadzanie/wyprowadzanie danych

Skrzynka warunku (blok operacyjny) - sprawdzanie warunku (czy np. x>0), wychodzą z niej 2 połączenia - TAK i NIE

Tak Nie

Wielowybór - wybór z kilku możliwych sytuacji

Zasady budowy:

• Każda operacja jest w skrzynce

• Schemat ma jedną skrzynkę START i jedną skrzynkę STOP

• Skrzynki są ze sobą połączone

• Ze skrzynki wychodzi 1 połączenie (z wyjątkiem skrzynek decyzyjnych i STOPu)

Schematy NS - w nich cały algorytm jest prezentowany jako prostokąt:

Sekwencje poleceń to prostokąt podzelony poziomą linią:

Selekcja: w trójkąt wpisuje się warunek selekcji, a prostokąty pod nim odpowiadają kolejnym krokom algorytmu:

Iteracja (powtórzenie) - prostokąt to czynność powtarzana

Dopóki „W” dopóty „R”

„powtarzaj .... aż do”

Pseudokod - przeważnie modyfikowana wersja języka PASCAL, np.:

S:=0

I:=0

Dokóki i<10 rób

Wprowadź liczbę(a)

Czy a>5

Jak tak to s:=s+a

I:=i+1

Powtarzaj

Drukuj S

Koniec

Konstrukcje algorytmiczne - z rodziny Algol'60, np. Pascal, Modula 2, MODSIM, C, C++, C#, Visual Basic, Nava. W większości przypadków, logika wspólna dla nich wszystkich.

Schemat sekwencji działań

Semantyka - wykonywanie kolejnych kroków algorytmu zgodnie z zadaną sekwencją (Start -> krok 1 -> krok 2 -> krok 3 -> Stop)

Selekcja (instrukcja warunkowa) - działa wg jednego ze schematów: jeśli sprawdzony warunek W, wykonaj A/ jeśli sprawdzony jest warunek W, wykonaj A; w przeciwnym razie wykonaj B

Schemat instrukcji selekcji (alternatywny):

• Semantyka - wybór jednego z dwóch torów

• Notacje BNF

• Diagramy Niklausa Wirtha

Iteracja - wielokrotne powtarzanie grupy czynności aż do spełnienia warunku (ze znaną ilością powtórzeń/ze spełnieniem określonego warunku przed lub po wykonaniu działania)

Metoda czarnej skrzynki - weryfikacje poprawności algorytmu poprzez analizę uzyskanych wyników po zadaniu określonego zestawu danych wejściowych.

Wykład z 13-11-2007 Dane i ich reprezentacje

Rodzaje informacji - cyfrowe i analogowe. Informacją cyfrową nazywamy informację przedstawioną w postaci słów cyfrowych. Słowo cyfrowe to dowolny ciąg składający się z symboli 0 i/lub 1. W słowach cyfrowych wyróżnia się najstarszą i najmłodszą pozycję, tj. bit najbardziej i najmniej znaczący.

Dziesiętny system liczbowy:

Do zapisu dowolnej liczby system wykorzystuje dwa symbole (cyfry): 0 i 1
Dowolną liczbę w systemie dwójkowym możemy przedstawić jako następującą sumę:

20:2=10

10:2=5

5:2=2 reszta 1 kierunek odczytu

2:2=1

1:2=0 reszta 1

czyli 20_D=10100_B

Heksadecymalny - do zapisu dowolnej liczby system wykorzystuje 16 symboli (cyfr i liczb). Dowolną liczbę w systemie 16-tkowym możemy przedstawić jako sumę:

450:16 = 28 reszty 2

28:16 = 1 reszty 12 (C) 450_D=1C2_H

1:16 = 0 reszty 1

Kodowanie liczb i tekstu:

• Kody binarne - naturalny NKB, BCD, Gray'a

• Kodowanie - przyporządkowanie poszczególnym elementom zbioru kodowanego odpowiadających im elementów zwanych słowami kodowymi, przy czym każdemu słowu kodowemu musi odpowiadać dokładnie jeden element kodowany
  Kodem liczbowym nazywamy taki kod który liczbom dowolnego systemu będzie przyporządkowywał słowa kodowe w postaci zerojedynkowej
  Zbiorem kodowanym może być zbiór dowolnych obiektów.
  Proces kodowania może być opisem słownym wzoru.

Naturalny kod binarny (NKB)

Jeżeli dowolnej liczbie dziesiętnej przyporządkujemy odpowiadającą jej liczbę binarną to otrzymamy NKB.

Długość K słowa binarnego reprezentowanego przez liczbę dziesiętną A musi spełniać warunek: A<2^K<2A+1

Kodowanie znaków:

ASCII - to kod 7bitowy definiujący 128-elementowy zestaw znaków o wartościach kodowych od 0 do 127. Zestaw zawiera litery łacińskie (duże i małe), cyfry i znaki interpunkcji oraz różne znaki specjalne.

Kod ASCII rozszerzony, wprowadza dodatkowe 128 znaków wykorzystujących mało używany 8 bit.

Typy danych: dane elementarne (proste) i złożone (struktury danych).

Dane: para składająca się z nazwy i wartości; dane stałe i zmienne; deklaracja danych; inicjowanie danych - nadanie początkowej wartości; przypisanie wartości.

Struktury danych - konstrukcje języka programowego wykorzystywane do reprezentowania modeli danych.
Modele danych są implementowane za pomocą struktur danych i wykorzystujących je programów.

Modele danych:

• Abstrakcyjne modele danych

• Modele danych w aplikacjach

• Modele danych w językach programowania (logiczny, graficzny, relacyjny, drzewa, listy)

• Modele danych w edytorach tekstu (znaki, wierszy, akapity, strony, sekcje, operacje redagowania - modyfikacje wierszy, przesunięcia; zmiana formatu)

Podstawowe struktury danych:

• Statyczne (rekordy, tablice, zbiory)

• Dynamiczne (kolejki, drzewa)

Tablica - jest złożoną strukturą danych, która zawiera zbiór elementów tego samego typu. Każdy element tablicy jest identyfikowany przez jego numer (indeks) oraz posiada wartość.

Stos - struktura liniowa uporządkowanych danych które umożliwiają dostęp tylko do jednego elementu - ostatniego, który został wstawiony (wierzchołek).

Działania na nim można porównać do stosu talerzy: nie można usunąć talerza znajdującego się na dnie stosu nie usuwając wcześniej wszystkich innych. Nie można także dodać nowego talerza gdzieś indziej niż na samą górę. LIFO (last in - first out ).

Kolejka - struktura liniowo uporządkowanych danych w których dodawać nowe dane można jedynie na koniec kolejki, a usuwać z początku. Procedura usunięcia danych z końca kolejki jest taka jak w przypadku stosu, z 1 różnicą, że usuwamy dane od początku, a nie od końca. FIFO (first in - first out).

Wykład z 27-11-2007 Ewolucje programowania

Paradygmaty programowania:

• Programowanie proceduralne (imperatywne)

• Pr. Deklaratywne

• Pr. Obiektowe

• Pr. Strukturalne

• Pr. Funkcyjne

• Pr. Intencyjne

• Pr. Zdarzeniowe

• Pr. ekstremalne

Programowanie proceduralne:

Charakteryzuje się tym, że program musi zawierać pełen opis rozwiązywania problemu (algorytmu) w postaci sekwencji elementarnych czynności (instrukcji).

W programowaniu proceduralnym określa się JAK ma przebiegać proces przetwarzania, aby z wprowadzonych danych otrzymać żądane wyniki.

Z myślą o tym programowaniu zostały zaprojekt. języki: Fortran, Algol, Pascal, C.

Program składa się z 2 części:

• Deklaratywnej - opisuje się obiekty (dane), na których on działa

• Proceduralnej - opisuje się czynności (Instrukcje), które są wykonywane na tych samych danych

Punktem centralnym w programowaniu proceduralnym jest instrukcja.

Program musi zawierać szczegółowy opis kolejnych kroków postępowania zgodnie z przyjętym algorytmem - JAK przetwarzać.

Zaletą podejścia proceduralnego jest to, że wiele pojęć łatwiej jest zaprezentować w postaci procedur niż za pomocą np. deklaracji.

Programowanie deklaratywne:

Jest to styl programowania polegający na określeniu związków (relacji) pomiędzy danymi, a wynikami.

Wymagane jest określenie CO ma zostać przetworzone zamiast JAK ma przebiegać proces przetwarzania.

Omawiany styl programowania opiera się na logice.

Najbardziej popularnym językiem tej klasy jest PROLOG, w którym wykorzystywano klauzulową odmianę logiki (klauzulę Horna), ponieważ język klauzul jest prostszy niż standardowy język logiki.

Zadanie do rozwiązania przedstawione jest w postaci celu, natomiast fakty oraz reguły określają obiekty konieczne do rozwiązania danego problemu oraz związki, jakie między takimi obiektami zachodzą.

Fakt - bezwarunkowo prawdziwe stwierdzenie.

Reguła - warunkowe stwierdzenie o istnieniu pewnych zależności między obiektami.

Na przykład:

Fakt - dziecko (Kain, Ewa) oznacza ,że Kain jest dzieckiem Ewy.

Reguła - matka (X,Y):- kobieta (X), dziecko (X,Y) oznacza, że „X” jest matką „Y” jeśli „X” jest kobietą i „Y” dzieckiem „X”.

W arkuszu kalkulacyjnym - wzory (formuły), funkcja.

Zalety:

• Jest często bardziej ekonomiczne pod względem zapisu niż programowanie proceduralne - fakt zapisany jeden raz może być używany na różne sposoby, dzięki mechanizmowi wnioskowania

• Jest komunikatywne - w naturalny sposób definiowane są problemy

• Występuje minimalizacja składnika sterowania na rzecz logiki

Programowanie obiektowe:

Program jest opisem działania zbioru wzajemnie powiązanych obiektów. Obiekty kontaktują się ze sobą za pomocą komunikatów.

Programowanie obiektowe różni się od tradycyjnego programowania tym, że centralnym punktem jest obiekt, a nie instrukcja.

Obiekty:

Zawierają zarówno metody (funkcje), jak i pola (zmienne). Pojawienie się idei obiektu rozwiązało kilka problemów:

• Lepsze odzwierciedlenie świata rzeczywistego

• Ukrycie zmiennych przed wszystkimi metodami innych obiektów

Klasy:

Klasa stanowi specyfikację (wzorzec) jednego lub więcej obiektów. Często istnieje potrzeba tworzenia wielu obiektów tego samego typu (tej samej klasy). Np. klasa samochód. Obiekty: Ford, Mercedes, Toyota.

Klasy i obiekty:

• Tworzenie obiektów umożliwiają klasy

• Klasa - abstrakcyjna definicja jeszcze nie istniejącego obiektu określająca, jakie cechy charakteryzują dany obiekt i jakim operacjom obiekt ten można poddawać

• Gdy mamy zdefiniowaną klasę, powołujemy do życia obiekty podając konkretne wartości cech, jakie dany egzemplarz wyróżniają

• Na bazie jednej klasy na ogół powołujemy do życia wiele obiektów

Cechy programowania obiektowego:

• Abstrakcja

• hermetyzacja (enkapsulacja)

• dziedziczenie

• polimorfizm

Abstrakcja - programując abstrahujemy od szczegółów, które na danym etapie nie są istotne

Hermetyzacja (enkapsulacja) - wszystkie dane i funkcje w programie grupujemy wokół klas, udostępniając je jedynie upoważnionym przez nas klasom

Dziedziczenie - tworzenie pewnej klasy zwanej rozszerzoną (ang. Extended) na podstawie innej klasy, zwanej bazową (ang. Base class).

Dziedziczenie łatwo pozwala dodawać nowe cechy i możliwości do istniejących klas. Dzięki temu mechanizmowi można wykorzystać istniejące klasy do innych celów.

Polimorfizm - polega na traktowaniu obiektów różnych klas w ten sam sposób. Aby to było możliwe rozpatrywane klasy muszą być pochodnymi tej samej klasy bazowej.

W praktyce polimorfizm polega zwykle na wywoływaniu metody, która w rzeczywistości powoduje wykonanie różnych metod dla obiektów różnych klas.

Na przykład wywołanie metody obliczPole() dla obiektu klasy Kwadrat spowodowałoby wywołanie metody z klasy Kwadrat podczas gdy dokładnie to samo wywołanie ale dla obiektu klasy Prostokąt, wywoływałoby inną metodę obliczPole(), z klasy Prostokąt.

Polimorfizm upraszcza projektowanie i implementowanie programu.

Wywołana metoda na rzecz pewnego obiektu, nie musi być zdefiniowana bezpośrednio w klasie opisującej obiekt, ale w którejś z klas nadrzędnych.

Jeśli jednak z jakiegoś powodu metoda stworzona w klasie nadrzędnej nam nie odpowiada, możemy w nowo tworzonej podklasie zdefiniować nową wersję tej metody.

W trakcie wykonywania programu automatycznie dobrana zostaje metoda najbliższa obiektowi, na rzecz którego metoda została wykonana.

Wykład z 11-12-2007 Metodyki programowania

Programowanie ekstremalne - ma na celu wydajne tworzenie małych i średnich „projektów wysokiego ryzyka”, czyli takich, w których nie wiadomo do końca co się tak naprawdę robi i jak to prawidłowo zrobić. Przyświeca temu koncepcja prowadzenie projektu informatycznego, wywodząca się z obserwacji innych projektów, które odniosły sukces.

Podstawą ekstremalnego programowania jest synergia, wynikająca ze stosowania rozmaitych praktyk, które same w sobie mają wiele zalet, lecz mogą być trudne w zastosowaniu. Łączne użycie tych praktyk, ma zapewniać zaniknięcie niedogodności każdej z nich. Podstawowe założenia zostały sformułowane przez Kenta Becka.

Zalecenia:

• iteracyjność - program tworzy się w iteracjach (krótkie, przyrostowe kroki programistyczne) - i co ważniejsze - planuje tylko następną iterację.
  Efektem każdej iteracji (kilka tygodni), powinna być wersja programu spełniająca założenia dla danej iteracji. Następnie planuje się co zrobić dalej.

• nie projektować z założeniami z góry - nie można z góry powiedzieć, jaka architektura będzie najlepsza dla danego problemu. Dlatego należy ją tworzyć w miarę rozszerzania programu.

• testy zespołów - pisze się ja zanim w ogóle zacznie się pisać kod, najlepiej na początku iteracji. Potem pisze się kod, który potrafi je wszystkie przejść.
  Takie testy dają zapewnienie (o ile są dobrze napisane), że to co ważne zostanie zaprojektowane, na to zaś co nie jest ważne programiści nie będą tracić czasu.

• ciągłe modyfikacje architektury - architektura nie jest niczym, czego nie wolno ruszać. Jeśli modyfikacja architektury ułatwi przejście danej iteracji i nie zepsuje wyników testów uzyskanych na poprzednich, należy ją wykonać. Pod tą zasadę podlega także usuwanie wszystkich znanych błędów przed rozszerzeniem funkcjonalności.

• programowanie parami - danym kodem powinny się zajmować dwie osoby. Kod którym zajmuje się tylko jedna osoba ma tendencje do stawania się całkowicie niezrozumiałym dla kogoś innego niż autor, a więc dodatkowy programista zwiększa jakość kodu. Poza tym umożliwia to wyłapanie wielu błędów.

• stały kontakt z klientem - specyfikacje są prawie zawsze wieloznaczne, dziurawe i sprzeczne ze sobą. Tak więc należy mieć stały kontakt z tym, dla kogo to oprogramowanie jest tworzone (klient zamawiający program czy też użytkownicy końcowi). Jeśli kontakt jest dobry, można się obyć nawet bez specyfikacji.

Sprawy kontrowersyjne:

• brak dokładnej specyfikacji

• konieczna stała dostępność przedstawiciela klienta

Programowanie w cyklu kształcenia informatyków:

• programowanie, a projektowanie systemów informatycznych

• tworzenie aplikacji internetowych

• inżynieria programowania

• programowanie, a bazy danych

• programowanie, a inżynieria wiedzy

Złożoność algorytmów

Czynniki wpływające na złożoność algorytmów:

• rozmiar zadania - rozmiar danych niezbędnych do realizacji algorytmu. Bierze się pod uwagę: rozmiar danych wejściowych, roboczych i wyjściowych.

• Czas działania algorytmu - liczba kroków przekładająca się na czas faktycznej pracy maszyny realizującej algorytm. Istotne znaczenie mają w tym przypadku: złożoność rozwiązywanego zadania, spójność konstrukcji algorytmu, wydajność maszyny realizującej obliczenia.

Złożoność obliczeniowa algorytmów - analiza algorytmów:

• Złożoność obliczeniowa jest podstawową własnością określaną dla algorytmów

• Zadaniem analizy algorytmu jest określenie tej złożoności, a co za tym idzie realizowalności algorytmu

• Algorytmy realizowane mają złożoność aproksymowaną funkcją: liniową (wielomianem), logarytmiczną.
  Mówi się , że takie algorytmy określają zadania ze zbioru zadań rozwiązywalnych (a co za tym idzie implementowalnych). Najszybsze są algorytmy o złożoności logarytmicznej.

• Nie potrafimy skutecznie implementować algorytmów o złożoności wykładniczej.

Złożoność obliczeniowa algorytmu - ilość zasobów komputera jakiej potrzebuje dany algorytm. Pojęcie wprowadzili J. Hartmanis i R.Stearns. Najczęściej przez „zasób” rozumie się czas oraz pamięć, dlatego używa się określeń „złożoność czasowa” i „złożoność pamięciowa”.

Rodzaje złożoności algorytmu:

• Złożoność zasobowa (pamięciowa) - wyrażana w skali zajętości zasobów (PAO, pamięci zewnętrznych itp.) niezbędnych dla realizacji algorytmu.

• Złożoność czasowa - wyrażana w skali czasu wykonania algorytmu (liczba kroków, aproksymowany czas rzeczywisty).

• Wszystko przenosi się w konsekwencji na koszty eksploatacji oprogramowania, realizującego analizowany algorytm.

Funkcja kosztu zasobowego algorytmu - stanowi odwzorowanie zadania w umowne jednostki kosztu algorytmu (np. rozmiar zasobów, jednostki monetarne).

FKz : RZ -> WKz , gdzie FKz - funkcja kosztu zasobowego, Rz - rozmiar zadania, WKz - wartość kosztu zasobowego.

Nie tylko koszty zasobowe są brane pod uwagę. Często analizuje się inne koszty realizacji algorytmów (np. pieniądze).

Złożoność obliczeniowa - rozróżnia się 2 typy złożoności: pesymistyczną (czyli w najgorszym przypadku), oczekiwaną.

Notacja O(f(N)) oznacza złożoność algorytmu rzędu f(N), gdzie „f” to pewna funkcja zmiennej „N”. Jest to funkcja pomnożona przez pewną stałą, dlatego możemy powiedzieć, że np. wyszukiwanie w poprzednim algorytmie wymaga czasu O(N), a wstawianie elementu wymaga stałego czasu O(1).

Używając notacji O() nie jest ważny czas wyrażony w sekundach lecz zależność szybkości działania algorytmu od liczby elementów.

Najczęściej spotykane złożoności: O(1), O(logN), O(N).

Charakterystka wybranych języków programowania

Język programowania jest środkiem umożliwiającym zapis algorytmów w postaci zrozumiałej dla człowieka, a równocześnie przetwarzanej do postaci zrozumiałej dla komputera (maszyny algorytmicznej).

Kod źródłowy programu przetworzenie programu źródłowego w kod maszynowy kod wynikowy programu (w języku maszynowym).

Semiotyka języka programowania - zajmuje się badaniem symboli, znaków. W jej skład wchodzą:

• Semantyka, zajmująca się określeniem znaczenia programu zapisanego w określonym języku programowania

• Syntaktyka, zajmująca się określaniem przynależności danego słowa do zestawu określonego słownika języka programowania

Zapis algorytmu w języku programowania jest traktowany jako zapis formalny. Program komputerowy jest uznawany za jeden z rodzajów modeli matematycznych. Jest to algorytmiczny model zadania, czy też rzeczywistości, którą modelujemy.

Syntaktyka języka programowania - jest częścią ogólnej teorii znaków (semiotyki) i zajmuje się strukturą i formą wyrażeń, a także dopuszczalnymi zmianami ich formy (przekształceniami). Wyróżnia się 2 rodzaje reguł składniowych: reguły formowania (określające zbiór wyrażeń poprawnie zbudowanych na określonym alfabecie języka) i reguły przekształcania.

Najczęściej przyjmuje się, że mamy do czynienia z dwoma podzbiorami syntaktyki:

syntaktyką formalną (która jest rozumiana jako ogólne badania formalne dotyczące języków logiki i matematyki, jak również języków naturalnych) i syntaktyką logiczną (która zajmuje się badaniem języków logiki i matematyki, np. rachunek predykatów, rachunek zdań).

Zapis definicji syntaktyki programowania:

• Zapis Nackusa-Baura BNF (Backus-Naur Form). Został on po raz pierwszy zastosowany do opisu języka Algol60. Przykład definicji słownika w zapisie BNF:

<operator arytmetyczny> ::= + |-|*|/|^|DIV|MOD

<operator logiczny> ::= AND|OR|NOT|XOR|=

<nawias> ::=[|]|(|)|{|}|'|begin|end

• Diagramy syntaktyczne Wirtha - zestaw symboli jest zapisywany w DNF

Semantyka języka programowania zajmuje się interpretacją formuł zapisanych zgodnie z określonymi regułami syntaktycznymi języka. Tarski zaproponował używanie pojęcia semantyka naukowa dla określenia semantyki zajmującej się formalnym badaniem prawdziwości formuł w zakresie znaczeniowym definiowanego języka. Od lat 70-tych rozwija się tzw. semantyka wartości logicznych.

Kryteria (intuicyjne) oceny języków programowania:

• Prostota

• Łatwość nauczenia się

• Czytelność i zwartość struktur programowych

• Uniwersalność

• Modularność

• Niezależność od komputera

• Efektywność tłumaczenia programu źródłowego

Kod maszynowy

Jedyną zrozumiałą bezpośrednio dla komputera (mikroprocesora) formą przedstawiania instrukcji stanowią liczby binarne (dwójkowe), które dla lepszej czytelności dla człowieka zapisywane są często w postaci liczb szesnastkowych. Program zapisywany w takiej postaci jest nazywany kodem (językiem) maszynowym.

Pierwsza kolumna kodu przedstawia adresy pamięci operacyjnej, a pozostałe kolumny kody.

Języki wyższego rzędu

Niedogodności programowania w Asemblerze doprowadziły do powstania języków programowania wyższego rzędu.

Cechy tych języków:

• Istnieją standardy (wzorce) tych języków

• Są niezależne od sprzętu komputerowego

• Używają kompilatorów lub interpreterów

Pascal - nazwa języka wywodzi się od nazwiska matematyka Blaise'a Pascala, został opracowany w 1971r. na politechnice w Zurychu przez Niklausa Wirtha. Mocnymi stronami tego języka są: możliwość stosowania w nim technik programowania strukturalnego, szeroka klasa algorytmów dająca w sposób naturalny zapisywać się w nim, język jest ścisły ale jednocześnie prosty i czytelny, jest łatwo i efektywnie implementowany. Pascal jest powszechnie stosowany w nauczaniu programowania.

SQL - jest znany jako standardowy język programowania relacyjnych baz danych. Istnieje wiele wersji języka SQL, pierwsza z nich została opracowana w laboratorium IBM w San Jose. Język ten, nazwany pierwotnie Sequel, był stosowany jako część projektu System R, powstającego we wczesnych latach 70-tych. Język Sequel rozwinął się od tego czasu i jego nazwa została zmieniona na SQL (Structure Query Language - Strukturalny Język Zapytań). Większość obecnych systemów baz danych obsługuje język SQL.

C++ , jego autorem jest Bjarne Stroustrup, język powstał w 1979 r. Jest on nadzbiorem, z pewnymi wyjątkami, języka C. Najważniejszą cechą tego języka jest pojęcie klasy, jako typu definiowanego przez użytkownika. Klasy w C++ umożliwiają stosowanie technik programowania obiektowego. Zachowuje on jednak zdolność C do efektywnej współpracy z podstawowymi obiektami sprzętowymi (bitami, bajtami, adresami itp.). C++ jest językiem ogólnego przeznaczenia, jego podstawową dziedziną zastosowań jest programowanie systemowe.

Jest to język, którego nowe i różnorodne właściwości rozbudowane zostały na fundamencie istniejącej już składni - języka C. Z tego powodu jest on nazywany hybrydowym językiem obiektowym.

JAVA - platforma JAVA2 ma trzy wersje:

• J2SE (Standard Edition)

• J2EE (Enterprise Edition)

• J2MM (Micro Edition)

Platforma .NET

.NET jest platformą stworzoną Microsoft jako odpowiedź na dwa produkty firmy SUN - język JAVA i technologię J2EE.

.NET Framework składa się z maszyny wirtualnej (CLR) oraz biblioteki klas (CLI). Dzięki takiemu projektowi środowiska pojawiła się możliwość pisania programów w różnych językach i kompilacji ich do jednakowego kodu pośredniego (CLI).

Główne języki programowania: C#, Visual Basic, J#, C++

Mimo zapowiedzi Microsoftu, platforma .NET Framework nie jest w pełni przenośna, ponieważ działa jedynie na systemach z rodziny Windows. Dlatego powstały alternatywne projekty:

MONO czyli darmowa implementacja .NET rozwijana przez firmę XIMIAN

DotGNU portable .NET

Wykład z 08-01-2008 Programowanie z wykorzystaniem komponentów wielokrotnego użycia

Programowanie z użyciem wielokrotnym kodu

Założenia:

• W większości dziedzin tworzenie systemów jest oparte na wielokrotnym użyciu komponentów

• Podstawą projektów są komponenty, które wypróbowano i przetestowano

Użycie wielokrotne funkcji: można wielokrotnie użyć komponenty programowe takie jak pojedyncze funkcje matematyczne.

Użycie wielokrotne komponentów: można wielokrotnie używać komponentów programu użytkowego mających różne rozmiary od podsystemów do pojedynczych obiektów.

Użycie wielokrotne systemów programów użytkowych - można ponownie użyć cały system programów użytkowych przez włączenie go w niezmienionej postaci do innych systemów albo budowę rodziny programów użytkowych działających na różnych platformach lub dostosowanych do potrzeb użytkownika.

Praktyka programowania: użycie wielokrotne funkcji jest uznane w postaci standardowych bibliotek funkcji nadających się do wielokrotnego użytku takich jak biblioteki matematyczne czy graficzne.

Zalety użycia wielokrotnego:

• Zwiększona niezawodność

• Zmniejszone zagrożenie procesu

• Efektywne wykorzystanie specjalistów

• Zgodność ze standardami

• Przyspieszone tworzenie

Wymaganie stawiane tworzeniu oprogramowania z użyciem wielokrotnym:

• Musi istnieć możliwość znalezienia odpowiednich komponentów użycia wielokrotnego

• Osoba ponownie używająca komponent musi być przekonana że będzie on działał zgodnie ze specyfikacją i będzie niezawodny

• Komponenty muszą mieć dokumentację która pomoże osobie pragnącej je wykorzystać w zrozumieniu ich i zaadaptowaniu do naszych zastosowań

Koszty i kłopoty:

• Zwiększone koszty pielęgnacji

• Brak wspomagania narzędziowego

• Syndrom „nie wymyślono tutaj”

• Prowadzenie biblioteki komponentów

• Znajdowanie i adaptowanie komponentów użycia wielokrotnego

Podejścia do tworzenia programów z użyciem gotowych komponentów:

• Generowanie programów

• Tworzenie komponentowe

• Szkielety programów (frameworks)

• Wzorce projektowe

Generowanie programów: polega na umieszczaniu wielokrotnie używanej wiedzy w systemie generowania programów (w generatorze), który może posługiwać się językiem specyficznym dla dziedziny zastosowania.

W opisie programu użytkowego w abstrakcyjny sposób określa się które komponenty do wielokrotnego użycia mają być wykorzystane.

Typy generatorów:

• Generator programów użytkowych do przetwarzania danych gospodarczych

• Generator analizatorów składniowych do przetwarzania języków

• Generator kodu w narzędziach CASE

Programowanie komponentowe:

• Pojawiło się we wczesnych latach 90-tych w postaci podejścia do tworzenia systemów oprogramowania z użyciem wielokrotnym komponentów

• Przesłanką powstania było dostrzeżenie, że programowanie obiektowe nie doprowadziło do szerokiego stosowania wielokrotnego użycia jak się wcześniej spodziewano. Poszczególne klasy obiektów były zbyt szczegółowe i specyficzne. Musiały być dołączane do programów użytkowych w czasie kompilacji lub konsolidacji systemu. Do ich wykorzystania była potrzebna szczegółowa wiedza co zwykle oznaczało konieczność udostępnienia kodu źródłowego

• Powodowało to trudne problemy ze sprzedażą komponentów na rynku

• Wbrew własnym optymistycznym przewidywaniom nigdy nie powstał znaczący rynek pojedynczych obiektów

Komponenty:

• Niezależny, wykonywalny byt. Kod źródłowy nie jest dostępny, a zatem komponentu nie kompiluje się z innymi komponentami systemu

• Komponenty publikują swój interfejs, wszystkie interakcje odbywają się przez ten interfejs. Interfejs komponentu jest zapisywany w kategoriach parametryzowanych operacji. Jego wewnętrzny stan nie jest ujawniany

Interfejsy komponentów:

• Interfejs oferowany - definiuje się usługi oferowane przez ten komponent

• Interfejs wymagany - określa się jakie usługi muszą być dostępne w systemie używającego tego komponentu

Poziomy abstrakcji komponentów:

• Abstrakcja funkcyjna - komponent jest implementacją jednej funkcji

• Przypadkowe grupowanie - komponent jest grupą luźno powiązanych bytów

• Abstrakcja danych - komponent jest abstrakcją danych lub klasą obiektowego języka programowania

• Abstrakcja grupowa - komponent jest grupą powiązanych klas, które działają razem

• Abstrakcja systemowa - komponent jest całym samodzielnym systemem

Frameworks:

• Projekty podsystemów składających się z kolekcji klas abstrakcyjnych, klas konkretnych oraz interfejsu między nimi

• Poszczególne części systemu programów użytkowych implementuje się przez dodanie komponentów i sprawowanie konkretnych implementacji klas abstrakcyjnych zrębu programu

• Szkielety są rzadko programami użytkowymi

• Idea przygotowania szkieletów aplikacji wynika z rozwoju własnego warsztatu programisty

• Właściwy dla danej aplikacji kod stanowi jedynie część całego programu, reszta się powtarza i daje wielokrotnie zastosować w innych aplikacjach

Użycie wielokrotne produktów COTS: podejście produktów COTS może być zastosowane do każdego komponentu oferowanego przez zewnętrznego dostawcę.

Rodziny programów użytkowych:

• Zbiór powiązanych programów użytkowych które mają wspólną architekturę charakterystyczną dla dziedziny

• Poszczególne programy użytkowe są jednak na swój sposób wyspecjalizowane

Start

Stop

i=i+1

Int a,b,c

x>0

Tak Nie

x>0

Warunek powtarzania pętli

W

W R

R

R

W

Warunek powtarzania

pętli

W R

R

OSOBA

Student 1 roku

Student

Pracownik administracji

Pracownik naukowy

---