WPROWADZENIE DO INFORMATYKI PDF

POLITECHNIKA LUBELSKA WYDZIAŁ ELEKTROTECHNIKI I INFORMATYKI INFORMATYKA WPROWADZENIE DO INFORMATYKI  Algorytm ______________________________________________________________________________ Słowo algorytm pochodzi od nazwiska perskiego matematyka o nazwisku Chuwarizmi Al-Mu...

POLITECHNIKA LUBELSKA WYDZIAŁ ELEKTROTECHNIKI I INFORMATYKI INFORMATYKA WPROWADZENIE DO INFORMATYKI  Algorytm ______________________________________________________________________________ Słowo algorytm pochodzi od nazwiska perskiego matematyka o nazwisku Chuwarizmi Al-Muhammad Ibn Musa, które w formie zlatynizowanej brzmi Algorithmus. Urodził się on ok. 780 roku w Chorezmie, zmarł ok. 850 roku, matematyk, astronom, geograf i kartograf. Dzięki jego pracom: zaczęto stosować w Europie pochodzący z Indii dziesiętny system liczenia i pozycyjny system zapisu liczb, cyfry arabskie wyparły cyfry rzymskie w Europie, wprowadzono pojęcia zera, ułamków, funkcje trygonometryczne i elementy algebry.  Algorytmy i jego własności ______________________________________________________________________________ Algorytm jest to sposób rozwiązania danego problemu, podany w formie przepisu określającego skończoną liczbę operacji oraz kolejność w jakiej operacje te powinny być wykonywane. Program to algorytm zapisany w języku zrozumiałym dla komputera. Komputer rozwiązuje problemy dające się zapisać w postaci algorytmu. Własności algorytmu: określoność – znane są wszystkie przypadki, jakie mogą zaistnieć w czasie realizacji algorytmu, skończoność – wszystkie obliczenia zawarte w algorytmie powinny zostać zrealizowane w skończonej liczbie kroków, wykonalność – właściwe zdefiniowanie poszczególnych kroków algorytmu, tak aby możliwe było jego efektywne wykonanie. ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 3  Algorytmy ______________________________________________________________________________ Algorytm powinien się charakteryzować prostotą budowy: łatwiejsza implementacja, czytelniejszy kod , łatwość testowania, łatwość pisania dokumentacji. Algorytm powinien być efektywny i zoptymalizowany pod względem liczby wykonywanych działań. zajętość pamięci, czas potrzebny na jego wykonanie, obciążenie sieci komputerowej, liczba danych odczytywanych i zapisywanych na dysku. ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 4  Notacje zapisu algorytmów ______________________________________________________________________________ Język naturalny, zapis słowny pozwala określić kierunek działań i odpowiedzieć na pytanie, czy zagadnienie jest możliwe do rozwiązania. Lista kroków zapis bardziej konkretny, wymaga określenia danych i wyniku oraz zapisania kolejnych kroków. Zapis graficzny: schematy blokowe (N-S – Nassi Schneidermana) Pseudo-kod Języki programowania ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 5  Python ______________________________________________________________________________ def suma(a, b): return a + b # Driver code def main(): a = int(input("a = ")) b = int(input("b = ")) print("suma = ", suma(a, b)) if __name__ == "__main__": # __ double underscore main() Instrukcja if __name__ == "__main__": ma na celu sprawdzenie czy plik jest uruchamiany bezpośrednio.  Jeśli moduł jest uruchamiany bezpośrednio, jego zmienna __name__ jest ustawiona na __main__.  Jeśli moduł jest importowany wewnątrz innego modułu, jego __name__ jest ustawiana na nazwę modułu. ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 6  Algorytmy i ich rodzaje ______________________________________________________________________________ Algorytm liniowy ma postać ciągu kroków, które muszą zostać bezwarunkowo wykonane jeden po drugim. nie zawiera żadnych warunków ani rozgałęzień. Przykład Sformułowanie zadania: oblicz sumę S dwóch liczb naturalnych a, b. Dane wejściowe: dwie liczby a i b Cel obliczeń: obliczenie sumy S = a + b Dodatkowe ograniczenia: sprawdzenie warunku dla danych wejściowych np. czy a, b są naturalne, sprawdzenie warunków sprawia, że algorytm przestaje być liniowy. ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 7  Algorytmy i ich rodzaje ______________________________________________________________________________ Algorytm z rozgałęzieniem wymaga sprawdzenia pewnych warunków, zadanie jest wielowariantowe, w przypadku iteracji (pętli) liczba powtórzeń może być znana odgórnie lub zależeć od spełnienia pewnego warunku. Przykład wyznaczanie pierwiastków równania kwadratowego, wyznaczanie największego wspólnego dzielnika dwóch liczb naturalnych. ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 8  Instrukcje ______________________________________________________________________________ Sekwencja Instrukcje warunkowe (wariantowe) Instrukcje iteracyjne (pętle) 1966 r. – Corrado Bohm i Giuseppe Jacopini udowodnili, że te trzy rodzaje instrukcji wystarczają dla wyrażenia każdego sensownego algorytmu. Twierdzenie to stało się fundamentem strukturalnych metod i technik programowania. ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 9  Podstawowe symbole w schematach blokowych ______________________________________________________________________________ Początek, Koniec (Start, Stop) Przetwarzanie Proces uprzednio zdefiniowany WE / WY Decyzja Kierunek przepływu danych Łączenie dróg przepływu danych ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 10  Przykładowy schemat blokowy (sieć działań) ______________________________________________________________________________ ‘ ‘ ‘ ‘ ‘ ‘ ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 11  Schematy N-S – zapis algorytmu ______________________________________________________________________________ a Instrukcja WE, wczytanie a Instrukcja Przetwarzanie ’a=’,a Instrukcja WY, wydruk a Warunek Instrukcja warunkowa (dwuwariantowa) tak nie jeżeli Warunek to Instrukcje1 Instrukcje1 Instrukcje2 w przeciwnym razie Instrukcje2 ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 12  Sekwencja, instrukcje warunkowe ______________________________________________________________________________ Klatkę dzielimy liniami poziomymi na tyle prostokątów, ile zadań składa się na sekwencję Instrukcja1 Instrukcja1 a następnie Instrukcja2 Instrukcja2 a następnie Instrukcja3 Instrukcja3 Warunek Warunek tak nie tak nie Instrukcje1 Instrukcje2 Instrukcje1 dwuwariantowa z jednym wariantem pustym Jeżeli Warunek to Jeżeli Warunek to Instrukcje1 Instrukcje1 w przeciwnym razie Instrukcje2 ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 13  Instrukcje warunkowe – wybór wielowariantowy ______________________________________________________________________________ W1 W2 W3 Instrukcje1 Instrukcje2 Instrukcje3 Instrukcje4 1 a44 ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 14  Pętla „dopóki” ______________________________________________________________________________ Instrukcje Warunek Refren Konstrukcja schematu N-S dla konstrukcji iteracyjnej „dopóki” dopóki Warunek, dopóty Refren dopóki Warunek jest spełniony, powtarzaj Refren pętli ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 15  Pętla „aż do” ______________________________________________________________________________ Instrukcje Refren Warunek Konstrukcja schematu N-S dla pętli „aż do” powtarzaj Refren aż do chwili, gdy stwierdzisz, że Warunek jest spełniony ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 16  Schemat N-S – obliczanie BMI ______________________________________________________________________________ ’Obliczanie BMI’ masa wzrost masa>0 and wzrost>0 Tak Tak Nie Tak bmi = masa/(wzrost*wzrost)*10000 bmi < 20 Tak Nie ’bledne ’niedowaga’ bmi < 25 dane’ Tak Nie ’norma’ ’nadwaga’ ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 17  Schemat N-S – równanie kwadratowe ______________________________________________________________________________ ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 18  Sieć działań ______________________________________________________________________________ ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 19  Schematy N-S – zasady projektowania algorytmów ______________________________________________________________________________ Schematy N-S składają się ze zwartych bloków uniemożliwiają zapis skoków wewnątrz algorytmu, zmuszając programistę do myślenia strukturalnego. Sposób rozwiązania danego problemu zapisany w postaci schematu zwartego jest łatwiejszy do zrozumienia. Zapis algorytmu w postaci schematu N-S ułatwia sprawdzenie jego poprawności, programy pisane według tego schematu zawierają mniej błędów. Konstruowanie schematu zaczynamy od prostokąta symbolizującego cały algorytm, o wystarczająco dużych rozmiarach – cały arkusz z pozostawieniem marginesu na komentarze. Kolejne podziały klatki dokonujemy kolejno według schematu sekwencji, proporcjonalnie do przewidywanych rozmiarów zawartości. Również proporcjonalnie planujemy podziały liniami pionowymi. Nie umieszczamy zbyt wiele podklatek na jednym rysunku, w razie potrzeby wyodrębniamy podschematy dla większych fragmentów algorytmu. ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 20  Obliczenie objętości kuli ______________________________________________________________________________ print('Obliczanie objętości kuli') r = float(input('r= ')) pi = 3.14159265 v = 4.0/3.0 * pi * r * r * r print(v) ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 21  Wyznaczanie największej z trzech liczb ______________________________________________________________________________ print('Obliczanie maksimum') a = int(input('a= ')) b = int(input('b= ')) c = int(input('c= ')) if a > b: if a > c: print(a) else: print(c) else: if b > c: print(b) else: print(c) ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 22  Pętla „dopóki” ______________________________________________________________________________ n n 0’ n n = int(input('n= ')) while n max Tak Nie max = a k = k + 1 ’Max = ’, max ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 32  Obliczanie ilości liczb dodatnich ______________________________________________________________________________ n ile = 0 k = 0 k < n a a > 0 Tak Nie ile = ile + 1 k = k + 1 ’Ile dodatnich = ’, ile ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 33 POLITECHNIKA LUBELSKA WYDZIAŁ ELEKTROTECHNIKI I INFORMATYKI INFORMATYKA Materiały zostały opracowane w ramach projektu „Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga”, umowa nr POWR.03.05.00-00-Z060/18-00 w ramach Programu Operacyjnego Wiedza Edukacja Rozwój 2014-2020 współfinansowanego ze środków Europejskiego Funduszu Społecznego ______________________________________________________________________________ Zintegrowany Program Rozwoju Politechniki Lubelskiej – część druga 34