Metoda - dziel i zwyciężaj.

Dziel i zwyciężaj (ang. divide and conquer) 

– jedna z głównych metod 

projektowania algorytmów w informatyce, prowadząca do bardzo efektywnych rozwiązań. Nazwa pochodzi od łacińskiej sentencji dziel i rządź (łac. divide et impera). W strategii tej problem dzieli się rekurencyjnie na dwa lub więcej mniejszych podproblemów tego samego (lub podobnego) typu tak długo, aż fragmenty staną się wystarczająco proste do bezpośredniego rozwiązania. Z kolei rozwiązania otrzymane dla podproblemów scala się, uzyskując rozwiązanie całego zadania.

Klasyczne przykłady algorytmów korzystających z tej metody to m.in. sortowanie przez scalanie (mergesort), sortowanie szybkie (quicksort), wyszukiwanie binarne (binary search).

Język programowania - C++

 

 

 Język programowania- zbiór zasad określających, kiedy ciąg symboli tworzy program komputerowy oraz jakie obliczenia opisuje.

 Język programowania może być zdefiniowany ze względu na kilka cech: 

• Funkcja: Język programowania służy do tworzenia programów komputerowych, których zadaniem jest przetwarzanie danych, wykonywanie obliczeń i algorytmów oraz kontrolowanie/obsługa zewnętrznych urządzeń, np. drukarek, robotów itd.
• Przeznaczenie: Języki naturalne służą do komunikacji między ludźmi, natomiast języki programowania umożliwiają wydawanie poleceń maszynom. Niektóre z języków są wykorzystywane również do kontrolowania jednego urządzenia przez inne. Przykładowo, program wykonywany na komputerze może wygenerować kod PostScript do sterowania pracą drukarki bądź wyświetlacza.
• Konstrukcje składniowe: Język programowania może zawierać konstrukcje składniowe do manipulowania strukturami danych oraz zarządzania przepływem sterowania.
• Moc: Teoria obliczeń klasyfikuje języki według rodzajów obliczeń, które można za ich pomocą zrealizować (hierarchia Chomsky'ego). We wszystkich językach zupełnych w sensie Turinga da się zaimplementować ten sam zbiór algorytmów. Przykładem często stosowanego języka niezupełnego jest SQL służący do komunikacji z bazą danych.

Interpreter- program komputerowy, który analizuje kod źródłowy programu, a przeanalizowane fragmenty wykonuje.

Realizowane jest to w inny sposób niż w procesie kompilacji, podczas którego nie wykonuje się wejściowego programu (kodu źródłowego), lecz tłumaczy go do wykonywalnego kodu maszynowego lub kodu pośredniego, który jest następnie zapisywany do pliku w celu późniejszego wykonania.
Wykonanie programu za pomocą interpretera jest wolniejsze, a do tego zajmuje więcej zasobów systemowych niż wykonanie kodu skompilowanego, lecz może zająć relatywnie mniej czasu niż kompilacja i uruchomienie. Jest to zwłaszcza ważne przy tworzeniu i testowaniu kodu, kiedy cykl edycja-interpretacja-debugowanie może często być znacznie krótszy niż cykl edycja-kompilacja-uruchomienie-debugowanie.
Interpretacja kodu jest wolniejsza niż uruchamianie skompilowanego kodu, ponieważ interpreter musi analizować każde wyrażenie i następnie wykonać akcję, a kod skompilowany jedynie wykonuje akcję. W implementacjach będących w pełni interpreterami wykonanie wielokrotne tego samego fragmentu kodu wymaga wielokrotnej interpretacji tekstu. Ta analiza nazywana jest "kosztem interpretacji". Dostęp do zmiennych jest także wolniejszy w interpreterze, gdyż odwzorowanie identyfikatorów na miejsca w pamięci operacyjnej musi zostać dokonane podczas uruchomienia lub działania, a nie podczas kompilacji. Dlatego niektóre interpretery tworzą dodatkowe dane (np. adresy zmiennych) przyspieszające wykonanie programu.

 Kompilator- program służący do automatycznego 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). Proces ten nazywany jest kompilacją. 

