wtorek, 17 grudnia 2013

17.12.2013 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).




rozdz. w podr. 1.7.

piątek, 29 listopada 2013

29.11.2013 C++

1. Specyfikacja:
Dane:
- dowolne
- liczby
- rzeczywiste a, b
Wynik:
wartość rzeczywista pierwiastka równania kwadratowego x lub komunikat:
 - brak rozwiązania
lub
- nieskończenie wiele rozwiązań


2. Lista kroków:
krok 0: wczytaj a, b
krok 1: jeżeli a != 0 to oblicz x = -b / a, wpisz x, koniec alg.
krok 2: jeżeli b = 0 wypisz (NWR - nieskończenie wiele rozwiązań), w przeciwnym wypadku wpisz (RS - równanie sprzeczne)
RÓWNANIE BLOKOWE:
 

DRZEWO ALGORYTMU:

Program C++

C++ – język programowania ogólnego przeznaczenia.
Umożliwia abstrakcję danych oraz stosowanie kilku paradygmatów programowania: proceduralnego, obiektowego i generycznego. Charakteryzuje się wysoką wydajnością kodu wynikowego, bezpośrednim dostępem do zasobów sprzętowych i funkcji systemowych, łatwością tworzenia i korzystania z bibliotek (napisanych w C++, C lub innych językach), niezależnością od konkretnej platformy sprzętowej lub systemowej (co gwarantuje wysoką przenośność kodów źródłowych) oraz niewielkim środowiskiem uruchomieniowym. Podstawowym obszarem jego zastosowań są aplikacje i systemy operacyjne.
C++ został zaprojektowany przez Bjarne Stroustrupa jako rozszerzenie języka C o obiektowe mechanizmy abstrakcji danych i silną statyczną kontrolę typów. Zachowanie zgodności z językiem C na poziomie kodu źródłowego pozostaje jednym z podstawowych celów projektowych kolejnych standardów języka.
W latach 90. XX wieku język C++ zdobył pozycję jednego z najpopularniejszych języków programowania ogólnego przeznaczenia. Na początku XXI wieku liczbę programistów języka C++ szacowano na około 3 miliony.
Od 1998 obowiązuje standard ISO/IEC 14882:1998 (Standard for the C++ Programming Language) z drobnymi poprawkami zatwierdzonymi w 2003 r. (ISO/IEC 14882:2003). W 2009 roku ogłoszono nowy standard (tzw. C++0x), który zaczął obowiązywać od 12 sierpnia 2011 roku, lecz wciąż oczekuje na opublikowanie (ISO/IEC 14882:2011).

Cechy standardów

Projekt języka C++ usiłuje zachować możliwie jak największą zgodność (na poziomie kodu źródłowego) z językiem C. Zgodność pomiędzy obydwoma językami nie zawsze była całkowita, ale jak dotąd ewentualne różnice były w praktyce nieistotne. Większym problemem związanym ze zgodnością była niekompatybilność kompilatorów języka C++ w zakresie obsługiwanej składni – przez wiele lat programy napisane pod jednym nie działały pod innym. Biblioteki C++ związane z interfejsami systemów nie są przenośne poza ich obręb, co wynika z faktu, że takie interfejsy są specyficzne dla danego systemu i nie dotyczy to wyłącznie C++.
Większość użytecznych programów w C++ wymaga stosowania bibliotek niestandardowych. Są one łatwo dostępne w Sieci zarówno jako produkty własnościowe, jak i jako FLOSS. Programy napisane w C++ mogą korzystać również z zasobów bibliotek języka C.
Język C++ posiada swój oficjalny standard (aktualnie jest to C++0x z 2011).
Język C++ nie jest własnością żadnej osoby, instytucji czy korporacji.

Właściwości języka

 

  • Język C++ jest językiem wieloparadygmatowym. Oznacza to, że można w nim stosować jednocześnie różne style programowania, w tym programowanie proceduralne, obiektowe, generyczne, jak również programować na poziomie asemblera.
  • Język C++ zakłada statyczną kontrolę typów; posiada też elementy dynamicznej kontroli typów.
  • Język C++ umożliwia bezpośrednie zarządzanie wolną pamięcią.
  • Projekt języka zakłada, że żadna nowa (względem języka C) cecha języka C++ nie może mieć negatywnego wpływu na szybkość działania programu lub zapotrzebowanie na pamięć operacyjną. Dzięki temu dobrze napisany program w C++ jest z reguły co najmniej równie szybki, jak jego odpowiednik napisany w C; co więcej, dzięki możliwości zastosowania algorytmów generycznych w wielu przypadkach C++ jest wyraźnie szybszy od C (np. podczas sortowania).
  • Język C++ ze względu na bardzo rozbudowaną składnię oraz surowe wymogi w zakresie wydajności kodu stanowi duże wyzwanie dla twórców kompilatorów.
  • Do dziś (2012) żaden popularny kompilator nie jest w pełni zgodny z obowiązującym standardem języka, aczkolwiek ewentualne niezgodności dotyczą już tylko drugorzędnych cech języka (np. implementacji słowa kluczowego export).

