Graf to – w uproszczeniu – zbiór wierzchołków, które mogą być połączone krawędziami, w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków. Graf prosty - graf bez pętli własnych i krawędzi wielokrotnych. Graf z wagami, graf ważony (angielskie weighted graph), graf w którym z każdą krawędzią jest związana jej waga. Digraf, graf skierowany, graf w którym zbiór połączeń, zwanych łukami, jest zbiorem uporządkowanych par wierzchołków.W digrafie wszystkie krawędzie (łuki) mają określony kierunek. Graf spójny, graf połączony graf w którym każda para wierzchołków jest połączona drogą. Drzewo, spójny, acykliczny graf nieskierowany. W zależności od tego, czy wszystkie wierzchołki drzewa są równoprawne, czy też któryś jest wyróżniony, mówi się o drzewie wolnym lub ukorzenionym. Drzewo binarne (angielskie binary tree), struktura danych określona na skończonym zbiorze węzłów, którą można opisać rekurencyjnie w sposób następujący: 1) nie zawiera żadnych węzłów (drzewo puste); 2) składa się z trzech rozłącznych zbiorów węzłów: korzenia, lewego poddrzewa drzewa binarnego i prawego poddrzewa drzewa binarnego. Węzeł drzewa binarnego (każdy lub większość) zawiera wskaźnik do ojca (węzła nadrzędnego) oraz do prawego i lewego syna (węzłów podrzędnych), czyli co najwyżej dwa następniki. Pełne drzewo binarne ma w każdym wierzchołku 0 lub 2 następniki. Proces tworzenia i uruchamiania programów: Zadanie do wykonania-algorytm i projekt programu-test programu (plik źródłowy)-plik wykonywalny programu-system operacyjny, komputer. Algorytm – przepis postępowania prowadzącydo rozwiązania określonego zadania. Program – zapis algorytmu i danych w konkretnym języku programowania. Sposoby reprezentacji algorytmów Język naturalny.-Lista kroków.-Drzewo algorytmu.-Schemat blokowy.-Pseudokod (mniej formalny, bardziej intuicyjny system notacji).-Kod w języku programowania	Własności algorytmów Skończoność (realizowany ciąg operacji powinien mieć swój koniec). Określoność (operacje oraz porządek ich wykonywania powinny być ściśle określone). Ogólność (algorytm powinien odnosić się nie tylko do jednego szczególnego przypadku, ale do pewnej klasy zadań). Efektywność (algorytm powinien prowadzić do rozwiązania możliwie najprostszą drogą). Całkowita poprawność algorytmu Algorytm jest całkowicie poprawny jeśli dla każdych danych wejściowych spełniających wymagane warunki wstępne zatrzymuje się i daje poprawny wynik. Dowód poprawności algorytmu: – udowodnienie własności stopu (dla każdych danych wejściowych spełniających wymagane warunki wstępne algorytm zatrzymuje się), – udowodnienie częściowej poprawności (jeśli algorytm zatrzymuje się to daje poprawny wynik). Podstawowe typy danych w języku C/C++ short, int, long – typy reprezentujące liczby całkowite, usigned short, unsigned int, unsigned long – typy reprezentujące liczby całkowite, float, double – typy reprezentujące liczby rzeczywiste, char – typ reprezentujący znaki. if (warunek) instrukcja Jeśli warunek jest prawdziwy (true), instrukcja zostaje wykonana i sterowanie przenoszone jest do kolejnych instrukcji po instrukcji warunkowej. Jeśli warunek nie jest prawdziwy (false), instrukcja nie zostaje wykonana, a sterowanie przenoszone jest bezpośrednio do kolejnych instrukcji po instrukcji warunkowej. instrukcja może być instrukcją złożoną { }. if (warunek)instrukcja1 else instrukcja2 Jeśli warunek jest prawdziwy (true), tylko instrukcja1 zostaje wykonana i sterowanie przenoszone jest do kolejnych instrukcji po instrukcji warunkowej. Jeśli warunek nie jest prawdziwy (false), tylko instrukcja2 zostaje wykonana i sterowanie przenoszone jest do kolejnych instrukcji po instrukcji warunkowej. instrukcja1 oraz instrukcja2 mogą być instrukcjami złożonymi { }. while (warunek) instrukcja Dopóki warunek jest prawdziwy (true), instrukcja jestwykonywana. Gdy warunek przestaje być prawdziwy (false )sterowanie przenoszone jest do kolejnych instrukcji po instrukcji WHILE. do {instrukcja} while (warunek); Pętla DO-WHILE działa podobnie jak pętla WHILE. Różnicapolega na tym, że warunek jest testowany po wykonaniu instrukcji. W związku z tym instrukcja zostaje wykonana co najmniej jeden raz.	for (zm=pocz; zm<=koniec; zm++) instrukcja ● pocz oraz koniec są wyrażeniami typu całkowitego. ● Zmiennej zm przypisywana jest wartość pocz. Dopóki wartość zmiennej jest mniejsza lub równa wartości koniec, instrukcja jest wykonywana. Za każdym razem wartość zmiennej zwiększana jest o 1. Gdy wartość zmiennej zm staje się większa od wartości koniec sterowanie jest przenoszone do kolejnych instrukcji po instrukcji FOR. Sortowanie przez selekcję (selectionsort) ● W sortowanej tablicy (a[0], a[1], ..., a[n-1]) wybierany jest element minimalny (maksymalny), który zamieniany jest miejscami z pierwszymelementem tablicy (tj. a[0]). ● Z pozostałej części tablicy (a[1], a[2], ..., a[n-1]) ponownie wybierany jest element minimalny (maksymalny), który zamieniany jest miejscami z drugim elementem tablicy (tj. a[1]). ● Analogicznie proces jest kontynuowany dla pozostałych części tablicy. Sortowanie przez wstawianie (insertionsort) ● Sortowana tablica podzielona jest na dwie części: – część uporządkowaną (na początku zawierającą tylko element a[0]), – część nieuporządkowaną (na początku zawierającą elementy a[1], a[2], ..., a[n-1]). ● W każdym kroku kolejny element części nieuporządkowanej przenoszony jest do części uporządkowanej przez wstawienie go na odpowiedniej pozycji. Sortowanie bąbelkowe (bubblesort) ● Sortowanie bąbelkowe polega na zamianie miejscami sąsiadujących ze sobą elementów jeśli są one ustawione w nieodpowiednim porządku. ● Proces powtarzany jest dla nieposortowanych części tablicy dopóty, dopóki wszystkie elementy tablicy nie będą we właściwym porządku. Wydawanie reszty ● Problem: Należy wydać resztę A używając najmniejszej liczby monet. ● Wejście: – A – reszta do wydania, – D – tablica nominałów monet: ● D[0]=1, ● D[0]<D[1]<D[2]<...<D[n-1], ● n – liczba nominałów monet. ● Reguła zachłanna: w każdym kroku należy użyć największego możliwego nominału. Przeszukiwanie proste ● Przeszukiwanie proste polega na porównywaniu wzorca znak po znaku z kolejnymi znakami w tekście aż do momentu gdy wzorzec zostanie odnaleziony w tekście. ● Wejście: – tekst t o długości n, – wzorzec p o długości m, gdzie m≤n. ● Wyjście: – pozycja wzorca p w tekście t.	Przykład 1: Wydawanie reszty ● Problem: Należy wydać resztę A używając najmniejszej liczby monet. ● Wejście: – A – reszta do wydania, – D – tablica nominałów monet: ● D[0]=1, ● D[0]<D[1]<D[2]<...<D[n-1], ● n – liczba nominałów monet. ● Reguła zachłanna: w każdym kroku należy użyć największego możliwego nominału i=1; while(A>0) { c=A/D[n-i]; cout<<”użyj ”<<c<<”monet o nominale ” << D[n-1]; A=A-c*D[n-1]; i=i+1; } Rekurencyjny algorytm obliczania silni int silnia(int n) { if(n==0) { return 1; } if(n>0) { return silnia(n-1)*n; } Wyszukiwanie liniowe pozycja=-1; for(int i=0; i<n; i++) { if( e==t[i]) //element został znaleziony { pozycja=i; break; } } cout<<pozycja; Wyszukiwanie binarne pozycja=-1; lewy=0; prawy=n-1; while(lewy<=prawy) { srodek=(lewy+prawy)/2; if( e==tab[srodek]) //element został znaleziony { pozycja=srodek; break; } else { if( e<tab[srodek]) //należy przeszukiwać pierwszą część { prawy=srodek-1; } else //należy przeszukiwać drugą część { lewy=srodek+1; } } } cout<<pozycja; IF Ptla FOR