Oprogramowanie użytkowe (ang. application software) — programy należące do konkretnych kategorii zastosowań, takie jak edytory, arkusze kalkulacyjne, bazy danych, CAD, CAM, CIM, zarządzanie zasobami ludzkimi (kadrowo- płacowe), gospodarka materiałowa itp. Odwrotna notacja polska (ONP, ang. Reverse Polish Notation, RPN) – jest sposobem zapisu wyrażeń arytmetycznych, w którym znak wykonywanej operacji umieszczony jest po operandach (zapis postfiksowy), a nie pomiędzy nimi jak w konwencjonalnym zapisie algebraicznym (zapis infiksowy) lub przed operandami jak w zwykłej notacji polskiej (zapis prefiksowy). Zapis ten pozwala na całkowitą rezygnację z użycia nawiasów w wyrażeniach, jako że jednoznacznie określa kolejność wykonywanych działań. ONP bardzo ułatwia wykonywanie na komputerze obliczeń z nawiasami i zachowaniem kolejności działań. Zarówno algorytm konwersji notacji konwencjonalnej (infiksowej) na odwrotną notację polską (postfiksową), jak i algorytm obliczania wartości wyrażenia danego w ONP są bardzo proste i wykorzystują stos. Zmienna - konstrukcja programistyczna posiadająca trzy podstawowe atrybuty: symboliczną nazwę, miejsce przechowywania i wartość; pozwalająca w kodzie źródłowym odwoływać się przy pomocy nazwy do wartości lub miejsca przechowywania. Nazwa służy do identyfikowania zmiennej w związku z tym często nazywana jest identyfikatorem. Miejsce przechowywania przeważnie znajduje się w pamięci komputera i określane jest przez adres i długość danych. Wartość to zawartość miejsca przechowywania. Zmienna zazwyczaj posiada również czwarty atrybut: typ, określający rodzaj danych przechowywanych w zmiennej i co za tym idzie sposób reprezentacji wartości w miejscu przechowywania. W programie wartość zmiennej może być odczytywana lub zastępowana nową wartością, tak więc wartość zmiennej może zmieniać się w trakcie wykonywania programu, natomiast dwa pierwsze atrybuty (nazwa i miejsce przechowywania) nie zmieniają się w trakcie istnienia zmiennej^[1]. W zależności od rodzaju języka typ zmiennej może być stały lub zmienny. Konstrukcją podobną lecz nie pozwalającą na modyfikowanie wartości jest stała. Program licznikowy Instrukcje * przypisanie zmiennej wartości zero; * dodanie lub odjęcie jedynki od danej zmiennej i przypisanie wyniku innej zmiennej; * skok warunkowy przy zerowej wartości danej zmiennej. Poprawność całkowita Algorytm całkowicie poprawny ¶ poprawnie rozwiązuje zadanie dla każdego zestawu danych X z I. Czyli zakańcza zadanie. Definicja Algorytm A jest całkowicie poprawny względem danego warunku WP i danego warunku WK wtedy i tylko wtedy, gdy dla dowolnych danych wejściowych spełniających warunek WP algorytm A zatrzymuje się i dane wyjściowe tego algorytmu spełniaj_ warunek WK. Poprawność częściowa Definicja Algorytm A jest częściowo poprawny względem danego warunku WP i danego warunku WK wtedy i tylko wtedy, gdy dla dowolnych danych wejściowych spełniających warunek WP, jeżeli algorytm A zatrzymuje się, to dane wyjściowe algorytmu spełniaj_ warunek WK. Drzewo Struktura z porządkiem. * Wyróżnia się specjalny obiekt będący „początkiem” całej struktury: korzeń. * Inne elementy to „następniki” albo potomstwo. * Każdy obiekt może mieć kilku równoważnych potomków. * Każdy potomek to węzeł drzewa. * Obiekty, które nie mają potomków to liście. * Gałąź to droga od korzenia do liścia. Procesor wektorowy, w przeciwieństwie do skalarnego, pozwala na przetwarzanie,w pojedynczych cyklach całych wektorów danych. Operandami instrukcji są wieloelementowe zbiory liczb. Dzięki temu można przyspieszyć niektóre obliczenia.Procesory wektorowe stosowane są także we współczesnych superkomputerach. Reduced Instruction Set Computers -Zredukowana liczba rozkazów do niezbednego minimum. Ich liczba wynosi kilkadziesiąt (setki w procesorach). Upraszcza to znacznie konstrukcję procesora. -Redukcja trybów adresowania _ wiekszosc operacji wykonuje sie wg schematu: rejestrC = rejestrA operacja rejestrB. -Ograniczenie komunikacji pomi¦dzy pami¦ci¡, a procesorem. Do przesyªania danych pomi¦dzy pami¦ci¡, a rejestrami słuzą instrukcje, które nazywaj¡ się load (zaªaduj z pami¦ci), oraz store (zapisz do pami¦ci); pozostałe instrukcje operują wylącznie na rejestrach. Schemat działania - załaduj dane z pamięci do rejestru, -na zawartosci rejestru wykonaj dziaªanie, -przepisz wynik z rejestru do pami¦ci. -Zwi¦kszenie liczby rejestrów (np. 32, 192, 256, _ x86 jest 8), co również ma wpływ na zmniejszenie liczby odwołań do pamięci. Zero Instruction Set Computer Jeden z pierwszych procesorów ZISC zawieral 36 niezaleznych komórek (uwazane sa za neurony lub równolegle procesory). Kazda z nich moze porówna¢ wektor wejsciowy (64 bajty) z podobnym wektorem przechowywanym w komórkach pami¦ci. Jezli wektor wejsciowy odpowiada wektorowi w komórce pamieci to komórka ta „wypala”. Sygnał wyjsciowy zawiera komórki, która miała dopasowanie, oraz znacznik mówiacy, ze nie wystapiło dopasowanie. Podstawowe koncepty *Dwa tryby pracy: 1. System Operacyjny 2. Program uzytkowy *Maszyna wirtualna (rodzaj „kapsulki” dzieki której program „mysli”, ze ma do wylacznej dyspozycji caly komputer. *Proces (task) * W¡tek (thread) *”Urzadzenie wirtualne” Przekazanie sterowania: Skok bezwarunkowy ma posta¢ przejdz do „G” („G" to okreslone miejsce programu - algorytmu). Skok warunkowy przejdz do „G” jezeli spelniony jest jakis warunek. Duza liczba skoków (do przodu, do tylu) zmniejsza czytelnosc algorytmu. Skoki powoduja równiez problemy techniczne: czy można „wyskoczy¢” ze srodka petli? Czy mozna do srodka pętli wskoczy¢? Inne struktury danych - Listy (pewne podobie«stwo do wektorów czy tablic). - Bazy danych (pewne podobie«stwo do tablic). - Grafy (pewne podobie«stwo do drzew). Architektura von Neumanna _ rodzaj architektury komputera przedstawionej po raz pierwszy w 1945 roku przez von Neumanna stworzonej wspólnie z Johnem W. Mauchly’ym i Johnem Presper Eckertem. Polega na scislym podziale komputera na trzy podstawowe czesci: -procesor (w ramach którego wydzielona bywa czesc Sterująca oraz czesc arytmetyczno-logiczna) -pamięc komputera (zawierająca dane i sam program) - urządzenia wejścia/wyjścia System komputerowy zbudowany w oparciu o architekture von Neumanna powinien: - mieć skonczona i funkcjonalnie pelna liste rozkazów -miec mozliwosc wprowadzenia programu do systemu komputerowego poprzez urzadzenia zewnetrzne i jego przechowywanie w pamieci w sposób identyczny jak danych - dane i instrukcje w takim systemie powinny by¢ jednakowo dostępne dla procesora -informacja jest tam przetwarzana dzięki sekwencyjnemu odczytywaniu instrukcji z pamięci komputera i wykonywaniu tych instrukcji w procesorze. Podane warunki pozwalają przełączac system komputerowy z wykonania jednego zadania (programu) na inne bez fizycznej ingerencji w strukturę systemu, a tym samym gwarantuj¡ jego uniwersalnoś¢. System komputerowy von Neumanna nie posiada oddzielnych pamięci do przechowywania danych i instrukcji. Instrukcje jak i dane s¡ zakodowane w postaci liczb. Bez analizy programu trudno jest okreslic czy dany obszar pamięci zawiera dane czy instrukcje. Wykonywany program może Się sam modyfkowa¢ traktując obszar instrukcji jako dane, a po przetworzeniu tych instrukcji -danych –zacząć je wykonywa¢.	Definicja Złożoność obliczeniowa programu dla danych o wielkości jest to maksymalna liczba operacji, jakie może wykonać program na danych wejściowych o rozmiarze co najwyżej . Złożoność obliczeniowa to pojęcie wprowadzone w celu umożliwienia porównania programów komputerowych rozwiązujących zadany problem. Teoria złożoności obliczeniowej - dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów. Wyniki, jakie podaje t.z.o., można podzielić na dwie kategorie: pozytywne i negatywne, czyli na takie, które podają, co i jak da się obliczyć, oraz takie, w których dowodzi się, czego nie da się obliczyć, wykorzystując określoną ilość zasobów. Wyniki pozytywne są łatwiejsze do uzyskania i zwykle mają postać algorytmu rozwiązującego dany problem wraz z dowodem poprawności oraz opisem potrzebnych zasobów. Złożoność obliczeniowa to dziedzina informatyki teoretycznej zajmująca się klasyfikacją języków formalnych ze względu na ilość zasobu — czasu i pamięci — potrzebnego do rozpoznawania języka. Ponieważ język formalny jest abstrakcyjnym odpowiednikiem problemu algorytmicznego, teoria ta dostarcza narzędzi do szacowania trudności obliczeniowej takich problemów. Niniejszy kurs zapoznaje uczestników z najważniejszymi rezultatami badań dotyczącymi klas złożoności, ich własności i wzajemnych zależności a także omawia wynikające z tych faktów wnioski dotyczące praktycznych problemów algorytmicznych. Stos jest strukturą liniowo uporządkowanych danych, z których jedynie ostatni element, zwany wierzchołkiem, jest w danym momencie dostępny. W wierzchołku odbywa się dołączanie nowych elementów, również jedynie wierzchołek można usunąć. Stos jest bardzo często wykorzystywaną strukturą danych. Działanie na nim jest często porównywane do stosu talerzy: nie można usunąć talerza znajdującego się na dnie stosu nie usuwając wcześniej wszystkich innych. Nie można także dodać nowego talerza gdzieś indziej, niż na samą górę. Kolejka * Struktura bardzo podobna do wektora. * Dane dostarczane są do jednego „końca”. * Do odbioru danych służy drugi „koniec”. Systemem operacyjnym nazywamy zbiór programów (oprogramowanie) nadzorujących (zarządzających) pracę całego komputera oraz programów. System operacyjny zarządza wszystkimi urządzeniami komputerowymi tj. sprzętem (hardware) oraz oprogramowaniem (software) uruchamianym na tym komputerze. Tablice decyzyjne to mieszanka warunków i decyzji, które należy podejmować w zależności od ich spełnienia. * Alternatywa dla schematu blokowego. * Bardzo wygodne w przypadku opisu problemów z ogromną ilością decyzji. * Nieźle nadaje się do opisu problemów _z życia wziętych_. * Średnie zastosowanie w przypadku problemów obliczeniowych. * Dziś już nieco zapomniane. Szybkosc- wiele procesorów *Batch processing (przetwarzanie wsadowe) -wiele zadan -wiele komputerów (polaczonych), - zadania zapisywane są do kolejki (kolejek), -zadania przekazywane sa do wykonania na poszczególnych komputerach zgodnie z przyjetą polityką *Symmetric Multi-Processing (SMP) - jeden komputer (wspólna pamieć) i kilka procesorów -jeden komputer (wspólna pami¦e¢) i procesor „kilkurdzeniowy” (multicore) Very Long Instruction Word - uproszczenie jednostki sterujacej, I zwiekszanie liczby jednostek wykonawczych, I technika wczesniejszego wykonania instrukcji (Out-of-Order Execution), -sterowanie pracą procesora zostało przerzucone na kompilator (to on decyduje o sposobie działania procesora). Kompilator (ang. compiler) to program służący do automatycznego tłumaczenia kodu napisanego w jednym jezyku (języku żródłowym) na równowazny kod w innym j¦zyku (j¦zyku wynikowym) Program (1973) _ ciag dyrektyw majacych spowodowa¢ okreslone działanie automatu bedacy algorytmem zakodowanym w jakims jezyku programowania. Automat (1973) _ obiekt dzialajacy w pelnym cyklu swojej pracy bez bezposredniego udzialu czlowieka zgodnie z zalozonym algorytmem funkcjonowania Automat (2008) _ urz¡dzenie, maszyna lub ich zestaw, wykonuj¡ce samoczynnie cykl czynno±ci lub operacji okre±lony konstrukcj¡ lub programem, nie wymagaj¡ce bezpo±redniego udziaªu czªowieka. Program binarny: 1. Zalezy od procesora 2. Zalezy od Systemu Operacyjnego Jak powstaje oprogramowanie? Jezyki programowania: 1. J¦zyk maszynowy 2. Assembler 3. Makro assembler 4. J¦zyki wysokiego rzedu 5. Systemy automatycznego tworzenia programów ALGORYTM Slowo algorytm jest bardzo nowe (w pewnym sensie). Pochodzi od nazwiska Muhammed ibn Musa Alchwarizmi - perskiego matematyka (IX w) i pierwotnie oznaczalo (kazde) obliczenia w dziesietnym systemie obliczeniowym. Algorytm to jednoznaczny przepis przetworzenia w skonczonym czasie pewnych danych wejsciowych do pewnych danych wynikowych. (Wikipedia) Czasami rezygnuje si¦ z żądania skonczonosci. Czasami, jezeli algorytm sie nie konczy- nazywamy go metoda obliczeniową. Cechy algorytmu: Po pierwsze powinien by¢ skonczony; oznacza to, ze po skonczonej (być moze bardzo duzej) liczbie kroków algorytm sie zatrzyma.1 Pytanie pomocnicze: Co gwarantuje, ze algorytm Euklidesa zakonczy sie w skonczonej liczbie kroków? Procedura, która ma wszystkie cechy algorytmu poza skonczonosci¡ nazywana jest metoda obliczeniową. Podaj przykłady metod obliczeniowych realizowanych przez rzeczywiste komputery. Po drugie powinien by¢ „dobrze zdefniowany”. Kazdy krok algorytmu musi by¢ opisany precyzyjnie. Wszystkie mozliwe przypadki powinny by¢ uwzglednione, a podejmowane akcje dobrze opisane.2 Oczywiscie język naturalny nie jest wystarczająco precyzyjny - moze to prowadzi¢ do nieporozumien. z tego powodu u»ywa si¦ bardziej formalnych sposobów zapisu algorytmów, az po jezyki programowania. . . Po trzecie powinien mie¢ precyzyjnie zdefniowane dane wejsciowe. Pewne algorytmy moga nie miec danych wejsciowych (mie¢ zero danych wejsciowych). Dane wejsciowe to wartosci, które musza byc zdefniowane zanim rozpocznie sie wykonanie algorytmu Po czwarte zdefniowane dane wyjsciowe. Daną wyjsciową algorytmu Euklidesa jest liczna n która jest naprawde najwiekszym wspólnym dzielnikiem danych wejsciowych. Osobna sprawe jest pokazanie skąd wynika, ze wynik algorytmu Euklidesa jest rzeczywiscie NWD liczb m i n. Po piate algorytm powinien by¢ okreslony efektywnie to znaczy jego operacje powinny by¢ wystarczajaco proste by mozna je (teoretycznie?) wykona¢ w skonczonym czasie z wykorzystaniem kartki i olówka.	Schemat blokowy - diagram, na którym procedura, system albo program komputerowy, są reprezentowane przez opisane figury geometryczne połączone liniami zgodnie z kolejnością wykonywania czynności wynikających z przyjętego algorytmu rozwiązania zadania. Blok graniczny oznacza on początek, koniec, przerwanie lub wstrzymanie wykonywania działania, np. blok startu programu. Blok wejścia-wyjścia przedstawia czynność wprowadzania danych do programu i przyporządkowania ich zmiennym dla późniejszego wykorzystania jak i wyprowadzenia wyników obliczeń, np. czytaj z, pisz z+10. Blok obliczeniowy oznacza wykonanie operacji w efekcie, której zmienią się wartości, postać lub miejsce zapisu danych, np. z = z + 1. Blok decyzyjny przedstawia wybór jednego z dwóch wariantów wykonywania programu na podstawie sprawdzenia warunku wpisanego w ów blok, np. a = b. Blok wywołania podprogramu oznacza zmianę wykonywanej czynności na skutek wywołania podprogramu, np. MAX(x,y,z) Blok fragmentu przedstawia część programu zdefiniowanego odrębnie, np. sortowanie. Blok komentarza pozwala wprowadzać komentarze wyjaśniające poszczególne części schematu co ułatwia zrozumienie go czytającemu, np. wprowadzenie danych. Łącznik wewnętrzny służy do łączenia odrębnych części schematu znajdujących się na tej samej stronie, powiązane ze sobą łączniki oznaczone są tym samym napisem, np. A1, 7. Łącznik zewnętrzny służy do łączenia odrębnych części schematu znajdujących się na odrębnych stronach, powinien być opisany jak łącznik wewnętrzny, poza tym powinien zawierać numer strony, do której się odwołuje, np. 4.3, 2,B2. Rekursja albo rekurencja to w logice, programowaniu i w matematyce odwoływanie się (np. funkcji lub definicji) do samej siebie. Rekurencja jest podstawową techniką wykorzystywaną w funkcyjnych językach programowania. Należy jednak zachować ostrożność przy używaniu rekurencji w rzeczywistych programach. Ryzyko istnieje szczególnie przy przetwarzaniu dużej ilości głęboko zagnieżdżonych danych. Maszyna Turinga jest prostym urządzeniem algorytmicznym, uderzająco prymitywnym w porównaniu z dzisiejszymi komputerami i językami programowania, a jednak na tyle silnym, że pozwala na wykonanie nawet najbardziej złożonych algorytmów. Maszyna Turinga jest mechanizmem powstałym w wyniku ciągu uproszczeń: danych, sterowania nimi oraz uproszczeń podstawowych operacji. Maszynę tą wymyślił w roku 1936 brytyjski matematyk Alan M.Turing Abstrakcyjny model komputera służącego do wykonywania algorytmów, składającego się z nieskończenie długiej taśmy podzielonej na pola. Taśma może być nieskończona jednostronnie lub obustronnie. Complex Instruction Set Computers -nazwa architektury mikroprocesorów o nast¦puj¡cych cechach: - duża liczba rozkazów (instrukcji) - mała optymalizacja _ niektóre rozkazy potrzebują duzej liczby cykli procesora do wykonania -występowanie złozonych, specjalistycznych rozkazów - du»a liczba trybów adresowania - do pamięci moze się odwoływać bezpośrednio duza liczba rozkazów - mniejsza od RISC-ów częstotliwość taktowania procesora -powolne działanie dekodera rozkazów Przyklady rodzin procesorów o architekturze CISC to miedzy innymi: I AMD I x86 I M68000 Podstawowy element oprogramowania komputera stanowi¡cy rodzaj interfejsu pomi¦dzy sprz¦tem (hardware), a cała _reszt¡ Świata_. I Jedn¡ z podstawowych funkcji Systemu Operacyjnego jest obsªuga (zapewnienie niezb¦dnej komunikacji) wszystkich komponentów komputera. Realizowane jest to przez tak zwane sterowniki (driver) i _urz¡dzenia wirtualne_.. I Inne funkcje usªugowe to zarz¡dzanie zasobami (przydziaª zasobów) komputera na rzecz programów i u»ytkowników: I przydziaª pami¦ci, I przydziaª miejsca na dysku, I przydziaª czasu procesora, I rezerwacja wszelkich zasobów, I dbanie o równomierne wykorzystanie zasobów. I Ochrona zasobów/danych System operacyjny i jego funkcje: *Podstawowy element oprogramowania komputera stanowiacy rodzaj interfejsu pomi¦dzy sprz¦tem (hardware), a cała „resztą swiata”. *Jedna z podstawowych funkcji Systemu Operacyjnego jest obsługa (zapewnienie niezbednej komunikacji) wszystkich komponentów komputera. Realizowane jest to przez tak zwane sterowniki (driver) i „urzadzenia wirtualne”.. *Inne funkcje uslugowe to zarządzanie zasobami (przydzial zasobów) komputera na rzecz programów i uzytkowników: -przydzial pami¦ci, -przydzial miejsca na dysku, -przydzial czasu procesora, -rezerwacja wszelkich zasobów, -dbanie o równomierne wykorzystanie zasobów. *Ochrona zasobów/danych Zadanie algorytmiczne składa sie ze: -scharakteryzowania dopuszczalnego, by¢ moze nieskonczonego zbioru potencjalnych zestawów danych wejsciowych; -specyfkacji poządanych wyników jako funkcji danych wejsciowych. Zaklada sie, że zadany jest albo zestaw dozwolonych akcji (operacji) podstawowych albo konfguracja sprzetowa, w którą je wbudowano. Rozwiązanie zadania algorytmicznego stanowi algorytm zlozony z elementarnych instrukcji zadajacych akcje z ustalonego zbioru. Prawo autorskie (USA) ochrona przed nieautoryzowanym „kopiowaniem”. Ochronie nie podlegaj¡: -niezakonczone prace -tytuly i krótkie frazy, slogany -pomysly -artykuly uzytkowe Prawo patentowe (USA): ochrona idei przed wykorzystaniem -Lata 70-te: Oprogramowanie traktowane bylo jako zapis algorytmu matematycznego, a te podobnie jak „prawdy naukowe” nie podlegały patentowaniu. -Lata 80-te: Amerykanski Sad Najwyzszy „zmusił” Urzad Patentowy do zmiany zdania. Programy komputerowe stawaly sie coraz czesciej fragmentem procesów technologicznych. - Lata 90-te: W dlugotrwalym procesie decyzyjnym uznano, ze praktycznie kazdy program komputerowy moze by¢ opatentowany. Nie mozna patentowa¢: (Europa) 1. Odkryc, teorii naukowych i metod matematycznych. 2. Dziela sztuki (aesthetic creations) 3. Schematy, zasady i metody rozumowania uzywane podczas przemyśleń, rozgrywanie gier, prowadzenia biznesu oraz tworzenia programów komputerowych 4. Sposobów prezentowania informacji. Prawo patentowe przewiduje, ze w pewnych sytuacjach metody komputerowe mogą by¢ patentowane. Od 1978 EPO udzieliła ok. 30000 patentów „zaimplementowane komputerowo wynalazki”.