1 Wykład 6 Inżynieria programowaniaInżynieria Środowiska Wykład 6 Inżynieria programowania

2 ALGORYTMY Algorytm jest to sformalizowany ciąg logicznie powiązanych instrukcji (poleceń, rozkazów), których wykonanie pozwoli na przetworzenie informacji wejściowych (danych) w informacje wyjściowe (wyniki). Algorytm - rozwiązywanie "krok po kroku" dowolnego problemu.

3 Algorytm ma przeprowadzić system z pewnego stanu początkowego do pożądanego stanu końcowego.Badaniem algorytmów zajmuje się algorytmika.

4 Każdy algorytm komputerowy musi być wprowadzony do komputera w bardzo rygorystycznie zdefiniowanym języku - jednoznaczne instrukcje. Jeżeli dany algorytm da się wykonać na maszynie o dostępnej mocy obliczeniowej i pamięci oraz akceptowalnym czasie, to mówi się że jest to algorytm obliczalny. Algorytm – przepis niezależny od implementacji (NARZĘDZIA) Program – zastosowanie algorytmu w języku zrozumiałym przez komputer

5 Czynności służące do rozwiązania zadania:analiza treści zadania wykaz danych wejściowych; wiadomych i niewiadomych oraz relacji między nimi sprawdzenie czy zadanie posiada jednoznaczne rozwiązanie wybór metody rozwiązania zadania opis czynności dla wybranej metody rozwiązania sporządzenie i przedstawienie wyników rozwiązania zadania

6 Sposoby zapisu algorytmówOpis słowny - przedstawienie kolejnych czynności (akcji) na elementach (danych). Przykład:przepis kulinarny Schemat blokowy – operacje na danych przedstawione graficznie w postaci elementarnych bloków.

7 ZASADY BUDOWY SCHEMATU BLOKOWEGO1) Każda operacja jest umieszczona w bloku 2) Schemat ma tylko jeden blok "START" i przynajmniej jeden blok "STOP" 3) Bloki mają połączenia ukierunkowane 4) Z bloku wychodzi jedno połączenie; wyjątki - "STOP" (nie wychodzą żadne połączenia) - blok "warunkowy" ( wychodzą dwa połączenia opisane TAK i NIE) 5) W bloku "operacyjnym" odbywa się nadanie wartości (przypisanie) znak :=

8 Reguły graficzne tworzenia schematów blokowychStart Stop START STOP Operacje wejścia i wyjścia wczytaj a,b,x pisz suma, wynik Instrukcja wykonawcza (proces) blok operacyjny Blok decyzyjny oblicz suma:=a+b TAK ? suma>0 Łącznik stronicowy NIE 1

9 Klasy problemów Metodykaalgorytmy obliczeniowe ( - np. całkowanie numeryczne, obliczanie funkcji z sumy wyrazów ciągu, wyznaczanie liczb pierwszych, zamiana systemów liczbowych itp.) algorytmy sortujące algorytmy wyszukujące algorytmy kompresji Metodyka algorytm "krok po kroku" algorytmy rekurencyjne algorytmy genetyczne algorytmy sztucznej inteligencji

10 Dla utworzenia algorytmu konieczne są:• opis obiektów do przechowywania danych wejściowych, danych pośrednich i wyników • opis czynności jakie należy wykonać z obiektami, co realizujemy przy pomocy instrukcji, które opisują: sposób działania kolejność ich wykonywania ewentualne warunki jakie muszą być spełnione • opis wyników - zawiera sposób udostępnienia wyników rozwiązanego zadania

11 Aby zatem tworzyć działające programy wymagane są:jakaś metoda wprowadzania i przechowania danych (liczb, tekstów itp.) jakieś instrukcje, które umożliwią obliczenia wyników jakieś metody pokazania wyniku

12 Rodzaje sieci działań:Proste (sekwencyjne) - kolejność realizacji poszczególnych operacji jest ściśle określona i żadna z nich nie może być pominięta ani powtórzona - nie używa się bloków warunkowych. Z rozwidleniem - zawiera w sobie wybór jednej z kilku możliwych dróg realizacji danego zadania, istnieje przynajmniej jeden blok warunkowy. Z pętlą, często w trakcie realizacji zadania konieczne jest powtórzenie niektórych operacji różniących się zestawem danych. Pętla obejmuje tę część bloków, która ma być powtarzana. Złożone - będące kombinacją powyższych sieci.