W informatyce kompilatorem nazywa się najczęściej program do tłumaczenia kodu źródłowego w języku programowania na język maszynowy. Niektóre z nich tłumaczą najpierw do języka asemblera, a ten na język maszynowy jest tłumaczony przez asembler..
Stosowanie kompilatorów ułatwia programowanie (programista nie musi znać języka maszynowego) i pozwala na większą przenośność kodu pomiędzy platformami.

Język niskiego poziomu– typ języka programowania, który w małym stopniu abstrahuje od konstrukcji jednostki centralnej komputera. Innymi słowy, język ten wykazuje duże podobieństwo do kodu maszynowego, zaś kompilacja jest w miarę nieskomplikowana.

Występuje pewna względność ocen: język C może być oceniany jako język wysokiego poziomu przez programujących w asemblerze, lecz jako język niskiego poziomu przez używających Javy. Pewnym obiektywnym miernikiem wysokości poziomu języka może być to, jak bardzo jest on niezależny od tego, jak działa komputer. W asemblerze operujemy bezpośrednio na rejestrach komputera, w C piszemy programy za pomocą pewnych instrukcji, natomiast Java i inne języki obiektowe pozwalają nam posługiwać się zdarzeniami występującymi między obiektami. W języku tym praktycznie nie widzimy w żaden sposób budowy komputera.
Najbardziej typowym przykładem języka niskiego poziomu jest asembler.

Asembler jest językiem niskiego poziomu i nie jest już powszechnie wykorzystywany przez programistów tworzących popularne aplikacje.

Programista Asemblera nie musi już co prawda używać wyłącznie zer i jedynek, jednak programowanie w Asemblerze nadal jest trudne i wymaga dużej wiedzy i cierpliwości.

 Język wysokiego poziomu(autokod) – typ języka programowania, którego składnia i słowa kluczowe mają maksymalnie ułatwić rozumienie kodu programu dla człowieka, tym samym zwiększając poziom abstrakcji i dystansując się od sprzętowych niuansów. 

Kod napisany w języku wysokiego poziomu nie jest bezpośrednio „zrozumiały” dla komputera – większość kodu stanowią tak naprawdę normalne słowa, np. w języku angielskim. Aby umożliwić wykonanie programu napisanego w tym języku należy dokonać procesu kompilacji.

Podział ze względu na zastosowanie

Języki programowania dzielimy na:

• wewnętrzne
• maszynowe(Java,NET)
• algorytmiczne (Pascal, częściowo C), 
• języki czwartej generacji (w tym niektóre języki do tworzenia aplikacji na bazie danych np. SQL)

Grupy języków programowania

• Bazodanowe:
  dBase, Clipper, FoxPro, Access, Delphi, SQL-owe (np. Oracle).
  Ukierunkowanie na tworzenie aplikacji baz danych (zbiór informacji jednorodnych, łatwiej dopisywać informacje, dostosowanie do pracy w sieci, sortowanie)
  
• Obliczeniowe (naukowo techniczne, statystyka), np.
  Fortran (są biblioteki do grafiki),
  Pascal,
  C/C++ (ojciec Pascal, matka assembler), podobny do UNIXa, wykonuje instrukcje nie dyskutuje.
  Jest jakby językiem uniwersalnym, właściwości sieciowe.C++ cechuje obiektowość. Gorzej z zastosowaniami bazodanowymi, biblioteka funkcji matematycznych mniejsza niż w Fortranie.
• Specjalizowane: sztuczna inteligencja, systemy ekspertowe, przetwarzanie list, do symulacji procesów
  
