Untitled

Dane i ich reprezentacja

• Dane to uporządkowane informacje, które można przechowywać, przetwarzać i przesyłać w systemach komputerowych.
• Sposób reprezentacji danych wpływa na efektywność przetwarzania, szybkość operacji i łatwość wymiany informacji.

Podstawowe Typy Danych

• Całkowite: przechowują liczby całkowite.
• Zmiennoprzecinkowe: przechowują liczby z ułamkami.
• Logiczne: przechowują wartości prawda/fałsz (true/false).
• Strukturalne: tablice, listy, struktury.

Bity i Bajty

• Bit to najmniejsza jednostka informacji, przyjmuje wartość 0 lub 1.
• Bajt składa się z 8 bitów.
• Ciągi bitów mogą reprezentować wiadomości poprzez odpowiednie kodowanie.

Operatory Logiczne

• AND (&&): oba argumenty muszą być prawdziwe (1).
• OR (||): jeden argument musi być prawdziwy.
• NOT (!): neguje wartość.
• XOR: zwraca prawdę, gdy argumenty są różne.

Bramki Logiczne

• Bramki logiczne wykonują operacje logiczne na sygnałach wejściowych, generując sygnał wyjściowy.
• Działają w oparciu o algorytmy logiczne: AND, OR, NOT, NAND, NOR, XOR, XNOR.

Przerzutnik

• Układ pamięciowy przechowujący stan logiczny (0 lub 1).
• Pełniąc ważna rolę w technologii przetwarzania informacji jako element pamięci.

Sposoby Przechowywania Informacji

• Pamięć RAM.
• Dyski twarde.
• Nośniki optyczne.
• Pamięć flash.

Standardy Reprezentacji Danych Alfanumerycznych

• Standardy określają kodowanie znaków, np. ASCII, Unicode.
• Różnią się liczbą obsługiwanych znaków.

Systemy Liczbowe

• Pozycyjne: wartość cyfry zależy od pozycji (dziesiętny, binarny).
• Niepozycyjne: każda cyfra ma stałą wartość (rzymski).

Systemy Dwójkowy, Dziesiętny i Szesnastkowy

• Dwójkowy (binarny): używa cyfr 0 i 1.
• Dziesiętny: używa 10 cyfr (0-9).
• Szesnastkowy (heksadecymalny): używa 16 cyfr (0-9, A-F, gdzie A=10, F=15).
• Każda liczba może być reprezentowana w każdym systemie.

Cyfry w systemach

• Binarny: 0, 1.
• Dziesiętny: 0-9.
• Szesnastkowy: 0-9, A-F.

Zamiana Liczb

• Binarna na dziesiętną: przekształcenie liczby binarnej według pozycji bitów, np. (11010101_2 = 2^7 + 2^6 + 2^4 + 2^2 + 2^0 = 213_{10}).
• Dziesiętna na binarną: dzielenie liczby przez 2 i zapisywanie reszt w odwrotnej kolejności.
• Binarna na szesnastkową: grupowanie bitów po cztery od prawej i zamiana każdej grupy na odpowiednią cyfrę szesnastkową.

Błędy Przepełnienia i Niedomiaru

• Przepełnienie: wynik operacji przekracza zakres reprezentacji liczby.
• Niedomiar: wynik operacji jest zbyt mały, by go poprawnie reprezentować.

Dodawanie Liczb Binarnych

• Dodawanie odbywa się podobnie jak w systemie dziesiętnym, z uwzględnieniem przeniesienia.

Ułamki w Kodzie Dwójkowym

• Ułamki zapisuje się jako sumę potęg liczby 2, zaczynając od miejsc po przecinku.
• Każda cyfra po przecinku to wartość (\frac{1}{2^n}), gdzie n to pozycja cyfry.

Dodawanie Liczb Rzeczywistych w Kodzie Dwójkowym

• Dodawanie polega na dodawaniu części całkowitej i ułamkowej oddzielnie, uwzględniając przeniesienia.

Zapis Liczby w Kodzie Uzupełnieniowym do Dwóch

• Używa się n-bitowego systemu, gdzie najstarszy bit oznacza znak (0 - dodatnia, 1 - ujemna).
• Dla liczby ujemnej najpierw zapisuje się jej wartość bezwzględną, a potem wykonuje uzupełnienie do dwóch.