Historia

Język C++ został stworzony w latach osiemdziesiątych XX wieku (pierwsza wersja pojawiła się w 1979 r.) przez Bjarne Stroustrupa jako obiektowe rozszerzenie języka C. Poza językiem C, na definicję języka C++ miały wpływ takie języki, jak Simula (z której zaczerpnął właściwości obiektowe) oraz Algol, Ada, ML i Clu.
Początkowo język C++ był dostępny w takim standardzie, w jakim opracowano ostatnią wersję kompilatora Cfront (tłumaczący C++ na C), później opublikowano pierwszy nieformalny standard zwany ARM (Annotated Reference Manual), który sporządzili Bjarne Stroustrup i Margaret Ellis. Standard języka C++ powstał w 1998 roku (ISO/IEC 14882-1998 "Information Technology – Programming Languages – C++"). Standard ten zerwał częściowo wsteczną zgodność z ARM w swojej bibliotece standardowej; jedyne, co pozostało w stanie w miarę nienaruszonym to biblioteka iostream.
Początkowo najważniejszą zmianą wprowadzoną w C++ w stosunku do C było programowanie obiektowe, później jednak zaimplementowano wiele innych ulepszeń, mających uczynić ten język wygodniejszym i bardziej elastycznym od swojego pierwowzoru. Niektóre zmiany w standardzie języka C były zainspirowane językiem C++ (np. słowo inline w C99).
Nazwa języka została zaproponowana przez Ricka Mascitti w 1983 roku, kiedy to po raz pierwszy użyto tego języka poza laboratorium naukowym. Odzwierciedla ona fakt, że język ten jest rozszerzeniem języka C. Wcześniej używano nazwy "C z klasami". Nazwa języka C++ nawiązuje do faktu bycia "następcą języka C", przez użycie w niej operatora inkrementacji "++". Inkrementacja to zwiększenie liczby o 1, w języku C++ do jej wykonania wykorzystywany jest ww. operator; dla przykładu:
zapis:

 


Nazwa C++ jest więc symbolicznym stwierdzeniem, iż jest to język C, unowocześniony, o większych możliwościach.
Pierwsze kompilatory języka C++, podobnie jak Cfront, były wyłącznie translatorami na język C. Kompilatory takie dostępne są i dziś. Jednym z nich jest Comeau C++ – jeden z niewielu kompilatorów oferujących pełne wsparcie dla standardu języka. Pierwszym kompilatorem natywnym (produkującym od razu kod asemblerowy) dla języka C++ był g++ z pakietu GCC, którego pierwszym autorem był Michael Tiemann, założyciel Cygnus Solutions

Przykładowy program

Poniższy program wyprowadza na standardowe urządzenie wyjścia napis "Hello world"

 

 

 

 

Nowe cechy języka C++ względem języka ANSI C z 1989 roku


Uwaga: niektóre z poniższych elementów trafiły do standardu języka C z 1999 roku (tzw. C99).
  • Możliwość programowania obiektowego:
    • Mechanizmy enkapsulacji:
      • funkcje składowe
      • sekcje prywatne, chronione i publiczne
      • zaprzyjaźnianie funkcji i klas
    • Klasy, jako rozszerzenie struktury o funkcje składowe, enkapsulację, dziedziczenie i polimorfizm
    • Obiekty, będące instancjami klas
    • Dziedziczenie (w tym dziedziczenie wielobazowe)
    • Metody wirtualne dostarczające polimorfizm
    • Konstruktory (służące również do niejawnej konwersji; później dodano również możliwość zakazania niejawnej konwersji przez konstruktor za pomocą explicit)
    • Destruktory, czyli funkcja wywoływana niejawnie przed (ściśle ustalonym) usunięciem obiektu
    • Operatory new i delete
    • Dynamiczna kontrola typów (RTTI), czyli dynamiczne (sprawdzane w czasie wykonywania) rzutowanie pomiędzy typami spokrewnionych klas, oraz określanie typu w czasie wykonywania (operatory dynamic_cast i typeid)
    • Słowo kluczowe this (dostęp do obiektu, na rzecz którego wołana jest metoda)
    • Wskaźniki do składowych (pól i metod)
    • Metody i pola statyczne
  • Udogodnienia związane z programowaniem generycznym:
    • Szablony (wzorce) klas i funkcji
    • Włączenie do biblioteki standardowej generycznej biblioteki STL
  • Obsługa wyjątków:
    • Deklaracja wychwytywania wyjątków: try ... catch
    • Deklaracja wywoływania wyjątku: throw
    • Deklaracja ograniczania wyjątków: throw(...) (określanie, jakie wyjątki mogą być propagowane z danej funkcji/metody)
  • Zmiany natury ogólnej:
    • Przestrzenie nazw i operator zasięgu ::
    • Traktowanie definicji zmiennych i obiektów jak zwykłych instrukcji
    • Dynamiczna inicjalizacja zmiennych globalnych i lokalnych zmiennych statycznych (tzn. mogą być inicjalizowane wartością funkcji)
    • Możliwość uzyskania dostępu do przesłoniętej zmiennej globalnej za pomocą operatora ::
    • Referencje
    • Słowa kluczowe const, volatile (również C99) i mutable (usuwanie modyfikatora const z podanego pola, jeśli taki został nadany całemu obiektowi)
    • Przeciążanie funkcji
    • Przeciążanie operatorów
    • Funkcje rozwijalne (inline) (również C99)
    • Nowy typ logiczny bool i stałe true i false (również C99, z tym że w C++ są to słowa kluczowe)
    • "Szeroki" typ znakowy, wchar_t (również C99) wraz ze wszystkimi zależnościami (np. klasy strumieniowe, w tym wiostream, oraz dodatkowe pliki nagłówkowe, np. wstring)
    • Operatory precyzyjnego rzutowania: dynamic_cast (rzutowanie tylko pomiędzy typami, z uwzględnieniem hierarchii klas), reinterpret_cast (rzutowanie wymuszone tylko pomiędzy typami) i const_cast (rzutowanie zmieniające modyfikatory typu const i volatile)

 