• Języki typu "Visual" (np. Visual C++,  C#, Visual Basic, Delphi)

Algorytmy

Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.

Algorytm ma przeprowadzić system z pewnego stanu początkowego do pożądanego stanu końcowego. Badaniem algorytmów zajmuje się algorytmika. Algorytm może zostać zaimplementowany w postaci programu komputerowego.

Jako przykład stosowanego w życiu codziennym algorytmu podaje się często przepis kulinarny. Dla przykładu, aby ugotować bigos należy w określonej kolejności oraz odstępach czasowych (imperatyw czasowy) dodawać właściwe rodzaje kapusty i innych składników. Może istnieć kilka różnych przepisów dających na końcu bardzo podobną potrawę. Przykład ten ma wyłącznie charakter poglądowy, ponieważ język przepisów kulinarnych nie został jasno zdefiniowany. Algorytmy zwykle formułowane są w sposób ścisły w oparciu o język matematyki.

W niektórych krajach, jak USA, algorytmy mogą zostać opatentowane, jeżeli zostaną zaimplementowane w jakimś praktycznym celu. Niektórzy twierdzą, że patentowanie algorytmów spowalnia rozwój informatyki, bo jeden producent może uzyskać monopol, np. na pisanie oprogramowania tworzącego pewne typy plików (np. GIF). Wiele koncernów komputerowych prowadzi między sobą spory prawne dotyczące praw własności do niektórych patentów. Kontrargumentem jest tzw. prawo własności intelektualnej (jaką objęty jest np. utwór muzyczny, będący wytworem intelektu i pracy muzyka) zakładające, że program jest intelektualną własnością twórcy.

 Reprezentacja algorytmów

Zapis algorytmu w postaci kodu
Najbardziej ścisłym opisem algorytmu jest program zapisany w danym j zyku programowania.
O ile jednak algorytm przedstawiony w formie listy kroków, schematu blokowego lub drzewa jest
uniwersalny, o tyle jego reprezentacja w kodzie ródłowym jest ci le zwi zana ze składni i semantyk
zastosowanego j zyka programowania.

 Zapis algorytmu w postaci listy kroków
Algorytm mo e by przedstawiony za pomoc listy kroków. Poszczególne kroki zawieraj cisły opis
czynno ci do wykonania. Poszczególne kroki algorytmu s numerowane i wykonywane w kolejno ci
rosn cej, przy czym w opisie danego kroku mo na wskaza inny krok, który nale y wykona jako
nast pny w kolejno ci. Innym ograniczeniem sekwencyjnego wykonywania kolejnych kroków algorytmu
s warunki, których spełnienie b d nie spełnienie przenosi działanie do wskazanego kroku.

Pseudokodem nazywany jest taki sposób zapisu algorytmu, który, zachowując strukturę charakterystyczną dla kodu zapisanego w języku programowania, rezygnuje ze ścisłych reguł składniowych na rzecz prostoty i czytelności. Pseudokod nie zawiera szczegółów implementacyjnych (jak np. inicjalizacja zmiennych, alokacja pamięci), często też opuszcza się w nim opis działania podprocedur (jeśli powinien być on oczywisty dla czytelnika), zaś nietrywialne kroki algorytmu opisywane są z pomocą formuł matematycznych lub zdań w języku naturalnym.

Nie istnieją w chwili obecnej szerzej przyjęte standardy zapisu pseudokodu. Większość autorów używa przyjętej ad hoc składni, często opierając się na składni istniejących języków programowania (Pascal, ALGOL, C).

Za graficzny wariant pseudokodu uznać można schemat blokowy.

 Magiczne Bloczki to program stworzony do projektowania schematów blokowych opisujących pewien algorytm. Opcja przeprowadzania symulacji działania algorytmu daje użytkownikowi możliwość sprawdzenia jego poprawności.
Magiczne Bloczki oferuję także wydruk oraz eksport grafiki (schematów blokowych) do znanych formatów graficznych. Twórca Magicznych Bloczków jest Eri Software.

PRZYKŁADY ALGORYTMÓW :

 

 

Algorytmy

1.Definicja.
2.Reprezentacja algorytmów.
-lista kodów
-algorytm graficzny(schemat blokowy)
-pseudokod
-kod źródłowy w wybranym języku programowania