-
Notifications
You must be signed in to change notification settings - Fork 1
/
Opracowanie_do_obrony_EZI.tex
2603 lines (1932 loc) · 158 KB
/
Opracowanie_do_obrony_EZI.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\documentclass[a4paper,twoside]{report}
\usepackage[T1]{fontenc}
\usepackage[polish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{hhline}
\usepackage{hyperref}
\PassOptionsToPackage{hyphens}{url}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{psfrag}
\usepackage{float}
\restylefloat{figure}
\usepackage{lmodern}
\usepackage{float}
\selectlanguage{polish}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{geometry}
\newgeometry{tmargin=2.5cm, bmargin=2.5cm, lmargin=2.5cm, rmargin=2.5cm}
\renewcommand*\thesection{\arabic{section}} % zmiana numeracji sekcji 0.X -> X
\author{\textbf{KN EZI Team}}
\title{Opracowanie pytań do obrony (EZI)}
\frenchspacing
\begin{document}
\maketitle
%\bigskip
\tableofcontents %spis tresci
\thispagestyle{empty}
\part{Zagadnienia specjalnościowe}
\bigskip
\chapter{Sterowniki mikroprocesorowe i ich zastosowania}
Główną częścią takiego sterownika jest mikrokontroler pełniący funkcję jednostki wykonującej operacje logiczne i arytmetyczne.
\section{Sterownik PLC}
\paragraph{Programowalny sterownik logiczny PLC} (ang. Programmable Logic Controller) uniwersalne urządzenie mikroprocesorowe przeznaczone do sterowania pracą maszyny lub urządzenia technologicznego. Sterownik PLC musi zostać dopasowany do określonego obiektu sterowania poprzez wprowadzenie do jego pamięci żądanego algorytmu działania obiektu - zaprogramowanie go. Cechą charakterystyczną sterowników PLC odróżniającą ten sterownik od innych sterowników komputerowych jest cykliczny obieg pamięci programu. Algorytm jest zapisywany w dedykowanym sterownikowi języku programowania. Istnieje możliwość zmiany algorytmu przez zmianę zawartości pamięci programu. Sterownik wyposaża się w odpowiednią liczbę układów wejściowych zbierających informacje o stanie obiektu i żądaniach obsługi oraz odpowiednią liczbę i rodzaj układów wyjściowych połączonych z elementami wykonawczymi, sygnalizacyjnymi lub transmisji danych. Układy I/O mogą być cyfrowe lub analogowe.
Zasada działania: przeglądanie wejść i w zależności od ich stanu oraz
wprowadzonego programu użytkownika ustawianie stanu wyjść dwustanowych (zał/wył).
PLC jest w swej istocie komputerem przemysłowym ze specjalnie zaprojektowaną jednostką centralną oraz rozbudowanymi układami wejść/wyjść do kontaktu z zewnętrznymi urządzeniami przemysłowymi (urządzeniami polowymi). Wcześniej działanie sterowników były realizowane przy pomocy rozbudowanej sieci elektrycznej przy zastosowaniu przekaźników.
\paragraph{Historia\\}
Inżynierowie z Hydramatic Division firmy GM w roku 1968 sformułowali założenia dla sterownika programowalnego, którego główna zaletą miała być redukcja wysokich kosztów związanych z niewielką elastycznością systemów przekaźnikowych. W 1969 r. został opracowany pierwszy sterownik PLC.
\paragraph{Założenia sterownika}
\begin{itemize}
\item realizacja na urządzeniach półprzewodnikowych,
\item elastyczność komputera,
\item praca w środowisku przemysłowym (wibracje, wysoka temperatura, zapylenie itp.),
\item możliwość przeprogramowywania,
\item łatwe programowanie i obsługa przez elektryków i techników.
\end{itemize}
\paragraph{Budowa}
\begin{itemize}
\item jednostka centralna (CPU),
\item zasilacz,
\item pamięć,
\item układy I/O,
\item port komunikacyjny (np. PROFIBUS),
\item gniazdo rozszerzenia.
\end{itemize}
\paragraph{Języki programowania}
\begin{itemize}
\item \textbf{drabinkowy LD} (ang. Ladder Diagram) - logika drabinkowa, a schemat podobny do klasycznego rysunku technicznego elektrycznego,
\item \textbf{blokowy FBD} (ang. Function Block Diagram) - diagram bloków funkcyjnych, sekwencji linni zawierająca te bloki,
\item \textbf{strukturalny ST} (ang. Structured Text) - tekst strukturalny - język zbliżony do Pascala;
\item \textbf{lista instrukcji IL} (ang. Instruction List) lista instrukcji - rodzaj asemblera,
\item \textbf{sekwencyjny SFC} (ang. Sequential Function Chart) sekwencyjny ciąg bloków - sekwencja bloków programowych z warunkami przejścia.
\end{itemize}
\paragraph{Poziomy sygnałów cyfrowych}
\begin{itemize}
\item 5, 12, 24, 48 VDC,
\item 24, 128, 240 VAC.
\end{itemize}
\paragraph{Poziomy sygnałów analogowych}
\begin{itemize}
\item 0 ... 20 mA,
\item 4 ... 20 mA (najczęściej),
\item 0 ... 5, 10 V,
\item -10 ... 10 V.
\end{itemize}
Źródłami sygnałów analogowych są: termometry, przepływomierze, wilgotnościomierze, mierniki nacisku, potencjometry.
Analogowe sygnały wejściowe sterują: zaworami analogowymi, szybkością obrotów silników, rejestratorami.
\paragraph{Zadania PLC}
\begin{itemize}
\item skanowanie wejść,
\item wykonywanie instrukcji,
\item ustawianie wyjść,
\item samodiagnostyka.
\end{itemize}
\section{Regulator PID}
\paragraph{Regulator PID} (ang. Proportional-Integral-Derivative controller) – regulator stosowany w układach regulacji składający się z trzech członów: proporcjonalnego, całkującego i różniczkującego. Najczęściej jego celem jest utrzymanie wartości wyjściowej na określonym poziomie, zwanym wartością zadaną. Jest najczęściej stosowanym regulatorem w przemyśle.\\
Właściwości dynamiczne idealnych regulatorów PID mogą być opisane za pomocą transmitancji operatorowej, będącej stosunkiem transformaty Laplace’a sygnału wyjściowego regulatora U’(s) i transformaty Laplace’a uchybu regulacji (sygnału wejściowego) E(s):
\begin{equation}
G_r(s)=\dfrac{U'(s)}{E(s)} = k_p(1+\dfrac{1}{T_i \cdot s}+ T_d \cdot s),
\label{wzor:PID_idealny}
\end{equation}
gdzie: \\
$k_p$ - wzmocnienie członu proporcjonalnego,\\
$T_i$ - czas całkowania (zdwojenia),\\
$T_d$ - czas różniczkowania (wyprzedzenia).\\
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.7]{obrazy/PID_blok.png}
\caption{Schemat blokowy idealnego regulatora PID}
\label{rys:PID_blok}
\end{figure}
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.8]{obrazy/PID_uC_blok.png}
\caption{Schemat blokowy mikroprocesorowego regulatora PID}
\label{rys:PID_uC_blok}
\end{figure}
\paragraph{Zakres proporcjonalności} $X = (1/k_p) \cdot 100 \%$ jest to procentowa część pełnego zakresu zmian wielkości wejściowej e, potrzebna do wywołania pełnej zmiany wielkości wyjściowej u’ regulatora.
\paragraph{Czas zdwojenia (całkowania)} $T_i$ dotyczy regulatorów PI, których wielkość wyjściowa ma zarówno składową proporcjonalną $u_p$, jak i całkującą $u_i$. Czas zdwojenia określa się na podstawie znajomości charakterystyki czasowej skokowej regulatora. Jest to czas potrzebny na to, aby sygnał wyjściowy regulatora, będący wynikiem działania całkującego, stał się równy sygnałowi będącemu wynikiem działania proporcjonalnego (rysunek \ref{rys:czas_zdwojenia}.).
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.4]{obrazy/czas_zdwojenia.png}
\caption{Sposób wyznaczania czasu zdwojenia Ti}
\label{rys:czas_zdwojenia}
\end{figure}
Zatem sygnał wyjściowy z regulatora PI (wypadkowy dla obu oddziaływań) po czasie $T_i$ zwiększa dwukrotnie swoją wartość. Stąd pochodzi jego nazwa – czas zdwojenia.
\paragraph{Czas wyprzedzenia (różniczkowania)} $T_d$ dotyczy regulatorów PD, których wielkość wyjściowa ma zarówno składową proporcjonalną, jak i różniczkującą. Czas wyprzedzenia określa się na podstawie odpowiedzi regulatora na wymuszenie w postaci narastającego liniowo sygnału uchybu regulacji e. Jest to czas, po którym sygnał wyjściowy regulatora, związany zdziałaniem proporcjonalnym $u_p$, zrówna się z sygnałem pochodzącym od działania różniczkującego $u_d$ (rysunek \ref{rys:czas_wyprzedzenia}.).
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.5]{obrazy/czas_wyprzedzenia.png}
\caption{Sposób wyznaczania czasu wyprzedzenia Td}
\label{rys:czas_wyprzedzenia}
\end{figure}
Wielkości $k_p$ (w starszych typach regulatorów X), $T_i$ i $T_d$ noszą nazwę nastaw regulatora. Są to parametry nastrajalne, które dobieramy tak, aby:
\begin{itemize}
\item uzyskać odpowiednie własności dynamiczne regulatora,
\item uzyskać najlepszą jakość regulacji.
\end{itemize}
Transmitancja określona wzorem \eqref{wzor:PID_idealny} dotyczy regulatora idealnego, którego w praktyce nie daje się zrealizować. W warunkach rzeczywistych w członie różniczkującym występuje inercja, określona stałą czasową T. Stała ta nie jest nastawialna. Zatem zamiast członu~$T_d \cdot s$ w transmitancji występuje człon~$T_ds/Ts+1$. Transmitancja operatorowa rzeczywistego regulatora PID ma wówczas postać:
\begin{equation}
G_r(s)=\dfrac{U'(s)}{E(s)} = k_p(1+\dfrac{1}{T_i \cdot s}+ \dfrac{T_d \cdot s}{T s + 1}),
\end{equation}
\section{Sterownik CNC}
\paragraph{Sterownik CNC} (ang. Computer Numerical Control) to typ sterownika mikroprocesorowego, który programuje się za pomocą tzw. G code'u. Sterowniki te używane są m.in. do kontroli takich urządzeń jak: frezarki, tokarki a w szerszym zastosowaniu do sterowania robotami fabrycznymi, które pracują w tzw. trybie taśmy montażowej np. automaty składające podzespoły samochodowe.
W nowoczesnych maszynach CNC stosuje się sterowniki pracujące na bazie komputera przemysłowego IPC w technologii ,,PC-based Automation''. W tej technologii sterownik CNC działa programowo, a nie sprzętowo, tak jak to odbywało się w starego typu dedykowanych sterownikach. System operacyjny czasu rzeczywistego sterownika, realizuje funkcje PLC, HMI i sterowania ruchem, odpowiadając za funkcjonalność całej maszyny.
\section{Kontroler PAC}
\paragraph{Sterowniki PAC} (ang.Programmable Automation Controller) zwane sterownikami automatyki są dużymi systemami sterownikowymi przeznaczonymi do obsługi złożonych procesów technologicznych. Wiele dotychczasowych sterowników PLC o największej wydajności zostało nazwanych przez producentów sterownikami PAC. Granica pomiędzy dużymi i wydajnymi sterownikami PLC a sterownikami PAC jest obecnie słabo widoczna.
Współczesne procesy sterowania wykorzystują ogromne ilości sygnałów i danych, począwszy od analogowych i cyfrowych urządzeń wejścia/wyjścia, poprzez szybkie kamery wysokiej rozdzielczości, a kończąc na wieloosiowych
sterownikach ruchu. Takie zastosowania, jak: szybka produkcja, monitoring pracy maszyn w czasie rzeczywistym, sterowanie precyzyjne czy sterowanie złożonym procesem, wymagają deterministycznych systemów akwizycji, zaawansowanej analizy i algorytmów przetwarzania danych.Wyższej klasy sterowniki PLC w pewnym stopniu spełniają te wymagania. Jednakże do wydajnego przetwarzania tych danych trzeba zastosować odpowiednie środki informatyczne, m.in. procesory zmiennoprzecinkowe i duże zasoby pamięci. Sterowniki PAC integrują tego rodzaju gotowe składniki sprzętowe w ramach systemu czasu rzeczywistego, oferując w ten sposób wydajną platformę dla inżynierów automatyki.
\chapter{Lokalne sieci komputerowe}
\paragraph{Sieci lokalne LAN} (ang. Local Area Network), są sieciami prywatnymi obejmującymi pojedynczy budynek lub grupę budynków w obszarze o średnicy do kilku kilometrów. Sieci te są powszechnie używane do łączenia komputerów osobistych i stacji roboczych w biurach firmy i fabrykach w celu udostępnienia zasobów (np. drukarek) i wymiany informacji.
Sieci LAN od innych typów odróżniają trzy cechy:
\begin{itemize}
\item rozmiary,
\item technologie transmisji,
\item topologia.
\end{itemize}
Sieci LAN mają ograniczone rozmiary, co oznacza, że czas przesyłu w najgorszym przypadku jest ograniczony i z góry znany. Znajomość tych granic umożliwia użycie pewnych rozwiązań, które w innych przypadkach byłyby niemożliwe do zastosowania, a jednocześnie upraszcza zarządzanie siecią.
Sieci lokalne mogą korzystać z technologii transmisji opartej na kablu, do którego podłączone są wszystkie komputery. Tradycyjne sieci LAN charakteryzują się szybkością przesyłu od 10 Mb/s do 100 Mb oraz niskim opóźnieniem. Nowsze sieci lokalne działają z szybkością do 10 Gb/s.
W rozgłoszeniowych sieciach LAN możliwe są różnorodne topologie. Przykładem jest sieć magistralowa (zbudowana z kabla liniowego). W sieci magistralowej, w każdej chwili najwyżej jedno urządzenie jest nadrzędne i ma prawo do nadawania. Potrzebny jest zatem mechanizm arbitrażu który rozstrzyga konflikt tgdy dwa lub więcej urządzeń chce nadawać jednocześnie. Mechanizm arbitrażu może być scentralizowany lub rozproszony. Na przykład sieć Ethernet jest siecią rozgłoszeniową opartą na magistrali ze zdecentralizowanym sterowaniem. Komputery w tej sieci mogą nadawać w dowolnej chwili; w razie kolizji dwóch lub więcej pakietów każdy komputer oczekuje losowy odstęp czasu i ponawia próbę. Drugim typem systemu rozgłoszeniowego jest pierścień. W pierścieniu każdy bit propaguje się samodzielnie bez czekania na resztę pakietu,do którego należy. Zazwyczaj każdy bit okrąża cały pierścień w czasie potrzebnym na transmisję kilku bitów, często zanim komplety pakiet zostanie wysłany.
\chapter{Bazy danych i ich zastosowania}
\paragraph{Baza danych} zbiór danych zapisanych zgodnie z określonymi regułami. W węższym znaczeniu jest to program (system) służący do zbierania, przetwarzania i organizowania informacji.
Bazy danych pozwalają przechowywać dowolne informacje, na przykład informacje o ludziach, produktach czy zamówieniach. Dla systemów komputerowych mogą to być dane numeryczne, tekstowe, binarne, daty, lub inne dostępne typy w danym systemie. Można więc przechowywać grafikę, muzykę - np. jako pliki binarne. Kartoteka w bibliotece to również baza danych.
Za bazę danych uważany może być plik tekstowy, arkusz kalkulacyjny, plik binarny. Gdy ilość danych rośnie, powstają nadmiarowe i niespójne dane. Dlatego wprowadza się różne systemy bazodanowe umożliwiające łatwiejsze zarządzanie dużą ilością danych - np. MS SQL, MySQL, Access.
Z uwagi na cenę danych współczesne systemy bazodanowe stanowią podstawą działalności wielu firm, co wymaga istnienia możliwie niezawodnych systemów baz danych. \\
\textbf{System zarządzania bazą danych} - oprogramowanie umożliwiające tworzenie oraz eksploatację bazy danych oraz jej użytkowników. \\
\textbf{baza danych} = dane + schemat bazy danych (np. relacyjny) \\
\textbf{system bazy danych} = baza danych + system zarządzania bazą
\medskip
\paragraph{Kryteria klasyfikacji baz danych}
\begin{itemize}
\item wielkość
\item liczba odwołań
\item stopień ważności informacji
\item struktura informacji
\item implementacja komputerowa
\end{itemize}
Bazy danych można podzielić według struktur organizacji danych, których używają:
\begin{itemize}
\item Bazy proste: kartotekowe, hierarchiczne (struktura drzewa, np katalogi w systemie)
\item Bazy złożone: relacyjne, obiektowe, relacyjno-obiektowe, strumieniowe, temporalne, nierelacyjne (NoSQL), grafowe
\end{itemize}
Z wymienionych struktur, w praktyce zdecydowanie najczęściej używane są bazy relacyjne.
\medskip
\section{Bazy relacyjne}
Relacyjny model danych został zaproponowany w latach 70. Zaimplementowany w latach 80.
Opiera się on (suprise) na pojęciu relacji. Dane grupowane są w relacje reprezentowane przez tablice. Czyli tablica STUDENCI zawierająca wiersze (krotki) z danymi studentów (imię, indeks - kolumny), o odpowiednich typach - całość tworzy relację.
W modelu obiektowym relacji odpowiada obiekt. \\
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.7]{obrazy/bazy/Relational_model_concepts_PL.png}
\caption{Relacja}
\end{figure}
\paragraph{Pojęcia}
\begin{itemize}
\item klucz podstawowy (główny) - najkrótszy zbiór atrybutów (czyli kolumn) pozwalający na \textbf{jednoznaczną} identyfikację wiersza w tabeli. Max 1 na tabelę
\item klucz obcy - kolumna zawierająca wartości wskazujące na \textit{klucz główny} w innej tabeli, pozwala stworzyć związek pomiędzy tabelami. Typy związków: jeden do jednego, jeden do wielu, wiele do wielu (najczęściej realizowane za pomocą tabeli pośredniej)
\end{itemize}
Związki pomiędzy relacjami pozwalają uniknąć nadmiarowości danych i pozwalają zapewnić ich spójność. Jeżeli np. mamy tabelę studenci i samochody, relacja wiele do jednego (każdy samochód posiada klucz obcy czyli np. indeks studenta). Jeden student może posaiadać więc wiele samochodów. Jeżeli chcemy sprawdzić czyj jest dany samochód to mamy klucz obcy studenta, a nie jesgo wszystkie dane - czyli wystarczy raz wpisać studenta, a zmiana jego danych następuje tez w jednym miejscu. Czyli minimalna ilośc danych zapewnia spójność. Zły przypadek - tabela samochody zawiera wszystkie dane studenta, on zmienia imię, trzeba aktualizować dane we wszystkich jego samochodach (i pewnie o którymś się zapomni).\\
Zasady projektowania schematów relacyjnych baz danych opisują \textbf{zasady normalne}, najważniejsze:
\begin{itemize}
\item 1NF atrybuty są atomowe (niepodzielne) - kolumna [imię,nazwisko] - należy rodzielić na 2 osobne kolumny, jedna komórka zawiera jedną wartość, czyli nie chcemy kolumny imiona
\item 2NF każda kolumna niekluczowa zależy funkcyjnie od całego klucza głównego (i tak nikt o to nie zapyta ani nikt nie wykuje, ale wstawiam)
\item 3NF każda komórka w wierszu zależy jedynie od klucza głównego, \\
\lbrack indeks\rbrack, \lbrack imię\rbrack], \lbrack płeć\rbrack \\
Zakładając że indeks to klucz główny, a płeć jest jednak związana z imieniem to ta ka tabela nie spełni tego wymagania, należy wydzielić drugą tabelę imiona: [imię], [płeć] a studentowi zostawić indeks i klucz obcy do tabeli imiona
\end{itemize} .
Do pracy z relacyjnymi bazami danych służy SQL - standardowy język zapytań, używany do tworzenia, modyfikowania baz danych oraz do umieszczania i pobierania danych z baz danych.
Konkretnie: selekcje, projekcje, złączanie, usuwanie, modyfikację dodawania danych, a także operacje na schematach bazy danych - tworzenie, modyfikowanie tabel. \\
Zawiera on typy danych, umożliwia tworzenie funkcji, procedur składowanych.
\section{Z wikipedii (takie powtórzenie)}
Relacyjne bazy danych (jak również przeznaczony dla nich standard SQL) oparte są na kilku prostych zasadach:
\begin{enumerate}
\item Wszystkie wartości danych oparte są na prostych typach danych.
\item Wszystkie dane w bazie relacyjnej przedstawiane są w formie dwuwymiarowych tabel (w matematycznym żargonie noszących nazwę „relacji”). Każda tabela zawiera zero lub więcej wierszy (w tymże żargonie – „krotki”) i jedną lub więcej kolumn (,,atrybutów''). Na każdy wiersz składają się jednakowo ułożone kolumny wypełnione wartościami, które z kolei w każdym wierszu mogą być inne.
\item Po wprowadzeniu danych do bazy, możliwe jest porównywanie wartości z różnych kolumn, zazwyczaj również z różnych tabel, i scalanie wierszy, gdy pochodzące z nich wartości są zgodne. Umożliwia to wiązanie danych i wykonywanie stosunkowo złożonych operacji w granicach całej bazy danych.
\item Wszystkie operacje wykonywane są w oparciu o algebrę relacji, bez względu na położenie wiersza tabeli. Nie można więc zapytać o wiersze, gdzie (x=3) bez wiersza pierwszego, trzeciego i piątego. Wiersze w relacyjnej bazie danych przechowywane są w porządku zupełnie dowolnym – nie musi on odzwierciedlać ani kolejności ich wprowadzania, ani kolejności ich przechowywania.
\item Z braku możliwości identyfikacji wiersza przez jego pozycję pojawia się potrzeba obecności jednej lub więcej kolumn niepowtarzalnych w granicach całej tabeli, pozwalających odnaleźć konkretny wiersz. Kolumny te określa się jako ,,klucz podstawowy'' (ang. primary key) tabeli.
\end{enumerate}
\paragraph{Zastosowania}
\begin{itemize}
\item systemy bankowe (bankomat)
\item systemy masowej obsługi (hipermarket)
\item rezerwacja biletów lotniczych
\item telefonia komórkowa (sms)
\item Dziekanat Wydziału Elektroniki
\item toto-lotek
\item policja (ewidencja przestępców, rejestr samochodów)
\item rejestry sądowe, księgi wieczyste
\item ankiety internetowe
\item sklepy internetowe
\item gry internetowe
\item system audiotele
\item biblioteka PWr.
\end{itemize}
\subsection{Architektura Oracle}
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.7]{obrazy/archoracle.png}
\caption{Architektura systemu}
\end{figure}
\medskip
\paragraph{Rodzaje plików}
\begin{itemize}
\item pliki konfiguracyjne (init files) — najważniejszy z nich to plik parametrów (tzw. parameter file, w skrócie pfile) o nazwie init<SID>.ora, gdzie <SID> to unikalny (najczęściej 4-literowy) identyfikator instancji na danej maszynie, plik jest tekstowy i zawiera informacje o ustawieniach przy starcie bazy, a także o nazwie i położeniu plików kontrolnych
\item pliki kontrolne (control files) — binarne, bardzo ważne, zawierają informacje o położeniu WSZYSTKICH plików bazy danych wraz z datą i godziną ich zamknięcia
\item pliki danych (data files) — przechowują dane w postaci binarnej, z danych w nich zawartych korzysta się za pośrednictwem procesów serwera (tła)
\item pliki dziennika powtórzeń (redo-log files) - rejestrują wszystkie operacje wykonane na bazie (na wypadek awarii), mogą być aktywne lub zarchiwizowane
\item pliki śladu (trace files) — zawierają informacje o uszkodzeniach i o błędach procesów tła oraz procesów użytkowników
\item pliki kodu (code files) — wszelkie kody źródłowe, skrypty SQL itp
\end{itemize}
\textbf{SGA} (ang. System Global Area).
Składa się z:
\begin{itemize}
\item bufora danych, który:
Zawiera dane załadowane z dysku, okresowo zapisane (Dirty blocks), przechowuje informacje o zmianach, ma strukturę cykliczną.
\item bufora dziennika powtórzeń, który przechowuje informację o zmianach, ma strukturę cykliczną.
\item obszaru współdzielonego
\end{itemize}
\paragraph{Procesy tła}
\begin{itemize}
\item DBWR — database writer — zapisuje DIRTY BLOCKS na dysk
\item LGWR — log writer — zapisuje zmiany do loga
\item CKPT — checkpoint — sygnalizuje tzw. punkt kontrolny + aktualizuje nagłówki plików kontrolnych
\item SMON — system monitor — odtwarza instancję, scala wolne obszary na dysku
\item PMON — process monitor — zwalnia zasoby procesu użytkownika, który się ,,zawiesił''
\item ARCH — archiwizator — opcjonalny, spowalnia pracę, umożliwia skonfigurowanie serwera lustrzanego
\end{itemize}
\paragraph{Stany bazy danych}
\begin{itemize}
\item IDLE - nieczynna, pliki zamknięte, procesy tła nie działają
\item NOMOUNT - stan po odczytaniu pfile-a, zainicjowaniu SGA i uruchomieniu procesów tła, stan służący do tworzenia nowej bazy danych
\item MOUNT - stan po odczytaniu plików kontrolnych i otwarciu połaczenia z plikami danych i log-ami
\item OPEN - stan otwarcia bazy, dane są dostępne dla użytkowników (w wyjątkowych sytuacjach stan można uruchomić w tzw. trybie RESTRICTED, wtedy dostęp do bazy mają tylko administratorzy)
\end{itemize}
\chapter{Przetwarzanie obrazów, metody i zastosowania}
\paragraph{Reprezentacja obrazu}
Obraz cyfrowy powstaje poprzez kwantyzację i próbkowanie obrazu analogowego. Wynikiem jest uporządkowana siatka kwadratów, z których każdy zawiera informację o obrazie wejściowym jak np. średnia jasność w obszarze. Każdy z kwadratów siatki zwany jest pikselem, a ich liczba i wielkość są podstawowymi wartościami opisującymi matryce służące do akwizycji obrazu jak CCD lub CMOS.
Rozróżniamy obrazy jednobarwne - \textit{monochromatyczne}, binarne, barwne.
Cyfrowy zapis obrazu polega na zdefiniowaniu przestrzeni barw w jakiej zapisujemy obraz (RGB, CMYK, inne), głębi obrazu - czyli bitów na kanał co określa ilość możliwych do przedstawienia barw. Przykładowo: \\
typowa kamerka internetowa - ramka obrazu składa się z trzech kanałów - obrazów monochromatycznych, dla których zakres wartości przypisywanych pikselom należy do przedziału 0-255. Kanały reprezentują kolory z palety barw RBG, obraz końcowy powstaje poprzez złączenie wszystkich kanałów.
Zapewnia to 24-bitową głębie kolorów (3 kanały po 8 bitów), tzn. pozwala reprezentować $2^{24}$ kolorów. Tryb ten nazywany jest \textit{true color}.
4 kanałem często używanym np. w formacie png może być kanał A \textit{Alpha} odpowiadający za (nie)-przeźroczystość.
\section{Algorytmy przetwarzania obrazów}
Pojęcie \textbf{przetwarzania obrazów} można rozumieć dwojako. W wąskim sensie oznacza operacje, które przetwarzają jedne obrazy w inne - zarówno dane wejściowe jak i wyjściowe mają formę obrazu. W tym sensie zawierają się:
\begin{itemize}
\item akwizycja obrazów - wprowadzenie obrazów, zwłaszcza cyfrowych do systemów technicznych (sorki, brzydka definicja),
\item reprezentacja obrazu i modelowanie - dobór reprezentacji obrazu w systemie tech., by odpowiadała ona charakterowi obrazu i przeznaczeniu reprezentacji, również modele matematyczne obrazów. Głębia, przestrzeń barw
\item polepszanie obrazów - wytwarzanie obrazów subiektywnie ocenianych przez człowieka jako lepsze
\item odzyskiwanie, restauracja obrazów - usuwanie zniekształceń (geometrycznych), zakłóceń (szumy, rozmycia)
\item kompresja obrazów - bezstratna jak i stratna
\item znakowanie wodne - umieszczanie i odczytywanie dodatkowych, często niewidocznych informacji
\item prezentacja, wyświetlanie obrazów
\end{itemize}
Z tego punktu widzenia grafika komputerowa, animacje komputerowe stanowią oddzielną grupę metod.
W szerszym sensie do przetwarzania obrazów zalicza się \textbf{analizę obrazów}, w której dane wejściowe odpowiadają obrazom, natomiast dane wyjściowe mają inny charakter. Z analizą obrazów związane jest \textbf{rozpoznawanie wzorców} którego celem jest identyfikacja pewnych struktur w obrazach.
Trzecią kategorię metod przetwarzania stanowi \textbf{analiza obrazów}:
\begin{itemize}
\item analiza ogólnych cech obrazu lub jego fragmentu - np. analiza cech ilościowych wartości pikseli, barwy punktów
\item ekstrakcja cech - np. krawędzi, struktur geometrycznych
\item segmentacja - podział obrazu na spójne obszary o podobnych cechach (ruch, kolor)
\item analiza tekstur - wydzielenie np. drewna, tkaniny i analiza cech
\item analiza sceny i zdarzeń - określanie zależności przestrzennych i czasowych pomiędzy obiektami, analiza ruchu obiektów, zdarzeń itp.
\end{itemize}
\subsection{Operacje punktowe}
Należą do I grupy metod (obraz w obraz). Przekształcają każdy z pikseli wejściowych $ u(n_1,n2) $ w piksel $ y(n_1,n2) $ według:
$$ y(n_1,n2) = F[u(n_1,n_2)] $$
Gdzie $n_1, n_2 $- indeks poszczególnego piksela, np. współrzędne x,y, trzeci parametr ($n_3$) może być kanałem.
Przykład - dodanie +70 do wartości każdego piksela przyciemni obraz kolorowy jako całość, przy obrazie binarnym zamiana 0 na 1 i odwrotnie - negatyw obrazu.
Wszystkie piksele obliczane są niezależnie, co pozwala zrównoleglać te algorytmy. Przykłady:
\begin{itemize}
\item dodanie stałej C $ y(n_1,n2) = u(n_1,n_2) + C $
\item inwersja obrazu $ y(n_1,n2) = 255 - u(n_1,n_2) $ (dla 8-bitowego obrazu)
\end{itemize}
Operacje punktowe pozwalają wykorzystywać tablicowanie, (\textit{look-up-table} - LUT), zamiast wyliczać każdy piksel przechowujemy w pamięci zbiór wszystkich wartości, np. 40 zamieniamy na 70, 41 na 71... dzięki czemu wystarczy sprawdzić i wstawić wartość zamiast liczyć.
Wszystkie operacje punktowe można wykonywać z nasyceniem lub bez, dodanie 100 do 200 w 8 bitowej głębi (max 255) może dać czarny (255) przy nasyceniu (operacja nieliniowa!), lub 45 (czyli jasny) przy ,,zawinięciu`` się wartości.
\subsection{Histogramy}
Wyliczenie histogramu pozwala ,,zobaczyć`` ile pikseli jakiego koloru występuje w obrazie, np. dominują piksele czerwone nad zielonymi, albo jasne nad ciemnymi.
Pozwala ocenić kontrast - równomierny histogram oznacza wiele detali w obrazie (dużo różnych pikseli), w innym przypadku obraz jest np. niedoświetlony. Histogram pozwala również opisać operacje punktowe. Dodanie stałej to nic innego jak przesunięcie histogramu.
\subsection{Operacje algebraiczne}
Operacje punktowe działające na wielu obrazach, przykładowo mając kilka identycznych obrazów, z różnym szumem można je dodać i uśrednić eliminując szum.
\subsection{Binaryzacja} - progowanie, zmiana obrazu na binarnym, według jakiegoś progu, np. $u<100 \ge 0$, $u \ge 100 \ge 1$.
\subsection{Filtracje}
Algorytmy usuwające zakłócenia, szumy. Wartość piksela obliczana jest na podstawie jego i otoczenia - o jego wielkości i kształcie decyduje maska, np prostokątna o wymiarach 5x5. Przykładowe filtry:
\begin{itemize}
\item \textbf{uśredniający} - najprostszy, liczy średnią wartość pikseli pod maską, rozmywa obraz (ale usuwa szumy)
\item \textbf{Gaussa} - rozmywający, ale według rozkładu normalnego. Czyli średnia ważona
\item \textbf{bilateralny} - Gaussa z uwzględnieniem różnicy kolorów (jak zupełnie inne piksele to nie uśrednia), usuwa szum, zachowuje krawędzie więc bardzo przydatne przed np. wykrywaniem krawędzi
\item \textbf{medianowy} - filtr nieliniowy, wartość piksela równa jest medianie pikseli pod maską, suwa zakłócenia impulsowe z obrazu (\textit{pieprz i sól}), losowe bardzo jasne/ciemne piksele na obrazie
\end{itemize}
\subsection{Decymacja i interpolacja\\\\}
Zmniejszenie/zwiększenie rozdzielczości obrazu. Interpolację można opisać jako wstawienie zer w miejsca nowych próbek, a następnie wygładzenie obrazu filtrem dolnoprzepustowym.
\subsection{Wykrywanie krawędzi\\\\}
Rodzina algorytmów krawędziujących, np. na podstawie gradientu czyli skokowych zmian wartości pikseli. Przydatne przy algorytmach identyfikujących, pozwalają łatwiej ocenić kształt.
\section{Inne zastosowania}
Wszelkie algorytmy identyfikujące, twarz, rękę, samochód. Działają na podstawie wykrycia kształtu i/lub koloru. Okrągłe i cieliste - raczej głowa, kolorowe i kwadratowe - pewnie samochód. (sorki, chyba za późno to piszę).
\chapter{Miary i oceny dokładności algorytmów przybliżonych}
\paragraph{Algorytmy aproksymacyjne} – algorytmy służące do znajdowania przybliżonych rozwiązań problemów optymalizacyjnych. Stosuje się je zwykle do rozwiązywania problemów, dla których nie są znane szybkie algorytmy znajdujące rozwiązanie dokładne, na przykład dla problemów NP-zupełnych.
Istotą algorytmu aproksymacyjnego, tym co odróżnia go od algorytmu heurystycznego, jest związana z każdym takim algorytmem informacja o koszcie zwracanego rozwiązania w stosunku do rozwiązania optymalnego. Mianowicie koszt rozwiązania zwróconego przez algorytm aproksymacyjny jest nie większy (w przypadku problemu minimalizacyjnego) albo nie mniejszy (w przypadku problemu maksymalizacyjnego) od rozwiązania optymalnego pomnożonego przez pewną stałą.
\paragraph{Oszacowania jakości algorytmów aproksymacyjnych\\\\}
Załóżmy, że mamy do czynienia z problemem optymalizacyjnym, w którym każde potencjalne rozwiązanie ma dodatni koszt i, że chcemy znaleźć rozwiązanie prawie optymalne. Zależnie od problemu rozwiązanie optymalne może być zdefiniowane jako to o maksymalnym możliwym koszcie lub o minimalnym; zadanie może polegać na maksymalizacji albo na minimalizacji.
Mówimy, że algorytm aproksymacyjny dla danego problemu ma ograniczenie względne p(n), jeśli dla dowolnych danych wejściowych rozmiaru n koszt C rozwiązania konstruowanego przez ów algorytm szacuję się z dokładnością do czynnika p(n) przez koszt C' rozwiązania optymalnego:
$$ max(\frac{C}{C'},\frac{C'}{C}) \le p(n) $$
Definicja ta stosuję się zarówno do problemów minimalizacji, jak i maksymalizacji. Dla problemu maksymalizacji $ 0 < C \le C' $, a współczynnik C'/C określa ile razy koszt rozwiązania optymalnego jest większy od kosztu rozwiązania przybliżonego. Podobnie dla problemu minimalizacji $ 0 < C' \le C$, a współczynnik C/C' określa ile razy koszt rozwiązania przybliżonego jest większy od kosztu rozwiązania optymalnego. Ponieważ zakładamy, że wszystkie rozwiązania mają dodatni koszt, współczynniki te są zawsze dobrze określone. Ograniczenie względne algorytmu aproksymacyjnego nigdy nie jest mniejsze niż 1, ponieważ nierówność C/C' < 1 implikuje C'/C > 1. Ograniczeniem względnym algorytmu optymalnego jest 1, a algorytm aproksymacyjny o dużym ograniczeniu względnym może dać rozwiązanie znacznie gorsze niż optymalne.
Czasami wygodniej operować pojęciem błędu względnego. Dla dowolnych danych wejściowych błąd względny definiuję się jako:
$$ \frac{|C-C'|}{C'}$$
gdzie, jak poprzednio C' jest kosztem rozwiązania optymalnego, a C to koszt rozwiązania uzyskanego za pomocą algorytmu aproksymacyjnego. Błąd względny jest zawsze nieujemny. Dla algorytmu aproksymacyjnego $\epsilon (n$ jest ograniczeniem błędu względnego, jeśli:
$$ \frac{|C-C'|}{C'} \le \epsilon(n)$$
Z powyższych definicji wynika, że ograniczenie błędu względnego można oszacować przez funkcje ograniczenia względnego
$$ \epsilon (n) \le p(n) -1 $$
(Dla problemu minimalizacyjnego jest to równość, podczas gdy dla problemu minimalizacyjnego mamy $\epsilon (n) = (p(n)-1)/p(n) $; spełniona jest wiec nierówność, ponieważ $ p(n) \ge 1 $).
Dla wielu problemów skonstruowano algorytmy aproksymacyjne o stałym, niezależnym od n ograniczeniu względnym. W takich przypadkach bedziemy pisać p lub $\epsilon$ wskazując w ten sposób na niezależność od n.
Dla innych problemów informatykom nie udało się zaprojektować żadnego wielomianowego algorytmu aproksymacyjnego o stałym ograniczeniu względnym. Wszystko co można wówczas robić to potraktować ograniczenie względne jako funkcję rosnąco wraz z rozmiarem danych wejściowych. Przykładem takiego problem jest problem pokrycia zbioru.
Dla niektórych problemów NP- zupełnych istnieją algorytm aproksymacyjne za pomocą których można uzyskiwać coraz mniejsze ograniczenie względne (lub, równoważnie, malejący błąd względny) kosztem dłuższego czasu obliczeń. Inaczej mówiąc, zachodzi odwrotnie proporcjonalna współzależność między czasem obliczeń a jakością aproksymacji. Przykładem może być problem sumy podzbioru. Sytuacja jest na tyle ważna, że zasługuje na własną nazwę.
\paragraph{Schemat aproksymacyjny} dla problemu optymalizacyjnego to algorytm aproksymacyjny, otrzymujący na wejściu nie tylko komplet danych opisujących problem, ale także wartość $\epsilon > 0$ taką, że dla każdego ustalonego $\epsilon$ schemat ten jest algorytmem aproksymacyjnym o ograniczeniu błędu względnego $\epsilon$. Mówimy, że schemat aproksymacyjny jest wielomianowym schematem aproksymacji, jeśli dla dowolnego ustalonego $\epsilon > 0$ działa on w czasie wielomianowym ze względu na rozmiar n jego danych wejściowych.
Czas działania wielomianowego schematu aproksymacji nie powinien też rosnąć zbyt gwałtownie, kiedy zmniejsza się $\epsilon$. Najlepiej, gdyby zmniejszenie $\epsilon$ o stały czynnik nie powodowało wzrostu czasu obliczeń potrzebnych do osiągnięcia dostatecznego przybliżenia o więcej niż stały czynnik. Innymi słowy, chcielibyśmy aby czas obliczeń było wielomianem ze względu na n, ale również, ze względu na $1/\epsilon$.
Mówimy, że schemat aproksymacji jest w pełni wielomianowym schematem aproksymacji, jeśli czas jego działania jest wielomianem zarówno ze względu na $1/\epsilon$ jak i rozmiar n danych wejściowych, gdzie $\epsilon$ jest ograniczeniem błędu względnego schematu. Czas działania schematu mógłby na przykład wynosić $ (1/\epsilon)^2 \cdot n^3 $. Dla takiego schematu dowolne zmniejszenie o stały czynnik ograniczenia błędu względnego daję się osiągnąć za pomocą odpowiedniego zwiększenia o stały czynnik czasu obliczeń.
\chapter{Systemy operacyjne komputerów}
\paragraph{System operacyjny}
(ang. Operating System) jest środowiskiem programów tworzących główną platformę programową umożliwiającą działanie zainstalowanego w systemie oprogramowania. OS nadzoruje pracę wszystkich uruchomionych procesów oraz urządzeń komputera. Pomimo iż swą pracę wykonuje przeważnie w tle i sam w sobie nie tworzy z komputera w pełni funkcjonalnego narzędzia jednak bez niego komputer jest kompletnie bezużyteczny. System operacyjny zainstalowany na dysku twardym komputera decyduje jakie oprogramowanie może zostać uruchomione pod jego kontrolą, wpływa na bezpieczeństwo danych, realizuje połączenia do sieci nadzorując podrzędne systemy pracujące na innych komputerach, określa kompatybilność wobec innych systemów, decydując o funkcjonalności stabilności pracy. Niestety nie istnieje system idealny, każdy ma swoje zalety i wady.
\paragraph{Budowa i zadania poszczególnych warstw OS\\\\}
Podczas pracy OS komunikuje się zazwyczaj z elektroniką komputera poprzez BIOS i sterowniki choć jest możliwa również jego bezpośrednia komunikacja ze sprzętem co zostało pokazane na rysunku \ref{rys:warstwowy_model_OS}. System operacyjny można przedstawić w postaci modelu warstwowego.
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.8]{obrazy/warstwowy-model-systemu.jpg}
\caption{Warstwowy model systemu}
\label{rys:warstwowy_model_OS}
\end{figure}
\paragraph{Główne zadania stawiane przed systemami operacyjnymi to:}
\begin{itemize}
\item zarządzanie zasobami komputera - systemy operacyjne staruję oraz optymalizują wykorzystanie określonych urządzeń, które wchodzą w skład zestawu komputerowego; specjalne moduły zwane sterownikami, które składają się na system operacyjny udostępniają aplikacjom spójne metody programowania urządzeń (interfejsy), co gwarantuje współdziałanie każdego nowego urządzania z oprogramowaniem (jeżeli producent dostarczy właściwy sterownik)
\item gromadzenie oraz zarządzanie danymi - systemy operacyjne wyposażone są w modułu obsługujące system plików, czyli struktury umieszczone na dyskach, pomagające w logiczny sposób uporządkować dane, grupując je w katalogi i pliki
\item maszyny wirtualne - systemy operacyjne udostępniają aplikacjom tzw. maszyny wirtualne, czyli uproszczone obrazy maszyn, na których pracują aplikacje; system udostępnia aplikacjom szczegóły dna temat komputera oraz rozszerzenia ułatwiające pracę (np. zasoby udostępniane poprzez sieć aplikacje widzą tak, jakby znajdowały się one na dysku lokalnym; aplikacja, która korzysta z takiego zasobu nie obsługuje pracy sieciowej, więc aby umożliwić jej dostęp do zasobu, system operacyjny symuluje, jest zasób ten jest lokalny udostępniając go dla aplikacji)
\item wielozadaniowość - na pojedynczym komputerze funkcjonować może wiele aplikacji w jednym czasie; każda aplikacja otrzymuje swoją maszynę wirtualną i może pracować jakby była pojedynczym programem działającym na maszynie; dzięki takiej właściwości systemów operacyjnych nie ma potrzeby przystosowywania aplikacji, by mogła dzielić się daną maszyną z innymi aplikacjami
\item interakcja z użytkownikiem - rolę tę spełnia najbardziej zewnętrzna warstwa systemu operacyjnego zwana powłoką (ang. shell), która pozwala użytkownikowi uruchamiać aplikacje; w systemach graficznych do powłoki zaliczają się także typowe elementy interfejsu, z których korzysta aplikacja, jak kontrolki czy okna dialogowe
\item komunikowanie się z innymi komputerami - jest to jeden z najistotniejszych elementów systemów operacyjnych; dzięki modułom obsługi sieci można uzyskać dostęp do Internetu, do dysków komputerów stojących w sąsiednim pomieszczeniu czy sieciowych urządzeń peryferyjnych jak drukarki czy skanery
\end{itemize}
\paragraph{Najważniejszymi cechami, które decydują o użyteczności danego systemu operacyjnego są:}
\begin{itemize}
\item prostota instalacji oraz użytkowania systemu
\item współpraca z innymi systemami, czyli możliwość odczytu i zapisu danych na partycjach z innych systemów a także współpraca oraz wymiana danych między komputerami w sieciach lokalnych i Internecie
\item zgodność sprzętowa (instalację na konkretnej maszynie utrudnia czasami brak właściwych sterowników dla określonych urządzeń)
\item wymiana danych, czyli możliwość przeglądania oraz wymiany dokumentów pomiędzy różnymi aplikacjami pracującymi pod kontrolą różnych systemów
\item możliwość pracy sieciowej (wygoda podczas przeglądania zasobów sieciowych, wymiany protokołów, itp.)
\item cena
\item liczba aplikacji, które działają w danym systemie (nawet najlepiej pracujący system będzie niemal bezużyteczny, jeżeli oferta oprogramowania, które współpracuje z tym systemem będzie niewielka)
\item lokalizacja (możliwość komunikacji użytkownika z systemem w ojczystym języku)
\end{itemize}
Schemat z rysunku \ref{rys:warstwowy_model_OS}. przedstawia ogólną budowę systemu operacyjnego. Podstawową częścią OS jest jądro systemu (kernel). Jądro odpowiedzialne jest za pracę systemu i wykonywanie wszystkich jego zadań. Jądro poprzez sterowniki i BIOS komunikuje się z elektroniką komputera. Aby użytkownik mógł komunikować się z jądrem system operacyjny posiada powłokę (Shell lub też interpreter). Powłoka systemowa jest to program pełniący rolę pośrednika pomiędzy całym systemem operacyjnym a użytkownikiem. Powłoki mogą być tekstowe lub graficzne.
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.7]{obrazy/zadania-systemu-operacyjnego.png}
\caption{Składniki systemu operacyjnego i ich zadania}
\label{rys:zadania_systemu_operacyjnego}
\end{figure}
\paragraph{Systemy operacyjne podzielić można ze względu na:}
\subparagraph{Sposób komunikacji systemu z użytkownikiem:}
\begin{itemize}
\item systemy tekstowe - komunikacja przebiega przy pomocy komend wprowadzanych z linii poleceń (DOS, CP/M)
\item systemy graficzne - komunikacja odbywa się przy pomocy graficznych symboli (okienek oraz ikon); obsługa systemu polega na manipulacji przy pomocy myszy bądź klawiatury symbolami odpowiadającym określonym zadaniom (MC Windows, MacOS)
\end{itemize}
\subparagraph{Architekturę systemu:}
\begin{itemize}
\item monolityczne - jednozadaniowe systemy posiadające najprostszą strukturę, gdzie w danym czasie może być realizowane tylko jedno zadanie
\item warstwowe - posiadające hierarchiczną strukturę poleceń systemowych; możliwa jest realizacja wielu zadań jednocześnie (np. nadzorowanie procesu drukowania podczas edycji tekstu)
\item klient/serwer - systemy posiadając bardzo rozbudowaną strukturę, nadzorujące podrzędne systemy zainstalowane na komputerach w sieci; systemy te postrzegają aplikacje jako klientów, korzystających z usług serwerów; aplikacja ,,klient'' komunikuje się z serwerem przez jądro systemowe, natomiast każdy serwer działa we własnej, chronionej i wydzielonej przestrzeni adresowej w pamięci operacyjnej, gdzie jest odizolowany od innych zadań; systemy klient/serwer realizują swe zadania na trzy sposoby:
\item wszelkie aplikacje uruchamiane są na serwerze, a wyniki prezentowane u "klienta"
\item serwer dostarcza zasobów dla aplikacji, które uruchamiane są po stronie klienta
\item wszelkie komputery współdziałają ze sobą na zasadzie równy z równym (ang. peer to peer), wykorzystując wzajemnie swoje zasoby
\end{itemize}
\paragraph{Przykłady systemów:}
\begin{itemize}
\item Windows
\item Linux
\item Unix
\item OS X/ Mac OS X
\item Android
\end{itemize}
\chapter{Zadania optymalizacji i techniki ich rozwiązywania}
Optymalizacja - znalezienie wariantu ocenianego według danego kryterium jako najlepszy spośród wariantów uznanych za dopuszczalne.
\subsection{Sformułowanie zadania optymalizacji}
Wektor zmiennych decyzyjnych x:
\[x=[x_1, x_2,...x_n]^T,\]
gdzie:\\
n - ilość zmiennych decyzyjnych.
\\\\
Funkcja celu (funkcja kryterialna) f(x):
\[f(x)~:~R^n \longrightarrow R^1\]
oraz m funkcji ograniczeń $g_i(x)$:
\[g_i(x): R^n \longrightarrow R^1~~dla~i=1,...,m\]
Zadanie optymalizacji polega na znalezieniu wektora zmiennych decyzyjnych
x, należącego do zbioru rozwiązań dopuszczalnych \textbf{X} w postaci:
\[X = {x|g_i(x) \le 0,~~i=1,...,m}\]
takiego, że dla wszystkich $x \in X$
\[f(\hat{x})<= f(x).\]
Co jest równoznaczne zapisowi:
\[min_{x \in X} f(x) = f(\hat{x}).\]
\begin{figure}[H]
\includegraphics[scale=1.2
]{obrazy/optymalizacja/opt1.png}
\end{figure}
D - zbiory dopuszczalne.\\
\\
PO POLSKU: \\
Sformułowanie zadania optymalizacji polega na znalezieniu takiego zestawu wielkości zmiennych (z wektora zmiennych decyzyjnych), że będzie spełniał podane ograniczenia (na przykład że nie mogą być wartości ujemne), czyli należał do zbioru dopuszczalnego, oraz że będzie to rozwiązanie najlepsze według podanego kryterium, czyli funkcji celu (najmniejsze, największe, itp). Może też okazać się , że zadanie nie posiada rozwiązania , bądź też posiada nieskończenie wiele rozwiązań optymalnych. \\
Przypomnienie czym są ekstrema lokalne i globalne:
\begin{figure}[H]
\includegraphics[scale=1.2
]{obrazy/optymalizacja/opt2.png}
\end{figure}
\subsubsection{Klasyfikacja zadań}
Ze względu na ograniczenia:
\begin{itemize}
\item Zadania bez ograniczeń (dopuszczalne wszystkie warianty)
\item Zadania z ograniczeniami (określono w zadaniu zbiór wartości dopuszczalnych)
\end{itemize}
Ze względu na postać:
\begin{itemize}
\item Zadania liniowe - oznacza że funkcja celu oraz układ ograniczeń są liniowe
\item Zadania nieliniowe
\end{itemize}
Inne podziały:
\begin{itemize}
\item metody rozwiązania: numeryczne/analityczne
\item ze względu na liczbę funkcji celu :
a) zadania jednokryterialne (skalarna funkcja celu)/
zadania wielokryterialne (więcej niż jedno kryterium funkcja celu wektorowa)
\item ze względu na tym zmiennych decyzyjnych: całkowitoliczbowe/zerojedynkowe/mieszane
\item kilka innych
\end{itemize}
Najważniejszy podział to na zadanie liniowe lub nieliniowe, ponieważ zadanie nie może należeń jednocześnie do obu tych klas, co nie dotyczy pozostałych podziałów, np, możliwe jest zadanie bez ograniczeń nieliniowe.
\subsection{Zadanie programowania liniowego PL}
Dobrze wytłumaczone zadanie programowanie liniowe:\\
\url{http://www.cs.put.poznan.pl/jjozefowska/wyklady/bo/Rozdzial3.pdf}
Warto przeanalizować przykład z kawą, wtedy wszystko jest jaśniejsze.
\begin{figure}[H]
\includegraphics[scale=1
]{obrazy/optymalizacja/opt3.png}
\end{figure}
Przypadki szczególne rozwiązania zadania programowania liniowego
(PL)
\begin{itemize}
\item Istnieje jedno rozwiązanie optymalne zadani PL.
\item Zadanie PL jest zadaniem nieograniczonym – brak rozwiązania.
\item W zadaniu PL zbiór rozwiązań dopuszczalnych jest pusty – brak
rozwiązania.
\item W zadaniu PL wszystkie zmienne lub ich część przyjmuje
\item wartości rzeczywiste.
\item Zadanie PL posiada nieskończoną liczbę rozwiązań.
\end{itemize}
\subparagraph{Metody rozwiązywania:}
\begin{itemize}
\item simpleks
\item dwufazowy simpleks
\item dualny simpleks
\item metoda graficzna
\end{itemize}
\subsubsection{Metoda simpleks}
Algorytm simpleks wymaga sprowadzenia zadania PL do postaci standardowej, w której ograniczenia mają postać równań, wszystkie zmienne są nieujemne, a także prawe strony ograniczeń są liczbami nieujemnymi. Czasem wymaga to dodania do macierzy pomocniczych zmiennych (w przypadku ograniczeń mniejszościowych lub większościowych).
Przyjmując m - liczba ograniczeń, n - liczba zmiennych decyzyjnych. \\
Obliczenia simpleks wygodnie jest prowadzić w tablicy, która reprezentuje bazowe rozwiązanie dopuszczalne. Ma m+1 wierszy i n kolumn. Kolumny to zmienne decyzyjne, wiersze odpowiadają zmiennym bazowym. \\
\begin{enumerate}
\item tworzy się postać początkową tablicy simpleks zawierającą rozwiązanie dopuszczalne. Jeśli dopuszczalne, następny krok.
\item Test optymalności (czy współczynniki w wierszu x0 są dodatnie?) jesli tak, to jest rozwiązanie, jeśli nie - następny krok.
\item Wybór zmiennej wchodzącej do bazy (najmniejsza wartość w wierszu x0)
\item wybór zmiennej usuwanej z bazy
\item Eliminacja Gaussa w celu uzyskania nowego rozwiązania bazowego dopuszczalnego. Powrót do kroku 1.
\end{enumerate}
Tutaj jest rozwiązany przykład na str 3., warto to przejrzeć i samemu zrozumieć.
\url{http://staff.iiar.pwr.wroc.pl/ewa.szlachcic/materialy\%20dydaktyczne/eit%20technika%20optymalizacji/4w_to_proglin2.pdf}
\subsubsection{Metoda graficzna}
Jest najprostsza, ale można ją zastosować jedynie do zadań o dwóch zmiennych decyzyjnych.
\begin{figure}[H]
\includegraphics[scale=0.7
]{obrazy/optymalizacja/opt4.png}
\end{figure}
Rysujemy ograniczenia, zaznaczamy zbiór dopuszczalny, rysujemy funkcję celu i wybieramy najlepszy punkt optycznie.
\subsubsection{Metoda simpleksu dwufazowego}
Ma dwie fazy:
\begin{enumerate}
\item należy znaleźć pierwsze rozwiązanie bazowe dopuszczalne poprzez rozwiązanie zadania pomocniczego (wprowadzenie pomocniczej funkcji celu.)
\item maksymalizacja funkcji celu x0 dla następnego rozwiązania bazowego dopuszczalnego wg algorytmu simpleks.
\end{enumerate}
I faza zachodzi, gdy Krok 1 – nie ma możliwości stworzenia pierwszego rozwiązania bazowego dopuszczalnego.
\begin{figure}[H]
\includegraphics[scale=0.7
]{obrazy/optymalizacja/opt5.png}
\end{figure}
Po tej fazie następuje II faza, czyli podstawowy simpleks (prymalny).\\
Szczególny przypadek jest wtedy, gdy po I fazie nadal nie ma rozwiązania dopuszczalnego. Wtedy brak rozwiązań.\\
\\
przykład:\\
\url{http://staff.iiar.pwr.wroc.pl/ewa.szlachcic/materialy%20dydaktyczne/eit%20technika%20optymalizacji/5w_to_proglin3.pdf}
\\
W tym miejscu, wszem i wobec oddaję honor pani dziekan, ponieważ jej przykłady obliczeniowe(!) są czytelne i łatwe do zrozumienia, w przeciwieństwie do internetowych, amen.
\paragraph{Zadanie liniowego programowania całkowitoliczbowego PCL\\\\}
Zagadnieniem liniowym całkowitoliczbowym nazywamy zadanie optymalizacji
liniowej, w którym wszystkie zmienne lub ich część są liczbami całkowitymi.
\[max_{x \in X} x_0 = c^Tx~~dla~x \in X \subset R^n\]
dla każdego $$1 \le i \le t~~~x_i \in \mathbb{Z}$$
Metody uproszczone:
\begin{itemize}
\item Przegląd zupełny zbioru rozwiązań dopuszczalnych X
\item Zaokrąglenie rozwiązania optymalnego zadania PL do zmiennych całkowitych
Zaokrąglenie do części całkowitych rozwiązania optymalnego zadania PL w
celu zyskania rozwiązania zadania PCL
W ten sposób można uzyskać rozwiązanie PCL nie spełniające zbioru
rozwiązań dopuszczalnych X.
Należy sprawdzić miarę niedopuszczalności rozwiązania zaokrąglonego
mierząc procentowe niespełnienie ograniczeń.
\end{itemize}
Metody złożone:
\begin{itemize}
\item Metoda odcięć Gomory'ego
\begin{enumerate}
\item Krok 1
Znajdź rozwiązanie zadania PL (2). Idź do Kroku 2.
\item Krok 2
Test na optymalność\\
Jeśli rozwiązanie zadania jest całkowitoliczbowe ,
wówczas jest ono
jednocześnie rozwiązaniem zadania (1) – Stop.
W przeciwnym wypadku idź do Kroku 3.
\item Krok 3
Odcinanie \\
Dodaj odcięcie z odpowiednio dobraną wartością h. Dokonaj ponownej optymalizacji stosując algorytm simpleks. Może zaistnieć konieczność wykonania większej liczby kroków eliminacji, zgodnie z procedurą simpleks.
Wróć do Kroku 2.
\end{enumerate}
Odcięciem Gomoryego nazywamy więc ograniczenie obszaru dopuszczalnego półprzestrzenią :
\begin{figure}[H]
\includegraphics[scale=1
]{obrazy/optymalizacja/opt6.png}
\end{figure}
\item Metoda podziału i ograniczeń \\
Podstawą metody B\&B jest przegląd drzewa rozwiązań.
Wykorzystuje się fakt skończoności zbioru możliwych
wartości
zmiennych całkowitoliczbowych w przypadku ograniczonych zadań
PCL.
W każdym wierzchołku drzewa rozwiązuje się problem programowania
liniowego z dodatkowym ograniczeniem na wybraną zmienną.
Warunek całkowitoliczbowości zmiennych zostaje odrzucony.
\item Metody przybliżone = metody heurystyczne
\end{itemize}
\subsection{Zadanie programowania nieliniowego PN}
$$min_{x \in X} f(x) = f(\hat{x})$$
przy ograniczeniach:
$$X={x|g_i(x)=<0, i=1,...,m|}$$
\\
Zadanie programowania nieliniowego polega na znalezieniu wektora zmiennych decyzyjnych $\hat{x}$, należącego do zbiory rozwiązań dopuszczalnych \textbf{X} w postaci:
takiego, że dla
$$x \in X$$
$$f(\hat{x})=<f(x)$$
Przeważnie stosuje się metody przybliżone, tylko szczególne przypadki można rozwiązać analitycznie, na przykład sprowadzając do problemu liniowego. Metoda rozwiązywania zależy od postaci, jaką przyjmuje zadanie, nie ma uniwersalnej.
\begin{figure}[H]
\includegraphics[scale=0.3
]{obrazy/optymalizacja/opt8.png}
\end{figure}
\begin{figure}[H]
\includegraphics[scale=0.3
]{obrazy/optymalizacja/opt7.png}
\end{figure}
\begin{figure}[H]
\includegraphics[scale=0.5
]{obrazy/optymalizacja/opt9.png}
\end{figure}
\paragraph{Nieliniowe zadanie optymalizacji statycznej z ograniczeniami\\\\}
Znaleźć wektor rozwiązań optymalnych $\hat{x}, taki, że:$
$$f(\hat{x})=min_{x \in X}f(x)$$
gdzie:
$$X={x:g_i(x) \le 0,~~i=1,...,m}$$
$$f:X = R^n \longrightarrow R^1$$
oraz $$g_i:X = R^n \longrightarrow R^1~dla~każdego~i=1,...,m$$
\subparagraph{Ograniczenie aktywne\\\\}
Ograniczenie nierównościowe, spełnione równościowo nazywa się ograniczeniem aktywnym.\\
Dla $\hat{x}$ ograniczenie przyjmuje postać:
\[ g_i(\hat{x})=0 \]
$$ g_i(\hat{x}+\tau d) \le 0, dla każdego i \in A(\hat{x})$$
przy czym $\tau \in [0,\sigma]$
\subparagraph{Przypadki:}
\begin{enumerate}
\item Jedno ograniczenie aktywne – rozwiązanie optymalne na brzegu ograniczenia
aktywnego.
\item Wszystkie ograniczenia aktywne - rozwiązanie optymalne na przecięciu ograniczeń
aktywnych.
\item Brak ograniczeń aktywnych – rozwiązanie optymalne wewnątrz obszaru rozwiązań
dopuszczalnych ( rozwiązanie optymalne zadania bez ograniczeń spełnia
ograniczenia problemu.
\end{enumerate}
W celu uwzględnienia ograniczeń można postąpić w poniższy sposób:\\
• dokonać transformacji zmiennych decyzyjnych
• dokonać transformacji funkcji celu wprowadzając funkcje kary\\
Funkcja kary charakteryzuje się tym, że w zbiorze rozwiązań dopuszczalnych X przyjmuje wartość równą zeru lub bliską zeru, a poza tym obszarem przyjmuje bardzo duże wartości.\\
Rodzaje funkcji kary:
\begin{itemize}
\item Metody zewnętrznej funkcji kary (metoda Couranta,
metoda
Schmita i Foxa)
\item Metody wewnętrznej funkcji kary (metoda Rosenbroc
ka,
metoda Carolla)
\item Metody przesuwanej funkcji kary (metoda Powella).
\end{itemize}
Rozwiązanie zadania nieliniowego z ograniczeniami oznacza znalezienie takiego wektora rozwiązań optymalnych, że będzie on spełniał kryteria (to co w Matlabie było Tolx, TolCon...).
\subparagraph{Iteracyjne algorytmy optymalizacji:}
\begin{itemize}
\item Algorytmy optymalizacji w kierunku
\item Algorytmy optymalizacji bez ograniczeń
\item Algorytmy optymalizacji z ograniczeniami
\end{itemize}
Algorytm optymalizacji lokalnej (czyli to co wyżej) - przemierzanie obszaru rozwiązań dopuszczalnych w poszukiwaniu ekstremum funkcji celu według iteracyjnego schematu.
\subparagraph{Algorytmy bezgradientowe (minimalizacja w kierunku -wykorzystują tylko wartości funkcji)}
\begin{itemize}
\item Algorytm Nelder’a-Meade’a ( Matlab - funkcja fminsearch)
\item Algorytm Gauss’a-Seidla (bardzo wolna zbieżność
liniowa)
\item Algorytm Powella
\item złotego podziału
\begin{figure}[H]
\includegraphics[scale=0.5
]{obrazy/optymalizacja/opt10.png}
\end{figure}
\item aproksymacji kwadratowej
\end{itemize}
\subparagraph{Algorytmy gradientowe(minimalizacja w kierunku - wykorzystują wartości funkcji oraz co najmniej wartość pochodnej
kierunkowej w kierunku poszukiwań):}
\begin{itemize}
\item Algorytm największego spadku (zbieżność liniowa)
\item Algorytm Newtona (zbieżna
kwadratowo ale kosztowna i
nie zawsze stabilna)
\item Algorytm Zangwilla
\item Algorytm Fletchera-Reeves’a
\item Algorytm Polaka-Ribiery
\item Algorytm Fletchera-Powella-Davidona
\end{itemize}
Najefektywniejsze są tzw. metody quasi'newtonowskie, w
których w kolejnych iteracjach konstruuje się przybliżenie odwrotności hesjanu.
Przykłady metod quasinewtonowskich:
\begin{itemize}
\item Metoda Broyden-Fletcher-Goldfarb-Shanno (BFGS)\\
Właściwości metody:
-Brak operacji odwracania macierzy hesjanu\\
-Blisko rozwiązania optymalnego – dobra zbieżność\\
-Na początku obliczeń – zbieżność słaba – słabe jest przybliżenie hesjanu\\
-Przybliżenie hesjanu w każdej iteracji polepsza się
\end{itemize}
\url{chmielowski.eu/POLITECHNIKA/Dydaktyka/OPTYdoktoranci/Wyklady/W1.doc}\\
\url{smurf.mimuw.edu.pl/external_slides/MO/MO_1_Przyklady_zadan_optymalizacji/MO_1_Przyklady_zadan_optymalizacji.html}
\subsection{Optymalizacja globalna}
Do tej grupy nalezą stochastyczne iteracyjne algorytmy
przeszukiwania przestrzeni rozwiązań :\\
•metody przeszukiwania lokalnego\\
•metody przeszukiwania populacyjnego.\\
SCHEMAT ALGORYTMU:
\begin{enumerate}
\item Wygeneruj początkowy zbiór rozwiązań W i oceń każde
z nich.
\item Wygeneruj i oceń zbiór nowych kandydatów W’ drogą losowych
zmian u wybranych osobników z W.
\item Zastąp pewne osobniki z W osobnikami z W’ i wróć do kroku 2, o ile nie jest spełniony warunek zatrzymania algorytmu.
Są dwie metody generowania nowych osobników:
\begin{itemize}
\item Kolejni kandydaci są niewielkimi modyfikacjami po
przednich
kandydatów (mutacja). dotyczy metod przeszukiwania lokalnego.
\item . Nowy kandydat powstaje w drodze rekombinacji pewnych cech
dwóch lub więcej poprzedników (krzyżowanie). Dotyczy przeszukiwania populacyjnego
\end{itemize}
\begin{figure}[H]
\includegraphics[scale=0.3
]{obrazy/optymalizacja/opt11.png}
\end{figure}
\subsubsection{Techniki heurystyczne}
Algorytmy lokalnego poszukiwania – klasa algorytmów, w których rozwiązanie problemu jest
iteracyjne poprawiane poprzez przeglądanie sąsiedztwa rozwiązania.
\end{enumerate}
Metaheurystyki (naśladowanie rzeczywistości):\\
\begin{itemize}
\item symulowanie wyżarzanie \\
Na początku działania algorytmu temperatura (patametr) jest wysoka, dzięki czemu
algorytm może bardzo często zmieniać konfigurację rozwiązania,
niejednokrotnie wybierając rozwiązanie gorsze. Wraz z kolejnymi
iteracjami algorytmu temperatura spada i wybierane są częściej
rozwiązania lepsze. Pod koniec pracy algorytmu, temperatura jest na tyle
niska, że prawdopodobieństwo wyboru gorszego rozwiązania jest bliskie
zeru. Algorytm zachowuje się wówczas, jak typowy algorytm iteracyjny i
stara się maksymalnie ulepszyć rozwiązanie.
\item przeszukiwanie TABU\\
Jest to metoda pozwalająca uniknąć niebezpieczeństwa
wielokrotnego powracania do tego samego rozwiązania.
Algorytm jest wyposażony w pamięć dotychczas odwiedzanych
punktów.
Ponowne odwiedzenie punktów znajdujących się w pamięci tabu
jest zakazane.
\item systemy mrówkowe
W prawdziwym świecie, mrówki poruszają się w sposób losowy; gdy znajdują pożywienie, wracają do swojej kolonii pozostawiając ślad składający się z feromonów. Gdy inna mrówka natknie się na ten ślad, przestaje poruszać się w sposób losowy i podąża za śladem w kierunku pożywienia. Gdy mrówki odnajdujące najbliżej położony pokarm wracają szybciej zostawiają szybciej feromony i jest ich coraz więcej, gdyż reszta podąża za częstszym zapachem. W ten sposób na koniec większość mrówek chodzi drogą najkrótszą.
\item algorytmy ewolucyjne
Idea algorytmów genetycznych polega na naśladowaniu ewolucji gatunków. Podczas iteracji kod genetyczny czyli chromosomy ulegają krzyżowaniu lub selekcji tworząc w ten sposób potomstwo, mogą one również podlegać mutacji z pewnym prawdopodobieństwem. Algorytmy genetyczne umożliwiają utrzymanie równowagi pomiędzy szerokim badaniem przestrzeni a wykorzystaniem wcześniejszych wyników. W każdej następnej populacji znajdą się osobniki lepsze, zgodnie z funkcją celu. Osobniki gorsze podlegaj ą eliminacji.
\item optymalizacja rojem cząstek
Każda cząstka reprezentuje potencjalne rozwiązanie.
Cząstki poruszają się przez wielowymiarową przestrzeń
poszukiwań.
Pozycja jest aktualizowana według własnego doświadczenia oraz doświadczenia sąsiadów, poprzez dodanie wektora
prędkości do ich aktualnego stanu przemieszczania się.
Aktualna prędkość zależy od, poprzedniej prędkości, dążenia do swojego najlepszego poprzedniego położenia oraz dążenia do globalnego lub lokalnego najlepszego wyniku sąsiada.
Każda cząstka jest zbieżna do punktu pomiędzy własnym
najlepszym rozwiązaniem a najlepszym rozwiązaniem
globalnym.
\end{itemize}
\subsection{Sformułowanie zadania optymalizacji}