Oznaczanie Znaku w Notacji Uzupełnieniowej do Dwóch

• Znak liczby oznaczany jest przez najstarszy bit: 0 – dodatnia, 1 – ujemna.

Zależności Między Ciągami Bitów w Kodzie Uzupełnieniowym do Dwóch

• Ciąg bitów liczby ujemnej jest odwrotnością ciągu bitów liczby dodatniej (po dodaniu 1).

Wartość Liczbowa w Notacji Uzupełnieniowej do Dwóch

• Jeśli najstarszy bit to 0, liczba jest dodatnia.
• Jeśli najstarszy bit to 1, liczbę trzeba odwrócić, dodać 1 i pomnożyć przez -1.

Dodawanie Liczb ze Znakiem w Notacji Uzupełnieniowej do Dwóch

• Dodawanie odbywa się jak dla liczb bez znaku, uwzględniając przeniesienie.
• Przepełnienie oznacza błąd.

Dlaczego Odejmowanie Można Sprowadzić do Dodawania w Systemie z Uzupełnieniem do Dwóch

• Odejmowanie to dodanie przeciwnika (negacji).
• Negacja liczby to jej uzupełnienie do dwóch, więc odejmowanie to dodawanie liczby uzupełnionej.

Przepełnienie i Wykrywanie Przepełnienia

• Przepełnienie występuje, gdy wynik wykracza poza zakres reprezentacji.
• Można je wykryć, obserwując przeniesienia.

Zapis Liczby w Notacji z Nadmiarem

• Polega na dodaniu do liczby stałej wartości (nadmiaru), co pozwala na reprezentację liczb ujemnych.

Elementy Ciągu Bitów w Notacji Zmiennopozycyjnej

• Mantysa: przechowuje znaczące cyfry liczby.
• Wykładnik: określa potęgę, przez którą należy pomnożyć mantysę.
• Znak: określa, czy liczba jest dodatnia, czy ujemna.

Wartość w Notacji Zmiennopozycyjnej

• Wartość oblicza się jako mantysa * podstawa^(wykładnik).

Zapis Liczby w Notacji Zmiennopozycyjnej

• Liczbę przedstawia się w postaci mantysy i wykładnika.

Postać Znormalizowana Liczby

• Oznacza zapis liczby tak, aby mantysa była większa lub równa 1, ale mniejsza od 2.

Błędy Zaokrąglenia

• Występują, gdy liczba jest reprezentowana w systemie o ograniczonej precyzji.

Kolejność Wykonywania Operacji w Notacji Zmiennopozycyjnej

• Kolejność ma wpływ na dokładność, dlatego operacje, które zmieniają wykładnik, trzeba przeprowadzać w odpowiedniej kolejności.

Techniki Reprezentacji Obrazów

• Rastrowa (bitmapowa): obrazy reprezentowane przez siatkę pikseli.
• Wektorowa: obrazy opisane za pomocą figur matematycznych.
• Oparta na transformatach: np. reprezentacja w przestrzeni częstotliwości (np. transformacja Fouriera).

Cel Kompresji Danych

• Zmniejszenie objętości danych, oszczędność miejsca.

Metody Kompresji Danych

• Bezstratna: dane po dekompresji są identyczne z oryginałem.
• Stratna: część informacji jest tracona, ale zmniejsza to objętość.

Metoda Kodowania Grupowego

• Grupowanie podobnych elementów danych i zapisanie ich jako pojedynczą jednostkę.

Kodowanie Względne

• Zapisywanie różnicy między kolejnymi wartościami.

Kodowanie Zależne od Częstości Wystąpień

• Przypisywanie krótszych kodów do częstszych symboli.

Kodowanie Słownikowe

• Tworzenie słownika z powtarzających się fragmentów danych i zapisywanie odwołań do słownika.

Sposoby Kodowania Obrazów

• JPEG: kompresja stratna, idealna do zdjęć.
• PNG: kompresja bezstratna, do grafiki internetowej.
• GIF: kompresja bezstratna, ograniczona do 256 kolorów, do animacji.

Techniki Kodowania Filmów