wtorek, 1 października 2013

Spotkanie 37- Algorytmy Interacyjne

Algorytm iteracyjny - algorytm, który uzyskuje wynik przez powtarzanie danej operacji początkowo określoną liczbę razy lub aż do spełnienia określonego warunku. Niektóre problemy można rozwiązać zarówno za pomocą algorytmu iteracyjnego, jak i rekurencyjnego, jak np. problem wież Hanoi.
 

wtorek, 24 września 2013

Spotkanie 34- Algorytmy WARUNKOWE

1.Z algorytmami warunkowymi możesz spotkać się w życiu codziennym. Chcesz zjeść świeże bułki na śniadanie więc idziesz do sklepu. Zakładasz, że sklep jest otwarty. Jeśli nie jest otwarty, idziesz do innego sklepu. Jeśli jest otwarty, sprawdzasz kolejny warunek – czy są świeże bułki. Jeśli warunek jest spełniony masz śniadanie ze świeżych bułeczek, jeśli nie jest spełniony – jesz na śniadanie stare bułki itd. Sytuacji, kiedy mamy do czynienia z warunkiem i odpowiednim postępowaniem zależnie od spełnienia i niespełnienia tego warunku można by podać wiele. Tak samo dzieje się w przypadku zadań matematycznych.
Przykład

Algorytm warunkowy w postaci listy kroków – obliczanie obwodu prostokąta

Dane: bok a i b
Lista kroków:
1. Początek algorytmu
2. Podaj bok a
3. Podaj bok b
4. Czy bok a>0?
   
jeśli tak idź do kroku 5,
    jeśli nie podaj komunikat wyjściowy: "nie można obliczyć obwodu" i zakończ algorytm.
5. Czy bok b>0?
    jeśli tak idź do kroku 6
    jeśli nie podaj komunikat wyjściowy: "nie można obliczyć obwodu" i zakończ algorytm.
6. Oblicz obwód Ob:=2*a+2*b
7. Wyprowadź wartość Ob
6. Koniec algorytmu
 
Algorytm warunkowy w postaci schematu blokowego – obliczanie obwodu prostokąta

 

piątek, 13 września 2013

Spotkanie 29,30- 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 :
 

 


:D :D :D  

Spotkanie 28- PSO, KLASA 2

Dzień dobry szkoło!
Klasa 2, rozszerzenie z informatyki ! ;)

piątek, 17 maja 2013

Spotkanie 25-Corel PaintShop Pro

Na dzisiejszym spotkaniu również zajmowaliśmy się grafiką, jednak dzisiaj używaliśmy programu  Corel PaintShop Pro.


Paint Shop Pro (PSP) - edytor grafiki bitmapowej i wektorowej dla komputerów z systemem operacyjnym Microsoft Windows.
Stworzony przez firmę Jasc Software, stał się jednym z popularniejszych edytorów pod ten system. Obecnie producentem programu jest Corel, który przejął Jasc w październiku 2004.
Aplikacja jest udostępniana na zasadach licencji shareware. Po wykupieniu pełnej wersji zazwyczaj użytkownik dostaje aplikację Animation Shop, która poza współpracą z PSP nadaje się do tworzenia animacji.
W PSP można stworzyć nową grafikę jak i też obrabiać gotowy plik, a także poprawiać. Program ma dużą kolekcję pędzli (brush), kształtów figur a także wzorów do malowania (tzw. Picture Tubes) oraz gotowych efektów.



 

piątek, 10 maja 2013

Spotkanie 24- Paint Shop Pro 7

Na dzisiejszym spotkaniu profesor w formie wykładu opowiedział nam o możliwościach edytora graficznego: Paint Shop Pro 7.

Paint Shop Pro (PSP) - edytor grafiki bitmapowej i wektorowej dla komputerów z systemem operacyjnym Microsoft Windows.



 Program można pobrać: lo-zywiec.pl/psp7.exe 

Jak uruchomić? ;)
Start-> wszystkie programy-> Jasc Software-> Paint Shop Pro 7