13 Przykład W algorytmach sortujących potrzebny jest mechanizm zamiany wartości umieszczonych w dwóch zmiennych, jeśli są w niewłaściwej kolejności Algorytm wymaga zmiennej pomocniczej (jak do zamiany zawartości dwóch szklanek potrzebna jest trzecia szklanka) Opis słowny: 1. Wczytaj dane do obiektów 1 i 2 2. Przepisz zawartość obiektu 1 do obiektu pomocniczego 3. Przepisz zawartość obiektu 2 do obiektu 1 4. Przepisz zawartość obiektu pomocniczego do obiektu 1 5. Wyprowadź wartości obiektów 1 i 2

14 schemat blokowy zamiany wartości w dwóch zmiennychwczytaj a,b schemat blokowy zamiany wartości w dwóch zmiennych pom:=a a:=b b:=pom drukuj a, b

15 obiekt pomocniczy 3 1 B A 2

16 Przykład 2 – z blokiem decyzyjnym i pętląIle razy trzeba podzielić na pół daną liczbę, aby uzyskać wartość mniejszą od  Opis słowny: Wczytaj liczbę i  Ustal wartość licznika równą 0 3. Podziel liczbę przez 2 4. Zwiększ licznik o 1 5. Sprawdź czy wynik jest mniejszy od , jeśli tak, to przejdź do punktu 6, jeśli nie to wróć do punktu 3 6. Wyprowadź wartość licznika

17 czy algorytm jest poprawny??liczba:=liczba/2 wczytaj liczba,  licznik:=0 licznik:=licznik+1 drukuj licznik liczba<  TAK NIE schemat blokowy czy algorytm jest poprawny??

18 A może tak lepiej? licznik:=0 liczba:=liczba/2 licznik:=licznik+1wczytaj liczba,  licznik:=0 drukuj licznik liczba<  TAK NIE licznik:=licznik+1 A może tak lepiej?

19 Widzimy, że potrzebna jakaś ocena poprawnościA może jeszcze inaczej? Który z tych trzech algorytmów jest poprawny? wczytaj liczba,  licznik:=0 licznik:=licznik+1 liczba:=liczba/2 NIE liczba<  TAK Widzimy, że potrzebna jakaś ocena poprawności drukuj licznik

20 A więc, aby tworzyć efektywne algorytmy i móc je aplikować programowo, potrzebne są następujące elementy: Spektrum obiektów programowych, możliwość ich odróżniania, klasyfikacja do typu, umieszczanie ich identyfikatorów (nazw) i wartości w pamięci Spektrum operacji (operatorów nadawania wartości, arytmetycznych, porównania) – operacje na obiektach! Mechanizm sterowania – co wykonać następnie po aktualnej operacji

21 Optymalny algorytm wyszukiwania indeksu najmniejszego elementu (czyli numeru elementu)1. Umieszczamy elementy w obiektach od x[1] do x[n] 2. Zmiennej pomocniczej min przypisujemy 1 3. Dla zmiennej i od 2 do n-1 z krokiem co 2 wykonujemy: Zmiennej pomocniczej min_lok przypisujemy indeks mniejszej liczby z pary x[i], x[i+1] (czyli przypiszemy i lub i+1) jeśli element x[min_lok] jest mniejszy (w sensie użytego operatora) od elementu x[min], to zmiennej min przypisujemy wartość min_lok 4. Jeśli n jest liczbą nieparzystą, to kończymy algorytm. Jeśli n jest liczbą parzystą to wykonujemy: jeśli element x[n] jest mniejszy (w sensie użytego operatora) od elementu x[min], to zmiennej min przypisujemy wartość n i kończymy algorytm

22 1 2 3 4 5 … min_lok min_lok

23 Podstawy programowaniaDo 1954 roku – język maszynowy (Eniac, Mark I- USA) – niskiego poziomu - dla Kodowanie instrukcji procesora w postaci ciągu liczb dwójkowych (elementarny rozkaz i dane) -        pracochłonność (same liczby, długie algorytmy działań takich jak dodawanie i mnożenie) – np. rzymskie -        trudność śledzenia błędów

