Systemy pozycyjne – metody zapisywania liczb w taki sposób, że w zależności od pozycji danej cyfry w ciągu, oznacza ona wielokrotność potęgi pewnej liczby uznawanej za bazę danego systemu. Algorytm – skończony zbiór reguł wskazujący kolejność operacji dla rozwiązania zadanego problemu. Cechy alg. • skończoność (wykonywanie al. kończy się po skończonej liczbie kroków) • poprawne zdefiniowanie (każdy krok al. opisany jest precyzyjnie i jednoznacznie) • efektywne zdefiniowanie (operacje al. jak najprost., wykonywane w najkrótszym czasie) • dane wejściowe (wartości znane przed rozpoczęciem działania al. lub dodane w czasie) • dane wyjściowe (al. generuje dane wyjściowe, powiązane w pewien sposób z wejść.) Fazy procesu rozwiązywania problemów •Sformułowanie problemu (specyfikacja) •Analiza problemu i znalezienie metody jego rozwiązania, tzn. algorytmu •Zakodowanie algorytmu (napisanie programu) •Uruchomienie i przetestowanie programu •Konserwacja oprogramowania Metody konstruowania algorytmu • met. zstępująca (od ogółu do szczegółu) – zadany problem dzielimy na coraz mniejsze logicznie domknięte moduły. W rezultacie uzyskujemy opis pojedynczych czynności w instrukcjach języka. • met. wstępująca (od szczegółu do ogółu) – zaczynamy rozwiązanie problemu od skonstruowania obliczeń dla jego najistotniejszych fragmentów. Następnie takie fragmenty łączymy i uzupełniamy o instrukcje wprowadzania danych, wyprowadzania wyników itp. Sposoby zapisywania algorytmów •przy pomocy języka naturalnego •bezpośrednio przy pomocy języka programowania •przy pomocy pseudo-kodu •graficznie w postaci schematów blokowych Elementy składniowe pseudo-kodu (elementami są zdania. Rodzaje zdań): • zdania proste (instrukcja) – określa czynność do wykonania • zdania decyzyjne jeśli (if) – zdanie zawierające decyzję podejmowaną w algorytmie - struktury prostej: jeśli warunek to / instrukcja - str. z alternatywą: jeśli warunek to / instrukcja 1 / w przeciwnym wypadku / instrukcja 2 •zdanie iteracyjne dopóki (while) –gdy pewne czynności należy powtarzać aż do spełnienia warunku: dopóki warunek wykonuj / instrukcje • zdanie iteracyjne wykonuj..dopóki (do..while) – czynność należy powtarzać w zależności od spełnienia warunku: wykonuj / instrukcję / dopóki warunek • zdanie iteracyjne dla (for) – czynność należy powtarzać określoną ilość razy: dla warunki wykonuj / instrukcje Przykład alg. w pseudokodzie – oblicz średnią z ciągu liczb. Dane: 100 kolejne liczby N Wynik: S – średnia arytmetyczna suma = 0 / i = 1 / powtarzaj / suma = suma + i / i = i + 1 / aż i > 100 / S = suma przez 100 / Pisz (S) Schemat blokowy – jest graficznym przedstawieniem zbioru instrukcji i wzajemnych powiązań między nimi. Połączenia wskazują kolejność wykonywanych akcji. Schemat zbudowany jest z figur geometrycznych oraz połączeń między nimi. Sortowanie przez wstawianie •dla j = 2 do ilość elementów (N) wykonaj •weź element o numerze j •i = j-1 •dopóki i>0 oraz elem. o num. i > elem. o num. j •elem. o num. i+1 = elem. o num, i •i = i-1 •wstaw element o numerze j w i-te miejsce Typ danych – określa zbiór wartości • do którego należy stała • które może przyjmować zmienna i wyrażenie • które może zwracać funkcja lub operator Typy danych: • proste: arytmetyczne (całkowite, rzeczywiste), znakowe • złożone: tablice, struktury Tablice – służą do przechowywania w pamięci określonej (skończonej) liczby obiektów tego samego typu. Są tablice jednowymiarowe (wektory) i dwuwymiarowe (macierze). Listy liniowe: lista to skończony ciąg elementów: q = [x­1,x2,…,xn] Skrajne el. listy x1 i xn nazywamy jej pocz. i końcem a |q| = n jej długością Stos – lista w której operacje wstawiania i usuwania są możliwe tylko na końcu tej listy. Kolejka – lista w której operacje wstawiania i usuwania są możliwe tylko na pocz. listy. Rekurencja – zdolność programu do wywołania samego siebie. Działa na zasadzie stosu. Metoda dziel i zwyciężaj W podejściu tym każdy z poziomów rekursji składa się z trzech etapów: • dziel – dzielimy problem na podproblemy • zwyciężaj – rozwiązujemy podproblemy rekurencyjnie • połącz – łączymy rozwiązania podpr. aby otrzymać rozwiązanie całego problemu. Algorytm zachłanny - wykonuje zawsze działanie, które w danej chwili wydaje się najkorzystniejsze. Wybiera zatem lokalnie optymalną możliwość w nadziei, że doprowadzi ona do globalnie optymalnego rozwiązania. Programowanie dynamiczne – jest techniką lub strategią projektowania algorytmów, stosowaną przeważnie do rozwiązywania zagadnień optymalizacyjnych. Jest alternatywą dla niektórych zagadnień rozwiązywanych za pomocą algorytmów zachłannych. Programowanie dynamiczne opiera się na podziale rozwiązywanego problemu na podproblemy względem kilku parametrów. W odróżnieniu od techniki dziel i zwyciężaj podproblemy w programowaniu dynamicznym nie są na ogół rozłączne, ale musi je cechować własność optymalnej podstruktury. Języki programowania – podział: • zorientowane maszynowo (asemblery) posługują się pojęciami na poziomie przesyłania informacji pomiędzy poszczególnymi komórkami pamięci. • zorientowane problemowo - rozwiązują zagadnienia określonej klasy, np: konstruowanie mostów, dyfuzja, termodynamika • języki wysokiego poziomu - ją uniwersalnymi językami, tzn. za ich pomocą można rozwiązać problemy różnych dziedzin Kompilacja – proces, w którym program w języku wysokiego poziomu jest tłumaczony na język adresów symbolicznych (asembler). Program realizujący ten proces nazywany jest kompilatorem. Interpreter – program tłumaczący każdą instrukcję na instrukcje poziomu maszyny i natychmiast ją wykonujący.

Języki cd. Fortran - do obliczeń numerycznych. Cobol - język dla przedsiębiorstw i handlu (mechanizmy definiowania struktury pliku) Pascal, C++ - języki uniwersalne Snobol - manipulowanie tekstami i napisami Prolog - oparty na logice faktów Lisp - przetwarzanie list, obliczenia symboliczne