Egzamin Wprowadzenie do Informatyki (7) PDF

Tematy na egzamin - Wprowadzenie do informatyki 1. Podstawy teorii informacji ​ Definicja i podstawowe cechy informacji ​ Przenoszenie i przetwarzanie informacji ​ Informatyka jako dziedzina nauki - definicja i zakres Definicja i podstawow...

Tematy na egzamin - Wprowadzenie do informatyki 1. Podstawy teorii informacji ​ Definicja i podstawowe cechy informacji ​ Przenoszenie i przetwarzanie informacji ​ Informatyka jako dziedzina nauki - definicja i zakres Definicja i podstawowe cechy informacji Informacja to zbiór danych, które mają znaczenie i mogą być wykorzystane do podjęcia decyzji. Może być przekazywana w różnej formie, np. tekstowej, dźwiękowej, graficznej lub w postaci sygnałów cyfrowych. Informacja ma kilka kluczowych cech: ​ Dokładność – musi być precyzyjna i zgodna z rzeczywistością, aby uniknąć błędnych interpretacji. ​ Kompletność – powinna zawierać wszystkie niezbędne dane potrzebne do podjęcia decyzji. ​ Aktualność – informacja powinna być na bieżąco aktualizowana, ponieważ przestarzałe dane mogą prowadzić do błędnych decyzji. ​ Przydatność – powinna mieć wartość dla odbiorcy, umożliwiając skuteczniejsze działanie. ​ Zrozumiałość – musi być przedstawiona w sposób czytelny i zrozumiały dla odbiorcy. Przenoszenie i przetwarzanie informacji Informacja jest przetwarzana w różnych systemach i może być przekazywana na różne sposoby. Proces ten obejmuje kilka kluczowych etapów: ​ Kodowanie informacji – przekształcanie informacji w postać umożliwiającą jej przechowywanie lub transmisję (np. tekst na kod binarny w komputerze). ​ Przesyłanie informacji – informacja jest przesyłana między nadawcą a odbiorcą za pomocą medium komunikacyjnego (np. sieć komputerowa, fale radiowe, światłowody). ​ Odbiór i dekodowanie – odbiorca otrzymuje informację i przekształca ją na czytelny format. ​ Przetwarzanie informacji – operacje na danych mające na celu ich analizę, organizację lub interpretację (np. filtrowanie wiadomości e-mail, analiza dużych zbiorów danych w bazach informatycznych).  ​ Zapisywanie informacji – przechowywanie informacji na nośnikach cyfrowych lub w chmurze obliczeniowej. Informatyka jako dziedzina nauki – definicja i zakres Informatyka to nauka zajmująca się automatycznym przetwarzaniem informacji przy użyciu komputerów i systemów cyfrowych. Jej główne obszary to: ​ Teoria obliczeń – analiza problemów, które mogą być rozwiązane za pomocą algorytmów. ​ Algorytmika i struktury danych – projektowanie efektywnych metod przechowywania i przetwarzania danych. ​ Programowanie – tworzenie kodu komputerowego w różnych językach programowania. ​ Sztuczna inteligencja (AI) – projektowanie systemów zdolnych do samodzielnego uczenia się i podejmowania decyzji. ​ Sieci komputerowe i komunikacja – projektowanie i zarządzanie systemami komunikacji między urządzeniami. ​ Cyberbezpieczeństwo – ochrona systemów informatycznych przed zagrożeniami. ​ Bazy danych i analiza danych – przechowywanie, zarządzanie i analiza dużych zbiorów informacji. Współczesna informatyka znajduje zastosowanie w niemal każdej dziedzinie życia, od medycyny po finanse, przemysł i rozrywkę. 2. Miary i kodowanie informacji ​ Ilościowa i jakościowa teoria informacji ​ Miara informacji i entropia ​ Jednostki informacji (bit, bajt i ich wielokrotności) ​ Redundancja i jej znaczenie Ilościowa i jakościowa teoria informacji Teoria informacji dzieli się na dwa główne nurty: ​ Teoria ilościowa (Claude Shannon) – zajmuje się matematycznym opisem informacji i jej miarą. ​ Teoria jakościowa (Marian Mazur) – analizuje wartość i znaczenie informacji dla odbiorcy. Shannon określił, że informacja jest tym większa, im mniejsze jest prawdopodobieństwo jej wystąpienia. Mazur skupił się na ocenie użyteczności informacji w kontekście podejmowania decyzji. Miara informacji i entropia Miara informacji określa ilość informacji zawartą w przekazie. Shannon zaproponował wzór: I=−log⁡2(P)I = -\log_2(P) gdzie PP to prawdopodobieństwo danego zdarzenia. Entropia to średnia ilość informacji przypadająca na jeden symbol w wiadomości. Definiuje się ją jako: H=−∑P(x)⋅log⁡2P(x)H = -\sum P(x) \cdot \log_2 P(x) Im większa entropia, tym większa niepewność przekazu. Jednostki informacji (bit, bajt i ich wielokrotności) Jednostkami informacji są: ​ Bit (b) – najmniejsza jednostka, przyjmująca wartości 0 lub 1. ​ Bajt (B) – 8 bitów, podstawowa jednostka przechowywania danych. ​ Kilobajt (kB) – 1024 bajty. ​ Megabajt (MB) – 1024 kB. ​ Gigabajt (GB) – 1024 MB. ​ Terabajt (TB) – 1024 GB. ​ Petabajt (PB) – 1024 TB. Redundancja i jej znaczenie Redundancja to nadmiarowość informacji, zwiększająca niezawodność transmisji. Występuje w dwóch głównych formach: ​ Redundancja strukturalna – dodanie zbędnych informacji (np. kody korekcyjne). ​ Redundancja logiczna – powtarzanie informacji w celu ochrony przed błędami (np. RAID w pamięciach masowych). Redundancja pozwala na wykrywanie i korygowanie błędów w przesyłanych danych. 3. Kodowanie informacji ​ Algorytm Shannona-Fano ​ Algorytm Huffmana ​ Porównanie algorytmów kodowania ​ Warunek Fano Algorytm Shannona-Fano Algorytm Shannona-Fano to metoda bezstratnego kodowania informacji, polegająca na przypisywaniu krótszych kodów bardziej prawdopodobnym symbolom w przekazie. Proces kodowania przebiega następująco: 1.​ Sortowanie symboli – symbole w wiadomości są uporządkowane malejąco według częstości ich występowania. 2.​ Podział na grupy – zbiór symboli jest dzielony na dwa podzbiory o możliwie najbardziej równym prawdopodobieństwie. 3.​ Przypisanie bitów – pierwszej grupie przypisuje się 0, drugiej 1. 4.​ Rekursja – proces powtarza się dla każdego podzbioru, aż każdy symbol otrzyma unikalny kod binarny. Przykład: Załóżmy, że mamy symbole {A: 0.4, B: 0.3, C: 0.2, D: 0.1}. Po podziale i przypisaniu bitów możemy uzyskać następujące kody: ​ A → 0 ​ B → 10 ​ C → 110 ​ D → 111 Algorytm Shannona-Fano jest efektywny, ale może generować nieco dłuższe kody niż algorytm Huffmana. Algorytm Huffmana Algorytm Huffmana to bardziej optymalna metoda kodowania bezstratnego. Działa poprzez konstruowanie drzewa kodowego: 1.​ Tworzenie listy symboli – każdy symbol jest traktowany jako pojedynczy węzeł drzewa o wartości równej jego prawdopodobieństwu.  2.​ Tworzenie drzewa Huffmana – dwa symbole o najmniejszym prawdopodobieństwie są łączone w jeden węzeł nadrzędny o sumarycznym prawdopodobieństwie. 3.​ Przypisanie kodów – dla każdej gałęzi drzewa przypisuje się 0 lub 1, w zależności od kierunku podziału. 4.​ Odczytanie kodów – gotowe kody binarne są odczytywane z drzewa od korzenia do liści. Przykład: Dla tych samych symboli {A: 0.4, B: 0.3, C: 0.2, D: 0.1} drzewo Huffmana może wyglądać tak: Unset (1.0) / \ (0.6) (0.4 - A) / \ (0.3-B) (0.3) / \ (0.2-C) (0.1-D) W rezultacie uzyskujemy kody: ​ A → 0 ​ B → 10 ​ C → 110 ​ D → 111 Kodowanie Huffmana zawsze generuje optymalne kody prefiksowe, minimalizując średnią długość zakodowanej wiadomości. Porównanie algorytmów kodowania Cecha Algorytm Algorytm Huffmana Shannona-Fano  Optymalność Nie zawsze Zawsze optymalne Metoda Rekurencyjny podział Konstrukcja drzewa kodowania zbioru Prefiksowość Tak Tak kodu Zastosowanie Podstawowe Skompresowane formaty plików (JPEG, kodowanie MP3, ZIP) Warunek Fano Warunek Fano zapewnia jednoznaczność dekodowania kodu i mówi, że: ​ Żaden kod nie może być prefiksem innego kodu. ​ Każdy kod powinien być jednoznacznie dekodowalny z sekwencji bitów. Przykład poprawnego kodowania spełniającego warunek Fano: ​ A → 0 ​ B → 10 ​ C → 110 ​ D → 111 Tutaj 0 jednoznacznie identyfikuje A, 10 identyfikuje B, 110 to C, a 111 to D. Nie ma sytuacji, w której dwa różne symbole zaczynają się od tych samych bitów. 4. Systemy liczbowe ​ System binarny (dwójkowy) ​ System oktalny (ósemkowy)  ​ System heksadecymalny (szesnastkowy) ​ Konwersje między systemami liczbowymi System binarny (dwójkowy) System binarny (dwójkowy) jest podstawowym systemem liczbowym używanym w informatyce i elektronice cyfrowej. Wykorzystuje tylko dwie cyfry: 0 i 1. Każda cyfra w systemie binarnym nazywana jest bitem. Zasada działania Każda pozycja w liczbie binarnej odpowiada potędze liczby 2. Przykładowa konwersja liczby binarnej 1011₂ na system dziesiętny: 10112=1⋅23+0⋅22+1⋅21+1⋅20=8+0+2+1=11101011_2 = 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = 8 + 0 + 2 + 1 = 11_{10} Zastosowanie ​ Przechowywanie i przetwarzanie danych w komputerach. ​ Reprezentacja stanów logicznych (0 – brak napięcia, 1 – obecność napięcia). ​ Podstawowy zapis instrukcji w języku maszynowym. System oktalny (ósemkowy) System oktalny (ósemkowy) ma podstawę 8 i używa cyfr od 0 do 7. Jest często stosowany w elektronice i informatyce jako skrócona forma zapisu binarnego. Konwersja binarny → oktalny Aby przekonwertować liczbę binarną na ósemkową, grupujemy bity po trzy od prawej strony: 1011102=(101)(110)2=5868=568101110_2 = (101)(110)_2 = 5_8 6_8 = 56_8 Zastosowanie ​ Używany w systemach wbudowanych i starszych komputerach. ​ Spotykany w kodowaniu uprawnień w systemie Unix/Linux (np. chmod 755). System heksadecymalny (szesnastkowy) System heksadecymalny (szesnastkowy) ma podstawę 16 i używa cyfr 0-9 oraz liter A-F (gdzie A = 10, B = 11,..., F = 15). Jest szczególnie popularny w informatyce, ponieważ pozwala na bardziej kompaktowy zapis liczb binarnych. Konwersja binarny → heksadecymalny Grupujemy bity po cztery od prawej strony: 110111102=(1101)(1110)2=DE=DE1611011110_2 = (1101)(1110)_2 = D_E = DE_{16} Zastosowanie ​ Adresy pamięci i kolory w HTML/CSS (np. #FFAA33). ​ Przechowywanie instrukcji maszynowych w asemblerze. ​ Identyfikatory unikalnych wartości w systemach komputerowych. Konwersje między systemami liczbowymi Konwersje między systemami liczbowymi są kluczowe w programowaniu i elektronice. Dziesiętny → binarny Dzielimy liczbę przez 2, zapisując reszty: ​ 25 ÷ 2 = 12 reszta 1 ​ 12 ÷ 2 = 6 reszta 0 ​ 6 ÷ 2 = 3 reszta 0 ​ 3 ÷ 2 = 1 reszta 1 ​ 1 ÷ 2 = 0 reszta 1 Czytamy reszty od dołu: 25₁₀ = 11001₂ Dziesiętny → ósemkowy Dzielimy przez 8: ​ 145 ÷ 8 = 18 reszta 1 ​ 18 ÷ 8 = 2 reszta 2 ​ 2 ÷ 8 = 0 reszta 2 Odczytujemy od dołu: 145₁₀ = 221₈ Dziesiętny → szesnastkowy  Dzielimy przez 16: ​ 250 ÷ 16 = 15 reszta 10 → A ​ 15 ÷ 16 = 0 reszta 15 → F Odczytujemy od dołu: 250₁₀ = FA₁₆ Binarny → dziesiętny Dodajemy wartości bitów zgodnie z wagami: 11012=1⋅23+1⋅22+0⋅21+1⋅20=8+4+0+1=13101101_2 = 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 8 + 4 + 0 + 1 = 13_{10} Ósemkowy → dziesiętny Każdą cyfrę mnożymy przez kolejne potęgi 8: 1578=1⋅82+5⋅81+7⋅80=64+40+7=11110157_8 = 1 \cdot 8^2 + 5 \cdot 8^1 + 7 \cdot 8^0 = 64 + 40 + 7 = 111_{10} Szesnastkowy → dziesiętny Każdą cyfrę mnożymy przez kolejne potęgi 16: 2F16=2⋅161+15⋅160=32+15=47102F_16 = 2 \cdot 16^1 + 15 \cdot 16^0 = 32 + 15 = 47_{10} 5. Reprezentacja liczb w komputerze ​ Kodowanie liczb ze znakiem (ZM, U1, U2) ​ Zapis stałoprzecinkowy ​ Zapis zmiennoprzecinkowy (standard IEEE 754) ​ Wartości specjalne w zapisie zmiennoprzecinkowym Kodowanie liczb ze znakiem (ZM, U1, U2) Liczby całkowite mogą być przechowywane w komputerze na różne sposoby. W systemach binarnych wyróżnia się trzy podstawowe sposoby kodowania liczb całkowitych ze znakiem:  1.​ Kod znak-moduł (ZM):​ ○​ Pierwszy bit określa znak liczby: 0 oznacza liczbę dodatnią, 1 oznacza liczbę ujemną. ○​ Pozostałe bity reprezentują wartość liczbową w systemie binarnym. ○​ Przykład: ​ +5₁₀ = 00000101₂ ​ -5₁₀ = 10000101₂ ○​ Wadą tego kodowania jest istnienie dwóch reprezentacji zera (00000000₂ i 10000000₂). 2.​ Kod uzupełnień do jedynki (U1):​ ○​ Dodatnie liczby zapisywane są tak samo jak w kodzie ZM. ○​ Liczby ujemne koduje się poprzez zanegowanie wszystkich bitów liczby dodatniej (zamiana 0 na 1 i 1 na 0). ○​ Przykład: ​ +5₁₀ = 00000101₂ ​ -5₁₀ = 11111010₂ ○​ Wadą jest konieczność specjalnego traktowania operacji dodawania i odejmowania. 3.​ Kod uzupełnień do dwójki (U2):​ ○​ Liczby dodatnie koduje się tak samo jak w U1 i ZM. ○​ Liczby ujemne koduje się poprzez zanegowanie wszystkich bitów liczby dodatniej i dodanie 1 do wyniku. ○​ Przykład: ​ +5₁₀ = 00000101₂ ​ -5₁₀ = 11111011₂ (negacja 00000101₂ + 1) ○​ Kod U2 eliminuje problem podwójnego zera i jest standardem w systemach komputerowych. Zapis stałoprzecinkowy Liczby rzeczywiste można przechowywać w formacie stałoprzecinkowym, gdzie pozycja przecinka jest ustalona na stałe. ​ Przykład: 123.45 może być zapisane jako 12345, przy założeniu, że przecinek jest zawsze po dwóch miejscach dziesiętnych. ​ Stosowany w systemach, które nie wymagają dużej dynamiki liczb (np. w kalkulatorach). ​ Wadą tego podejścia jest ograniczona precyzja oraz konieczność operowania na ustalonej skali. Zapis zmiennoprzecinkowy (standard IEEE 754) Standard IEEE 754 określa sposób reprezentowania liczb zmiennoprzecinkowych w komputerze. ​ Liczba zapisywana jest w postaci: (−1)S×M×2E(-1)^S \times M \times 2^E gdzie: ○​ S – bit znaku (0 dla liczb dodatnich, 1 dla ujemnych), ○​ M – mantysa (ułamek dziesiętny, zapisany w systemie binarnym), ○​ E – wykładnik potęgi 2, zapisany w kodzie U2. Formaty IEEE 754: 1.​ Pojedyncza precyzja (32 bity):​ ○​ 1 bit znaku ○​ 8 bitów wykładnika ○​ 23 bity mantysy ○​ Przykładowa liczba: 11000000101000000000000000000000₂ → -5.0₁₀ 2.​ Podwójna precyzja (64 bity):​ ○​ 1 bit znaku ○​ 11 bitów wykładnika ○​ 52 bity mantysy ○​ Stosowany w naukowych obliczeniach wymagających większej precyzji. Wartości specjalne w zapisie zmiennoprzecinkowym Standard IEEE 754 definiuje również specjalne wartości: ​ Zero: 00000000000000000000000000000000₂ (pojedyncza precyzja) lub 00000000000000000000000000000000000000000000000000000000000000 00₂ (podwójna precyzja). ​ Liczby denormalizowane: liczby bliskie zera, ale z precyzją mniejszą niż standardowa. ​ Nieskończoność (+∞, -∞): uzyskiwana przy przepełnieniu wartości wykładnika (wszystkie bity wykładnika na 1, mantysa zerowa). ​ NaN (Not a Number): wskazuje błędne obliczenia, np. 0/0 lub sqrt(-1). 6. Algorytmy i struktury danych ​ Definicja i własności algorytmu ​ Sposoby zapisu algorytmów ​ Podstawowe struktury danych (lista, graf, drzewo) ​ Złożoność obliczeniowa algorytmów Definicja i własności algorytmu Algorytm to zestaw jasno określonych kroków prowadzących do rozwiązania problemu. Musi spełniać kilka podstawowych cech: ​ Skończoność – algorytm powinien zakończyć działanie po określonej liczbie kroków. ​ Jednoznaczność – każda instrukcja musi być jasno zdefiniowana i nie budzić wątpliwości. ​ Poprawność – algorytm powinien zawsze zwracać poprawne wyniki dla poprawnych danych wejściowych. ​ Wydajność – jego wykonanie powinno być jak najbardziej optymalne pod względem czasu i pamięci. ​ Uniwersalność – algorytm powinien być możliwy do zastosowania dla różnych danych wejściowych. Sposoby zapisu algorytmów Algorytmy można zapisywać na kilka sposobów, zależnie od poziomu szczegółowości i zastosowania: ​ Opis słowny – przedstawienie algorytmu w naturalnym języku. ​ Lista kroków – uporządkowana lista kolejnych operacji. ​ Schemat blokowy – graficzna reprezentacja algorytmu w postaci diagramu blokowego. ​ Pseudokod – zapis przypominający kod programistyczny, ale pozbawiony składni konkretnego języka. ​ Język programowania – implementacja algorytmu w rzeczywistym języku programowania (np. Python, C++). Podstawowe struktury danych Struktury danych to sposoby organizowania i przechowywania informacji w pamięci komputera. Do podstawowych należą:  ​ Lista – liniowa struktura danych, w której elementy są uporządkowane w określonej kolejności. Może być dynamiczna (lista łączona) lub statyczna (tablica). ​ Graf – zbiór wierzchołków połączonych krawędziami, wykorzystywany m.in. w analizie sieci i algorytmach wyszukiwania ścieżek. ​ Drzewo – hierarchiczna struktura danych, w której każdy element (węzeł) może mieć wiele dzieci, ale tylko jednego rodzica (z wyjątkiem korzenia). Drzewo binarne to specjalny przypadek, w którym każdy węzeł ma maksymalnie dwóch potomków. Złożoność obliczeniowa algorytmów Złożoność obliczeniowa to sposób określania efektywności algorytmu w zależności od rozmiaru danych wejściowych. Wyróżniamy dwa główne rodzaje: ​ Złożoność czasowa – określa liczbę operacji wykonanych przez algorytm w zależności od rozmiaru wejścia. ​ Złożoność pamięciowa – określa ilość dodatkowej pamięci wymaganej do działania algorytmu. Najczęściej stosuje się notację dużego O (O-notation), która klasyfikuje algorytmy według szybkości wzrostu liczby operacji: ​ O(1) – czas działania jest stały, niezależnie od wielkości danych (np. dostęp do elementu w tablicy). ​ O(log n) – czas działania rośnie logarytmicznie wraz z wielkością danych (np. wyszukiwanie binarne). ​ O(n) – czas działania rośnie liniowo wraz z wielkością danych (np. przeszukiwanie tablicy). ​ O(n log n) – efektywne algorytmy sortowania (np. quicksort, mergesort). ​ O(n²) – mniej efektywne algorytmy sortowania, np. sortowanie bąbelkowe. ​ O(2ⁿ) – algorytmy wykładnicze, bardzo nieefektywne dla dużych danych (np. naiwny algorytm do znajdowania podzbiorów). 7. Podstawowe algorytmy ​ Algorytmy sortowania (selectionsort, insertionsort, quicksort, heapsort) ​ Problem słownika i jego implementacje ​ Algorytmy przechodzenia grafu  ​ Drzewa poszukiwań binarnych Algorytmy sortowania Sortowanie to kluczowy problem algorytmiczny w informatyce. Wyróżniamy kilka podstawowych metod sortowania: Selection Sort (Sortowanie przez wybór) ​ Polega na znajdowaniu najmniejszego elementu w zbiorze i zamianie go z pierwszym nieposortowanym elementem. ​ Powtarza się to dla kolejnych nieposortowanych elementów, aż cała tablica będzie uporządkowana. ​ Czas działania: O(n²). ​ Przykład (sortowanie rosnące): ○​ Wejście: [5, 3, 8, 4, 2] ○​ Iteracje: 1.​ Znajdujemy najmniejszy element 2 i zamieniamy go z 5 → [2, 3, 8, 4, 5] 2.​ Znajdujemy najmniejszy element 3 (już na miejscu) → [2, 3, 8, 4, 5] 3.​ Znajdujemy najmniejszy 4, zamieniamy z 8 → [2, 3, 4, 8, 5] 4.​ Znajdujemy 5, zamieniamy z 8 → [2, 3, 4, 5, 8] ○​ Wynik: [2, 3, 4, 5, 8] Insertion Sort (Sortowanie przez wstawianie) ​ Działa poprzez wstawianie elementu w odpowiednie miejsce w posortowanej części tablicy. ​ Czas działania: O(n²), ale efektywnie działa dla małych zbiorów. ​ Przykład: ○​ Wejście: [5, 3, 8, 4, 2] ○​ Iteracje: 1.​ 3 wstawiamy przed 5 → [3, 5, 8, 4, 2] 2.​ 8 pozostaje na swoim miejscu → [3, 5, 8, 4, 2] 3.​ 4 wstawiamy pomiędzy 3 i 5 → [3, 4, 5, 8, 2] 4.​ 2 wstawiamy przed 3 → [2, 3, 4, 5, 8] ○​ Wynik: [2, 3, 4, 5, 8] Quicksort (Sortowanie szybkie) ​ Algorytm „dziel i zwyciężaj”.  ​ Wybieramy pivot (element podziału) i umieszczamy mniejsze wartości po lewej, a większe po prawej. ​ Rekurencyjnie powtarzamy dla każdej podtablicy. ​ Czas działania: O(n log n) (średnio). ​ Przykład (pivot = 5): ○​ Wejście: [5, 3, 8, 4, 2] ○​ Podział: [3, 4, 2] | 5 | ○​ Rekurencyjnie sortujemy [3, 4, 2] → [2, 3, 4] ○​ Wynik: [2, 3, 4, 5, 8] Heapsort (Sortowanie przez kopiec) ​ Wykorzystuje strukturę kopca binarnego. ​ Tworzymy kopiec maksymalny, a następnie stopniowo usuwamy największy element. ​ Czas działania: O(n log n). ​ Jest bardziej stabilny niż quicksort. Problem słownika i jego implementacje ​ Słownik to struktura danych, w której elementy są przechowywane w postaci par (klucz, wartość). ​ Popularne implementacje: ○​ Tablica asocjacyjna – mapa, np. dict w Pythonie. ○​ Tablica mieszająca (hash table) – szybki dostęp O(1) dla większości operacji. ○​ Drzewo wyszukiwań binarnych (BST) – czas wyszukiwania O(log n). Przykład użycia słownika w Pythonie: Python słownik = {"jabłko": "owoc", "marchewka": "warzywo"} print(słownik["jabłko"]) # wynik: owoc Algorytmy przechodzenia grafu Graf to struktura danych składająca się z wierzchołków i krawędzi. Wyróżniamy dwa główne algorytmy przeszukiwania: ​ BFS (Breadth-First Search, przeszukiwanie wszerz):  ○​ Kolejkowanie wierzchołków. ○​ Używany do znajdowania najkrótszej ścieżki w grafie. ○​ Czas działania O(V + E), gdzie V – liczba wierzchołków, E – liczba krawędzi. ​ DFS (Depth-First Search, przeszukiwanie w głąb): ○​ Używa stosu lub rekurencji. ○​ Sprawdza wszystkie możliwe ścieżki do momentu dojścia do końca. ○​ Czas działania O(V + E). Przykład BFS w Pythonie: Python def bfs(graph, start): visited = [] queue = [start] while queue: node = queue.pop(0) if node not in visited: visited.append(node) queue.extend(graph[node]) return visited Drzewa poszukiwań binarnych (BST – Binary Search Tree) Drzewo poszukiwań binarnych to specjalny rodzaj drzewa, w którym: ​ Każdy węzeł ma co najwyżej dwóch potomków. ​ Lewy poddrzewo zawiera wartości mniejsze niż wartość węzła. ​ Prawe poddrzewo zawiera wartości większe niż wartość węzła. ​ Średni czas wyszukiwania: O(log n). Przykład drzewa BST:  Unset 8 / \ 3 10 / \ \ 1 6 14 Podstawowe operacje na BST: ​ Wstawianie – nowy element dodajemy na podstawie porównań. ​ Wyszukiwanie – idziemy w lewo, jeśli wartość jest mniejsza, w prawo, jeśli większa. ​ Usuwanie – bardziej skomplikowane, zależne od liczby dzieci węzła. Przykład wstawiania w Pythonie: Python class Node: def __init__(self, value): self.value = value self.left = None self.right = None def insert(root, value): if root is None: return Node(value) if value < root.value: root.left = insert(root.left, value) else:  root.right = insert(root.right, value) return root 8. Maszyna Turinga i architektura komputera ​ Model i działanie maszyny Turinga ​ Architektura von Neumanna ​ Przykładowa maszyna cyfrowa (PMC) ​ Podstawowe składniki komputera Model i działanie maszyny Turinga Maszyna Turinga to teoretyczny model obliczeniowy, zaproponowany przez Alana Turinga w 1936 roku. Jest fundamentem współczesnej informatyki i teorii obliczeń. Elementy maszyny Turinga: 1.​ Taśma – nieskończona w jedną stronę sekwencja komórek, które mogą przechowywać symbole (np. 0 i 1). 2.​ Głowica – może odczytywać, zapisywać i przesuwać się w lewo lub w prawo po taśmie. 3.​ Stan wewnętrzny – maszyna posiada skończoną liczbę stanów, między którymi przechodzi. 4.​ Tabela przejść – zbiór reguł, określających działanie maszyny w zależności od odczytanego symbolu. Zasada działania maszyny Turinga: 1.​ Głowica odczytuje symbol z taśmy. 2.​ Na podstawie aktualnego stanu i odczytanego symbolu maszyna: ○​ zapisuje nowy symbol, ○​ przesuwa głowicę w lewo lub prawo, ○​ zmienia stan.  3.​ Proces powtarza się, aż maszyna przejdzie do stanu końcowego (akceptującego lub odrzucającego). Maszyna Turinga pozwala modelować każdy algorytm, a jej rozszerzeniem są maszyny wielotaśmowe oraz maszyny niedeterministyczne. Architektura von Neumanna Architektura von Neumanna to klasyczny model budowy komputera, opracowany w latach 40. XX wieku przez Johna von Neumanna. Jest stosowana w większości współczesnych komputerów. Cechy architektury von Neumanna: ​ Wspólna pamięć dla danych i instrukcji – programy są przechowywane w pamięci RAM razem z danymi. ​ Jedna jednostka sterująca – przetwarza instrukcje sekwencyjnie, jedna po drugiej. ​ Szyna danych – wykorzystywana do komunikacji między pamięcią, procesorem i urządzeniami wejścia-wyjścia. Schemat działania: 1.​ Pobranie instrukcji z pamięci do jednostki sterującej. 2.​ Dekodowanie instrukcji – określenie, co ma być wykonane. 3.​ Wykonanie instrukcji przez jednostkę arytmetyczno-logiczną (ALU). 4.​ Przechowywanie wyniku w pamięci lub rejestrach. Wadą architektury von Neumanna jest tzw. wąskie gardło – ograniczona przepustowość między procesorem a pamięcią, co wpływa na wydajność systemu. Przykładowa maszyna cyfrowa (PMC) Przykładowa maszyna cyfrowa (ang. Program Counter Machine, PMC) to uproszczony model komputera, ilustrujący sposób wykonywania programów. Główne komponenty PMC: 1.​ Rejestry – małe, szybkie pamięci przechowujące dane i wyniki operacji. 2.​ Licznik rozkazów (PC, Program Counter) – przechowuje adres aktualnie wykonywanej instrukcji. 3.​ ALU (Jednostka Arytmetyczno-Logiczna) – wykonuje operacje matematyczne i logiczne.  4.​ Magistrale danych i adresów – umożliwiają komunikację między podzespołami. Działanie PMC: ​ Program jest sekwencją instrukcji zapisanych w pamięci operacyjnej. ​ Licznik rozkazów wskazuje aktualną instrukcję do wykonania. ​ ALU wykonuje operacje na danych i zapisuje wyniki w rejestrach lub pamięci. Podstawowe składniki komputera Każdy komputer składa się z kilku kluczowych elementów: 1. Procesor (CPU – Central Processing Unit) ​ Odpowiada za wykonywanie instrukcji programów. ​ Składa się z: ○​ Jednostki sterującej (CU – Control Unit) – odpowiada za sterowanie wykonywaniem programu. ○​ Jednostki arytmetyczno-logicznej (ALU – Arithmetic Logic Unit) – wykonuje operacje matematyczne i logiczne. ○​ Rejestrów – przechowują dane tymczasowe. 2. Pamięć operacyjna (RAM – Random Access Memory) ​ Przechowuje programy i dane w czasie wykonywania. ​ Jest ulotna – dane są tracone po wyłączeniu komputera. 3. Pamięć masowa ​ Służy do trwałego przechowywania danych. ​ Rodzaje pamięci masowej: ○​ Dyski HDD – klasyczne dyski twarde o dużej pojemności. ○​ Dyski SSD – szybsze, ale droższe od HDD. ○​ Nośniki optyczne (CD/DVD) i pamięci flash (pendrive, karta SD). 4. Urządzenia wejścia/wyjścia (I/O – Input/Output) ​ Służą do komunikacji użytkownika z komputerem. ​ Przykłady urządzeń wejściowych: ○​ Klawiatura, mysz, skaner, mikrofon. ​ Przykłady urządzeń wyjściowych: ○​ Monitor, drukarka, głośniki. 5. Magistrale systemowe ​ Łączą różne elementy komputera. ​ Rodzaje magistral: ○​ Magistrala danych – przesyła dane między komponentami. ○​ Magistrala adresowa – wskazuje adresy pamięci. ○​ Magistrala sterująca – zarządza przepływem danych.