• MPEG-4: kompresja obrazu i dźwięku, popularna w filmach i transmisjach strumieniowych.
• H.264: nowoczesny standard kompresji.
• HEVC (H.265): nowa generacja kompresji, lepsza jakość w mniejszych plikach.

Kodowanie Dźwięku

• Stratne (np. MP3, AAC): zmniejszenie rozmiaru pliku kosztem utraty jakości.
• Bezstratne (np. FLAC): pełna jakość, ale pliki są większe.

Błędy Komunikacji

• Mogą występować na różnych poziomach i wynikać z zakłóceń sygnału, błędów w transmisji, problemów z synchronizacją.

Techniki Minimalizacji Błędów Komunikacji

• Kody wykrywania błędów (np. suma kontrolna, CRC).
• Kody korekcji błędów (np. kody Hamminga, kody Reeda-Solomona).
• Redundancja.
• Protokół retransmisji.

Jednostki Opisywania Wielkości Danych

• Bajt (B): podstawowa jednostka, 8 bitów.
• Kilobajt (KB): 1024 bajty.

Wpływ Typu Danych

• Na rozmiar pamięci, zakres wartości, szybkość obliczeń, precyzję.

Elementy Niezbędne do Wykonania Algorytmu

• Sprzęt: komputery, procesory, pamięć.
• Oprogramowanie: system operacyjny, kompilatory, interpretery.

Algorytmika

• Zajmuje się opracowywaniem, analizowaniem i optymalizowaniem algorytmów.

Algorytmy w Czynnościach Codziennych

• Przepis kulinarny.
• Sortowanie książek.

Poziom Szczegółowości Algorytmu

• Szczegółowy opis kroków.
• Warunki brzegowe.
• Wejście i wyjście.

Akcje Podstawowe

• Najmniejsze, nierozkładalne operacje.
• Ważne jest uzgadnianie akcji podstawowych, aby algorytm działał spójnie i poprawnie.

Elementy Zadania Algorytmicznego

• Dane wejściowe.
• Kroki algorytmu.
• Dane wyjściowe.

Znaczenie Kolejności Wykonywania Akcji w Algorytmie

• Zmiana kolejności może prowadzić do błędów.

Struktury Przepływu Sterowania

• Warunkowe (np. instrukcja if).
• Pętle (np. for, while).
• Przerwania (np. break).

Sortowanie Bąbelkowe

• Porównywanie par sąsiednich elementów i zamiana, jeśli są w złej kolejności.
• Złożoność czasowa O(n^2).

Schematy Blokowe

• Graficzne przedstawienie algorytmów, używa się symboli:
  • Prostokąty: operacje.
  • Równoległoboki: wejście/wyjście.
  • Romb: decyzje, warunki.
  • Strzałki: przepływ sterowania.

Podprogramy

• Modularność, wielokrotne użycie, łatwiejsza konserwacja, testowanie i debugowanie.

Rekurencja

• Funkcja wywołuje sama siebie.
• Wymaga warunku zakończenia.

Metody Budowy Algorytmów

• Analityczna: analiza istniejących problemów i poszukiwanie algorytmów.
• Syntetyczna: tworzenie algorytmu od podstaw.

Związek Typu Danych z Akcjami Podstawowymi

• Typ danych określa, jakie operacje są dozwolone i jak są one przechowywane w pamięci.

Zmienne

• Zmienne to miejsca w pamięci, w których przechowywane są wartości, które wykorzystuje algorytm.
• Do przechowywania wyników, reprezentowania danych wejściowych i wyjściowych, przechowywania stanów.

Tablice Jednowymiarowe

• Przechowują kolekcję elementów tego samego typu, zorganizowanych w liniowy sposób.

Tablice Dwuwymiarowe

• Przechowują dane w postaci tabeli, składającej się z wierszy i kolumn.

Drzewo

• Struktura danych składająca się z węzłów połączonych krawędziami.
• Wykorzystywane do przechowywania danych, reprezentacji hierarchii, algorytmów przeszukiwania.

Sortowanie Drzewiaste

• Oparte na drzewie binarnym.
• Elementy:
  • Wartości w lewym poddrzewie są mniejsze.
  • Wartości w prawym poddrzewie są większe.

Listy LIFO i FIFO

