1 Matlab - obliczenia statystyczne Rekurencja Inne typy danych Wykład 5 INFORMATYKA 2 MPZI2 sem. 4 1
2 Sumowanie elementów wektora: sum(A) Sortowanie elementów wektora: sort(A) - rosnąco sort(A,'descend') - malejąco Liczba elementów wektora: length(A) Średnia arytmetyczna:mean(A) Mediana:median(A) Odchylenie standardowe:std(A) – dla próby std(A,1) – dla populacji Wariancja:var(A) – dla próby var(A,1) – dla populacji Wybrane funkcje statystyczne w Matlabie
3 3 Można sobie poradzić stosując iterację: clc, clear M=rand(1,100) suma=0; for k=1:length(M) suma=suma+M(k); end; suma srednia=suma/length(M) %sprawdzenie- funkcje wbudowane sum_s=sum(M) sr_s=mean(M) suma = 52.7994 srednia = 0.5280 sum_s = 52.7994 sr_s = 0.5280
4 4 Mediana to wartość środkowa zbioru. Wartość mediany wskazuje, że połowa wyników ma wartość poniżej wartości mediany, a druga połowa ma wartość powyżej wartości mediany. clc, clear M=rand(1,101); M=sort(M) %sortujemy rosnąco if rem(length(M),2)==1 med= M((length(M)+1)/2) else med= (M(length(M)/2)+M(length(M)/2+1))/2 end %sprawdzenie funkcji wbudowanej med_s= median(M) med = 0.5472 med_s = 0.5472 Mediana
5 5 Wariancja określa wielkość zróżnicowania wyników w zbiorze - czy różnice pomiędzy średnią a poszczególnymi wynikami są duże czy niewielkie. Odchylenie standardowe próby: Wariancja i odchylenie standardowe dla próby Badamy próbę, czyli podzbiór pełnego zbioru (całej populacji)
6 66 Odchylenie standardowe populacji: Wariancja i odchylenie standardowe dla populacji Badamy całą populację Wariancja populacji:
7 7 clear,clc N=100; % liczebność całej populacji M=rand(1,N); %średnia próby P=50;%liczebność próby sr_pr=sum(M(1:P))/P; s_pr=0; for k=1:P s_pr=s_pr+(M(k)-sr_pr)^2; end; war_pr=s_pr/(P-1); %WARIANCJA std_pr=sqrt(war_pr); %ODCHYLENIE STANDARDOWE fprintf('Wariancja dla próby=%f\n',war_pr) fprintf('Odchylenie dla próby=%f\n',std_pr) %sprawdzenie fprintf('war3_pr=%f\n',var(M(1:P))) %WARIANCJA fprintf('std3_pr=%f\n',std(M(1:P))) %ODCHYLENIE Obliczenia iteracyjne dla próby
8 8 Można też obliczać średnią geometryczną Do wyznaczania iloczynu wszystkich elementów wektora służyć może funkcja prod(M) Spróbować samodzielnie rozwiązać problem czyli
9 9 clc syms x sigma mi f=1/sqrt(2*pi*sigma)*exp(-(x-mi)^2/2/sigma^2) mi=0; %mediana sigma=1; f1=subs(f) ezplot(f1,[-4 4]) Rozkład Gaussa
10 Algorytmy rekurencyjne Wiele problemów obliczeniowych można zdefiniować rekurencyjnie. Rekurencja oznacza takie zdefiniowanie zagadnienia, gdzie w trakcie formułowania definicji odwołujemy się do niej samej. Przykładem definicji rekurencyjnej może być zapis całkowitej, nieujemnej potęgi rzędu n liczby rzeczywistej x: x n-1 *xdla n > 0(tu użycie definiowanej potęgi) 1dla n = 0 x n =
11 Rekurencja w językach programowania jest realizowana za pomocą podprogramów wywołujących kolejno same siebie ze zmienianymi parametrami wywołania. Aby podprogramy rekurencyjne działały poprawnie powinny zawierać warunek zakończenia rekurencji, aby wywołanie wykonywane było skończoną liczbę razy. Rekurencja daje proste programy lecz ma także wadę: każde wywołanie podprogramu wymaga wykonania przez procesor dodatkowych czynności, co spowalnia działanie programu oraz powoduje odłożenie na stos systemowy dużej liczby danych
12 function s= silnia (x) % Funkcja wyznacza silnię liczby x if x==1 s = 1; else s = silnia (x – 1)*x ; end ; {w definicji funkcji wykorzystanie samej funkcji} W Matlabie zapisalibyśmy tak: Matlab jednak nie dopuszcza takiej konstrukcji, a inne języki programowania dopuszczają
13 13 Typy danych Poznaliśmy… Liczbowe: x=4.6 y= 3+4i Tekstowe (łańcuchowe): x= 'Politechnika' Tablicowe (homogeniczne): x= [ 1 2; 4 5] y= ['a' 'b'; 'c' 'd' ] ten sam typ danych rzeczywiste zespolone Logiczne : x=true y=false
14 14 Tablice komórkowe (ang. cell - heterogeniczne ) Tablica, w której każdy element może być innego typu, w tym także typu złożonego. Zawartość takiej tablicy wpisujemy podobnie jak w tablicach homogenicznych lecz w nawiasach klamrowych { } (nie prostokątnych). oceny ={'fizyka', 3.5; 'informatyka', 4.0; 'mechanika',5.0} disp(oceny(1,1)) oceny = 'fizyka' [3.5000] 'informatyka' [ 4] 'mechanika' [ 5] 'fizyka'
15 15 Jej elementami są rekordy złożone z pól przechowujących wartości różnego typu i identyfikowanych przez swoje nazwy. W innych językach, w tym w językach obsługi baz danych, noszą nazwę typu rekordowego Tablice struktur (ang. struct)
16 Tablice struktur można definiować na dwa sposoby: a) Definiowanie z użyciem struct Przykład: student = struct('Nazwisko', 'Kowalski', 'Imie', 'Jan', 'Wiek', 23) b)Definiowanie przez przypisywanie wartości kolejnych pól. Nazwy pól oddzielamy kropką od nazwy tablicy lub jej elementu. W ten sposób możemy zarówno definiować pola nowej struktury jak i dodawać nowe pole do już istniejącego rekordu: student.grupa=1
17 17 Typ wyliczeniowy W innych językach programowania występują typy danych: I definicja zmiennej: Konieczna jest definicja typu dni_tygodnia=(pn, wt, sr, cz, pi, so, ni) x należy do typu dni_tygodnia x: dni_tygodnia Teraz w programie można używać zmiennej x: x = wt Wartość wt ma charakter abstrakcyjny (umowny) Zmienna przyjmuje jedną (!) wartość ze zbioru dopuszczalnych wartości
18 Typ zbiorowy to zbiór potęgowy danego typu porządkowego, czyli zbiór wszystkich podzbiorów tego typu. Zmienna typu zbiorowego może zatem zawierać zbiór pusty, jedno- lub wieloelementowy. Typ zbiorowy Zmienna typu zbiorowego zawierać może dowolny podzbiór elementów typu bazowego, od zbioru pustego do zbioru zawierającego wszystkie elementy.
19 Czyli: Zmienna typu liczbowego całkowitego może mieć wartość 1 lub 100 a nie może jednocześnie 1 i 100! Zmienna typu tablicowego może zawierać wiele wartości i nawet jak komórki są puste, to rezerwują pamięć komputera Zmienna typu zbiorowego może zawierać zero, jedną lub wiele wartości z danego zbioru Zmienne typu zbiorowego 1 5 719 4 8 34 67 69 88 100
20 Typ zbiorowy może być oparty na typie wyliczeniowym dzien = wt weekend= (so, nie) UWAGA: miesiac może przyjąć wartość tylko jednej z nazw – typ wyliczeniowy zmienna typu zbiorowego może przyjąć wartość dowolnego podzbioru z nazw bazowych – typ zbiorowy zmienna typu wyliczeniowego zmienna typu zbiorowego Przykłady: miesiac = luty kwartal1= (styczen, luty, marzec) zmienna typu wyliczeniowego zmienna typu zbiorowego
21 Operacje logiczne wykonywane na zbiorach to relacje (porównania): A = B równość zbiorów, te same elementy w obu zbiorach, A Bróżność zbiorów, różne elementy w obu zbiorach (chociaż niektóre mogą się powtarzać) A = Bzawieranie zbioru B w zbiorze A (true jeśli każdy element zbioru B jest w zbiorze A) c in A ma wartość logiczną - czy element c jest w zbiorze A Wartość logiczną sprawdzamy oczywiście wykorzystując instrukcję warunkową if
22 Czcionka w aplikacjach Windows definicja zmiennych (język Pascal) x, y, z: set of (pochylony, pogrubiony, podkreslony); Przykład : x= [ ] //zbiór pusty y= [pochylony, podkreslony] z= [pochylony, pogrubiony] wykorzystanie
23 +suma zbiorów –różnica zbiorów iloczyn zbiorów ( zbiór wspólny!!! ) x =(2, 3, 4) + (4, 5, 6) %wynik(2,3,4,5,6) y = (2, 3, 4) – (4, 5, 6) %wynik(2,3) v = (2, 3, 4) * (4, 5, 6) %wynik(4)(zbiór wspólny) y = v * x ;%przeanalizować wynik Operatory działań na zmiennych typu zbiorowego (znaczenie jak w teorii mnogości):
24 Podstawowe cechy programowania obiektowego
25 Programowanie strukturalne (proceduralne) – koncepcja tradycyjna. Główną jego składową są instrukcje działające na danych. Złożone programy korzystają z podprogramów (funkcji, procedur, a także modułów grupujących podprogramy) w celu uproszczenia zarządzania i kontroli nad programem, lecz nie zmienia to podstawowej koncepcji.
26 ■ dane są powszechnie dostępne – łatwo o błędy, ■ sekwencyjność wykonywania programu, ■ wszystkie sytuacje trzeba przewidywać i obsługiwać, ■ konieczność testowania po każdej zmianie, ■ wiele instrukcji, obszerny kod, trudność zrozumienia algorytmu Wady programowania strukturalnego
27 Zauważono „Kryzys oprogramowania” – programowanie strukturalne utrudnia panowanie nad bardzo złożonymi systemami informatycznymi SI (rozwój sprzętu wyprzedzał techniki budowania SI). Potrzebne były metody zwiększające wydajność i systematyczność tworzenia SI,a następnie ich wydajność. Poza tym powstały interfejsy graficzne (Windows)! Korzenie technologii obiektowej – lata 60-te, Nygaard i Dohl, Simula 1, Simula67 (1967).
28 OBIEKTOWOŚĆ – filozofia tworzenia na podstawie rzeczywistych zjawisk otaczającego świata (nie tylko język programowania). Obiekty (świata rzeczywistego a także systemu operacyjnego komputera – plik, ikona, przycisk, okno) – mają: właściwości (nazwa, kolor itp.), a także zbiory operacji na nich czy przez nie wykonywanych.
29 nie określa się jednak sposobów operacji na tablicach (np. dodawanie tablic), trzeba do tej operacji tworzyć własne kody lub korzystać z bibliotecznych podprogramów, których użycie wymaga szczegółowego zapoznania się z zestawem parametrów formalnych (sposób użycia). ■ wymiar ■ rozmiar ■ typ przechowywanych danych Np. typ tablica ma swoje cechy – atrybuty:
30 Stworzono tzw. ADT – abstrakcyjny typ danych – podążanie w kierunku naturalnego języka (zbliżenie do rzeczywistości), nazwano modułem (język Modula) lub klasą (język Simula). System reaguje na zdarzenia („siły sprawcze”), efektem są procesy: ■ funkcje przetwarzania parametrów obiektów ■ przesyłu informacji między obiektami ■ oddziaływania jednych obiektów na inne
31 Programowanie zorientowane obiektowo (OOP – Object Oriented Programming) umożliwia przedstawienie problemu w postaci logicznie powiązanych ze sobą struktur danych zwanych obiektami, wymieniających informacje między sobą. PROGRAMOWANIE OOP – podstawowe pojęcia „Obiektowość” opiera się na koncepcyjnym (intuicyjnym) klasyfikowaniu rzeczywistości. Na świat składają się obiekty i procesy w nich zachodzące.
32 KLASA = typ obiektowy=encja (entity) OBIEKT = instancja w klasie = reprezentacja w klasie, element przechowujący dane Podobnie jak typ zmiennej i zmienna Koncepcje (pojęcia)
33 Klasa (typ obiektowy) jest to złożona struktura danych o określonej liczbie atrybutów. Atrybuty klasy dzielimy na: pola metody
34 pola (fields) – atrybuty (właściwości opisane wartościami dowolnych typów, także strukturalnych) Pole jest to zmienna, która może być różnego typu. metody (methods) – funkcje wykonywane na polach. Metoda jest czynnością wykonywaną na obiekcie w postaci podprogramu (najczęściej funkcji). Metoda obiektu operuje na polach (danych) obiektu, przy ich pomocy mamy dostęp do pól. Czyli można powiedzieć, że typ obiektowy to typ rekordowy poszerzony o metody
35 Metoda jest to funkcja mająca deklarację w ramach typu obiektowego. Nazwa jest kwalifikowana, tzn. wskazuje na obiekt, którego dotyczy i ma postać: nazwa_obiektu.nazwa_metody(argumenty).. identycznie jak w strukturach czy rekordach
36 Konstruktor – specjalna metoda używana przy tworzeniu (instancji) obiektu danej klasy – zmienna typu obiektowego Destruktor – specjalna metoda wywoływana automatycznie tuż przed zakończeniem istnienia obiektu (niszczenie obiektu)
37 37 classdef Pies %definicja klasy Pies properties %właściwości nogi=4; ileHau = 0; end methods %metody function obj = Pies() % konstruktor end function Hau(obj) disp('hauuuuuuuuuu'); obj.ileHau = obj.ileHau + 1; end function ileNog(obj) disp(obj.ileNog); end Przykład – plik Pies.m
38 Na bazie powyższej definicji można wykonać nasz m-plik: clc,clear d=Pies; %utworzenie obiektu d.Hau(); %wykonanie metody d.Hau(); disp(d.ileHau); disp(d.nogi); hauuuuuuuuuu 3 4
39 //definicja klasy classdef Tczlowiek properties imie; wiek; waga=10; end methods function obj=Tczlowiek(); end function jedz(posilek); Tczlowiek.waga:=Tczlowiek.waga+posilek/20; end; aktywowanie metody jedz wpłynie na wagę obiektu osoba, należącej do klasy czlowiek Inny przykład osoba=Tczlowiek osoba.jedz(0.2);
40 Cechy obiektowości hermetyzacja polimorfizm dziedziczenie
41 Własność polegająca na dostępie do pól jedynie przy użyciu metod nazywa się hermetyzacją. Tworzy to dyscyplinę programowania, w jednym miejscu mamy dane i dozwolone operacje na nich. Ułatwia kontrolę poprawności złożonych programów. HERMETYZACJA
42 DZIEDZICZENIE niezależny, (zdefiniowany podobnie jak typ rekordowy) – rodzic drzewa jako potomek istniejącego. Wtedy mówimy, że obiekt dziedziczy wszystkie elementy (pola i metody) swojego przodka lub jest typem potomnym. Obiekty potomne mogą mieć własnego potomka (lub wielu). Typ obiektowy może on być:
43 Dziedziczność bezpośrednia – przodek jest niezależny (sam nie ma przodka) Dziedziczność pośrednia – przodek już dziedziczy (sam ma przodka) Wzajemne zależności obiektów układają się w drzewo hierarchii obiektów. polozenie = class{typ niezależny} x; y; end; punkt = class (polozenie){typ potomny} widocznosc; end; Przykład dziedziczenia klas:
44 Potomek może mieć tę samą nazwę metody jak przodek, „przykrywa” ona wówczas metodę przodka. Definiując metodę potomka (rozwijając ją lub modyfikując, np. gdy jest ona rozszerzeniem metody nadrzędnej), można odwołać się do metody dziedziczonej od przodka. Jest to tzw. POLIMORFIZM Polimorfizm (wielopostaciowość) - wykorzystanie tzw. metod wirtualnych. POLIMORFIZM
45 polozenie = class x y function przesun (nx, ny); x=x+nx; y=y+ny; end; end Przykład:
46 TYPY DYNAMICZNE Cel podstawowy – oszczędność pamięci, w języku Matlaba możemy zmieniać wielkość elementu Np. tablice są dynamiczne – możemy zmieniać rozmiary): Struktury w Matlabie też są dynamiczne – możemy dodawać nowe pola M=[1 1;2 2] M(3,3)=1; M 1 2 11 0 22 0 0 0 1 zwiększyliśmy rozmiar tablicy – w innych językach może to być niemożliwe bez stosowania typów dynamicznych (wskaźnikowych)
47 47 Do zbioru (uporządkowanego według określonej metody) możemy dołączać nowe elementy. Rozmiar elementu nie jest zdefiniowany, każde dołączanie nowego elementu powoduje nową rezerwację pamięci. Pobieranie elementu, jego usuwanie, dołączanie nowego elementu – mogą być obarczone pewnymi kryteriami dostępu. W językach programowania pozwalających na dostęp do pamięci stosuje się tzw. zmienne wskaźnikowe – wskaźnik jest logicznym adresem w pamięci ZASADY Zwykle istnieje też specjalny symbol, który określa wskazanie jako puste. W językach C jest to NULL, w C++ nullptr, w Pascalu nil
48 Lista jednokierunkowa dane adresdane adres dane adres dane nil koniec musi być znane wskazanie (adres) p początku listy Rodzaje typów dynamicznych Lista jednokierunkowa może być "w przód" lub "wstecz", czyli element może zawierać wskaźnik na następny lub poprzedni element.
49 Jest to liniowo uporządkowany zbiór składników, w którym dla każdego składnika (poza pierwszym i ostatnim), jest określony składnik poprzedni i następny. Dla ostatniego składnika listy dwukierunkowej jest określony tylko składnik poprzedni, a dla pierwszego tylko następny. dane wskaźnik na poprzedni wskaźnik na następny Lista dwukierunkowa
50 Jest to struktura danych, składająca się z liniowo uporządkowanych zbiorów składników (elementów), z których tylko ostatnio dołączony jest w danej chwili dostępny. Miejsce dostępu to wierzchołek stosu. Jest to jedyne miejsce, do którego można dołączyć lub z którego można usunąć elementy. FILO lub LIFO first in – last out last in - first out Stos (stack)
51 Jest t struktura danych, składająca się z liniowo uporządkowanych zbiorów składników, do której można dołączyć składnik tylko na jednym końcu (koniec kolejki), a usunąć tylko w drugim końcu (początek kolejki). Powiązanie między składnikami kolejki jest takie samo jak pomiędzy składnikami stosu. FIFO first in – first out Kolejka (queue)
52 jest strukturą danych, składającą się nieliniowo uporządkowanych zbiorów składników. Do każdego składnika można dołączyć jeden lub dwa składniki. Drzewo ma swój "korzeń" z którego wyrasta struktura. Drzewo binarne Drzewo binarne, w którym liczba synów każdego wierzchołka wynosi albo zero albo dwa, nazywane jest drzewem regularnym dane wsk_lewe wsk_prawe dane wsk_lewe nil dane wsk_lewe wsk_prawe dane nil dane nil dane nil
53 KONIEC