Programowanie Komputerów
Prof. Dr hab. Jerzy Gołuchowski
Programowanie (w szerszym znaczeniu ):
Jest to jednoznaczne formułowanie zdań oraz sposobu ich rozwiązywania za pomocą komputera prowadzące do wykonania szeregu czynności.
Czynności składające się na proces programowania:
- Sformułowanie problemu
- Określenie metody rozwiązania
- Dyskusja warunków istnienia rozwiązania
- Tworzenie sieci działań
- Kodowanie algorytmu w wybranym języku programowania
- Uruchomienie testowe
- Opracowanie dokumentacji
Programowanie ( w węższym znaczeniu ):
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) w informacje wynikowe (wyniki).
Problemy związane z opracowywaniem algorytmów:
- Przed opracowywaniem algorytmu powinniśmy stwierdzić, czy zdanie posiada rozwiązanie i czy rozwiązanie jest jednoznaczne.
- 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 opracowywaniu algorytmu zakłada się pewien poziom szczegółowości, na którym formułuje się algorytm.
- Algorytm powinien uwzględniać wszystkie teoretyczne warianty przebiegu obliczeń zaistniałe z powodu różnego doboru danych wejściowych.
- Algorytm musi by kompletny.
Etapy opracowywania programu:
1. Analiza problemu i sformułowanie algorytmu.
2. Zakodowanie algorytmu w języku programowania.
3. Wprowadzenie tekstu programu źródłowego do komputera.
4. Tłumaczenie programu.
5. Testowanie i ewentualne poprawienie błędów formalnych ( składniowych ) wykrytych w kroku 4 i ponowne tłumaczenie programu.
6. Uruchomienie programu i poprawienie błędów logicznych.
7. Opracowanie dokumentacji.
Kodowanie algorytmu w języku programowania:
Jako ograniczenia zawężające możliwości wyboru języka przyjmuje się m.in.:
- Klasę problemu.
- Kwalifikacje programisty.
- Struktury danych.
- Dostępność translatora języka.
Cechy dobrego programu:
- Poprawny - „ testowanie może wykazać obecność pomyłki, nigdy nie może zaś wykazać nieobecności błędu”.
- Przystosowywalny – modularna budowa.
- Odporny - na błędy użytkownika.
- Stabilny – nie „załamuje się” w przypadku prostego błędu danych wejściowych.
- Optymalny – minimalizujący zajętość pamięci i czasu pracy procesora.
System programowania ( środowisko programistyczne – zawierające co najmniej translator języka ):
- Język programowania.
- Translator.
Systemy programowania obejmują:
- Edytory do zapisu programu źródłowego.
- Narzędzia do testowania i uruchamiania programów ( debugger ) pozwalające wykrywa 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 ).
Rodzaje środowisk programistycznych:
- Testowe.
- Graficzne.
Język programowania:
Zbiór symboli oraz reguł syntaktycznych i normatycznych stosowanych w trakcie definiowania sposobu przetwarzania określonego zadania.
Elementy języka programowania:
- Alfabet - czyli zbiór określonych symboli, z których będą tworzone słowa i zdania w tym języku.
- Składnia ( syntaktyczna ) - czyli reguły tworzenia poprawnych zdań ( instrukcji ) tego języka.
- Reguły znaczeniowe ( semantyka ) - interpretujących znaczenie poszczególnych zdań i konstrukcji języka.
Translacja programu:
Programy z reguły są pisane w językach programowania łatwo zrozumiałych przez człowieka, natomiast niezrozumiałych dla komputera. Dlatego konieczny jest proces tłumaczenia języka źródłowego w jakim napisany jest program na język docelowy zrozumiały przez maszynę.
Translacja – proces tłumaczenia programu źródłowego na wynikowy. Translacji dokonuje się przeważnie przez:
- Interpretację – przez interpretery.
- Kompilację – przez kompilatory.
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 dowolnym sprzęcie.
Kompilacja
Kompilator analizuje program napisany w określonym języku programowania( program źródłowy ) i tłumaczy go na równoważnie funkcjonalnie program w języku wewnętrznym ( program wynikowy ).
Jeśli proces tłumaczenia zakończy się poprawnie to w dalszej pracy nad programem, czyli w trakcie jego testowania pracuje się z wersją wynikową, program wynikowy może być uruchomiony na każde żądanie bez konieczności ponownego tłumaczenia.
Kompilacja – proces automatycznego tłumaczenia kodu napisanego w języku programowania na drugi. Kod źródłowy – dane wejściowe. Tłumaczenie języka z wyższego poziomu na język niższego poziomu. Odwrotny proces to dekompilacja.
Polega na przekształceniu programu źródłowego na równoważny program wyrażony w języku maszynowym przed jego uruchomieniem. Następnie uruchamia się już skompilowany program.
Przykłady języków: Pascal, Fortan, C, ...
Interpretator pobiera kolejne instrukcje programu, sprawdza ich poprawność, rozpoznaje jakie czynności należy wykonać i wykonuje je.
- Każde uruchomienie programu wymaga jego tłumaczenia !!!
- Programy interpretowane działają bardzo wolno w porównaniu z programami kompilowanymi.
- Zaletą interpretacji jest możliwość wykonania tylko fragmentu programu – łatwe lokalizowanie błędów i nanoszenie poprawek.
1. Interpreter analizuje postać znakową każdej instrukcji języka źródłowego i tłumaczy ją na kod maszynowy za każdym razem, gdy instrukcja ta jest wykonywana.
2. Jeśli dana instrukcja wykonywana ma być wielokrotnie, lepszym podejściem jest analizowanie postaci znakowej tylko raz i zastąpienie jej ciągiem symboli łatwiejszym do interpretacji.
Interpretacja – przekształcanie ( translacja ) instrukcji programu na bieżąco do kodu maszynowego lub innej formy pośredniej i natychmiastowe ich wykonywanie. Zmusza to do ustawicznego tłumaczenia instrukcji, co wielokrotnie wydłuża czas działania programu. Zaletą jest natomiast łatwość dokonywania zmian w programie w trybie konwersacyjnym.
- Nadawanie informacjom wejściowym nowych znaczeń na wyjściu. Bezpośrednie przetwarzanie informacji ( danych ) w działania.
- Reinterpretacja – ponowna interpretacja.
Testowanie – w praktyce testowanie programu na wszystkich możliwych danych teoretycznych jest niemożliwe. Najczęściej stosuje się test:
- Funkcjonalny.
- Według oceny użytkownika.
- Według struktury programu.
Algorytmy:
1. Wstęp.
2. Rodzaje algorytmów.
3. Metody zapisu.
4. Złożoność.
5. Przykłady algorytmów sortowania.
Podstawowe pojęcia algorytmów:
- Określenie dziedziny algorytmiki.
- Klasyfikacja algorytmów.
- Własności algorytmów.
- Konstrukcje algorytmiczne w językach programowania.
- Metody weryfikacji algorytmów.
- Pojęcie złożoności obliczeniowej algorytmów.
Algorytmika – nauka o algorytmach:
- Jest dziedziną wiedzy zajmującą się badaniem algorytmów.
- W informatyce jest ona nieodłącznie związana z algorytmami przetwarzania struktur danych.
Dzisiejsze pojęcie algorytmu:
Dzisiejsze, uogólnione znaczenie słowa „algorytm” zastosowano w zasadzie dopiero w 20-stym stuleciu, kiedy to algorytm zaczął być rozumiany jako:
Zbiór reguł postępowania umożliwiający rozwiązanie określonego zadania w skończonej liczbie kroków i w skończonym czasie.
Każdy algorytm:
1. Posiada dane wejściowe:
- ( w ilości większej lub równej zero ) pochodzące z dobrze zdefiniowanego zbioru.
2. Zwraca pewien wynik:
- ( nie koniecznie numeryczny).
3. Jest precyzyjnie zdefiniowany:
- ( każdy krok algorytmu musi być jednoznacznie określony).
4. Jest zbieżny:
- ( dla każdego dopuszczalnego zbioru danych początkowych liczb operacji prowadzących do poszukiwania wyniku jest skończona).
Pochodzenie słowa algorytm:
Słowo algorytm pochodzi od łacińskiego „algorism”, co w średniowieczu było rozumiane jako sztuka rachowania na liczbach w systemie decymalnym. Słowo „algorism” zostało utworzone od nazwiska perskiego matematyka z 9-tego wieku n.e., tj. Muhameda ibu-Musy al.- Choresmi, twórcy systemu dziesiętnego i zasad działania na liczbach dziesiętnych w sposób „ mechaniczny”.
Przykłady algorytmów:
· Programowanie matematyczne:
- Algorytmy rozwiązywania zadań liniowych ( programowanie liniowe ).
- Programowanie dynamiczne, ...
· Sztuczne inteligencja, wspomaganie podejmowania decyzji:
- Sieci neuronowe.
- Algorytmy genetyczne.
- Metody symulacyjne.
· Przetwarzanie danych:
- Wstawianie, wyszukiwanie i usuwanie elementów ze struktur danych.
- Sortowanie struktur danych.
- Reorganizacja struktur danych, ...
· Systemy operacyjne:
- Równoważenie obciążenia w dostępie do zasobów w systemach rozproszonych i nierozproszonych.
- Synchronizacja procesów współbieżnych.
- Usuwanie nieużytków z pamięci operacyjnej, ..., itp. ..., itd. ...
Sposoby zapisu algorytmów:
Algorytm powinien precyzyjnie przedstawiać kolejne jego kroki. Do opisu tych kroków mogą być stosowane następujące sposoby:
· Zapisy werbalne.
· Zapisy formalne np.:
- Zapisy graficzne ( schematy blokowe ).
- Formalne specyfikacje programów ( VDM, CSP).
- Zapisy w postaci pseudokodów ( „paraprogramów” ).
- Implementacje w dowolnym języku programowania.
Algorytm liniowy ( sekwencyjny ):
Składa się z ciągu instrukcji, które wykonywane są jedna po drugiej w kolejności, jaka wynika z ich następstwa w zapisie algorytmu.
Np.: Gotowanie jajka :
- Wlanie do garnka zimnej wody.
- Zapalenie gazu.
- Podgrzewanie wody do wrzenia.
- Włożenie jajka.
- Odczekanie odpowiedniego czasu ( 5 min ).
- Zgaszenie gazu.
- Wyjęcie jajka.
Algorytm nieliniowy:
Większość algorytmów ma rozbudowaną strukturę. Często występują w nich instrukcje, których wykonanie uzależnione jest od spełnienia określonego warunku lub też spełnienie pewnego warunku powoduje wykonanie jednej instrukcji, a niespełnienie go innej.
Algorytm nieliniowy może zawierać następujące elementy konstrukcyjne:
- Selekcję.
- Iterację.
halucek89