24 lata 50-te - zastąpienie kodów liczbowych operacji nazwami mnemotechnicznyminp. mnożenie MPY (multiply) język symboliczny - assembler ASSEMBLER – także program tłumaczący na kod maszynowy (wewnętrzny) DISSASSEMBLER – tłumaczenie odwrotne Cechy Assemblera -         wąski zbiór rozkazów, prymitywna architektura ówczesnych komputerów, brak rejestrów (pamięci pomocniczych), brak operacji zmiennoprzecinkowych

25 1954 –języki tzw. wysokiego poziomu(kod maszynowy i assembler to niski poziom – bliższy procesorowi) Zapis operacji w sposób łatwiejszy, zrozumiały i dobrze kontrolowany przez programistę Po stworzeniu kodu programu w języku następuje proces translacji (tłumaczenia, kompilacji) na język wewnętrzny komputera.

26 Problemy: - zrozumiałość - jednoznaczność - skuteczność tłumaczeniaJęzyki wysokiego poziomu po etapie początkowym stały się maszynowo niezależne z powodu wielu wersji translatorów (programów kompilujących) Kompilator (ang. compiler) to program służący do tłumaczenia kodu napisanego w jednym języku (języku źródłowym) na równoważny kod w innym języku (języku wynikowym). Najczęściej jest to tłumaczenie z języka wysokiego poziomu (łatwiejszego dla programisty) ma język wewnętrzny procesora. Proces ten nazywany jest kompilacją.

27 Języki wysokiego poziomuCOBOL – dla przedsiębiorstw, język prawie naturalny (ang) MULTIPLY – mnożenie, ADD – dodawanie, czy dobrze?? Do dziś specjaliści potrzebni (w USA 500 $/godz za zmiany daty w 2000) W kolejnych latach - obfitość języków programowania BASIC, LOGO – prostota, interpretacja w odróżnieniu od kompilacji, tłumaczenie „na bieżąco” każdej instrukcji a nie programu w całości PASCAL, C, C+, C++ - języki strukturalne z elementami tzw. programowania obiektowego OOP (Object Oriented Programming) – języki zorientowane obiektowo (PROLOG, Visual Basic, Delphi, Java, C#)

28 Program - algorytm zapisany w języku programowaniaOBIEKTY - dane dana (nazwa danej, wartość danej) deklaracje, definicje - opisy obiektów instrukcje - czynności na obiektach Program - algorytm zapisany w języku programowania

29 Podprogram - wyodrębniona część programu (ze względu na czytelność lub wielokrotne użycie) posiadająca wyodrębnioną nazwę i sposób wymiany informacji z pozostałymi jego częściami

30 Deklaracja podprogramu - opis podprogramuInstrukcja wywołania podprogramu – wykonanie, zastosowanie podprogramu wewnątrz programu głównego lub innego podprogramu Kod źródłowy - tekst programu w języku programowania (plik tekstowy pas) Kompilacja - tłumaczenie (w całości) kodu źródłowego na wykonywaną postać binarną, ładowalną (plik exe) – odrębny proces Interpretacja – tłumaczenie kolejnych instrukcji w trakcie procesu wykonywania

31 Przetwarzanie programu użytkowegoKomunikaty o błędach PROGRAMISTA EDYCJA Kompilacja Wykonanie postać źródłowa programu ładowalna dane wyniki parametry

32 Przykładowy język JavascriptJavaScript jest to interpretowany, zorientowany obiektowo, skryptowy język programowania. JavaScript jest oddzielnym językiem (nie jest uproszczoną wersją Javy). Może być osadzany w innych programach, na przykład w przeglądarce internetowej, aby, mając dostęp do obiektów otoczenia (np. modelu obiektowego przeglądarki internetowej - DOM), można sprawować nad tym otoczeniem kontrolę. Javascript jest łatwy w nauce i pozwala na pewne „zdynamizowanie” stron internetowych. Przeglądarki mogą pytać o zezwolenie na wykonanie skryptu.

33 Wstawienie skryptu do dokumentu HTMLSkrypty JavaScript są zagnieżdżane w dokumentach HTML. Skrypt JavaScript umieszczane są między znacznikami . { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.pl/1217397/3/images/33/Wstawienie+skryptu+do+dokumentu+HTML.jpg", "name": "Wstawienie skryptu do dokumentu HTML", "description": "Skrypty JavaScript są zagnieżdżane w dokumentach HTML. Skrypt JavaScript umieszczane są między znacznikami i .

34 Może istnieć wiele skryptów naprzemiennie z pozostałym kodem HTML

To jest tekst 1