• LIFO (Last In, First Out): ostatni na wejściu, pierwszy na wyjściu, np. stos (stack).
• FIFO (First In, First Out): pierwszy na wejściu, pierwszy na wyjściu, np. kolejka (queue).

Składnia Języków Programowania

• Precyzyjna składnia jest niezbędna, aby komputer mógł poprawnie zinterpretować program.
• Język musi zawierać: Reguły dotyczące słów kluczowych, Zasady używania nawiasów, średników, Definicje typów danych, Struktury kontrolne

Reguły Składniowe

• Reguły składniowe języka programowania przedstawione mogą być przy pomocy: Drzewa składniowe lub/i opis za pomocą przykładów.

Semantyka

• Oprócz składni i interpunkcji bardzo ważna jest semantyka danego język programowania. Składnia - określa poprawny sposób zapisywania instrukcji a semantyka - określa, co ta instrukcja faktycznie robi.
• Błąd Skladniowy doprowadzi do tego, że program się nie kompiluje za to błąd semantyczny sprawia, że program się skompiluje, ale się nie wykona lub wykona się niepoprawnie!

Sposoby Wykonywania Programu

• Etapy Niezbędne:
  • Pisanie programu
  • Kompilacjia
  • Liknowanie
  • Uruchomienie programu Istnieją różne sposoby wykonywania programu, np: Kompilacja, Interpretacja lub Kompilacja i interpretacja

Kompilacja i Interpretacja

• Kompilacja - Proces polega na tłumaczeniu całego programu na kod maszynowy przed jego uruchomieniem
• Interpretacja - Program jest tłumaczony i wykonywany linia po linii przez interpreter.

Język adresów symbolicznych

• Język programowania o bardzo niskim poziomie, który bezpośrednio odwzorowuje instrukcje procesora.

Uniwersalny język programowania

• Nie istnieje jeden uniwersalny język programowania, ponieważ: Różne potrzeby i zastosowania, Wydajność, Ewolucja technologii, Preferencje programistów

Metoda Dziel i Rządź

• Polega na dzieleniu problemu na mniejsze, łatwiejsze do rozwiązania podproblemy. - Metoda te jest stosowana w wielu algorytmach, takich jak:. Sortowanie szybkie (Quicksort) oraz Sortowanie przez scalanie (Merge sort)

Metoda Zachłanna

• Polega na podejmowaniu decyzji, które w danym momencie wydają się najlepsze lokalnie, z nadzieją, że prowadzą one do rozwiązania optymalnego. - Metoda ta jest stosowana w wielu algorytmach, takich jak: Kruskal's algorithm, Algorytm Dijkstry

Graf

• Graf to struktura danych składająca się z wierzchołków (nodów) i krawędzi (połączeń między wierzchołkami). Graf ma następujące typy: Graf Skierowany, Graf Spójny lub Graf Acykliczny.

Planowanie Dynamiczne

• Technika algorytmiczna, która polega na rozwiązywaniu problemów przez dzielenie ich na mniejsze podproblemy, które są rozwiązywane raz, a ich wyniki są zapisywane i wykorzystywane w kolejnych obliczeniach. -- przykłady: Problem plecakowy, Obliczanie liczb Fibonacciego

Sposoby Konstrulowania Algorytmów

• Istnieją następujące ogólne podejścia do konstrukcji algorytmów: Podział na mniejsze podproblemy, Optymalizacja lokalna lub Zastosowanie dynamicznego programowania.

Złożoność Projektów

• Złożoność projektów należy szacować z powodu tego aby móc podejmować decyzje o wyborze najlepszych rozwiązań (zwłaszcza w przypadku dużych zbiorów danych, złożonych obliczeń lub systemów wymagających szybkiej odpowiedzi).
• Na złożoność algorytmu wpływają: Czas działania algorytmu, Zużycie pamięci, Rodzaj danych, Optymalizacja

Transakcja Optymalizująca

• Polega na modyfikacji algorytmu lub kodu w celu poprawy jego wydajności bez zmiany jego funkcjonalności. Może to obejmować Optymalizację czasową - zmienia strukturę danych i ulepsza algorytm, Optymalizację pamięciową lub Optymalizację kompilatora

Notacja O()

• Służy do wyrażenia złożoności algorytmów w kontekście wzrostu czasu wykonywania lub pamięci w zależności od rozmiaru danych wejściowych