-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathMaturitní otázky z programování.html
926 lines (797 loc) · 153 KB
/
Maturitní otázky z programování.html
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
<!doctype html>
<html>
<head>
<meta charset='UTF-8'><meta name='viewport' content='width=device-width initial-scale=1'>
<style type='text/css'>html {overflow-x: initial !important;}:root { --bg-color: #ffffff; --text-color: #333333; --select-text-bg-color: #B5D6FC; --select-text-font-color: auto; --monospace: "Lucida Console",Consolas,"Courier",monospace; --title-bar-height: 20px; }
.mac-os-11 { --title-bar-height: 28px; }
html { font-size: 14px; background-color: var(--bg-color); color: var(--text-color); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; -webkit-font-smoothing: antialiased; }
body { margin: 0px; padding: 0px; height: auto; inset: 0px; font-size: 1rem; line-height: 1.42857143; overflow-x: hidden; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: inherit; tab-size: 4; background-position: inherit; background-repeat: inherit; }
iframe { margin: auto; }
a.url { word-break: break-all; }
a:active, a:hover { outline: 0px; }
.in-text-selection, ::selection { text-shadow: none; background: var(--select-text-bg-color); color: var(--select-text-font-color); }
#write { margin: 0px auto; height: auto; width: inherit; word-break: normal; word-wrap: break-word; position: relative; white-space: normal; overflow-x: visible; padding-top: 36px; }
#write.first-line-indent p { text-indent: 2em; }
#write.first-line-indent li p, #write.first-line-indent p * { text-indent: 0px; }
#write.first-line-indent li { margin-left: 2em; }
.for-image #write { padding-left: 8px; padding-right: 8px; }
body.typora-export { padding-left: 30px; padding-right: 30px; }
.typora-export .footnote-line, .typora-export li, .typora-export p { white-space: pre-wrap; }
.typora-export .task-list-item input { pointer-events: none; }
@media screen and (max-width: 500px) {
body.typora-export { padding-left: 0px; padding-right: 0px; }
#write { padding-left: 20px; padding-right: 20px; }
.CodeMirror-sizer { margin-left: 0px !important; }
.CodeMirror-gutters { display: none !important; }
}
#write li > figure:last-child { margin-bottom: 0.5rem; }
#write ol, #write ul { position: relative; }
img { max-width: 100%; vertical-align: middle; image-orientation: from-image; }
button, input, select, textarea { color: inherit; font-family: inherit; font-size: inherit; font-style: inherit; font-variant-caps: inherit; font-weight: inherit; font-stretch: inherit; line-height: inherit; }
input[type="checkbox"], input[type="radio"] { line-height: normal; padding: 0px; }
*, ::after, ::before { box-sizing: border-box; }
#write h1, #write h2, #write h3, #write h4, #write h5, #write h6, #write p, #write pre { width: inherit; }
#write h1, #write h2, #write h3, #write h4, #write h5, #write h6, #write p { position: relative; }
p { line-height: inherit; }
h1, h2, h3, h4, h5, h6 { break-after: avoid-page; break-inside: avoid; orphans: 4; }
p { orphans: 4; }
h1 { font-size: 2rem; }
h2 { font-size: 1.8rem; }
h3 { font-size: 1.6rem; }
h4 { font-size: 1.4rem; }
h5 { font-size: 1.2rem; }
h6 { font-size: 1rem; }
.md-math-block, .md-rawblock, h1, h2, h3, h4, h5, h6, p { margin-top: 1rem; margin-bottom: 1rem; }
.hidden { display: none; }
.md-blockmeta { color: rgb(204, 204, 204); font-weight: 700; font-style: italic; }
a { cursor: pointer; }
sup.md-footnote { padding: 2px 4px; background-color: rgba(238, 238, 238, 0.7); color: rgb(85, 85, 85); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; cursor: pointer; }
sup.md-footnote a, sup.md-footnote a:hover { color: inherit; text-transform: inherit; text-decoration: inherit; }
#write input[type="checkbox"] { cursor: pointer; width: inherit; height: inherit; }
figure { overflow-x: auto; margin: 1.2em 0px; max-width: calc(100% + 16px); padding: 0px; }
figure > table { margin: 0px; }
tr { break-inside: avoid; break-after: auto; }
thead { display: table-header-group; }
table { border-collapse: collapse; border-spacing: 0px; width: 100%; overflow: auto; break-inside: auto; text-align: left; }
table.md-table td { min-width: 32px; }
.CodeMirror-gutters { border-right-width: 0px; background-color: inherit; }
.CodeMirror-linenumber { }
.CodeMirror { text-align: left; }
.CodeMirror-placeholder { opacity: 0.3; }
.CodeMirror pre { padding: 0px 4px; }
.CodeMirror-lines { padding: 0px; }
div.hr:focus { cursor: none; }
#write pre { white-space: pre-wrap; }
#write.fences-no-line-wrapping pre { white-space: pre; }
#write pre.ty-contain-cm { white-space: normal; }
.CodeMirror-gutters { margin-right: 4px; }
.md-fences { font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; overflow: visible; white-space: pre; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: inherit; position: relative !important; background-position: inherit; background-repeat: inherit; }
.md-fences-adv-panel { width: 100%; margin-top: 10px; text-align: center; padding-top: 0px; padding-bottom: 8px; overflow-x: auto; }
#write .md-fences.mock-cm { white-space: pre-wrap; }
.md-fences.md-fences-with-lineno { padding-left: 0px; }
#write.fences-no-line-wrapping .md-fences.mock-cm { white-space: pre; overflow-x: auto; }
.md-fences.mock-cm.md-fences-with-lineno { padding-left: 8px; }
.CodeMirror-line, twitterwidget { break-inside: avoid; }
.footnotes { opacity: 0.8; font-size: 0.9rem; margin-top: 1em; margin-bottom: 1em; }
.footnotes + .footnotes { margin-top: 0px; }
.md-reset { margin: 0px; padding: 0px; border: 0px; outline: 0px; vertical-align: top; text-decoration: none; text-shadow: none; float: none; position: static; width: auto; height: auto; white-space: nowrap; cursor: inherit; line-height: normal; font-weight: 400; text-align: left; box-sizing: content-box; direction: ltr; background-position: 0px 0px; }
li div { padding-top: 0px; }
blockquote { margin: 1rem 0px; }
li .mathjax-block, li p { margin: 0.5rem 0px; }
li blockquote { margin: 1rem 0px; }
li { margin: 0px; position: relative; }
blockquote > :last-child { margin-bottom: 0px; }
blockquote > :first-child, li > :first-child { margin-top: 0px; }
.footnotes-area { color: rgb(136, 136, 136); margin-top: 0.714rem; padding-bottom: 0.143rem; white-space: normal; }
#write .footnote-line { white-space: pre-wrap; }
@media print {
body, html { border: 1px solid transparent; height: 99%; break-after: avoid; break-before: avoid; font-variant-ligatures: no-common-ligatures; }
#write { margin-top: 0px; padding-top: 0px; border-color: transparent !important; }
.typora-export * { -webkit-print-color-adjust: exact; }
.typora-export #write { break-after: avoid; }
.typora-export #write::after { height: 0px; }
.is-mac table { break-inside: avoid; }
.typora-export-show-outline .typora-export-sidebar { display: none; }
}
.footnote-line { margin-top: 0.714em; font-size: 0.7em; }
a img, img a { cursor: pointer; }
pre.md-meta-block { font-size: 0.8rem; min-height: 0.8rem; white-space: pre-wrap; background-color: rgb(204, 204, 204); display: block; overflow-x: hidden; }
p > .md-image:only-child:not(.md-img-error) img, p > img:only-child { display: block; margin: auto; }
#write.first-line-indent p > .md-image:only-child:not(.md-img-error) img { left: -2em; position: relative; }
p > .md-image:only-child { display: inline-block; width: 100%; }
#write .MathJax_Display { margin: 0.8em 0px 0px; }
.md-math-block { width: 100%; }
.md-math-block:not(:empty)::after { display: none; }
.MathJax_ref { fill: currentcolor; }
[contenteditable="true"]:active, [contenteditable="true"]:focus, [contenteditable="false"]:active, [contenteditable="false"]:focus { outline: 0px; box-shadow: none; }
.md-task-list-item { position: relative; list-style-type: none; }
.task-list-item.md-task-list-item { padding-left: 0px; }
.md-task-list-item > input { position: absolute; top: 0px; left: 0px; margin-left: -1.2em; margin-top: calc(1em - 10px); border: none; }
.math { font-size: 1rem; }
.md-toc { min-height: 3.58rem; position: relative; font-size: 0.9rem; border-top-left-radius: 10px; border-top-right-radius: 10px; border-bottom-right-radius: 10px; border-bottom-left-radius: 10px; }
.md-toc-content { position: relative; margin-left: 0px; }
.md-toc-content::after, .md-toc::after { display: none; }
.md-toc-item { display: block; color: rgb(65, 131, 196); }
.md-toc-item a { text-decoration: none; }
.md-toc-inner:hover { text-decoration: underline; }
.md-toc-inner { display: inline-block; cursor: pointer; }
.md-toc-h1 .md-toc-inner { margin-left: 0px; font-weight: 700; }
.md-toc-h2 .md-toc-inner { margin-left: 2em; }
.md-toc-h3 .md-toc-inner { margin-left: 4em; }
.md-toc-h4 .md-toc-inner { margin-left: 6em; }
.md-toc-h5 .md-toc-inner { margin-left: 8em; }
.md-toc-h6 .md-toc-inner { margin-left: 10em; }
@media screen and (max-width: 48em) {
.md-toc-h3 .md-toc-inner { margin-left: 3.5em; }
.md-toc-h4 .md-toc-inner { margin-left: 5em; }
.md-toc-h5 .md-toc-inner { margin-left: 6.5em; }
.md-toc-h6 .md-toc-inner { margin-left: 8em; }
}
a.md-toc-inner { font-size: inherit; font-style: inherit; font-weight: inherit; line-height: inherit; }
.footnote-line a:not(.reversefootnote) { color: inherit; }
.md-attr { display: none; }
.md-fn-count::after { content: "."; }
code, pre, samp, tt { font-family: var(--monospace); }
kbd { margin: 0px 0.1em; padding: 0.1em 0.6em; font-size: 0.8em; color: rgb(36, 39, 41); background-color: rgb(255, 255, 255); border: 1px solid rgb(173, 179, 185); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px; box-shadow: rgba(12, 13, 14, 0.2) 0px 1px 0px, rgb(255, 255, 255) 0px 0px 0px 2px inset; white-space: nowrap; vertical-align: middle; }
.md-comment { color: rgb(162, 127, 3); opacity: 0.6; font-family: var(--monospace); }
code { text-align: left; }
a.md-print-anchor { white-space: pre !important; border: none !important; display: inline-block !important; position: absolute !important; width: 1px !important; right: 0px !important; outline: 0px !important; text-shadow: initial !important; background-position: 0px 0px !important; }
.os-windows.monocolor-emoji .md-emoji { font-family: "Segoe UI Symbol", sans-serif; }
.md-diagram-panel > svg { max-width: 100%; }
[lang="flow"] svg, [lang="mermaid"] svg { max-width: 100%; height: auto; }
[lang="mermaid"] .node text { font-size: 1rem; }
table tr th { border-bottom-width: 0px; }
video { max-width: 100%; display: block; margin: 0px auto; }
iframe { max-width: 100%; width: 100%; border: none; }
.highlight td, .highlight tr { border: 0px; }
mark { background-color: rgb(255, 255, 0); color: rgb(0, 0, 0); }
.md-html-inline .md-plain, .md-html-inline strong, mark .md-inline-math, mark strong { color: inherit; }
.md-expand mark .md-meta { opacity: 0.3 !important; }
mark .md-meta { color: rgb(0, 0, 0); }
@media print {
.typora-export h1, .typora-export h2, .typora-export h3, .typora-export h4, .typora-export h5, .typora-export h6 { break-inside: avoid; }
}
.md-diagram-panel .messageText { stroke: none !important; }
.md-diagram-panel .start-state { fill: var(--node-fill); }
.md-diagram-panel .edgeLabel rect { opacity: 1 !important; }
.md-fences.md-fences-math { font-size: 1em; }
.md-fences-advanced:not(.md-focus) { padding: 0px; white-space: nowrap; border: 0px; }
.md-fences-advanced:not(.md-focus) { background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: inherit; background-position: inherit; background-repeat: inherit; }
.typora-export-show-outline .typora-export-content { max-width: 1440px; margin: auto; display: flex; flex-direction: row; }
.typora-export-sidebar { width: 300px; font-size: 0.8rem; margin-top: 80px; margin-right: 18px; }
.typora-export-show-outline #write { --webkit-flex: 2; flex: 2 1 0%; }
.typora-export-sidebar .outline-content { position: fixed; top: 0px; max-height: 100%; overflow: hidden auto; padding-bottom: 30px; padding-top: 60px; width: 300px; }
@media screen and (max-width: 1024px) {
.typora-export-sidebar, .typora-export-sidebar .outline-content { width: 240px; }
}
@media screen and (max-width: 800px) {
.typora-export-sidebar { display: none; }
}
.outline-content li, .outline-content ul { margin-left: 0px; margin-right: 0px; padding-left: 0px; padding-right: 0px; list-style: none; }
.outline-content ul { margin-top: 0px; margin-bottom: 0px; }
.outline-content strong { font-weight: 400; }
.outline-expander { width: 1rem; height: 1.428571429rem; position: relative; display: table-cell; vertical-align: middle; cursor: pointer; padding-left: 4px; }
.outline-expander::before { content: ""; position: relative; font-family: Ionicons; display: inline-block; font-size: 8px; vertical-align: middle; }
.outline-item { padding-top: 3px; padding-bottom: 3px; cursor: pointer; }
.outline-expander:hover::before { content: ""; }
.outline-h1 > .outline-item { padding-left: 0px; }
.outline-h2 > .outline-item { padding-left: 1em; }
.outline-h3 > .outline-item { padding-left: 2em; }
.outline-h4 > .outline-item { padding-left: 3em; }
.outline-h5 > .outline-item { padding-left: 4em; }
.outline-h6 > .outline-item { padding-left: 5em; }
.outline-label { cursor: pointer; display: table-cell; vertical-align: middle; text-decoration: none; color: inherit; }
.outline-label:hover { text-decoration: underline; }
.outline-item:hover { border-color: rgb(245, 245, 245); background-color: var(--item-hover-bg-color); }
.outline-item:hover { margin-left: -28px; margin-right: -28px; border-left-width: 28px; border-left-style: solid; border-left-color: transparent; border-right-width: 28px; border-right-style: solid; border-right-color: transparent; }
.outline-item-single .outline-expander::before, .outline-item-single .outline-expander:hover::before { display: none; }
.outline-item-open > .outline-item > .outline-expander::before { content: ""; }
.outline-children { display: none; }
.info-panel-tab-wrapper { display: none; }
.outline-item-open > .outline-children { display: block; }
.typora-export .outline-item { padding-top: 1px; padding-bottom: 1px; }
.typora-export .outline-item:hover { margin-right: -8px; border-right-width: 8px; border-right-style: solid; border-right-color: transparent; }
.typora-export .outline-expander::before { content: "+"; font-family: inherit; top: -1px; }
.typora-export .outline-expander:hover::before, .typora-export .outline-item-open > .outline-item > .outline-expander::before { content: "−"; }
.typora-export-collapse-outline .outline-children { display: none; }
.typora-export-collapse-outline .outline-item-open > .outline-children, .typora-export-no-collapse-outline .outline-children { display: block; }
.typora-export-no-collapse-outline .outline-expander::before { content: "" !important; }
.typora-export-show-outline .outline-item-active > .outline-item .outline-label { font-weight: 700; }
.md-inline-math-container mjx-container { zoom: 0.95; }
:root {
--primary-color: #37352f;
--bg-color: #ffffff;
--bg-color-dark: #f7f6f3;
--dark-trait: #e9e9e7;
--light-trait-100: #ecedec;
--light-trait-200: #c70000;
--light-trait-300: #37352f;
--light-trait-400: #f7f6f3;
--text-color: #37352f;
--text-color-secondary: #73726e;
--text-highlight-color: #fff;
--text-highlight-bg: rgba(var(--primary-color-rgb), 0.3);
--select-text-bg-color: #c0e5f4;
--search-select-text-color:#448361;
--search-select-bg-color: #edf3ec;
--code-color: #9a6e3a;
--border-radius: 4px;
--font-size: 14px;
--font-family: -apple-system, BlinkMacSystemFont, "Segoe UI", Helvetica, "Apple Color Emoji", Arial, sans-serif, "Segoe UI Emoji", "Segoe UI Symbol";
--monospace: 'SF Mono Medium', 'Fira Code', 'Cousine', 'Consolas', monospace;
--heading-char-color: var(--light-trait-400);
--color-popover-bg-color: var(--text-color);
--rawblock-edit-panel-bd: var(--bg-color-dark);
--control-text-color: #72706b;
--meta-content-color: var(--primary-color);
--primary-btn-border-color: var(--primary-color);
--side-bar-bg-color: var(--bg-color-dark);
--item-hover-bg-color: #e8e7e4;
--active-file-bg-color: #e8e7e4;
--active-file-border-color: var(--bg-color);
--window-border: 1px solid var(--bg-color);
--focus-ring-color: transparent;
}
html {
font-size: var(--font-size);
}
body {
font-family: var(--font-family);
-webkit-font-smoothing: antialiased;
color: var(--text-color);
line-height: 1.6;
}
code {
background-color: #f7f6f3;
padding: 0 2px 0 2px;
}
#write {
max-width: 860px;
margin: 0 auto;
padding: 30px;
padding-bottom: 100px;
}
@media only screen and (min-width: 1400px) {
#write {
max-width: 1024px;
}
}
@media only screen and (min-width: 1800px) {
#write {
max-width: 1200px;
}
}
#write>ul:first-child, #write>ol:first-child {
margin-top: 30px;
}
a {
color: var(--primary-color);
}
h1, h2, h3, h4, h5, h6 {
position: relative;
margin-top: 2rem;
margin-bottom: 1rem;
font-weight: 700;
line-height: 1.4;
cursor: text;
}
h1:hover a.anchor, h2:hover a.anchor, h3:hover a.anchor, h4:hover a.anchor, h5:hover a.anchor, h6:hover a.anchor {
text-decoration: none;
}
h1 tt, h1 code, h2 tt, h2 code, h3 tt, h3 code, h4 tt, h4 code, h5 tt, h5 code, h6 tt, h6 code {
font-size: inherit;
}
h1 {
padding-bottom: 0.3em;
font-size: 2.2em;
line-height: 1.3;
}
h2 {
padding-bottom: 0.3em;
font-size: 1.75em;
line-height: 1.225;
}
h3 {
font-size: 1.4em;
line-height: 1.43;
}
h4 {
font-size: 1.2em;
}
h5 {
font-size: 1em;
}
h6 {
font-size: 1em;
color: var(--light-trait-300);
}
p, blockquote, ul, ol, dl, table {
margin: 0.8em 0;
}
li>ol, li>ul {
margin: 0 0;
}
hr {
background-color: var(--light-trait-100);
height: 1.5px;
border: none
}
a,
.md-def-url {
color: var(--text-color);
text-decoration: none;
border-bottom:0.05em solid;
border-color: #37352f;
opacity:0.6;
transition: all .1s ease-in;
}
a:hover {
text-decoration: none;
opacity:1;
}
sup.md-footnote {
background-color: var(--light-trait-400);
color: #888884;
}
li p.first {
display: inline-block;
}
ul, ol {
padding-left: 30px;
}
ul:first-child, ol:first-child {
margin-top: 0.35%;
}
ul:last-child, ol:last-child {
margin-bottom: 0;
}
mark, .ty-file-search-match-text, .md-search-hit {
background: #fdebec;
color: #d44c47;
}
mark {
border-radius: 4px;
color: #402c1b;
font-weight: inherit;
background-color: #fdecc8;
padding-left: 4px;
padding-right: 4px;
padding-top: 2px;
padding-bottom: 2px;
margin-left: 2px;
margin-right: 2px;
}
.md-search-hit * {
color: var(--search-select-text-color);
}
/* Search highlight */
.cm-search-hit.CodeMirror-selectedtext, .md-search-hit.md-search-select, .md-search-select {
outline: 0px solid var(--search-select-text-color);
}
.outline-item.select, .ty-search-item-line.select, .ty-search-item.select {
outline-width: 2px;
}
.outline-item.select {
outline-offset: 0px;
}
blockquote {
margin-left: 1.75px;
margin-right: 0px;
border-left: 4px solid var(--text-color);
padding: 10px 14px 7px 22px;
/* change the quote highlight */
background-color: #f7f7f7;
}
blockquote blockquote {
padding-right: 0;
}
/* Alternating color rows in table*/
table tr:nth-child(2n) {
background-color: #f7f7f7;
}
table tr:nth-child(2n + 1) {
background-color: #fdfdfd;
}
/* Alternating color rows in table*/
table {
padding: 0;
word-break: initial;
}
table tr {
border-top: 1px solid var(--dark-trait);
margin: 0;
padding: 0;
}
table tr th {
font-weight: bold;
border: 1px solid var(--dark-trait);
border-bottom: 0;
margin: 0;
padding: 6px 13px;
}
table tr td {
border: 1px solid var(--dark-trait);
margin: 0;
padding: 6px 13px;
}
table tr th:first-child, table tr td:first-child {
margin-top: 0;
}
table tr th:last-child, table tr td:last-child {
margin-bottom: 0;
}
kbd {
font-size: 0.875rem;
background: var(--bg-color-dark);
border: 1px solid var(--dark-trait);
box-shadow: 0 2px 0 var(--dark-trait);
color: var(--text-color-secondary);
}
.md-fences, code, tt {
border: none;
background-color: #f7f6f3;
border-radius: var(--border-radius);
padding: 2px 4px 0px 4px;
font-size: 0.975em;
font-weight: medium;
font-family: var(--monospace)
}
.md-fences {
margin-bottom: 15px;
margin-top: 15px;
padding-top: 8px;
padding-bottom: 6px;
}
#write pre.md-meta-block {
padding: 1rem;
font-size: 85%;
line-height: 1.45;
background-color: var(--bg-color-dark);
border: 0;
border-radius: var(--border-radius);
color: var(--text-color-secondary);
margin-top: 0 !important;
}
#write .mathjax-block .md-rawblock-tooltip {
border-top-left-radius: var(--border-radius);
border-top-right-radius: var(--border-radius);
}
#write .mathjax-block .md-math-container {
border-top-left-radius: var(--border-radius);
border-bottom-right-radius: var(--border-radius);
border-bottom-left-radius: var(--border-radius);
}
#write .md-mathblock-panel .md-rawblock-control:first-of-type {
border-top-left-radius: var(--border-radius);
}
.md-mathjax-midline {
background-color: var(--bg-color);
color: var(--text-color);
}
.md-inline-math script {
color: var(--code-color);
}
.CodeMirror-lines {
padding-left: 4px;
}
.code-tooltip {
box-shadow: none;
border-radius: var(--border-radius);
}
#write .code-tooltip {
bottom: initial;
top: 100%;
left: initial;
right: -1px;
background: var(--bg-color-dark);
border: 1px solid var(--dark-trait);
border-top-left-radius: 0;
border-top-right-radius: 0;
border-top: 0;
font-family: var(--monospace);
}
#write .md-mathblock-panel .code-tooltip {
right: 0;
border: none;
}
/* TODO */
#write .md-task-list-item>input {
-webkit-appearance: initial;
display: inline-block;
text-align: center;
vertical-align: middle;
position: absolute;
border: 1px solid var(--text-color);
/* border-radius: 100%; */
margin-left: -1.45rem;
height: 0.95rem;
width: 0.95rem;
transition: all 0.35s;
}
#write .md-task-list-item>input:focus {
outline: none;
box-shadow: none;
}
#write .md-task-list-item>input[checked] {
background: #2eaadc;
border: 1px solid #2eaadc;
text-decoration: line-through;
}
#write .md-task-list-item>input[checked]::before {
display: inline-block;
vertical-align: middle;
content: '✓';
position: absolute;
margin-top: 0.05rem;
top: 0;
left: 0;
height: 100%;
width: 100%;
text-align: absolute;
color: var(--bg-color);
font-size: 12px;
font-weight: 760;
}
#write .md-task-list-item>input[checked]::after {
text-decoration: line-through;
}
/* TODO */
.md-image>.md-meta {
border-radius: var(--border-radius);
padding: 2px 0px 0px 4px;
font-size: 0.9em;
color: inherit;
}
.md-toc {
margin-top: 20px;
padding-bottom: 20px;
}
/* Source mode */
.CodeMirror.cm-s-typora-default *, .cm-s-typora-default * {
background: inherit;
color: var(--text-color);
font-family: var(--monospace);
font-size: var(--font-size) !important;
font-style: normal;
font-weight: medium;
}
.CodeMirror.cm-s-typora-default div.CodeMirror-cursor {
border-left: 2px solid var(--text-color);
}
.sidebar-tabs {
border-bottom: none;
}
.outline-expander {
width: 1.5rem;
vertical-align: initial;
}
.outline-expander:before, .outline-expander:hover:before, .outline-item-open>.outline-item>.outline-expander:before, .outline-item-open>.outline-item>.outline-expander:hover:before {
content: "\f125";
transition: transform 125ms ease-in-out;
}
.outline-item-open>.outline-item>.outline-expander:hover:before, .outline-item-open>.outline-item>.outline-expander:before {
transform: rotate(90deg);
}
.outline-label:hover {
text-decoration: none;
}
#toc-dropmenu {
background: var(--bg-color-dark);
}
#toc-dropmenu .outline-title {
font-size: 1rem;
text-transform: uppercase;
}
.dropdown-menu .divider {
display: none;
}
.context-menu {
border: none!important;
backdrop-filter: saturate(180%) blur(20px) brightness(1.1);
background-color: var(--bg-color-dark);
box-shadow: 0 25.6px 57.6px 0 rgba(0, 0, 0, .22), 0 4.8px 14.4px 0 rgba(0, 0, 0, .18)!important;
}
.file-node-background {
height: 31px;
}
.file-node-content:hover .file-node-icon, .file-node-content:hover .file-node-open-state {
visibility: visible;
}
.file-node-icon {
margin-right: 8px;
}
.file-library-node:not(.file-node-root):focus>.file-node-content {
outline: none;
}
/* New file animation */
.blink-area {
animation: none;
}
.file-list-item-summary {
font-size: var(--font-size);
font-family: var(--font-family);
}
#md-searchpanel input {
border-radius: var(--border-radius);
box-shadow: none;
}
#md-searchpanel input:focus {
box-shadow: none;
border-color: var(--meta-content-color);
}
#md-searchpanel .search-type-selection {
width: auto;
}
#md-searchpanel .btn:not(.close-btn):hover {
box-shadow: none;
}
.mac-seamless-mode #typora-sidebar {
background-color: var(--side-bar-bg-color);
}
#md-notification .btn {
border: 0;
}
/* CODE HIGHLIGHT */
pre.CodeMirror-line {
color: #999999!important
}
.cm-variable {
color: #37352f!important;
}
.cm-keyword {
color: #0277aa !important
}
.cm-tag {
color: #ff5a5a!important
}
.cm-variable-3 {
color: #48ff00!important;
}
.cm-bracket, .cm-error {
color: #ff5a5a!important
}
.cm-attribute {
color: #0277aa!important;
}
.cm-def {
color: #dc4a68!important;
}
.cm-comment {
color: #708090!important;
}
.cm-string {
color: #669900!important;
font-variant-ligatures: common-ligatures!important;
}
.cm-tag:not() {
font-weight: 700;
}
.cm-operator {
color: #9a6e3b!important;
}
.cm-number {
color: #990055!important;
}
.cm-meta {
color: var(--text-color) !important;
font-weight: 700!important;
}
.cm-atom { color: #845dc4; }
.cm-builtin {
color: #669900 !important;
}
.cm-property {
color: var(--text-color) !important;
}
.cm-variable-2 {
color: var(--text-color) !important;
}
.cm-variable-3 {
color: #845dc4;
}
/* CODE HIGHLIGHT */
.file-tree-node.active>.file-node-background {
background-color: var(--active-file-bg-color);
border-left: 0px solid #dad9d6!important;
border-color: #dad9d6!important;
background-color: #e8e7e4!important;
}
.CodeMirror-gutters {
border-right: 1px solid #f1f3f450;
background: inherit;
white-space: nowrap;
}
.ty-footer, .sidebar-footer, footer {
backdrop-filter: saturate(120%) blur(20px) brightness(0.85);
border: none!important;
background: none;
background-color: #f7f6f3;
}
.code-tooltip {
border-radius: 4px;
background-color: #313334;
box-shadow: 0 25.6px 57.6px 0 rgba(0, 0, 0, .52), 0 4.8px 14.4px 0 rgba(0, 0, 0, .28)!important;
}
#sidebar-files-menu {
border-radius: 4px;
border: none!important;
box-shadow: 0 25.6px 57.6px 0 #f7f6f3, 0 4.8px 14.4px 0 rgba(0, 0, 0, .28);
}
.code-tooltip.md-tooltip-hide.md-hover-tip {
box-shadow: 0 25.6px 57.6px 0 rgba(0, 0, 0, .52), 0 4.8px 14.4px 0 rgba(0, 0, 0, .28);
}
#typora-sidebar {
border: none !important;
}
#footer-word-count-info, #spell-check-panel {
border: none!important;
backdrop-filter: saturate(120%) blur(20px) brightness(0.85)!important;
box-shadow: 0 25.6px 57.6px 0 rgba(0, 0, 0, .32), 0 4.8px 14.4px 0 rgba(0, 0, 0, .28)!important;
}
/* Windows/Linux unibody mode */
.megamenu-content,
.megamenu-opened header {
color: var(--primary-color);
background: var(--bg-color-dark);
}
#recent-file-panel-action-btn {
background: inherit;
border: 1px var(--light-trait-300) solid;
}
.megamenu-menu-panel table td:nth-child(1) {
color: var(--text-color);
background: var(--bg-color-dark);
}
.megamenu-menu-panel table td:nth-child(2) {
color: var(--text-color);
background: var(--bg-color-dark);
}
.megamenu-menu-panel tbody tr:hover td:nth-child(1) {
color: var(--text-color);
background: var( --active-file-bg-color);
}
.megamenu-menu-panel tbody tr:hover td:nth-child(2) {
color: var(--text-color);
background: var( --active-file-bg-color);
}
.megamenu-menu-panel input[type='text'] {
background: inherit;
border: 1px var(--control-text-color) solid;
}
#recent-file-panel-action-btn {
background: inherit;
}
.megamenu-menu,
#top-titlebar, #top-titlebar *,
.megamenu-content {
background: var(--side-bar-bg-color);
color: var(--text-color);
}
.megamenu-menu-header #megamenu-menu-header-title:before {
color: var(--text-color);
}
megamenu-back-btn {
color: var(--text-color);
border-color: var(--text-color);
}
.megamenu-menu-header #megamenu-menu-header-title,
.megamenu-menu-header:hover,
.megamenu-menu-header:focus {
color: inherit;
}
@media print { @page {margin: 0 0 0 0;} body.typora-export {padding-left: 0; padding-right: 0;} #write {padding:0;}}
</style><title>Maturitní otázky z programování</title>
</head>
<body class='typora-export'><div class='typora-export-content'>
<div id='write' class=''><p><span>Tomáš Hobza 6.F, 2022 - </span><strong><span>Maturitní otázky z Programování</span></strong></p><div class='md-toc' mdtype='toc'><p class="md-toc-content" role="list"><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n4"><a class="md-toc-inner" style="" href="#algoritmizace-úloh">Algoritmizace úloh</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n5"><a class="md-toc-inner" style="" href="#algoritmus"><strong>algoritmus</strong></a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n9"><a class="md-toc-inner" style="" href="#vlastnosti-algoritmu"><strong>vlastnosti algoritmu</strong></a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n19"><a class="md-toc-inner" style="" href="#program"><strong>program</strong></a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n25"><a class="md-toc-inner" style="" href="#způsoby-vyjádření-algoritmu"><strong>způsoby vyjádření algoritmu</strong></a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n29"><a class="md-toc-inner" style="" href="#abstrakce"><strong>abstrakce</strong></a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n37"><a class="md-toc-inner" style="" href="#dekompozice"><strong>dekompozice</strong></a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n45"><a class="md-toc-inner" style="" href="#programovací-jazyk---jazykové-konstrukce">Programovací jazyk - jazykové konstrukce</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n46"><a class="md-toc-inner" style="" href="#pojmy-1">pojmy</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n70"><a class="md-toc-inner" style="" href="#jazykové-konstrukce">jazykové konstrukce</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n189"><a class="md-toc-inner" style="" href="#příkazy"><strong>příkazy</strong></a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n240"><a class="md-toc-inner" style="" href="#programovací-jazyk---podprogramy">Programovací jazyk - podprogramy</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n241"><a class="md-toc-inner" style="" href="#prototyp-funkce-návratová-hodnota-parametry">prototyp funkce, návratová hodnota, parametry</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n270"><a class="md-toc-inner" style="" href="#parametry"><strong>parametry</strong></a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n312"><a class="md-toc-inner" style="" href="#lokální-a-globální-proměnné">lokální a globální proměnné</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n326"><a class="md-toc-inner" style="" href="#zásobník-a-fungování-podprogramu">zásobník a fungování podprogramu</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n338"><a class="md-toc-inner" style="" href="#programovací-jazyk----práce-se-soubory">Programovací jazyk – práce se soubory</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n339"><a class="md-toc-inner" style="" href="#proměnná-pro-práci-se-souborem">proměnná pro práci se souborem</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n360"><a class="md-toc-inner" style="" href="#způsoby-otevírání-souborů-módy"><strong>způsoby otevírání souborů</strong> (<em>módy</em>)</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n382"><a class="md-toc-inner" style="" href="#operace-pro-práci-se-souborem">operace pro práci se souborem</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n420"><a class="md-toc-inner" style="" href="#zobrazení-dat-v-počítači">Zobrazení dat v počítači</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n421"><a class="md-toc-inner" style="" href="#pojem-informace-jednotky-pro-měření-informace">pojem informace, jednotky pro měření informace</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n446"><a class="md-toc-inner" style="" href="#číselné-soustavy-převody-mezi-soustavami">číselné soustavy, převody mezi soustavami</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n478"><a class="md-toc-inner" style="" href="#přímý-inverzní-doplňkový-kód">přímý, inverzní, doplňkový kód</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n520"><a class="md-toc-inner" style="" href="#formální-jazyky-automaty">Formální jazyky, automaty </a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n521"><a class="md-toc-inner" style="" href="#pojmy-2">pojmy</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n587"><a class="md-toc-inner" style="" href="#dělení-jazyků">dělení jazyků</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n596"><a class="md-toc-inner" style="" href="#chomského-hierarchie-gramatik-1">Chomského hierarchie gramatik </a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n599"><a class="md-toc-inner" style="" href="#způsoby-popisu-jazyku">způsoby popisu jazyku</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n744"><a class="md-toc-inner" style="" href="#gramatiky"><strong>Gramatiky</strong></a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n745"><a class="md-toc-inner" style="" href="#pojmy-3">pojmy</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n793"><a class="md-toc-inner" style="" href="#vztah-mezi-jazykem-gramatikou-a-konečným-automatem">vztah mezi jazykem, gramatikou a konečným automatem</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n795"><a class="md-toc-inner" style="" href="#chomského-hierarchie-gramatik-2">Chomského hierarchie gramatik</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n806"><a class="md-toc-inner" style="" href="#model-počítače-strojové-jazyky">Model počítače, strojové jazyky</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n807"><a class="md-toc-inner" style="" href="#struktura-a-funkce-procesoru-registry-řadič-alu">Struktura a funkce procesoru: registry, řadič, ALU</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n840"><a class="md-toc-inner" style="" href="#von-neumannovo-schéma-harvardská-architektura">von Neumannovo schéma, Harvardská architektura</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n854"><a class="md-toc-inner" style="" href="#instrukční-cyklus">instrukční cyklus</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n867"><a class="md-toc-inner" style="" href="#jazyk-symbolických-adres-assembler">jazyk symbolických adres, assembler</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n881"><a class="md-toc-inner" style="" href="#metody-adresování-paměti">metody adresování paměti</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n909"><a class="md-toc-inner" style="" href="#model-paměti">model paměti</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n942"><a class="md-toc-inner" style="" href="#dynamické-datové-struktury">Dynamické datové struktury</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n943"><a class="md-toc-inner" style="" href="#pojem-abstraktní-datový-typ">pojem abstraktní datový typ</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n966"><a class="md-toc-inner" style="" href="#konstrukce-základních-dynamických-datových-struktur-a-operace-s-nimi">Konstrukce základních dynamických datových struktur a operace s nimi</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n1050"><a class="md-toc-inner" style="" href="#hromadné-zpracování-dat-databáze">Hromadné zpracování dat, databáze</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1051"><a class="md-toc-inner" style="" href="#proč-hzd-úlohy-hzd">Proč HZD? Úlohy HZD</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1086"><a class="md-toc-inner" style="" href="#organizace-souborů-z-pro-hromadné-zpracování-dat-tj-obrovské-soubory-přístup-k-souborům">Organizace souborů z pro hromadné zpracování dat (tj. obrovské soubory), přístup k souborům</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1173"><a class="md-toc-inner" style="" href="#součásti-databáze">Součásti databáze</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n1243"><a class="md-toc-inner" style="" href="#eliminační-metody-pro-řešení-soustav-n-lineárních-rovnic-o-n-neznámých">Eliminační metody pro řešení soustav n lineárních rovnic o n neznámých</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1244"><a class="md-toc-inner" style="" href="#pojmy-4">pojmy</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1283"><a class="md-toc-inner" style="" href="#vyjádření-soustavy-lineárních-rovnic-pomocí-matic">vyjádření soustavy lineárních rovnic pomocí matic</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1290"><a class="md-toc-inner" style="" href="#gaussova-eliminační-metoda">Gaussova eliminační metoda</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1318"><a class="md-toc-inner" style="" href="#gauss-jordanova-eliminační-metoda">Gauss-Jordanova eliminační metoda</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n1326"><a class="md-toc-inner" style="" href="#iterační-metody-pro-řešení-soustav-n-lineárních-rovnic-o-n-neznámých">Iterační metody pro řešení soustav n lineárních rovnic o n neznámých</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1327"><a class="md-toc-inner" style="" href="#pojmy-5">pojmy</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1359"><a class="md-toc-inner" style="" href="#iterační-výpočet">iterační výpočet</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1383"><a class="md-toc-inner" style="" href="#jacobiho-iterační-metoda"><strong>Jacobiho iterační metoda</strong></a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1394"><a class="md-toc-inner" style="" href="#gauss-seidelova-iterační-metoda"><strong>Gauss-Seidelova iterační metoda</strong></a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n1401"><a class="md-toc-inner" style="" href="#řešení-nelineárních-rovnic">Řešení nelineárních rovnic</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1402"><a class="md-toc-inner" style="" href="#pojmy-6">pojmy</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1420"><a class="md-toc-inner" style="" href="#vyčíslení-polynomu-hornerovým-schématem">vyčíslení polynomu Hornerovým schématem</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1430"><a class="md-toc-inner" style="" href="#definice-úlohy-řešení-nelineárních-rovnic">definice úlohy řešení nelineárních rovnic</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1436"><a class="md-toc-inner" style="" href="#metody">metody</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n1480"><a class="md-toc-inner" style="" href="#metoda-nejmenších-čtverců">Metoda nejmenších čtverců</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1481"><a class="md-toc-inner" style="" href="#pojmy-7">pojmy</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1493"><a class="md-toc-inner" style="" href="#princip">princip</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1508"><a class="md-toc-inner" style="" href="#odvození-pro-konstantní-a-lineární-funkci">odvození pro konstantní a lineární funkci</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n1518"><a class="md-toc-inner" style="" href="#metody-vnitřního-řazení">Metody vnitřního řazení</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1519"><a class="md-toc-inner" style="" href="#vlastnosti-řadících-algoritmů">vlastnosti řadících algoritmů</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1552"><a class="md-toc-inner" style="" href="#algoritmy">algoritmy</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1592"><a class="md-toc-inner" style="" href="#princip-ostatních-metod">princip ostatních metod</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n1627"><a class="md-toc-inner" style="" href="#metody-vnitřní-řazení">Metody vnitřní řazení</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1628"><a class="md-toc-inner" style="" href="#specifika-vnějšího-řazení">specifika vnějšího řazení</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1652"><a class="md-toc-inner" style="" href="#pojmy-8">pojmy</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1658"><a class="md-toc-inner" style="" href="#přímé-a-přirozené-řazení">přímé a přirozené řazení</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1688"><a class="md-toc-inner" style="" href="#metody-zlepšování">metody zlepšování</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1707"><a class="md-toc-inner" style="" href="#princip-polyfázového-slučování">princip polyfázového slučování</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n1717"><a class="md-toc-inner" style="" href="#vyhledávací-algoritmy">Vyhledávací algoritmy</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1718"><a class="md-toc-inner" style="" href="#pojmy-9">pojmy</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1729"><a class="md-toc-inner" style="" href="#sekvenční-vyhledávání">sekvenční vyhledávání</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1751"><a class="md-toc-inner" style="" href="#binární-vyhledávání">binární vyhledávání</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1775"><a class="md-toc-inner" style="" href="#hašovací-tabulka">hašovací tabulka</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1790"><a class="md-toc-inner" style="" href="#princip-index-sekvenčního-vyhledávání">princip index-sekvenčního vyhledávání</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1794"><a class="md-toc-inner" style="" href="#binární-vyhledávací-strom">binární vyhledávací strom</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1833"><a class="md-toc-inner" style="" href="#srovnání-vyhledávacích-metod">srovnání vyhledávacích metod</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n1893"><a class="md-toc-inner" style="" href="#objektově-orientované-programování">Objektově orientované programování</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1894"><a class="md-toc-inner" style="" href="#pojmy-10">pojmy</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1924"><a class="md-toc-inner" style="" href="#zapouzdření-dědičnost-polymorfismus">zapouzdření, dědičnost, polymorfismus</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1943"><a class="md-toc-inner" style="" href="#praktické-použití-oop">praktické použití OOP</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n1955"><a class="md-toc-inner" style="" href="#operační-systémy">Operační systémy</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1956"><a class="md-toc-inner" style="" href="#struktura-os-vrstvy">struktura OS (vrstvy)</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n1973"><a class="md-toc-inner" style="" href="#modulární-os">modulární OS</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n2042"><a class="md-toc-inner" style="" href="#multitasking">multitasking</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n2065"><a class="md-toc-inner" style="" href="#procesy-vlákna-životní-cyklus-procesu">procesy, vlákna, životní cyklus procesu</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n2091"><a class="md-toc-inner" style="" href="#počítačové-sítě---hardware">Počítačové sítě - hardware</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n2092"><a class="md-toc-inner" style="" href="#rozdělení-sítí">rozdělení sítí</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n2110"><a class="md-toc-inner" style="" href="#druhy-sítí">druhy sítí</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n2169"><a class="md-toc-inner" style="" href="#topologie">topologie</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n2224"><a class="md-toc-inner" style="" href="#prvky-sítě">prvky sítě</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n2275"><a class="md-toc-inner" style="" href="#metody-přístupu">metody přístupu</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n2296"><a class="md-toc-inner" style="" href="#funkce-počítačové-sítě">funkce počítačové sítě</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n2308"><a class="md-toc-inner" style="" href="#počítačové-sítě---software">Počítačové sítě - software</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n2309"><a class="md-toc-inner" style="" href="#model-isoosi">model ISO/OSI</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n2360"><a class="md-toc-inner" style="" href="#model-tcpip">model TCP/IP</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n2428"><a class="md-toc-inner" style="" href="#protokoly">protokoly</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n2477"><a class="md-toc-inner" style="" href="#internet">internet</a></span><span role="listitem" class="md-toc-item md-toc-h1" data-ref="n2498"><a class="md-toc-inner" style="" href="#booleova-algebra-a-její-využití">Booleova algebra a její využití</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n2499"><a class="md-toc-inner" style="" href="#základní-pojmy">základní pojmy</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n2532"><a class="md-toc-inner" style="" href="#logické-funkce">logické funkce</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n2556"><a class="md-toc-inner" style="" href="#zákony">zákony</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n2649"><a class="md-toc-inner" style="" href="#vyjadřování-logických-funkcí">vyjadřování logických funkcí</a></span><span role="listitem" class="md-toc-item md-toc-h2" data-ref="n2678"><a class="md-toc-inner" style="" href="#minimalizace-logických-funkcí">minimalizace logických funkcí</a></span></p></div><p> </p><h1 id='algoritmizace-úloh'><span>Algoritmizace úloh</span></h1><h2 id='algoritmus'><strong><span>algoritmus</span></strong></h2><ul><li><span>popis postupu řešení daného problému</span></li></ul><h2 id='vlastnosti-algoritmu'><strong><span>vlastnosti algoritmu</span></strong></h2><ul><li><span>jednoduchý (</span><em><span>elementární, jeden příkaz = jeden význam</span></em><span>)</span></li><li><span>konečný</span></li><li><span>resultativní (</span><em><span>vede k výsledku</span></em><span>)</span></li><li><span>deterministický (</span><em><span>jednoznačný, stejné parametry = stejný výsledek</span></em><span>)</span></li></ul><h2 id='program'><strong><span>program</span></strong></h2><ul><li><span>zápis algoritmu, aby mu rozuměl procesor</span></li><li><span>procesor = ten/to, co vykonává algoritmus</span></li></ul><h2 id='způsoby-vyjádření-algoritmu'><strong><span>způsoby vyjádření algoritmu</span></strong></h2><ul><li><span>slovní popis, vývojové diagramy, programovací jazyk</span></li></ul><h2 id='abstrakce'><strong><span>abstrakce</span></strong></h2><ul><li><span>princip řešení problému</span></li><li><span>řešení problému skládáním řešeních menších problémů</span></li><li><span>zdola nahoru</span></li></ul><h2 id='dekompozice'><strong><span>dekompozice</span></strong></h2><ul><li><span>princip řešení problému</span></li><li><span>rozdělení řešení velkého problému na řešení malých částí problému</span></li><li><span>shora dolů</span></li></ul><h1 id='programovací-jazyk---jazykové-konstrukce'><span>Programovací jazyk - jazykové konstrukce</span></h1><h2 id='pojmy-1'><span>pojmy</span></h2><ul><li><p><strong><span>deklarace</span></strong></p><ul><li><span>prohlášení existence</span></li><li><span>proměnné s daným typem a jménem</span></li></ul></li><li><p><strong><span>definice</span></strong></p><ul><li><span>příkaz</span></li><li><span>vyrobí danou proměnnou v paměti</span></li></ul></li><li><p><strong><span>inicializace</span></strong></p><ul><li><span>první přiřazení hodnoty do proměnné</span></li><li><span>neinicializována proměnná má nedefinovanou hodnotu</span></li></ul></li></ul><h2 id='jazykové-konstrukce'><span>jazykové konstrukce</span></h2><ul><li><p><strong><span>proměnná</span></strong></p><ul><li><span>pojmenovaná paměťová buňka</span></li><li><span>má datový typ</span></li><li><span>její hodnota se může měnit (narozdíl od konstanty)</span></li><li><span>global/local</span></li></ul></li><li><p><strong><span>datový typ</span></strong></p><ul><li><p><span>definuje druh jakých hodnot smí proměnná nabývat</span></p></li><li><p><span>dělení:</span></p><ul><li><p><span>složené (</span><em><span>složené z jiných datových typů</span></em><span>)</span></p><ul><li><span>homogenní (</span><em><span>pole integerů</span></em><span>)</span></li><li><span>heterogenní (</span><em><span>objekt</span></em><span>)</span></li></ul></li><li><p><span>jednoduché</span></p></li><li><p><span>ukazatelové (</span><em><span>obsahují adresu paměťového místa</span></em><span>)</span></p><ul><li><span>typové</span></li><li><span>netypové (</span><em><span>nemají typ, jen ukazují na místo pomocí voidu</span></em><span>)</span></li></ul></li></ul></li></ul></li><li><p><strong><span>příkaz</span></strong></p><ul><li><p><span>nejmenší samostatný prvek programu</span></p></li><li><p><span>vyjadřuje činnost, která má být provedena</span></p></li><li><p><span>obsahuje proveditelný kód</span></p></li><li><p><span>skládá se z výrazů</span></p></li><li><p><span>dělení:</span></p><ul><li><span>jednoduchý</span></li><li><span>složený (</span><em><span>blok, obsahuje jeden nebo více příkazů</span></em><span>)</span></li></ul></li></ul></li><li><p><strong><span>výraz</span></strong></p><ul><li><p><span>má nebo reprezentuje hodnotu konkrétního typu</span></p></li><li><p><span>dělení:</span></p><ul><li><p><span>L-hodnota</span></p><ul><li><span>výraz může být na obou stranách přiřazovacího operátoru</span></li><li><span>př.: </span><strong><span>x</span></strong><span> = a+b</span></li></ul></li><li><p><span>P-hodnota</span></p><ul><li><span>výraz, který může být pouze na pravé straně přiřazovacího operátoru</span></li><li><span>př.: x = </span><strong><span>a+b</span></strong></li></ul></li></ul></li><li><p><span>důležité operátory:</span></p><ul><li><p><span>dereferenční operátor (</span><strong><span>*</span></strong><span>)</span></p><ul><li><span>vrací </span><strong><span>hodnotu</span></strong><span> paměťové, na níž odkazuje ukazatel</span></li><li><span>celý výraz je L-hodnota</span></li></ul></li><li><p><span>referenční operátor (</span><strong><span>&</span></strong><span>)</span></p><ul><li><span>vrací </span><strong><span>adresu</span></strong><span> proměnné nebo výrazu</span></li><li><span>celý výraz je P-hodnota</span></li></ul></li><li><p><span>operátor indexování pole (</span><strong><span>[]</span></strong><span>)</span></p><ul><li><span>celý výraz je L-hodnota</span></li></ul></li><li><p><span>operátor přístupu ke složce struktury (</span><strong><span>.</span></strong><span>)</span></p><ul><li><span>celý výraz je L-hodnota</span></li></ul></li><li><p><span>operátor přístupu ke složce přes ukazatel na strukturu (</span><strong><span>-></span></strong><span>)</span></p><ul><li><span>celý výraz je L-hodnota</span></li></ul></li><li><p><span>operátor volání funkce (</span><strong><span>()</span></strong><span>)</span></p><ul><li><span>bez něj je výraz chápán jako ukazatel na funkci</span></li></ul></li></ul></li></ul></li><li><p><strong><span>podprogram</span></strong></p><ul><li><span>jazyková konstrukce, která označuje část programu, kterou jde opakovaně zavolat</span></li></ul></li></ul><h2 id='příkazy'><strong><span>příkazy</span></strong></h2><ul><li><p><strong><span>větvení</span></strong></p><ul><li><p><span>rozdělení průběhu programu na základě nějaké podmínky</span></p></li><li><p><span>pro zápis podmínky používáme </span><strong><span>relační operátory</span></strong><span> (<, <=, >, >=) nebo </span><strong><span>operátory rovnosti</span></strong><span> (==, !=)</span></p></li><li><p><span>příkazy:</span></p><ul><li><p><strong><span>if</span></strong></p><ul><li><span>začíná klíčovým slovem if, za kterým následuje výraz typu boolean </span></li><li><span>může obsahovat větev </span><strong><span>else</span></strong><span>, která se provede, pokud podmínka vrátí nepravdu</span></li><li><span>je-li větev na více řádcích, použijeme </span><strong><span>blok</span></strong></li></ul></li><li><p><strong><span>switch</span></strong></p><ul><li><span>nahrazení zřetězených příkazů if</span></li><li><span>obsahuje návěstí (</span><strong><span>case</span></strong><span>)</span></li></ul></li></ul></li></ul></li><li><p><strong><span>cykly</span></strong></p><ul><li><p><span>opakování příkazů v závislosti na ukončovací podmínce nebo předem daném počtu opakování</span></p></li><li><p><span>dělení:</span></p><ul><li><p><span>s pevným počtem opakování (</span><strong><span>for</span></strong><span>)</span></p><ul><li><span>provede se tolikrát, jak určuje rozsah řídící proměnné</span></li></ul></li><li><p><span>s podmínkou na začátku (</span><strong><span>while</span></strong><span>)</span></p><ul><li><span>v případě, že již na začátku neplatí podmínka, nepovede se vůbec</span></li></ul></li><li><p><span>s podmínkou na konci (</span><strong><span>do … while</span></strong><span>)</span></p><ul><li><span>vždy se provede alespoň jednou</span></li></ul></li></ul></li></ul></li></ul><h1 id='programovací-jazyk---podprogramy'><span>Programovací jazyk - podprogramy</span></h1><h2 id='prototyp-funkce-návratová-hodnota-parametry'><span>prototyp funkce, návratová hodnota, parametry</span></h2><ul><li><p><strong><span>prototyp funkce</span></strong></p><ul><li><span>“hlavička”</span></li><li><span>uvedení návratové hodnoty, identifikátoru a seznamu parametrů bez těla funkce</span></li></ul></li><li><p><strong><span>návratová hodnota</span></strong></p><ul><li><span>hodnota, kterou podprogram vrací</span></li><li><span>její datový typ je určený datovým typem podprogramu (funkce)</span></li></ul></li><li><p><strong><span>druhy podprogramů</span></strong></p><ul><li><p><strong><span>funkce</span></strong></p><ul><li><span>vrací návratovou hodnotu</span></li></ul></li><li><p><strong><span>procedura</span></strong></p><ul><li><span>nevrací návratovou hodnotu</span></li></ul></li></ul></li></ul><h2 id='parametry'><strong><span>parametry</span></strong></h2><ul><li><p><span>vstupní data podprogramu</span></p></li><li><p><span>druhy:</span></p><ul><li><p><strong><span>formální</span></strong></p><ul><li><span>vnitřní proměnná</span></li><li><span>parametr použitý při psaní funkce</span></li><li><span>je vždy před zpracováním nahrazována hodnotou </span><strong><span>skutečného parametru</span></strong></li></ul></li><li><p><strong><span>skutečný</span></strong></p><ul><li><span>proměnná nebo výraz dosazený při volání podprogramu</span></li><li><span>při volání podprogramu je jeho hodnota přiřazena </span><strong><span>formálnímu parametru</span></strong></li></ul></li></ul></li><li><p><span>dělení dle způsobu předávání:</span></p><ul><li><p><strong><span>hodnotou</span></strong></p><ul><li><span>skutečný parametr se před zpracováním podprogramu vyčíslí a výsledek se zkopíruje do lokální proměnné uvnitř volaného podprogramu</span></li><li><span>lokální proměnná po skončení podprogramu </span><strong><span>zanikne</span></strong></li><li><strong><span>není možné upravovat</span></strong><span> proměnnou, která byla předána jako skutečný parametr</span></li></ul></li><li><p><strong><span>odkazem</span></strong></p><ul><li><span>formální parametr je jen jiné označení (</span><em><span>alias</span></em><span>) pro proměnnou předanou jako skutečný parametr</span></li><li><span>předávání odkazem lze použít i jako vstupně-výstupní parametr</span></li></ul></li></ul></li></ul><h2 id='lokální-a-globální-proměnné'><span>lokální a globální proměnné</span></h2><ul><li><p><strong><span>lokální</span></strong></p><ul><li><span>existují jen v rámci podprogramu či bloku, ve kterém byli definované</span></li></ul></li><li><p><strong><span>globální</span></strong></p><ul><li><span>existují v celém programu od místa, kde byli definované</span><span> </span></li><li><strong><span>zastínění globální proměnné</span></strong><span> = lokální proměnná se stejným jménem jako globální má větší prioritu v podprogramu, kde lokální proměnná existuje</span></li></ul></li></ul><h2 id='zásobník-a-fungování-podprogramu'><span>zásobník a fungování podprogramu</span></h2><ul><li><p><strong><span>zásobník (volání)</span></strong></p><ul><li><span>ukládají se zde lokální proměnné a informace týkající se provádění podprogramu</span></li></ul></li><li><p><strong><span>fungování</span></strong></p><ul><li><span>podprogram funguje podle to co mu uživatel zadá, vyrábí se na něm lokální proměnné, vytvoří se nový v vnoření</span></li></ul></li></ul><h1 id='programovací-jazyk----práce-se-soubory'><span>Programovací jazyk – práce se soubory</span></h1><h2 id='proměnná-pro-práci-se-souborem'><span>proměnná pro práci se souborem</span></h2><ul><li><p><strong><span>soubor</span></strong></p><ul><li><p><span>souvislá, sekvenční posloupnost bajtů</span></p></li><li><p><span>má jméno a umístění </span></p></li><li><p><span>pamatuje si délku v souborovém záznamu (</span><em><span>nemá na konci značku konce</span></em><span>)</span></p></li><li><p><strong><span>souborový záznam</span></strong></p><ul><li><span>obsahuje jméno, délku a umístění prvního fyzického bloku souboru</span></li></ul></li></ul></li><li><p><strong><span>proměnná typu ukazatel na soubor</span></strong></p><ul><li><span>obsahuje adresu na souborový záznam</span></li></ul></li></ul><h2 id='způsoby-otevírání-souborů-módy'><strong><span>způsoby otevírání souborů</span></strong><span> (</span><em><span>módy</span></em><span>)</span></h2><ul><li><p><strong><span>standardní</span></strong></p><ul><li><strong><span>r</span></strong><span> - otevře existující soubor pro čtení</span></li><li><strong><span>w</span></strong><span> - vytvoří soubor pro zápis (</span><em><span>nebo přepíše existující</span></em><span>)</span></li><li><strong><span>r+</span></strong><span> - otevře existující soubor pro čtení a zápis</span></li><li><strong><span>w+</span></strong><span> - vytvoří soubor pro zápis a čtení (</span><em><span>nebo přepíše existující</span></em><span>)</span></li></ul></li><li><p><strong><span>speciální</span></strong></p><ul><li><strong><span>a</span></strong><span> - otevře soubor pro připisování na konec</span></li><li><strong><span>a+</span></strong><span> - otevře soubor pro připisování a zároveň čtení (</span><em><span>pokud neexistuje, vytvoří nový</span></em><span>)</span></li><li><strong><span>rb, wb</span></strong><span> - pro binární soubory ve Windows</span></li></ul></li></ul><h2 id='operace-pro-práci-se-souborem'><span>operace pro práci se souborem</span></h2><ul><li><p><strong><span>otevření</span></strong></p><ul><li><span>v jazyce C: </span><em><span>fopen()</span></em></li></ul></li><li><p><strong><span>čtení</span></strong></p><ul><li><p><span>po znacích</span></p><ul><li><span>v jazyce C: </span><em><span>fgetc()</span></em></li></ul></li><li><p><span>formátované</span></p><ul><li><span>v jazyce C: </span><em><span>fscanf()</span></em></li></ul></li></ul></li><li><p><strong><span>zápis</span></strong></p><ul><li><p><span>po znacích</span></p><ul><li><span>v jazyce C: </span><em><span>fputc()</span></em></li></ul></li><li><p><span>formátované</span></p><ul><li><span>v jazyce C: </span><em><span>fprintf()</span></em></li></ul></li></ul></li><li><p><strong><span>uzavření</span></strong></p><ul><li><span>v jazyce C: </span><em><span>fclose()</span></em></li></ul></li></ul><h1 id='zobrazení-dat-v-počítači'><span>Zobrazení dat v počítači</span></h1><h2 id='pojem-informace-jednotky-pro-měření-informace'><span>pojem informace, jednotky pro měření informace</span></h2><ul><li><p><strong><span>informace</span></strong></p><ul><li><p><span>srozumitelná a smysluplná data</span></p></li><li><p><span>interpretace dat a vztahů mezi nimi</span></p></li><li><p><span>kvantitativní vyjádření obsahu zprávy</span></p></li><li><p><strong><span>data</span></strong></p><ul><li><span>vše, co mohu zaznamenat smysly</span></li><li><span>surová data, údaje získané měřením, pozorováním, atd.</span></li><li><span>objem dat se měří v </span><strong><span>bitech</span></strong><span> a </span><strong><span>bajtech</span></strong></li></ul></li></ul></li><li><p><strong><span>jednotky pro měření informace</span></strong></p><ul><li><span>měří se v </span><strong><span>bitech</span></strong></li></ul></li></ul><h2 id='číselné-soustavy-převody-mezi-soustavami'><span>číselné soustavy, převody mezi soustavami</span></h2><ul><li><p><span>dělení:</span></p><ul><li><p><strong><span>poziční</span></strong></p><ul><li><span>vyjádření číselné hodnoty pomocí </span><strong><span>číslic</span></strong></li><li><strong><span>řád</span></strong><span> číslice odpovídá její pozici</span></li><li><span>počet možných číslic odpovídá </span><strong><span>základu</span></strong><span> dané soustavy</span></li></ul></li><li><p><strong><span>nepoziční</span></strong></p><ul><li><em><span>např.: římské číslice</span></em></li><li><span>neznají nulu</span></li><li><span>složité počítání</span></li></ul></li></ul></li><li><p><span>určení, vyčíslení hodnoty</span></p><ul><li><span>polynomiální zápis</span></li><li><span>hornerovo schema</span></li></ul></li><li><p><span>převody mezi soustavami</span></p></li></ul><h2 id='přímý-inverzní-doplňkový-kód'><span>přímý, inverzní, doplňkový kód</span></h2><ul><li><p><span>kódování celých čísel</span></p><ul><li><p><strong><span>přímý kód</span></strong></p><ul><li><span>nejvyšší bit je znaménkový</span></li><li><span>nevýhody: dvě nuly, obvody pro odečítání</span></li></ul></li><li><p><strong><span>inverzní kód</span></strong></p><ul><li><span>nejvyšší bit je znaménkový a záporné číslo je negací kladného</span></li><li><span>při počítání je třeba přičíst přenos z nejvyššího řádu</span></li><li><span>nevýhody: dvě nuly</span></li></ul></li><li><p><strong><span>doplňkový kód</span></strong></p><ul><li><span>nejvyšší bit je znaménkový a záporné číslo je negací kladného s přičtenou jedničkou</span></li><li><span>výhody: jen jedna nula</span></li></ul></li><li><p><span>kódování desetinných čísel (</span><em><span>nikdy nebudou přesné, nejde mít nekonečno desetinných míst</span></em><span>)</span></p><ul><li><p><span>standard IEEE 754</span></p></li><li><p><strong><span>znaménkový bit, exponent, mantisa</span></strong></p><ul><li><span>znaménkový bit - </span><strong><span>0 = kladné, 1 = záporné</span></strong></li><li><span>exponent - v aditivním kódu, počet desetinných míst posunutí čárky v mantise</span></li><li><span>mantisa - desetinný rozvoj čísla v normalizovaném tvaru</span></li></ul></li></ul></li></ul></li></ul><h1 id='formální-jazyky-automaty'><span>Formální jazyky, automaty </span></h1><h2 id='pojmy-2'><span>pojmy</span></h2><ul><li><p><strong><span>syntaxe</span></strong></p><ul><li><span>soubor pravidel pro zápis jazyka</span></li><li><span>může být vyjádřena gramatikou, syntaktickým diagramem, …</span></li></ul></li><li><p><strong><span>sémantika</span></strong></p><ul><li><span>význam vět a slov jazyka</span></li><li><span>(</span><em><span>programu dává význam člověk</span></em><span>)</span></li></ul></li><li><p><strong><span>řetězec</span></strong></p><ul><li><span>shluk symbolů abecedy</span></li></ul></li><li><p><strong><span>věta</span></strong></p><ul><li><span>řetězec symbolů nad abecedou</span></li><li><span>prázdná věta = </span><strong><span>𝛆</span></strong></li></ul></li><li><p><strong><span>(formální) jazyk</span></strong></p><ul><li><p><span>množina </span><strong><span>vět</span></strong><span> (</span><em><span>textových řetězců</span></em><span>) nad danou, konečnou abecedou </span></p></li><li><p><span>značí se symbolem </span><strong><span>L</span></strong></p></li><li><p><span>pro jeho popis se používá obvykle </span><strong><span>gramatika</span></strong><span> a </span><strong><span>automat</span></strong></p></li><li><p><span>značení jazyků:</span></p><ul><li><p><strong><span>∑*</span></strong></p><ul><li><span>jazyk všechny možných vět nad abecedou ∑</span></li><li><span>nekonečný jazyk</span></li><li><span>nemá gramatiku -> jakýkoliv </span><strong><span>řetězec</span></strong><span> je </span><strong><span>věta</span></strong></li></ul></li><li><p><strong><span>A*</span></strong></p><ul><li><span>∑* nad abecedou A</span></li><li><span>jazyk všech možných vět nad abecedou A </span><strong><span>včetně prázdného řetězce</span></strong></li></ul></li><li><p><strong><span>A+</span></strong></p><ul><li><span>jazyk všech možných vět nad abecedou A </span><strong><span>kromě prázdného řetězce</span></strong></li></ul></li><li><p><strong><span>A</span><sup><span>n</span></sup></strong></p><ul><li><span>jazyk všech vět </span><strong><span>o délce n</span></strong><span> nad abecedou A</span></li></ul></li></ul></li></ul></li></ul><h2 id='dělení-jazyků'><span>dělení jazyků</span></h2><ul><li><p><span>rozdělení:</span></p><ul><li><strong><span>konečné</span></strong><span> - lze ho vyjmenovat (</span><em><span>konečný počet vět</span></em><span>)</span></li><li><strong><span>nekonečné</span></strong><span> - nelze ho vyjmenovat (</span><em><span>popisuje se generativně</span></em><span>) </span></li></ul></li></ul><h2 id='chomského-hierarchie-gramatik-1'><span>Chomského hierarchie gramatik </span></h2><p><img src="assets/image-20220312202635498.png" alt="image-20220312202635498" style="zoom:50%;" /><span> </span></p><p> </p><h2 id='způsoby-popisu-jazyku'><span>způsoby popisu jazyku</span></h2><ul><li><p><strong><span>deklarativní popis:</span></strong></p><ul><li><p><strong><span>výčet</span></strong></p><ul><li><p><span>vyjmenování všech vět</span></p><ul><li><span>lze jen pro konečné jazyky</span></li></ul></li></ul></li></ul></li><li><p><strong><span>generativní popis:</span></strong></p><ul><li><p><strong><span>syntaktický diagram</span></strong></p><ul><li><p><span>grafický popis syntaxe</span></p></li><li><p><span>používané symboly: </span><strong><span>terminály</span></strong><span>, </span><strong><span>nonterminály</span></strong><span>, </span><strong><span>šipky</span></strong></p><p><img src="assets/image-20220312202620539.png" alt="image-20220312202620539" style="zoom:50%;" /><span> </span></p></li></ul></li><li><p><strong><span>EBNF</span></strong><span> - rozšířená Backus-Naurova forma</span></p><ul><li><p><span>používáno pro popis syntaxe programovacích jazyků</span></p></li><li><p><strong><span>non-terminály</span></strong><span> - zapisují se slovně (</span><em><span>písmeno, číslice, příkaz-if</span></em><span>)</span></p></li><li><p><strong><span>terminály</span></strong><span> - jsou uvozeny uvozovkami</span></p></li><li><p><strong><span>pravidlo</span></strong></p><ul><li><span>na levé straně může být jen </span><strong><span>jeden</span></strong><span> non-terminál</span></li><li><span>na pravé straně mohou být terminály i non-terminály</span></li><li><span>např.: </span><code>nonterminál = varianta1 | varianta2 | varianta 3 ;</code></li></ul></li><li><p><strong><span>symboly v pravidlech</span></strong></p><ul><li><p><code>=</code><span> - odděluje levou a pravou stranu pravidla</span></p></li><li><p><code>|</code><span> - varianta, z non-terminálu lze jít jednou z více cest</span></p></li><li><p><code>;</code><span> - středník ukončuje pravidlo</span></p></li><li><p><code>,</code><span> - čárka ukončuje sekvenci</span></p><ul><li><span>např.: </span><code>slovo = "a", "h", "o", "j"</code></li></ul></li><li><p><code>{}</code><span> - výraz, který lze opakovat 0 a vícekrát</span></p><ul><li><span>např.: </span><code>číslo = číslice, { číslice } ;</code></li></ul></li><li><p><code>[]</code><span> - výraz, který lze opakovat 0 nebo 1 krát</span></p><ul><li><span>např.: </span><code>[+], číslo |['-'], číslo</code></li></ul></li><li><p><code>()</code><span> - seskupení, podvýraz</span></p><ul><li><span>např.: </span><code>přiřazení = identifikátor , '=' , (číslo | identifikátor | řetězec) ;</code></li></ul></li><li><p><code>-</code><span> - mínus vyjadřuje výjimku</span></p><ul><li><span>např.: </span><code>řetězec = '"' , { znak − '"' } , '"' ;</code></li></ul></li><li><p><span>příkaz </span><code>if-else</code></p><ul><li><span>např.: </span><code>příkaz if-else = 'if', '(', výraz, ')' , příkaz , [ 'else' , příkaz ];</code></li></ul></li><li><p><span>identifikátor</span></p><ul><li><span>např.: </span><code>identifikátor = znak , { znak | číslice };</code></li></ul></li><li><p><span>blokový příkaz</span></p><ul><li><span>např.: </span><code>blok = '{' , { příkaz } , '}' ;</code></li></ul></li></ul></li></ul></li><li><p><strong><span>gramatika</span></strong></p><ul><li><span>matematická struktura popisující (generující) formální jazyk </span><strong><span>L</span><sub><span>G</span></sub></strong></li><li><strong><span>L</span><sub><span>G</span></sub></strong><span> značí jazyk generovaný gramatikou </span><strong><span>G</span></strong></li><li><span>konečným počtem konečných pravidel dokáže popsat i nekonečné jazyky</span></li></ul></li><li><p><strong><span>konečný automat</span></strong></p><ul><li><p><strong><span>automat</span></strong></p><ul><li><p><span>algoritmický matematický stroj</span></p></li><li><p><span>slouží k rozhodování zda řetězce jsou věty daného jazyka</span></p></li><li><p><strong><span>Turingův stroj</span></strong></p><ul><li><span>teoretický model nejobecnějšího počítače</span></li><li><span>umí řešit všechny algoritmicky řešitelné problémy.</span></li></ul></li></ul></li><li><p><span>zjednodušený automat s konečným počtem stavů</span></p></li><li><p><span>využití:</span></p><ul><li><span>přijímání a zpracování nejjednodušších (regulárních) jazyků</span></li><li><span>řešení problémů, které lze formulovat tak, že program prochází</span>
<span>přesně rozlišitelnými stavy</span></li></ul></li><li><p><span>uspořádaná pětice </span><strong><span>A = (S, Σ, σ, s, F)</span></strong></p><ul><li><p><strong><span>S</span></strong><span> - konečná množina stavů automatu</span></p></li><li><p><strong><span>∑</span></strong><span> - konečná abeceda (</span><em><span>množina vstupních symbolů</span></em><span>)</span></p></li><li><p><strong><span>σ</span></strong><span> - přechodová funkce – popisuje, do jakého</span>
<span>stavu se automat přepne při vstupu dalšího vstupního symbolu</span></p></li><li><p><strong><span>s ∈ S</span></strong></p><ul><li><span>počáteční stav automatu</span></li></ul></li><li><p><strong><span>F ⊆ S</span></strong></p><ul><li><span>množina koncových stavů</span></li></ul></li></ul></li></ul></li></ul></li></ul><h1 id='gramatiky'><strong><span>Gramatiky</span></strong></h1><h2 id='pojmy-3'><span>pojmy</span></h2><ul><li><p><strong><span>abeceda</span></strong></p><ul><li><span>množina </span><strong><span>terminálních</span></strong><span> symbolů</span></li></ul></li><li><p><strong><span>gramatika</span></strong></p><ul><li><p><span>matematická struktura obsahující pravidla pro generování správných vět jazyka</span></p></li><li><p><span>obsahuje: </span><strong><span>non-terminální a terminální symboly, pravidla a počáteční non-terminál</span></strong></p></li><li><p><strong><span>G = (N, ∑, P, S)</span></strong><span> - uspořádaná čtveřice</span></p><ul><li><span>N - non-terminální symboly</span></li><li><span>∑ - terminální symboly (</span><em><span>abeceda</span></em><span>)</span></li><li><span>P - pravidla</span></li><li><span>S - počáteční non-terminál</span></li></ul></li><li><p><strong><span>symboly</span></strong></p><ul><li><strong><span>terminální</span></strong><span> - koncové, nereprezentují nic dalšího</span></li><li><strong><span>non-terminální</span></strong><span> - zkratky pro další syntaktické diagramy</span></li></ul></li></ul></li><li><p><strong><span>gramatické pravidlo</span></strong></p><ul><li><p><span>přepisovací pravidlo (</span><em><span>zkráceně </span><strong><span>pravidlo</span></strong></em><span>)</span></p></li><li><p><span>Slouží pro generování vět jazyka L</span><sub><span>G</span></sub></p><ul><li><span>zapisují se ve tvaru </span><strong><span>α → β</span></strong></li><li><span>α, β jsou řetězce tvořené abecedou N ∪ Σ</span></li><li><span>α je levá část pravidla, nesmí to být prázdný řetězec</span></li><li><span>β je pravá část pravidla</span></li></ul></li></ul></li></ul><h2 id='vztah-mezi-jazykem-gramatikou-a-konečným-automatem'><span>vztah mezi jazykem, gramatikou a konečným automatem</span></h2><p><img src="assets/image-20220312202703813.png" alt="image-20220312202703813" style="zoom:50%;" /><span> </span></p><h2 id='chomského-hierarchie-gramatik-2'><span>Chomského hierarchie gramatik</span></h2><p><img src="assets/image-20220312202648001.png" alt="image-20220312202648001" style="zoom:50%;" /><span> </span></p><ul><li><strong><span>regulární</span></strong><span> - non-terminál přepisuje na terminál, nebo na kombinaci non-terminálu a terminálu</span></li><li><strong><span>bezkontextové</span></strong><span> - non-terminál přepisuje na kombinaci jednoho nebo více terminálů a non-terminálů</span></li><li><strong><span>kontextové</span></strong><span> - jak bezkontextové, jen záleží na znacích před a po</span></li><li><strong><span>neomezené</span></strong><span> - libovolné přepisování (cokoliv můžeme přepsat na cokoliv)</span></li></ul><h1 id='model-počítače-strojové-jazyky'><span>Model počítače, strojové jazyky</span></h1><h2 id='struktura-a-funkce-procesoru-registry-řadič-alu'><span>Struktura a funkce procesoru: registry, řadič, ALU</span></h2><ul><li><p><strong><span>struktura CPU</span></strong></p><ul><li><p><strong><span>procesor</span></strong></p><ul><li><p><strong><span>řadič</span></strong></p><ul><li><span>řídící jednotka</span></li><li><span>řídí činnost všech modulů </span><strong><span>CPU</span></strong><span> pomocí řídících signálů (</span><em><span>moduly nazpět posílají stavová hlášení</span></em><span>)</span></li></ul></li><li><p><strong><span>ALU</span></strong><span> (</span><em><span>aritmeticko-logická jednotka</span></em><span>)</span></p><ul><li><span>provádí veškeré aritmetické a logické operace</span></li><li><span>obsahuje </span><strong><span>sčítačky</span></strong><span>, </span><strong><span>násobičky</span></strong><span> a </span><strong><span>komparátory</span></strong></li></ul></li></ul></li><li><p><strong><span>registry</span></strong></p><ul><li><span>nejnižší a nejrychlejší úroveň paměti počítače</span></li><li><span>obsahují operandy instrukcí</span></li><li><span>po vykonání instrukce se do nich zapisují výsledky</span></li><li><span>existují různé druhy (</span><em><span>univerzální, specializované, matematické, vektorové, …</span></em><span>)</span></li></ul></li></ul></li></ul><h2 id='von-neumannovo-schéma-harvardská-architektura'><span>von Neumannovo schéma, Harvardská architektura</span></h2><ul><li><p><strong><span>von Neumannovo schéma</span></strong></p><p><img src="assets/image-20220312203000028.png" alt="image-20220312203000028" style="zoom:50%;" /><span> </span></p></li><li><p><strong><span>Harvardská architektura</span></strong></p><ul><li><span>oddělené paměti programu a dat</span></li><li><span>instrukce i data lze zpracovávat paralelně</span></li><li><span>využití: např.: jednoúčelové počítače</span></li></ul></li></ul><h2 id='instrukční-cyklus'><span>instrukční cyklus</span></h2><ul><li><p><span>program řídí řadič mikroprocesoru takto</span></p><ol start='' ><li><span>převzetí instrukce z operační paměti</span></li><li><span>dekódování instrukce</span></li><li><span>provedení operace</span></li><li><span>příprava k převzetí další instrukce</span></li></ol></li></ul><h2 id='jazyk-symbolických-adres-assembler'><span>jazyk symbolických adres, assembler</span></h2><ul><li><p><strong><span>jazyk symbolických adres</span></strong><span> (</span><em><span>JSI</span></em><span>)</span></p><ul><li><span>textová reprezentace strojového kódu</span></li><li><span>nejnižší programovací člověk použitelný člověkem</span></li></ul></li><li><p><strong><span>assembler</span></strong></p><ul><li><span>program pro překlad </span><strong><span>JSI</span></strong><span> do strojového kódu</span></li></ul></li></ul><h2 id='metody-adresování-paměti'><span>metody adresování paměti</span></h2><ul><li><p><code>INSTRUKCE operand1, operand2</code></p></li><li><p><strong><span>operand</span></strong></p><ul><li><span>přímý operand (konstanta)</span></li><li><span>registr</span></li><li><span>adresa paměťové buňky</span></li></ul></li></ul><ol start='' ><li><strong><span>přímý operand</span></strong><span> - operand umístěn přímo v instrukci</span></li><li><strong><span>přímé adresování</span></strong><span> - operand je určen pomocí absolutní adresy paměťového místa</span></li><li><strong><span>registr</span></strong><span> - operandem je registr</span></li><li><strong><span>relativní adresování</span></strong><span> - adresa = bázový registr + relativní posun</span></li><li><strong><span>stránkové adresování</span></strong><span> - relativní adresování se segmentovým registrem</span></li><li><strong><span>indexové adresování</span></strong><span> - adresování s indexovým registrem</span></li><li><strong><span>nepřímé adresování</span></strong><span> - paměťové místo určené předchozími metodami obsahuje</span>
<span>nikoliv operand, ale adresu</span></li></ol><h2 id='model-paměti'><span>model paměti</span></h2><ul><li><p><strong><span>3 sekce</span></strong></p><ul><li><p><strong><span>heap space</span></strong></p><ul><li><span>je dynamická</span></li><li><span>po alokaci lze doalokovat další část</span></li><li><span>přístup pouze skrz pointery</span></li></ul></li><li><p><strong><span>stack memory</span></strong></p><ul><li><span>je statická</span></li><li><span>po alokaci nelze zvětšit</span></li><li><span>přístup přímo (</span><em><span>skrz hodnoty proměnných</span></em><span>)</span></li><li><span>dealokuje se po skončení bloku (</span><em><span>nemusí se čistit</span></em><span>)</span></li></ul></li><li><p><strong><span>code section</span></strong></p><ul><li><span>zavedená při načtení souboru</span></li><li><span>obsahuje instrukce pro vykonání algoritmu</span></li></ul></li></ul></li></ul><p><span> </span><img src="assets/image-20220312203013972.png" alt="image-20220312203013972" style="zoom:50%;" /><span> </span></p><h1 id='dynamické-datové-struktury'><span>Dynamické datové struktury</span></h1><h2 id='pojem-abstraktní-datový-typ'><span>pojem abstraktní datový typ</span></h2><ul><li><p><span>výraz pro typy dat, které jsou nezávislé na vlastní implementaci</span></p></li><li><p><strong><span>definován názvem, množinou hodnot a množinou operací, které je možno vykonat</span></strong></p></li><li><p><span>umožňuje vytvářet i složitější datové typy (</span><em><span>např. zásobník, fronta a asociativní pole</span></em><span>)</span></p></li><li><p><span>zjednodušuje a zpřehledňuje programy</span></p></li><li><p><span>datový typ ukazatel</span></p></li><li><p><span>neobsahuje data, pouze </span><strong><span>adresu</span></strong><span> na místo v paměti</span></p></li><li><p><strong><span>dynamická datová struktura</span></strong></p><ul><li><span>mění svou velikost během života programu</span></li><li><span>tvořena prvky stejného typu</span></li><li><strong><span>prvek</span></strong><span> - struktura, obsahuje ukazatel na (alespoň na jeden) další prvek (</span><em><span>poslední má ukazatel na</span></em><span> </span><code>NULL</code><span>)</span></li></ul></li></ul><h2 id='konstrukce-základních-dynamických-datových-struktur-a-operace-s-nimi'><span>Konstrukce základních dynamických datových struktur a operace s nimi</span></h2><ul><li><p><strong><span>zásobník</span></strong><span> - LIFO</span></p><p><img src="assets/image-20220312203029766.png" alt="image-20220312203029766" style="zoom:50%;" /><span> </span><span> </span></p><ul><li><span>tvořen jednosměrně vázaným seznamem prvků</span></li><li><span>počáteční prvek - </span><strong><span>vrchol (top)</span></strong></li><li><strong><span>LIFO</span></strong><span> - last-in-first-out, otáčí pořadí prvků</span></li><li><span>operace: </span><strong><span>push</span></strong><span>, </span><strong><span>pop</span></strong></li></ul></li><li><p><strong><span>fronta</span></strong><span> - FIFO</span></p><p><img src="assets/image-20220312203051282.png" alt="image-20220312203051282" style="zoom:50%;" /><span> </span></p><ul><li><span>tvořen jednosměrně vázaným seznamem prvků</span></li><li><span>vytváří buffer (</span><em><span>odkládání prvků pro pozdější zpracování ve stejném pořadí</span></em><span>)</span></li><li><strong><span>FIFO</span></strong><span> - first-in-first-out, zachová pořadí prvků</span></li><li><span>operace: </span><strong><span>enqueue</span></strong><span>, </span><strong><span>dequeue</span></strong></li></ul></li><li><p><strong><span>seznam</span></strong></p><p><img src="assets/image-20220312203106402.png" alt="image-20220312203106402" style="zoom:50%;" /><span> </span></p><ul><li><span>řada vzájemně provázaných prvků</span></li><li><span>má “čtecí hlavu”, pamatuje si nad kterým prvek proběhla poslední operace</span></li><li><span>homogenní, lineární, sekvenční, dynamická struktura</span></li><li><strong><span>prvky lze vkládat a odebírat uprostřed seznamu</span></strong></li><li><span>může být </span><strong><span>obousměrný</span></strong></li><li><strong><span>kruhový seznam</span></strong><span> = poslední prvek ukazuje na první</span></li><li><span>operace: (zásobníku a fronty) + </span><strong><span>insert</span></strong><span>, </span><strong><span>removeNext</span></strong><span>, </span><strong><span>prev</span></strong><span> (posune aktuální prvek na předchozí)</span></li></ul></li><li><p><strong><span>binární vyhledávací strom</span></strong></p><p><img src="assets/image-20220312203121052.png" alt="image-20220312203121052" style="zoom:50%;" /><span> </span></p><ul><li><p><span>pro rychlé ukládání a vyhledávání podle klíče</span></p></li><li><p><strong><span>strukturovaná data</span></strong><span> = párové hodnoty: </span><strong><span>klíč</span></strong><span> + </span><strong><span>hodnota</span></strong></p><ul><li><strong><span>uzel stromu</span></strong><span> - obsahuje ukazatel na </span><strong><span>levý</span></strong><span> a </span><strong><span>pravý</span></strong><span> podstrom, nese hodnotu klíče a data asociovaná s klíčem</span></li></ul></li><li><p><strong><span>binární strom</span></strong><span> - ukazatel na </span><strong><span>kořenový uzel</span></strong></p></li><li><p><span>vlastnosti:</span></p><ul><li><strong><span>výška</span></strong><span> stromu - délka nejdelší cestu od kořene</span></li><li><strong><span>váha</span></strong><span> stromu - počet uzlů stromu</span></li><li><strong><span>vyvážený</span></strong><span> strom - po všechny uzly platí, že váha jejich podstromů se liší maximálně o jedničku</span></li></ul></li><li><p><span>operace:</span></p><ul><li><p><span>průchody stromem</span></p><ul><li><strong><span>inorder</span></strong><span> - </span><code>inorder(levý); akceSAktuálnímUzlem(); inorder(pravý);</code></li><li><strong><span>preorder</span></strong><span> - </span><code>akceSAktuálnímUzlem(); preorder(levý); preorder(pravý);</code></li><li><strong><span>postorder</span></strong><span> - </span><code>postorder(levý); postorder(pravý); akceSAktuálnímUzlem();</code></li></ul></li><li><p><strong><span>přidání</span></strong></p></li><li><p><strong><span>odebrání</span></strong></p></li><li><p><strong><span>vyhledání uzlu</span></strong></p></li></ul></li></ul></li></ul><h1 id='hromadné-zpracování-dat-databáze'><span>Hromadné zpracování dat, databáze</span></h1><h2 id='proč-hzd-úlohy-hzd'><span>Proč HZD? Úlohy HZD</span></h2><ul><li><p><span>důvodem jsou </span><strong><span>velká data</span></strong><span> (</span><em><span>dva problémy - ukládání a zpracování</span></em><span>)</span></p></li><li><p><strong><span>úlohy HZD</span></strong><span>:</span></p><ol start='' ><li><p><strong><span>řazení</span></strong><span> - usnadňuje hledání</span></p><ul><li><p><strong><span>fyzické řazení</span></strong><span> - při řazení podle různých klíčů vznikají kopie</span></p><p><span>souborů</span></p></li><li><p><strong><span>indexové soubory</span></strong><span> - obsahují odkazy na kmenový soubor řadí se</span></p><p><span>indexy, zabírají méně místa => může existovat více indexových</span></p><p><span>souborů seřazených podle jiných klíčů</span></p></li></ul></li><li><p><strong><span>výběr</span></strong><span> - hledání, zobrazení (</span><em><span>např.: SQL databáze</span></em><span>)</span></p></li><li><p><strong><span>aktualizace</span></strong><span> - úprava existujícího záznamu, přidání, odstranění</span></p><ul><li><p><strong><span>interaktivní</span></strong><span> - změny se provádí přímo do souboru (při velkém</span></p><p><span>množství příliš pomalé)</span></p></li><li><p><strong><span>dávková</span></strong><span> - rozdělení na kmenový soubor a soubor změn, je</span></p><p><span>potřeba aktualizační program, který se za určitý čas spustí a aplikuje změny do původního souboru (plynulejší, možnost stornovat)</span></p></li></ul></li><li><p><strong><span>konverze</span></strong><span> - převody mezi formáty dat</span></p><ol start='' ><li><strong><span>formuláře</span></strong><span> - interaktivní rozhraní pro vkládání dat uživatelem</span></li><li><strong><span>sestavy</span></strong><span> - přehledně formátované výsledky dotazů (</span><em><span>např.: stránka reprezentující nákupní košík</span></em><span>)</span></li></ol></li></ol></li></ul><h2 id='organizace-souborů-z-pro-hromadné-zpracování-dat-tj-obrovské-soubory-přístup-k-souborům'><span>Organizace souborů z pro hromadné zpracování dat (tj. obrovské soubory), přístup k souborům</span></h2><ul><li><p><strong><span>organizace souborů</span></strong></p><ul><li><p><strong><span>vkládání záznamů do seřazené souboru</span></strong></p><ul><li><p><span>řešení: </span><strong><span>oblast přeplnění</span></strong><span> + </span><strong><span>dávkové zpracování</span></strong></p></li><li><p><strong><span>oblast přeplnění</span></strong></p><ul><li><span>neseřazená část na konci souboru, kam se vkládají nové soubory </span></li><li><span>do seřazené se zařadí jednou za čas aktualizačním</span></li></ul></li><li><p><span>vyhledávání probíha ve dvou krocích: </span></p><ol start='' ><li><strong><span>rychlé vyhledávání v seřazené části</span></strong></li><li><strong><span>sekvenční vyhledávání s oblasti přeplnění</span></strong></li></ol><p><img src="assets/image-20220312203142770.png" alt="image-20220312203142770" style="zoom:50%;" /><span> </span></p></li></ul></li><li><p><strong><span>odstranění </span></strong></p><ul><li><p><span>řešení: </span><strong><span>změna příznaku v záznamu</span></strong></p></li><li><p><strong><span>logická položka</span></strong><span> - </span><strong><span>příznak aktivního/smazaného prvku</span></strong></p></li><li><p><span>ostatní operace ignorují záznamy s příznakem smazaného prvku</span></p></li><li><p><span>fyzické odstranění provede až aktualizační program</span></p><p><img src="assets/image-20220312203154079.png" alt="image-20220312203154079" style="zoom:50%;" /><span> </span></p></li></ul></li></ul></li><li><p><strong><span>přístup k souborům</span></strong></p><ul><li><p><strong><span>sekvenční soubory</span></strong></p><ul><li><span>neseřazené - jednoduchá implementace, pomalé</span></li><li><span>seřazené - možnost použít rychlejší algoritmy</span></li></ul></li><li><p><strong><span>soubory s přímým přístupem</span></strong></p><ul><li><span>jako u polí - dostat se k libovolnému prvku trvá stejně dlouho</span></li><li><span>fyzicky jen na specifickém hardware</span></li></ul></li><li><p><strong><span>index-sekvenční přístup</span></strong></p><ul><li><span>data rozdělena na </span><strong><span>bloky</span></strong></li><li><span>blok lze vyhledat rychle, </span><strong><span>přímým přístupem</span></strong></li><li><span>v rámci bloku se vyhledává </span><strong><span>sekvenčně</span></strong></li><li><span>princip kartotéky - šuplíky podle abecedy</span></li><li><strong><span>hašovací tabulka s kolizemi</span></strong><span> - kolize tvoří bloky, které je třeba prohledávat sekvenčně</span></li></ul></li><li><p><strong><span>indexový soubor</span></strong></p><ul><li><p><span>kmenový soubor - nemusí být řazený</span></p></li><li><p><strong><span>indexový soubor</span></strong></p><ul><li><span>pomocný soubor s odkazy na záznamy v kmenovém souboru</span></li><li><span>je seřazený podle vybraného klíče (čteného z kmenového souboru)</span></li><li><span>může jich existovat víc pro jeden kmenový soubor</span></li></ul><p><img src="assets/image-20220312203208432.png" alt="image-20220312203208432" style="zoom:50%;" /><span> </span></p><ul><li><span>výhody: řeší problémy s vyhledáváním podle různých klíču</span></li><li><span>nevýhody: zabírá místo navíc</span></li></ul></li></ul></li></ul></li></ul><h2 id='součásti-databáze'><span>Součásti databáze</span></h2><ul><li><p><span>součásti</span></p><ul><li><p><strong><span>databáze</span></strong><span> (DB)</span></p><ul><li><p><span>množina logicky uspořádaných dat</span></p></li><li><p><strong><span>relační databáze</span></strong></p><ul><li><p><span>data uložena v </span><strong><span>tabulkách</span></strong></p></li><li><p><strong><span>řádek</span></strong><span> tabulky = </span><strong><span>záznam</span></strong><span> = popis jedné konkrétní </span><strong><span>entity</span></strong><span> reálného světa</span></p></li><li><p><strong><span>tabulka</span></strong><span> je složená z </span><strong><span>entit</span></strong><span>, které mají své </span><strong><span>atributy</span></strong></p></li><li><p><span>vztahy = </span><strong><span>relace</span></strong></p><ul><li><p><span>pomocí struktury tabulek a odkazy mezi záznamy</span></p></li><li><p><span>realizovány pomocí </span><strong><span>primárních</span></strong><span> a </span><strong><span>cizích klíčů</span></strong></p><ul><li><p><strong><span>primární klíč</span></strong><span> </span></p><ul><li><span>jednoznačně identifikuje záznam</span></li><li><span>musí být jedinečný a neprázdný</span></li><li><strong><span>jednoduchý</span></strong><span> (</span><em><span>jeden atribut</span></em><span>) ✖️ </span><strong><span>složený</span></strong><span> (</span><em><span>množina atributů</span></em><span>)</span></li></ul></li><li><p><strong><span>cizí klíč</span></strong></p><ul><li><span>odkaz na jiný záznam v téže nebo jiné tabulce</span></li><li><span>obsahuje hodnotu primárního klíče odkazovaného záznamu</span></li></ul></li></ul></li></ul></li></ul></li></ul></li><li><p><strong><span>systém řízení báze dat</span></strong><span> (SŘBD)</span></p><ul><li><p><span>část DBS pro manipulaci a přístup k datům</span></p></li><li><p><span>obsahuje interpret jazyka pro:</span></p><ul><li><span>definici databáze</span></li><li><span>manipulaci s daty</span></li></ul></li></ul></li></ul></li><li><p><span>pojmy:</span></p><ul><li><strong><span>entita</span></strong><span> = rozlišitelný, jednoznačně identifikovatelný objekt reálného světa, který chceme ukládat do DB (jeden záznam/řádek)</span></li><li><strong><span>entitní množina</span></strong><span> = množina entit téhož typu (</span><em><span>tabulka</span></em><span>)</span></li><li><strong><span>atribut</span></strong><span> = vlastnosti entity</span></li><li><strong><span>kardinalita</span></strong><span> = počet vztahů, ve kterých se může entita vyskytovat (</span><em><span>1:1, 1:N, M:N</span></em><span>)</span></li><li><strong><span>formuláře</span></strong><span> - interaktivní rozhraní pro vkládání dat uživatelem</span></li><li><strong><span>sestavy</span></strong><span> - přehledně formátované výsledky dotazů (</span><em><span>např.: stránka reprezentující nákupní košík</span></em><span>)</span></li></ul></li></ul><h1 id='eliminační-metody-pro-řešení-soustav-n-lineárních-rovnic-o-n-neznámých'><span>Eliminační metody pro řešení soustav n lineárních rovnic o n neznámých</span></h1><h2 id='pojmy-4'><span>pojmy</span></h2><ul><li><p><strong><span>numerická metoda</span></strong></p><ul><li><p><span>algoritmus popisující cestu k řešení numerické úlohy</span></p></li><li><p><span>používá se, když je analytické řešení složité, nebo náročné</span></p></li><li><p><span>řešení soustav lineárních rovnic:</span></p><ul><li><p><strong><span>eliminační metody</span></strong></p><ul><li><strong><span>analytický</span></strong><span> algoritmický postup</span></li><li><span>pracuje s </span><strong><span>absolutní</span></strong><span> přesnosti</span></li></ul></li><li><p><strong><span>iterační metody</span></strong></p><ul><li><strong><span>aproximační</span></strong><span> algoritmický postup</span></li><li><span>pracují se </span><strong><span>zvolenou</span></strong><span> přesností (</span><em><span>čím déle počítají, tím přesnější jsou</span></em><span>)</span></li></ul></li></ul></li><li><p><span>prostředky:</span></p><ul><li><strong><span>interpolace</span></strong><span> (nalezení přibližné hodnoty spojením známých bodů)</span></li><li><strong><span>derivace</span></strong></li><li><strong><span>aproximace</span></strong><span> (odhad, často funkce)</span></li><li><strong><span>integrace</span></strong></li></ul></li></ul></li><li><p><strong><span>přesnost</span></strong><span> - přesnost výpočtů bude tak přesná, jako je přesnost výpočtů na počítači (</span><em><span>vždy dojde k nějakému danému zaokrouhlení</span></em><span>)</span></p></li></ul><h2 id='vyjádření-soustavy-lineárních-rovnic-pomocí-matic'><span>vyjádření soustavy lineárních rovnic pomocí matic</span></h2><p><img src="assets/image-20220312203223744.png" alt="image-20220312203223744" style="zoom:50%;" /><span> </span></p><ul><li><strong><span>řádky</span></strong><span> matice představují jednotlivé rovnice</span></li><li><strong><span>sloupce</span></strong><span> jednotlivé koeficienty</span></li></ul><h2 id='gaussova-eliminační-metoda'><span>Gaussova eliminační metoda</span></h2><ul><li><p><span>používá ekvivalentní úpravy nad </span><strong><span>rozšířenou maticí soustavy</span></strong></p></li><li><p><span>eliminuje neznámé pod hlavní diagonálou - </span><strong><span>horní trojúhelníková matice soustavy</span></strong></p></li><li><p><span>algoritmus:</span></p><ol start='' ><li><strong><span>přímý chod</span></strong><span> - převod rozšířené matice do tvaru horní trojúhelníkové matice za pomocí ekvivalentních řádkových úprav</span></li><li><strong><span>test řešitelnosti</span></strong><span> - má-li soustava 0 nebo ∞ řešení, skonči</span></li><li><strong><span>zpětný chod</span></strong></li></ol></li><li><p><strong><span>pivotování</span></strong><span> - popřehazování řádků tak, aby v každém sloupci byla v absolutní hodnotě největší hodnotou na hlavní diagonále (</span><em><span>ve sloupci hledám na hlavní diagonále a pod ní</span></em><span>)</span></p></li><li><p><span>výhody </span></p><ul><li><span>paralelizace</span></li><li><span>lze aplikovat na rozsáhlé matice</span></li><li><span>konvergence je u diagonálně dominantních funkcí zaručena nevýhody</span></li><li><span>pomalejší</span></li></ul></li></ul><h2 id='gauss-jordanova-eliminační-metoda'><span>Gauss-Jordanova eliminační metoda</span></h2><ul><li><span>upravena GEM, nuluje se </span><strong><span>pod i nad</span></strong><span> hlavní diagonálou</span></li><li><span>vytváří jednotkovou matici soustavy, tudíž odpadá zpětný chod</span></li><li><span>nelze paralelizovat</span></li></ul><h1 id='iterační-metody-pro-řešení-soustav-n-lineárních-rovnic-o-n-neznámých'><span>Iterační metody pro řešení soustav n lineárních rovnic o n neznámých</span></h1><h2 id='pojmy-5'><span>pojmy</span></h2><ul><li><p><strong><span>numerická metoda</span></strong></p><ul><li><span>algoritmus popisující cestu k řešení numerické úlohy</span></li><li><span>používá se, když je analytické řešení složité, nebo náročné</span></li></ul></li><li><p><strong><span>přesnost</span></strong></p><ul><li><span>přesnost výpočtů bude tak přesná, jako je přesnost výpočtů na počítači (</span><em><span>vždy dojde k nějakému danému zaokrouhlení</span></em><span>)</span></li><li><span>u iteračních metod se přesnost výsledků zvyšuje s časem/počtem opakování</span></li></ul></li><li><p><strong><span>konvergence</span></strong></p><ul><li><span>prvky řady se musí blížit k cílové hodnotě</span></li><li><img src="/Users/tomashobza/Library/Application Support/typora-user-images/image-20220309231810240.png" alt="image-20220309231810240" style="zoom:25%;" /><span> se od určitého bodu </span><strong><span>i</span></strong><span> musí limitně blížit nule</span></li><li><strong><span>matice je diagonálně dominantní</span></strong><span> = zaručená konvergence</span></li><li><em><span>opakem je divergence</span></em></li></ul></li><li><p><strong><span>stabilita</span></strong></p><ul><li><span>malé změny vstupních dat způsobí jen malé změny výstupních dat</span></li></ul></li></ul><h2 id='iterační-výpočet'><span>iterační výpočet</span></h2><ul><li><p><strong><span>rekurentní vztah</span></strong></p><p><span> </span><img src="assets/image-20220312203240277.png" alt="image-20220312203240277" style="zoom:50%;" /><span> </span></p><ul><li><span>pro výpočet další hodnoty potřebujeme </span><code>k+1</code><span> předchozích hodnot</span></li><li><span>člen posloupnosti je určen předchozími členy posloupnosti</span></li></ul></li><li><p><strong><span>algoritmické schéma výpočtu podle rekurentního vztahu</span></strong></p><p><span> </span><img src="assets/image-20220312203250072.png" alt="image-20220312203250072" style="zoom:50%;" /><span> </span></p><ol start='' ><li><span>Y = y</span><sub><span>0</span></sub></li><li><span>while (not B(Y)) Y = F(Y)</span></li></ol><ul><li><strong><span>Y</span></strong><span> - proměnná</span></li></ul><ul><li><strong><span>B</span></strong><span> - predikát (</span><em><span>podmínka požadované hodnoty závislá na přechozím výsledku </span><strong><span>Y</span></strong></em><span>)</span></li></ul><ul><li><strong><span>F</span></strong><span> - funkční symbol</span></li></ul></li></ul><h2 id='jacobiho-iterační-metoda'><strong><span>Jacobiho iterační metoda</span></strong></h2><p><span> </span><img src="assets/image-20220312203355692.png" alt="image-20220312203355692" style="zoom:50%;" /><span> </span></p><ul><li><span>začnu s polem neznámých </span><strong><span>x</span></strong><span>, které inicializuji na </span><strong><span>nulu</span></strong></li><li><span>neznámé </span><strong><span>x</span></strong><span> si v každé iteraci vypočítám a jejich nové hodnoty zapíšu do pole nových hodnot</span></li><li><span>na konci iterace si pole neznámých </span><strong><span>x</span></strong><span> přepíšu polem nových hodnot</span></li><li><span>opakuju, dokud rozdíl hodnot </span><strong><span>všech</span></strong><span> neznámých </span><strong><span>x</span></strong><span> mezi poli starých a nových hodnot není menší, jak daná přesnost (𝛆)</span></li></ul><h2 id='gauss-seidelova-iterační-metoda'><strong><span>Gauss-Seidelova iterační metoda</span></strong></h2><ul><li><p><span>skoro stejná Jacobiho metoda, ale nově vypočítané hodnoty zapisuji rovnou do pole starých hodnot</span></p></li><li><p><span>porovnávám přesnost před zapsáním nové hodnoty do pole (</span><em><span>předpoklad pozitivity v rámci jedné iterace; jestli najdu nepřesnost, tak je celá iterace nepřesná</span></em><span>)</span></p><p><img src="assets/image-20220312203407906.png" alt="image-20220312203407906" style="zoom:50%;" /><span> </span></p></li></ul><h1 id='řešení-nelineárních-rovnic'><span>Řešení nelineárních rovnic</span></h1><h2 id='pojmy-6'><span>pojmy</span></h2><ul><li><p><strong><span>přesnost</span></strong></p><ul><li><span>přesnost výpočtů bude tak přesná, jako je přesnost výpočtů na počítači (</span><em><span>vždy dojde k nějakému danému zaokrouhlení</span></em><span>)</span></li><li><span>u iteračních metod se přesnost výsledků zvyšuje s časem/počtem opakování</span></li></ul></li><li><p><strong><span>konvergence</span></strong></p><ul><li><span>prvky řady se musí blížit k cílové hodnotě</span></li><li><img src="/Users/tomashobza/Library/Application Support/typora-user-images/image-20220309231810240.png" alt="image-20220309231810240" style="zoom:25%;" /><span> se od určitého bodu </span><strong><span>i</span></strong><span> musí limitně blížit nule</span></li><li><em><span>opakem je divergence</span></em></li></ul></li></ul><h2 id='vyčíslení-polynomu-hornerovým-schématem'><span>vyčíslení polynomu Hornerovým schématem</span></h2><p><span> </span><img src="assets/image-20220312203427120.png" alt="image-20220312203427120" style="zoom:50%;" /><span> </span></p><ul><li><p><span>operace: násobení, sčítání</span></p></li><li><p><span>časová složitost: </span><strong><span>O(n)</span></strong></p></li><li><p><span>používá se na vyčíslení polynomů</span></p><p><img src="assets/image-20220312203439344.png" alt="image-20220312203439344" style="zoom:50%;" /><span> </span></p></li></ul><h2 id='definice-úlohy-řešení-nelineárních-rovnic'><span>definice úlohy řešení nelineárních rovnic</span></h2><ul><li><span>hledáme řešení rovnice </span><code>P(x) = 0</code><span>, kde </span><strong><span>P</span></strong><span> je polynom </span></li><li><span>pro funkci </span><code>f(x)</code><span> hledáme hodnotu </span><strong><span>a</span></strong><span> takovou, že </span><code>f(a) = 0</code></li></ul><h2 id='metody'><span>metody</span></h2><ol start='' ><li><p><strong><span>metoda půlení intervalů</span></strong></p><p><img src="assets/image-20220312203452876.png" alt="image-20220312203452876" style="zoom:50%;" /><span> </span></p><ul><li><p><span>v každém kroku se chyba aproximace sníží dvakrát</span></p></li><li><p><span>výhody:</span></p><ul><li><span>obecná, robustní metoda</span></li><li><span>při splnění podmínek zaručeně konverguje (</span><em><span>v případě více kořenů v intervalu najde jeden z nich</span></em><span>)</span></li></ul></li><li><p><span>nevýhody:</span></p><ul><li><span>relativně pomalá</span></li><li><span>hrozí ztráta přesnosti kvůli zaokrouhlovacím chybám</span></li></ul></li></ul></li><li><p><strong><span>metoda tětiv</span></strong><span> (regula falsi)</span></p><p><img src="assets/image-20220312203505070.png" alt="image-20220312203505070" style="zoom:50%;" /><span> </span></p><ul><li><p><span>výhody:</span></p><ul><li><span>vždy konverguje</span></li><li><span>obvykle rychlejší než půlení intervalů</span></li></ul></li><li><p><span>nevýhody:</span></p><ul><li><span>stejné, jako u půlení intervalů, jen menší</span></li></ul></li></ul></li><li><p><strong><span>metoda sečen</span></strong></p><p><span> </span><img src="assets/image-20220312203525077.png" alt="image-20220312203525077" style="zoom:50%;" /><span> </span></p></li><li><p><strong><span>newtonova metoda</span></strong></p><p><span> </span><img src="assets/image-20220312203534497.png" alt="image-20220312203534497" style="zoom:50%;" /><span> </span></p></li></ol><h1 id='metoda-nejmenších-čtverců'><span>Metoda nejmenších čtverců</span></h1><h2 id='pojmy-7'><span>pojmy</span></h2><ul><li><p><strong><span>aproximace</span></strong></p><ul><li><span>funkce, která se nejvíce blíží naměřeným hodnotám</span></li></ul></li><li><p><strong><span>interpolace</span></strong></p><ul><li><span>funkce, která prochází všemi naměřenými body</span></li></ul></li></ul><h2 id='princip'><span>princip</span></h2><ul><li><p><span>součet vzdáleností od bodů je lineární funkce a nemá minimum, proto součet čtverců kvadratická funkce a navíc snadno derivovatelná</span></p></li><li><p><span>postup:</span></p><ol start='' ><li><span>dosazení bodů, suma</span></li><li><span>parciální derivace podle </span><strong><span>a</span></strong><span> a </span><strong><span>b</span></strong></li><li><span>minimum má tečnu rovnoběžnou s osou x (</span><em><span>směrnice = 0 👉 derivace = 0</span></em><span>)</span></li><li><span>řešení dvou rovnic o dvou neznámých</span></li></ol></li></ul><h2 id='odvození-pro-konstantní-a-lineární-funkci'><span>odvození pro konstantní a lineární funkci</span></h2><p><img src="assets/image-20220312203554389.png" alt="image-20220312203554389" style="zoom:50%;" /><span> </span></p><ul><li><p><span>liší se tím, co dosadím za </span><strong><span>f()</span></strong></p><ul><li><span>konstantní - </span><code>f: y = b</code></li><li><span>lineární - </span><code>f: y = a*x + b</code></li></ul></li></ul><h1 id='metody-vnitřního-řazení'><span>Metody vnitřního řazení</span></h1><h2 id='vlastnosti-řadících-algoritmů'><span>vlastnosti řadících algoritmů</span></h2><ul><li><p><strong><span>časová složitost</span></strong><span> - </span><code>T(n)</code></p><ul><li><p><span>funkce závislá na rozměru řešené úlohy</span></p></li><li><p><strong><span>n</span></strong><span> - rozměr úlohy (</span><em><span>např.: počet prvků řazeného pole</span></em><span>)</span></p></li><li><p><span>výsledkem je počet elementárních kroků algoritmu</span></p></li><li><p><strong><span>odhad časové složitosti</span></strong><span> - </span><code>O(T(n))</code></p><ul><li><span>založený na nejrychleji rostoucí části vzorce</span></li></ul></li></ul></li><li><p><strong><span>prostorová složitost</span></strong></p><ul><li><span>funkce závislá na rozměru řešené úlohy</span></li><li><span>udává počet paměťových buněk potřebných pro výpočet</span></li><li><strong><span>in situ</span></strong><span> - “na místě,” nevyžaduje prostor pro kopii všech vstupních dat</span></li></ul></li><li><p><strong><span>přirozenost</span></strong></p><blockquote><p><span>Řadící algoritmus je přirozený, pokud platí, že čas pro řazení</span>
<strong><span>seřazených</span></strong><span> dat je </span><strong><span>menší</span></strong><span> než čas pro řazení </span><strong><span>náhodně</span></strong>
<span>uspořádaných dat a ten je </span><strong><span>menší</span></strong><span> než čas pro řazení </span><strong><span>opačně</span></strong>
<span>seřazených dat.</span></p></blockquote></li><li><p><strong><span>stabilita</span></strong></p><blockquote><p><span>Řadící algoritmus je sekvenční, pokud k prvkům přistupuje</span>
<span>sekvenčně, tj. navštěvuje vždy </span><strong><span>jen vedlejší prvky</span></strong>
<span>(následující nebo předchozí) a </span><strong><span>neskáče</span></strong><span> doprostřed</span>
<span>řazeného pole.</span></p></blockquote></li></ul><h2 id='algoritmy'><span>algoritmy</span></h2><ul><li><p><strong><span>Insertion sort</span></strong></p><p><img src="assets/image-20220312203619182.png" alt="image-20220312203619182" style="zoom:50%;" /><span> </span></p><ul><li><p><strong><span>se zarážkou</span></strong></p><ul><li><p><span>optimalizace procesu vkládání</span></p></li><li><p><span>vyrobím pole o jeden prvek delší a na pozici nula vložím vkládaný prvek </span><em><span>(data tudíž začínají na indexu 1)</span></em></p><p><img src="assets/image-20220312203629089.png" alt="image-20220312203629089" style="zoom:50%;" /><span> </span></p></li></ul></li><li><p><strong><span>O(n</span><sup><span>2</span></sup><span>)</span></strong><span>, </span><strong><span>je přirozený</span></strong><span>, </span><strong><span>je sekvenční</span></strong><span>, </span><strong><span>je stabilní</span></strong><span>, prostorová složitost - </span><strong><span>lineární, in situ</span></strong></p></li></ul></li><li><p><strong><span>Selection sort</span></strong></p><p><img src="assets/image-20220312203640063.png" alt="image-20220312203640063" style="zoom:50%;" /><span> </span></p><ul><li><strong><span>O(n</span><sup><span>2</span></sup><span>)</span></strong><span>, </span><strong><span>není přirozený</span></strong><span>, </span><strong><span>je sekvenční</span></strong><span>, </span><strong><span>není stabilní</span></strong><span>, prostorová složitost - </span><strong><span>lineární, in situ</span></strong></li></ul></li><li><p><strong><span>Bubble sort</span></strong></p><p><img src="assets/image-20220312203649955.png" alt="image-20220312203649955" style="zoom:50%;" /><span> </span></p><ul><li><p><strong><span>s pamětí poslední výměny</span></strong><span> - Ripple sort</span></p><ul><li><span>dělící čáru posune na index poslední výměny</span></li><li><span>na seřazeném poli stačí jeden průchod</span></li></ul></li><li><p><strong><span>Shaker sort</span></strong></p><ul><li><span>dva vnitřní cykly - jeden posouvá minimum doleva, druhý posouvá maximum doprava</span></li></ul></li><li><p><strong><span>O(n</span><sup><span>2</span></sup><span>)</span></strong><span>, </span><strong><span>základní verze není přirozená</span></strong><span>, </span><strong><span>je sekvenční</span></strong><span>, </span><strong><span>je stabilní</span></strong><span>, prostorová složitost - </span><strong><span>lineární, in situ</span></strong></p></li></ul></li></ul><h2 id='princip-ostatních-metod'><span>princip ostatních metod</span></h2><ul><li><p><strong><span>Merge sort</span></strong></p><p><img src="assets/image-20220312203701233.png" alt="image-20220312203701233" style="zoom:50%;" /><span> </span></p><ul><li><strong><span>O(n*log n)</span></strong><span> - průměrná i nejhorší, </span><strong><span>není přirozený</span></strong><span>, </span><strong><span>je sekvenční</span></strong><span>, </span><strong><span>je stabilní</span></strong><span>, prostorová složitost - </span><strong><span>O</span><sub><span>S</span></sub><span>(n), není in situ</span></strong></li></ul><p> </p></li><li><p><strong><span>Quick sort</span></strong></p><p><span> </span><img src="assets/image-20220312203716351.png" alt="image-20220312203716351" style="zoom:50%;" /><span> </span></p><ul><li><p><strong><span>pivot</span></strong></p><ul><li><span>ideálně medián, ale ten je obtížné najít</span></li><li><span>jeho výběr dramaticky mění časovou složitost algoritmu</span></li></ul></li><li><p><strong><span>dělení DNF</span></strong><span> - Dutch National Flag</span></p><ul><li><p><span>pole rozděleno na </span><strong><span>tři části</span></strong></p><ol start='' ><li><span>prvky </span><strong><span>menší</span></strong><span>, jak pivot</span></li><li><span>prvky </span><strong><span>stejně velké</span></strong><span>, jak pivot</span></li><li><span>prvky </span><strong><span>větší</span></strong><span>, jak pivot</span></li></ol></li></ul></li><li><p><strong><span>O(n*log n)</span></strong><span> - pro průměrný případ, </span><strong><span>přirozenost závisí na dělení a výběru pivota</span></strong><span>, </span><strong><span>jde udělat sekvenční</span></strong><span> (</span><em><span>ale zde není)</span></em><span>, </span><strong><span>není stabilní</span></strong><span>, prostorová složitost - </span><strong><span>O</span><sub><span>S</span></sub><span>(log n)</span></strong></p></li></ul></li></ul><h1 id='metody-vnitřní-řazení'><span>Metody vnitřní řazení</span></h1><h2 id='specifika-vnějšího-řazení'><span>specifika vnějšího řazení</span></h2><ul><li><p><span>data ve vnější paměti</span></p></li><li><p><span>sekvenční zpracování</span></p></li><li><p><span>pro data, která se nevejdou do paměti, tudíž nejde použít vnitřní řazení</span></p></li><li><p><span>pomalejší, než vnitřní řazení</span></p></li><li><p><strong><span>princip</span></strong><span>: přesouvání řazených prvků mezi sekvenčními soubory na disku</span></p></li><li><p><strong><span>Xpáskové</span></strong><span> </span></p><ul><li><span>pracují s určitým počtem souborů/pásek</span></li><li><span>vyžadují pomocné soubory/pásky</span></li></ul></li><li><p><strong><span>Yfázové</span></strong></p><ul><li><span>řazení rozděleno do několika fází</span></li></ul></li></ul><h2 id='pojmy-8'><span>pojmy</span></h2><ul><li><strong><span>fáze</span></strong><span> - operace, při které se manipuluje s celou množinou dat (</span><em><span>např.: rozdělovací fáze</span></em><span>)</span></li><li><strong><span>krok algoritmu</span></strong><span> - nejmenší podproces, jehož opakování se realizuje řazení</span></li></ul><h2 id='přímé-a-přirozené-řazení'><span>přímé a přirozené řazení</span></h2><ul><li><p><strong><span>přímé slučování</span></strong></p><ul><li><p><strong><span>3pásková</span></strong><span>, </span><strong><span>2fázová</span></strong><span> metoda</span></p></li><li><p><span>1 vstupní páska a 2 pomocné pásky</span></p></li><li><p><span>krok je rozdělen do </span><strong><span>2</span></strong><span> fází</span></p><ol start='' ><li><p><strong><span>rozdělovací fáze</span></strong></p><ul><li><span>rozděluju vždy na 2x větší části, jak v předchozím kroku</span></li></ul></li><li><p><strong><span>slučovací fáze</span></strong></p><ul><li><span>jedu po pomocných páskách a vždy na hlavní pásku zapíšu menší číslo, na té pásce se posunu dál a znovu porovnávám</span></li></ul></li></ol><p><img src="/Users/tomashobza/Library/Application Support/typora-user-images/image-20220310174425286.png" alt="image-20220310174425286" style="zoom:25%;" /><span> </span></p></li></ul></li><li><p><strong><span>přirozené slučování</span></strong></p><ul><li><span>jako přímé, jen místo úseků pracuje s </span><strong><span>běhy</span></strong></li><li><strong><span>běh</span></strong><span> = nejdelší seřazený úsek</span></li></ul></li></ul><h2 id='metody-zlepšování'><span>metody zlepšování</span></h2><ul><li><p><strong><span>vyvážené slučování</span></strong></p><ul><li><strong><span>4pásková</span></strong><span>, </span><strong><span>2fázová</span></strong><span> metoda</span></li><li><span>přidáním jedné pásky (částečně) eliminuje rozdělovací fázi</span></li></ul></li><li><p><strong><span>vícepáskové slučování</span></strong><span> (vícecestné vyvážené slučování)</span></p><ul><li><p><strong><span>n</span></strong><span> pásek, kde </span><strong><span>n</span></strong><span> je sudé číslo</span></p></li><li><p><strong><span>n/2cestné</span></strong><span>, </span><strong><span>jednofázové slučování</span></strong></p><ul><li><span>v každém kroku n/2 vstupních a n/2 výstupních pásek</span></li></ul></li></ul></li></ul><h2 id='princip-polyfázového-slučování'><span>princip polyfázového slučování</span></h2><ol start='' ><li><span>rozděl běhy do </span><strong><span>n-1</span></strong><span> pásek tak, aby počtem odpovídaly Fibonacciho posloupnosti</span></li><li><span>dokud není nejkratší páska prázdná, slučuj běhy na výstupní pásku</span></li><li><span>přepni pásky - výstupní se přepne na vstupní a prázdná na výstupní</span></li><li><span>opakuj, dokud nejsou vstupní pásky prázdné</span></li></ol><h1 id='vyhledávací-algoritmy'><span>Vyhledávací algoritmy</span></h1><h2 id='pojmy-9'><span>pojmy</span></h2><ul><li><p><strong><span>klíč</span></strong></p><ul><li><span>údaj podle kterého hledáme</span></li><li><strong><span>jednoduchý</span></strong><span> - jedna ze složek struktury</span></li><li><strong><span>složený</span></strong><span> - více složek struktury</span></li></ul></li></ul><h2 id='sekvenční-vyhledávání'><span>sekvenční vyhledávání</span></h2><ul><li><p><strong><span>v neseřazeném poli</span></strong></p><ul><li><p><span>sekvenční procházení prvků datové struktury dokud nenaleznu shodu nebo nedojdu na konec</span></p><ul><li><span>pomalé, ale některé údaje nejde seřadit</span></li></ul></li></ul></li><li><p><strong><span>v seřazeném poli</span></strong></p><ul><li><span>stejné jako v neseřazeném poli, ale skončím i když najdu větší klíč (</span><em><span>protože za ním už je zpravidla nemůže vyskytnout hledaný klíč</span></em><span>)</span></li></ul></li><li><p><strong><span>s zarážkou</span></strong></p><ul><li><span>ne konec pole dám zarážku, kterou nastavím na můj hledaný klíč</span></li><li><span>nemusím sledovat, jestli jsem na konci pole - když najdu, co jsem hledal, zjistím, jestli jsem našel zarážku nebo ne</span></li></ul></li></ul><h2 id='binární-vyhledávání'><span>binární vyhledávání</span></h2><ul><li><p><span>vyžaduje seřazené pole</span></p></li><li><p><span>intuitivní princip “hledání ve slovníku”</span></p></li><li><p><span>princip:</span></p><ol start='' ><li><p><span>hledám v daném intervalu</span></p></li><li><p><span>podívám se na prostřední prvek v intervalu</span></p><ul><li><span>pokud je shodný s hledaným klíčem, našel jsem hledaný prvek a algoritmus končí</span></li></ul></li><li><p><span>rekurzivně se zanořím do jedné z polovin v závislosti na porovnávání hledaného klíče se středovým prvkem intervalu</span></p></li><li><p><span>má-li interval délku jedna není v něm hledaný klíč, pole hledaný klíč neobsahuje</span></p></li></ol></li><li><p><span>nejrychlejší algoritmus nad seřazeným polem, O(log</span><sub><span>2</span></sub><span> n)</span></p></li><li><p><span>nefunguje v neseřazeném poli</span></p></li></ul><h2 id='hašovací-tabulka'><span>hašovací tabulka</span></h2><ul><li><p><span>klíče jsou pomocí </span><strong><span>hašovací funkce</span></strong><span> přepočítány na indexy v poli)</span></p></li><li><p><strong><span>hašovací funkce</span></strong></p><ul><li><span>matematická funkce: </span><code>hash(obrovské číslo) -> malé čislo</code></li><li><span>nemá inverzní funkci (</span><em><span>použití v kryptografii</span></em><span>)</span></li></ul></li><li><p><span>v ideálním případě je </span><strong><span>jednoznačná</span></strong><span> - neexistuje stejný hash pro různé klíče</span></p></li><li><p><span>je obtížné mít spolehlivou hašovací funkci a je v praxi nedosažitelné nemít kolize</span></p></li></ul><h2 id='princip-index-sekvenčního-vyhledávání'><span>princip index-sekvenčního vyhledávání</span></h2><ul><li><span>kvůli kolizím používáme hašovací tabulku pro identifikaci bloků a ty procházíme sekvenčně</span></li></ul><h2 id='binární-vyhledávací-strom'><span>binární vyhledávací strom</span></h2><p><img src="assets/image-20220312203732978.png" alt="image-20220312203732978" style="zoom:50%;" /><span> </span></p><ul><li><p><span>pro rychlé ukládání a vyhledávání podle klíče</span></p></li><li><p><strong><span>strukturovaná data</span></strong><span> = párové hodnoty: </span><strong><span>klíč</span></strong><span> + </span><strong><span>hodnota</span></strong></p><ul><li><strong><span>uzel stromu</span></strong><span> - obsahuje ukazatel na </span><strong><span>levý</span></strong><span> a </span><strong><span>pravý</span></strong><span> podstrom, nese hodnotu klíče a data asociovaná s klíčem</span></li></ul></li><li><p><strong><span>binární strom</span></strong><span> - ukazatel na </span><strong><span>kořenový uzel</span></strong></p></li><li><p><span>vlastnosti:</span></p><ul><li><strong><span>výška</span></strong><span> stromu - délka nejdelší cestu od kořene</span></li><li><strong><span>váha</span></strong><span> stromu - počet uzlů stromu</span></li><li><strong><span>vyvážený</span></strong><span> strom - po všechny uzly platí, že váha jejich podstromů se liší maximálně o jedničku</span></li></ul></li><li><p><span>operace:</span></p><ul><li><p><span>průchody stromem</span></p><ul><li><strong><span>inorder</span></strong><span> - </span><code>inorder(levý); akceSAktuálnímUzlem(); inorder(pravý);</code></li><li><strong><span>preorder</span></strong><span> - </span><code>akceSAktuálnímUzlem(); preorder(levý); preorder(pravý);</code></li><li><strong><span>postorder</span></strong><span> - </span><code>postorder(levý); postorder(pravý); akceSAktuálnímUzlem();</code></li></ul></li><li><p><strong><span>přidání</span></strong></p></li><li><p><strong><span>odebrání</span></strong></p></li><li><p><strong><span>vyhledání uzlu</span></strong></p></li></ul></li></ul><h2 id='srovnání-vyhledávacích-metod'><span>srovnání vyhledávacích metod</span></h2><ul><li><p><strong><span>sekvenční vyhledávání</span></strong></p><ul><li><p><span>výhody:</span></p><ul><li><span>nejobecnější algoritmus</span></li><li><span>v některých případech jiný přístup není možný (</span><em><span>nelze seřadit pole</span></em><span>)</span></li></ul></li><li><p><span>nevýhody:</span></p><ul><li><span>lineární časová složitost (</span><strong><span>O(n)</span></strong><span>)</span></li><li><span>hledání “hrubou silou,” neefektivní</span></li></ul></li><li><p><strong><span>se zarážkou</span></strong></p><ul><li><p><span>výhody:</span></p><ul><li><span>nemusí testovat konec pole -> rychlejší, ale ne o moc</span></li></ul></li><li><p><span>nevýhody:</span></p><ul><li><span>je třeba udělat pole větší o jeden prvek</span></li></ul></li></ul></li><li><p><strong><span>v seřazeném poli</span></strong><span> - rychlejší, ale je třeba pole napřed seřadit (</span><em><span>pomalejší přidávání prvků</span></em><span>)</span></p></li></ul></li><li><p><strong><span>binární vyhledávací strom</span></strong></p><ul><li><p><span>výhody:</span></p><ul><li><span>efektivní a rychlá metoda</span></li></ul></li><li><p><span>nevýhody:</span></p><ul><li><span>na neseřazeném poli nefunguje</span></li></ul></li></ul></li><li><p><strong><span>hašovací tabulka</span></strong></p><ul><li><p><span>výhody:</span></p><ul><li><span>rychlé a efektivní i co se týče úprav v poli</span></li></ul></li><li><p><span>nevýhody:</span></p><ul><li><span>kolize a nereálnost dokonalé hašovací funkce</span></li></ul></li></ul></li></ul><h1 id='objektově-orientované-programování'><span>Objektově orientované programování</span></h1><h2 id='pojmy-10'><span>pojmy</span></h2><ul><li><p><strong><span>třída</span></strong></p><ul><li><span>popisuje stejný typ objektu</span></li><li><span>modeluje vztah </span><code>předek - potomek</code></li></ul></li><li><p><strong><span>objekt</span></strong></p><ul><li><span>konkrétní entita</span></li><li><span>proměnná</span></li></ul></li><li><p><strong><span>atribut</span></strong></p><ul><li><span>vlastnost objektu</span></li><li><span>proměnná uvnitř objektu</span></li></ul></li><li><p><strong><span>metoda</span></strong></p><ul><li><span>činnost/služba objektu</span></li><li><span>podprogram popsaný v třídě</span></li></ul></li></ul><h2 id='zapouzdření-dědičnost-polymorfismus'><span>zapouzdření, dědičnost, polymorfismus</span></h2><ul><li><p><strong><span>zapouzdření</span></strong></p><ul><li><span>ukrývá informace uvnitř objektu</span></li><li><span>z vnějšku objektu se k informacím dá dostat jen přes jeho rozhraní</span></li></ul></li><li><p><strong><span>dědičnost</span></strong></p><ul><li><span>umožňuje snadné rozšiřování funkcionality tříd/objektů</span></li></ul></li><li><p><strong><span>polymorfismus</span></strong></p><ul><li><span>umožňuje stejné zacházení s předky i potomky, i když se potomci chovají jinak</span></li></ul></li></ul><h2 id='praktické-použití-oop'><span>praktické použití OOP</span></h2><ul><li><span>původně simulace a umělá inteligence</span></li><li><span>kód je přidružen k datům</span></li><li><span>vyšší bezpečnost programů</span></li><li><span>přirozená modularita</span></li><li><span>snaží se popisovat chování reálného světa pomocí termínů používaných v reálném světě</span></li></ul><h1 id='operační-systémy'><span>Operační systémy</span></h1><h2 id='struktura-os-vrstvy'><span>struktura OS (vrstvy)</span></h2><ol start='' ><li><p><strong><span>jádro</span></strong><span> (kernel)</span></p><ul><li><span>moduly pro přidělování prostředků, řízení procesů, …</span></li></ul></li><li><p><strong><span>systémové knihovny a programy</span></strong></p></li><li><p><strong><span>uživatelské rozhraní</span></strong></p><ul><li><span>CLI - textové rozhraní</span></li><li><span>GUI - grafické rozhraní</span></li></ul></li></ol><p><span> </span><img src="assets/image-20220312203749836.png" alt="image-20220312203749836" style="zoom:50%;" /><span> </span></p><h2 id='modulární-os'><span>modulární OS</span></h2><ul><li><p><span>moduly zefektivňují vývoj operačního systému</span></p></li><li><p><strong><span>monolitické jádro</span></strong></p><ul><li><span>jádro je kompaktní program</span></li><li><span>moduly na úrovni zdrojového kódu</span></li><li><span>po </span><strong><span>sestavení</span></strong><span> vzniká kompaktní binární program - </span><strong><span>jádro</span></strong></li></ul></li><li><p><strong><span>mikrojádro</span></strong></p><ul><li><span>malé základní jádro běžící v chráněném režimu</span></li><li><strong><span>moduly</span></strong><span> - servery, které obsluhují nekritické služby systému</span></li><li><em><span>např.: Hurd</span></em></li></ul></li><li><p><span>základní moduly:</span></p><ul><li><p><strong><span>modul přidělování paměti</span></strong></p><ul><li><strong><span>udržuje údaje o stavu paměti</span></strong></li><li><strong><span>přiděluje paměť</span></strong><span> procesům, co si o ni požádají (</span><em><span>např.: malloc()</span></em><span>)</span></li><li><strong><span>uvolňuje paměť</span></strong><span> procesům, co se ji vzdají (</span><em><span>např.: free()</span></em><span>)</span></li></ul></li><li><p><strong><span>modul přidělování procesoru</span></strong></p><ul><li><p><span>vyžaduje privilegovaný režim procesoru</span></p></li><li><p><strong><span>plánovač úloh</span></strong></p><ul><li><span>rozhoduje o přepínání procesů</span></li><li><span>rozhoduje o časových úsecích přiřazených procesu</span></li><li><span>bere v úvahu priority procesů</span></li></ul></li></ul></li><li><p><strong><span>modul správy periferií</span></strong></p><ul><li><span>sleduje stav periferie - </span><strong><span>dispečer</span></strong></li><li><strong><span>spooler</span></strong><span> - realizuje frontu požadavků (</span><em><span>např.: úloh pro tiskárnu</span></em><span>)</span></li></ul></li><li><p><strong><span>modul správy souborů</span></strong></p><ul><li><p><strong><span>sleduje</span></strong><span> stav souborů</span></p></li><li><p><strong><span>rozhoduje</span></strong></p><ul><li><span>o přístupů procesů k souborům na základě jejich práv</span></li></ul></li><li><p><strong><span>přiděluje</span></strong><span> soubor pro použití (</span><em><span>otevření souboru</span></em><span>)</span></p></li><li><p><strong><span>vyžaduje</span></strong><span> vrácení souboru (</span><em><span>zavření</span></em><span>)</span></p></li></ul></li></ul></li></ul><h2 id='multitasking'><span>multitasking</span></h2><ul><li><p><span>metoda přepínání procesů tak, aby se zdálo, že běží současně</span></p><ul><li><span>výměna vykonávaných procesů - </span><strong><span>přepnutí kontextu</span></strong></li></ul></li><li><p><strong><span>kooperativní</span></strong></p><ul><li><span>procesy se samy na chvíli vzdají procesoru</span></li><li><span>nebezpečné kvůli “chamtivým” procesům</span></li></ul></li><li><p><strong><span>preemptivní</span></strong></p><ul><li><span>jádro vynucuje přerušení procesů</span></li><li><span>musí mít podporu v HW (</span><em><span>procesoru</span></em><span>)</span></li><li><span>složitější, ale bezpečnější</span></li></ul></li></ul><h2 id='procesy-vlákna-životní-cyklus-procesu'><span>procesy, vlákna, životní cyklus procesu</span></h2><ul><li><p><strong><span>procesy</span></strong></p><ul><li><span>výpočet, který lze provádět paralelně s ostatními výpočty</span></li><li><span>spuštěny počítačový program</span></li><li><span>vytváří jej, je řízen a spravován operačním systémem</span></li><li><span>může se dělit na </span><strong><span>vlákna</span></strong></li></ul></li><li><p><strong><span>vlákna</span></strong></p><ul><li><span>odlehčené procesy</span></li><li><span>sdílejí paměť procesu</span></li><li><span>nutnost řešit synchronizaci</span></li></ul></li><li><p><strong><span>životní cyklus procesu</span></strong></p><p><img src="assets/image-20220312203808133.png" alt="image-20220312203808133" style="zoom:50%;" /><span> </span></p></li></ul><h1 id='počítačové-sítě---hardware'><span>Počítačové sítě - hardware</span></h1><h2 id='rozdělení-sítí'><span>rozdělení sítí</span></h2><ul><li><p><strong><span>spojové</span></strong></p><ul><li><span>uzly a aktivní prvky nejprve dohodnou pevnou cestu mezi dvěma počítači </span></li><li><span>typické pro telefonní sítě</span></li></ul></li><li><p><strong><span>nespojové</span></strong></p><ul><li><span>data rozdělena na pakety </span></li><li><span>o cestě paketu rozhodují jednotlivé uzly sami - </span><strong><span>přepojování paketů</span></strong></li><li><span>typické pro počítačové sítě (</span><em><span>LAN</span></em><span>)</span></li></ul></li></ul><h2 id='druhy-sítí'><span>druhy sítí</span></h2><ul><li><p><strong><span>podle rozsahu</span></strong></p><ul><li><p><strong><span>PAN</span></strong><span> - personal area network</span></p><ul><li><span>osobní, domácí síť</span></li><li><span>obvykle wi-fi + kabeláž</span></li></ul></li><li><p><strong><span>LAN</span></strong><span> - local area network</span></p><ul><li><span>lokální, homogenní sítě tvořené PC</span></li><li><span>obvykle kabeláž + wifi</span></li><li><em><span>např.: firma, škola</span></em><span> </span></li></ul></li><li><p><strong><span>MAN</span></strong><span> - metropolitan area network</span></p><ul><li><span>regionální/městská síť</span></li><li><span>propojuje menší sítě v regionu</span></li><li><span>obvykle kabeláž v kolektorech (drát, optika)</span></li></ul></li><li><p><strong><span>WAN</span></strong><span> - wide area network</span></p><ul><li><span>rozlehlé sítě - sítě sítí - národní, celosvětový rozsah</span></li><li><span>páteřní sítě</span></li><li><span>Internet, u nás CESNET</span></li></ul></li></ul></li><li><p><strong><span>podle řízení</span></strong></p><ul><li><p><strong><span>klient - server</span></strong></p><ul><li><p><span>hierarchické sítě s vyhrazenými servery</span></p><ul><li><span>centralizované uložení dat - zamezuje redundanci dat</span></li></ul></li></ul></li><li><p><strong><span>peer to peer</span></strong></p><ul><li><span>žádná hierarchie, všechny počítače jsou si rovny</span></li><li><span>především pro sdílení dat</span></li><li><span>decentralizované</span></li></ul></li></ul></li></ul><h2 id='topologie'><span>topologie</span></h2><ul><li><p><span>charakterizuje způsob propojení jednotlivých uzlů sítě</span></p><ul><li><strong><span>skutečná</span></strong><span> - fyzická podoba</span></li><li><strong><span>logická</span></strong><span> - virtuální podoba</span></li></ul></li><li><p><strong><span>kruh</span></strong><span> (ring)</span></p><p><img src="assets/image-20220312203822766.png" alt="image-20220312203822766" style="zoom:50%;" /><span> </span></p><ul><li><p><span>každý počítač je propojen se dvěma sousedy</span></p></li><li><p><span>pakety se posílají jedním směrem</span></p></li><li><p><span>vždy vysílá jen jeden počítač, ostatní posílají a přeposílají</span></p></li><li><p><strong><span>token ring</span></strong></p><ul><li><span>princip předávání práva vysílat (tokenu)</span></li></ul></li></ul></li><li><p><strong><span>sběrnice</span></strong><span> (bus)</span></p><p><img src="assets/image-20220312203832317.png" alt="image-20220312203832317" style="zoom:50%;" /><span> </span></p><ul><li><p><span>počítače připojeny k průběžnému vedení</span></p></li><li><p><span>vyslaná zpráva se šíří všemi směry, na konci vedení je pohlcena koncovkou (</span><em><span>rezistorem</span></em><span>)</span></p></li><li><p><span>realizována pomocí koaxiálních kabelů</span></p></li><li><p><span>kolize</span></p><ul><li><span>když vysílají dvě stanice zároveň, dochází k rušení signálu</span></li><li><span>řešením je například metoda token bus nebo metoda přístupu CSMA/CD</span></li></ul></li></ul></li><li><p><strong><span>hvězda</span></strong></p><p><img src="assets/image-20220312203843483.png" alt="image-20220312203843483" style="zoom:50%;" /><span> </span></p><ul><li><span>stanice jsou připojeny na </span><strong><span>rozbočovač</span></strong><span> (</span><strong><span>hub</span></strong><span>, propojovací centrum)</span></li><li><span>vyslaná stanice se šíří celou sítí, cílová stanice ji přijme</span></li><li><span>použití </span><strong><span>přepínače (switch)</span></strong><span> místo rozbočovače 👉 zpráva míří rovnou k adresátovi, ne k ostatním</span></li><li><span>dnes u LAN nejčastější</span></li></ul></li><li><p><strong><span>kombinované</span></strong></p></li></ul><h2 id='prvky-sítě'><span>prvky sítě</span></h2><ul><li><p><strong><span>pasivní</span></strong></p></li><li><p><strong><span>aktivní</span></strong></p><ul><li><p><strong><span>opakovač</span></strong><span> (repeater)</span></p><ul><li><span>zesiluje a obnovuje signál</span></li></ul></li><li><p><strong><span>rozbočovač</span></strong><span> (hub)</span></p><ul><li><span>umožňuje rozvětvení sítě</span></li><li><span>dnes nahrazeno </span><strong><span>přepínačem</span></strong></li></ul></li><li><p><strong><span>přepínač</span></strong><span> (switch)</span></p><ul><li><span>inteligentní propojovací prvek pro hvězdicovou topologii</span></li><li><span>pracuje s MAC adresami zařízení</span></li></ul></li><li><p><strong><span>most</span></strong><span> (bridge)</span></p><ul><li><span>odděluje segmenty sítě a tím zmenšuje zátěž</span></li><li><span>levnější, než router</span></li></ul></li><li><p><strong><span>směrovač</span></strong><span> (router)</span></p><ul><li><span>propojuje lokální sítě používající stejný komunikační protokol</span></li><li><span>směruje data mezi sítěmi pomocí IP adres</span></li><li><span>obvykle optimalizovaný počítač</span></li></ul></li><li><p><strong><span>brána</span></strong><span> (gateway)</span></p><ul><li><span>nejvýše postavený aktivní prvek v sítích</span></li><li><span>spojuje sítě s různými komunikačními protokoly</span></li><li><span>plní i práci routeru</span></li></ul></li></ul></li></ul><h2 id='metody-přístupu'><span>metody přístupu</span></h2><ul><li><p><strong><span>token ring</span></strong></p><ul><li><span>kruhová topologie, kde vysílá a přijímá jen stanice, která má zrovna token</span></li></ul></li><li><p><strong><span>token bus</span></strong></p><ul><li><span>sběrnicová topologie, kde vysílá a přijímá jen stanice, která má zrovna token</span></li></ul></li><li><p><strong><span>CSMA/CD</span></strong></p><ul><li><span>pokud volné, vysílá</span></li><li><span>dokud vysílá, poslouchá, jestli něco nepřichází</span></li><li><span>pokud došlo ke kolizi, přenos se ukončí a pokusí se ho provést znovu</span></li></ul></li></ul><h2 id='funkce-počítačové-sítě'><span>funkce počítačové sítě</span></h2><ul><li><strong><span>sdílení</span></strong></li><li><strong><span>přenos</span></strong></li><li><strong><span>ochrana dat</span></strong></li><li><strong><span>komunikace</span></strong><span> (</span><em><span>email, chat</span></em><span>, …)</span></li><li><strong><span>vzdálená práce</span></strong><span> (</span><em><span>ssh, …</span></em><span>)</span></li></ul><h1 id='počítačové-sítě---software'><span>Počítačové sítě - software</span></h1><h2 id='model-isoosi'><span>model ISO/OSI</span></h2><ul><li><p><span>OSI - Open System Interconnection</span></p></li><li><p><strong><span>vrstvy (7):</span></strong></p><ul><li><strong><span>aplikační</span></strong><span> - aplikace poskytující síťové služby uživateli</span></li><li><strong><span>prezentační</span></strong><span> - konverze dat (která mohou bát jinak kódována), často splývá s relační vrstvou</span></li><li><strong><span>relační</span></strong><span> - navazuje, udržuje a synchronizuje spojení mezi uživateli</span></li><li><strong><span>transportní</span></strong><span> - dělí pakety podle transportního protokolu, přijaté pakety skládá do zpráv</span></li><li><strong><span>síťová</span></strong><span> - přiřazuje adresy, volí trasu paketu - routing</span></li><li><strong><span>linková</span></strong><span> - stará se o přenos mezi dvěma fyzickými uzly, jeho bezchybnost</span></li><li><strong><span>fyzická</span></strong><span> - popisuje fyzické vlastnosti přenosového média</span></li></ul><p><span> </span><span> </span><img src="assets/image-20220312203908889.png" alt="image-20220312203908889" style="zoom:50%;" /><span> </span></p><ul><li><span>model komunikace v počítačové síti</span></li></ul></li><li><p><strong><span>princip komunikace</span></strong></p><p><img src="assets/image-20220312203920697.png" alt="image-20220312203920697" style="zoom:50%;" /><span> </span></p><ul><li><p><span>každá vrstva přidává k datům další údaje</span></p><ul><li><strong><span>SDU</span></strong><span> - Service Data Unit, užitečná data dané vrstvy</span></li><li><strong><span>PCI</span></strong><span> - Protocol Control Information, řídící informace dané vrstvy</span></li><li><strong><span>PDU</span></strong><span> - Protocol Data Unit, </span><code>= SDU + PCI</code></li></ul></li><li><p><strong><span>mezi vrstvami</span></strong></p><ul><li><span>komunikují spolu vždy stejné vrstvy </span></li></ul></li><li><p><strong><span>mezi uzly sítě</span></strong></p><ul><li><strong><span>vysílací uzel</span></strong><span> - vyšší vrstva předává data nižší vrstvě</span></li><li><strong><span>přijímací uzel</span></strong><span> - nižší vrstva předává data vyšší vrstvě</span></li></ul></li></ul></li></ul><h2 id='model-tcpip'><span>model TCP/IP</span></h2><ul><li><p><span>zjednodušení modelu ISO/OSI</span></p></li><li><p><strong><span>vrstvy (4):</span></strong></p><ol start='' ><li><p><strong><span>vrstva síťového rozhraní</span></strong></p><ul><li><span>přístup a definice fyzického rozhraní</span></li><li><span>specifická pro každou implementaci sítě</span></li><li><em><span>např.: Ethernet, Token Ring, …</span></em></li></ul></li><li><p><strong><span>síťová vrstva</span></strong></p><ul><li><span>zajišťuje adresaci, směrování a předávání datagramů</span></li><li><span>realizovaná ve všech prvcích sítě</span></li><li><em><span>např.: IP protokol, …</span></em></li></ul></li><li><p><strong><span>transportní vrstva</span></strong></p><ul><li><span>poskytuje spojení spolehlivým (</span><strong><span>TCP</span></strong><span>) nebo nespolehlivým (</span><strong><span>UDP</span></strong><span>) protokolem</span></li><li><span>realizovaná až v síťových kartách (koncových zařízeních)</span></li></ul></li><li><p><strong><span>aplikační vrstva</span></strong></p><ul><li><span>programy, které realizují konkrétní služby pro uživatele</span></li><li><span>spojení je určeno číslem </span><strong><span>portu</span></strong></li><li><strong><span>port</span></strong><span> - dohodnuté číslo přiřazené zvenčí aplikaci operačním systémem</span></li><li><em><span>např.: HTTP, FTP, DHCP, …</span></em></li></ul></li></ol></li><li><p><strong><span>model přenášených dat</span></strong></p><p><img src="assets/image-20220312203934492.png" alt="image-20220312203934492" style="zoom:50%;" /><span> </span></p></li><li><p><strong><span>metody adresování</span></strong></p><ul><li><p><strong><span>MAC</span></strong></p><ul><li><span>fyzická adresa</span></li><li><span>celosvětově jedinečný identifikátor</span></li></ul></li><li><p><strong><span>IP</span></strong></p><ul><li><span>určuje klienta serveru</span></li></ul></li><li><p><strong><span>DNS</span></strong></p><ul><li><span>distribuovaná databáze názvů hostitelských domén a jejich IP adres</span></li><li><span>tabulky jsou uloženy na směrovačích, přepínačích a branách různých vrstev internetu</span></li></ul></li></ul></li></ul><h2 id='protokoly'><span>protokoly</span></h2><ul><li><p><strong><span>definice</span></strong></p><ul><li><span>soubor pravidel pro komunikaci mezi 2 a více body</span></li></ul></li><li><p><strong><span>TCP/IP</span></strong></p><ul><li><span>rodina protokolů</span></li><li><span>4 vrstvy</span></li></ul></li><li><p><strong><span>IP</span></strong><span> - Internet Protocol</span></p><ul><li><span>vysílá a přijímá datagramy</span></li><li><span>poskytuje nespojové síťové spojení</span></li><li><span>nespolehlivé, spolehlivost zaručují vyšší vrstvy</span></li></ul></li><li><p><strong><span>TCP</span></strong><span> - Transmission Control Protocol</span></p><ul><li><p><span>spojový a spolehlivý přenos dat</span></p></li><li><p><span>fáze: navázání spojení, přenos dat, ukončení spojení</span></p></li><li><p><strong><span>paket</span></strong></p><ul><li><span>základní jednotka přenosu dat nespojových sítí se spolehlivým přenosem</span></li><li><span>ve 4. vrstvě</span></li></ul></li></ul></li><li><p><strong><span>UDP</span></strong><span> - User Datagram Protocol</span></p><ul><li><p><span>poskytuje nespolehlivou transportní službu pro aplikace, které spolehlivost nepotřebují</span></p></li><li><p><span>fáze: přenos dat</span></p></li><li><p><strong><span>datagram</span></strong></p><ul><li><span>základní jednotka přenosu dat nespojových sítí s nespolehlivým přenosem</span></li></ul></li></ul></li></ul><h2 id='internet'><span>internet</span></h2><ul><li><p><strong><span>vymezení</span></strong></p><ul><li><span>celosvětová sít komunikace</span></li><li><span>organizovaná skrze protokol TCP/IP</span></li></ul></li><li><p><strong><span>struktura</span></strong></p><ul><li><span>propojené malé sítě</span></li></ul></li><li><p><strong><span>adresování mezi uzly v internetu</span></strong></p><ul><li><span>komunikaci mezi sítěmi zajišťují gateway</span></li><li><span>pro lepší orientaci byla zavedena služba </span><strong><span>DNS</span></strong><span>, která se stará o domény a překlad IP adres do pro lidi stravitelného formátu</span></li></ul></li></ul><h1 id='booleova-algebra-a-její-využití'><span>Booleova algebra a její využití</span></h1><h2 id='základní-pojmy'><span>základní pojmy</span></h2><ul><li><p><strong><span>logická hodnota</span></strong></p><ul><li><span>hodnoty, jichž mohou nabývat logické proměnné</span></li></ul></li><li><p><strong><span>logická proměnná</span></strong></p><ul><li><span>nabývá právě dvou jasně rozlišitelných hodnot</span></li><li><span>v logickém obvodě reprezentuje fyzikální veličinu</span></li></ul></li><li><p><strong><span>logická funkce</span></strong></p><ul><li><span>obecně funkce - zobrazení, která n-tici nezávislých logických proměnných x</span><sub><span>i</span></sub><span> zobrazuje na m-tici stavů závisle proměnných y</span><sub><span>i</span></sub></li></ul></li><li><p><strong><span>logický obvod</span></strong></p><ul><li><span>fyzikální obvod, v němž každá vstupní, výstupní či vnitřní fyzikální veličina nabývá v ustáleném stavu pouze dvou, jasně odlišitelných, diskrétních hodnot</span></li><li><span>typy: </span><strong><span>kombinační, sekvenční</span></strong></li></ul></li><li><p><strong><span>logický člen</span></strong><span> (hradlo)</span></p><ul><li><span>elementární zařízení, které realizuje elementární logické funkce v číslicových počítačích nebo jiných číslicových zařázeních</span></li><li><em><span>např.: logický součin AND</span></em></li></ul></li></ul><h2 id='logické-funkce'><span>logické funkce</span></h2><ul><li><p><span>základní:</span></p><ul><li><strong><span>součet</span></strong><span> (OR)</span></li><li><strong><span>součin</span></strong><span> (AND)</span></li><li><strong><span>negace</span></strong><span> (NOT)</span></li><li><strong><span>exkluzivní součet</span></strong><span> (XOR)</span></li><li><strong><span>negovaný součin</span></strong><span> (NAND)</span></li><li><strong><span>negovaný součet</span></strong><span> (NOR)</span></li></ul></li><li><p><strong><span>logické výrazy</span></strong></p><ul><li><span>sestavují se z logických proměnných a konstant pomocí základních logických operací</span></li><li><span>příklad: </span><code>y = ab + bcd + abd</code></li></ul></li></ul><h2 id='zákony'><span>zákony</span></h2><ul><li><span>11 zákonů, slouží k úpravám, zjednodušování a odvozování logických výrazů</span></li></ul><ol start='' ><li><p><strong><span>Komutativní zákon</span></strong></p><ul><li><code>a+b = b+a</code></li><li><code>ab = ba</code></li></ul></li><li><p><strong><span>Asociativní zákon</span></strong></p><ul><li><code>(a+b)+c = a+(b+c)</code></li><li><code>(ab)c = a(bc)</code></li></ul></li><li><p><strong><span>Distributivní zákon</span></strong></p><ul><li><code>a(b+c) = ab+ac</code></li><li><code>a+bc = (a+b)(a+c)</code></li></ul></li><li><p><strong><span>Zákon vyloučeného třetího</span></strong></p><ul><li><code>a+!a = 1</code></li><li><code>a!a = 0</code></li></ul></li><li><p><strong><span>Zákon neutrálnosti nuly a jedničky</span></strong></p><ul><li><code>a+0 = a</code></li><li><code>a1 = a</code></li></ul></li><li><p><strong><span>Zákon agresivity nuly a jedničky</span></strong></p><ul><li><code>a+1 = 1</code></li><li><code>a0 = 0</code></li></ul></li><li><p><strong><span>Zákon tautologie</span></strong></p><ul><li><code>a+a = a</code></li><li><code>aa = a</code></li></ul></li><li><p><strong><span>Zákon absorbce</span></strong></p><ul><li><code>a+ab = a</code></li><li><code>a(a+b) = a</code></li></ul></li><li><p><strong><span>Zákon absorbce negace</span></strong></p><ul><li><code>a+!ab = a+b</code></li><li><code>a(!a+b) = ab</code></li></ul></li><li><p><strong><span>Zákon dvojité negace</span></strong></p><ul><li><code>!!a = a</code></li></ul></li><li><p><strong><span>De Morganovy zákony</span></strong></p><ul><li><code>!(a+b) = !a!b</code></li><li><code>!(ab) = !a+!b</code></li></ul></li></ol><ul><li><p><span>užití:</span></p><ul><li><p><span>k minimalizaci logických výrazů</span></p></li><li><p><span>převody do normálních forem:</span></p><ul><li><span>jen součty a negace</span></li><li><span>jen součiny a negace</span></li></ul></li></ul></li></ul><h2 id='vyjadřování-logických-funkcí'><span>vyjadřování logických funkcí</span></h2><ul><li><p><strong><span>rovnice</span></strong></p><ul><li><p><span>všechny logické funkce jde vyjádřit dvěma způsoby:</span></p><ul><li><strong><span>disjunktivní - součet součinů</span></strong><span> přímých a negovaných proměnných</span></li><li><strong><span>konjuktivní - součin součtů</span></strong><span> přímých a negovaných proměnných</span></li></ul></li></ul></li><li><p><strong><span>pravdivostní tabulka</span></strong></p><ul><li><p><span>tabulka, kde</span></p><ul><li><span>sloupce odpovídají členům logické funkce a výsledku</span></li><li><span>řádky odpovídají všem možným kombinacím vstupních hodnot</span></li></ul></li></ul></li><li><p><strong><span>Karnaughova mapa </span></strong></p><ul><li><span>matice logických výrazů</span></li><li><span>vychází z Vennova diagramu</span></li></ul></li></ul><h2 id='minimalizace-logických-funkcí'><span>minimalizace logických funkcí</span></h2><ul><li><p><span>způsoby:</span></p><ul><li><span>odvozováním pomocí zákonů</span></li><li><span>pomocí Karnaughovy mapy</span></li></ul></li></ul></div></div>
</body>
</html>