Notatki z informatyki - Systemy liczbowe, algorytmy, i operacje na danych PDF

1. Zdefiniuj pojęcie dane. Dane to uporządkowane informacje przedstawione w sposób umożliwiający ich przechowywanie, przetwarzanie i przesyłanie w systemach komputerowych. 2. Dlaczego sposób reprezentowania informacji jest ważny. Wpływa na efektywność jej przetwarzania, szybkość operacji or...

1. Zdefiniuj pojęcie dane. Dane to uporządkowane informacje przedstawione w sposób umożliwiający ich przechowywanie, przetwarzanie i przesyłanie w systemach komputerowych. 2. Dlaczego sposób reprezentowania informacji jest ważny. Wpływa na efektywność jej przetwarzania, szybkość operacji oraz możliwość łatwej wymiany informacji między systemami. 3. Podstawowe typy danych Całkowite: przechowują liczby całkowite Zmiennoprzecinkowe: liczby z ułamkami Logiczne: przechowują wartości true\false Strukturalne: tablice, listy, struktury 4. Co to jest bit i bajt. Bit to najmniejsza jednostka informacji, może przyjąć wartość 0 lub 1. Bajt składa się z 8 bitów. Ciągi bitów mogą reprezentować dowolne wiadomości poprzez odpowiednie kodowanie. 5. Znane operatory logiczne: AND (&&): oba argumenty muszą być prawdziwe (1) OR (||): przynajmniej jeden argument musi być prawdziwy NOT (!): neguje wartość XOR: Zwraca prawdę, gdy argumenty są różne 6. Co to są bramki logiczne: Bramki logiczne to podstawowe elementy w elektronice cyfrowej, które wykonują operacje logiczne na jednym lub kilku sygnałach wejściowych i generującymi pojedynczy sygnał wyjściowy. Ich działanie opiera się na algorytmach logicznych, takich jak AND, OR, NOT, NAND, NOR, XOR i XNOR. 7. Co to przerzutnik: Układ pamięciowy, przechowuje stan logiczny (0 lub 1). Ważne w technologii przetwarzania informacji jako elementy pamięci. 8. Sposoby przechowywania informacji Pamięć RAM Dyski twarde Nośniki optyczne Pamięć flash 9. Standardy reprezentacji danych alfanumerycznych Określają sposób kodowania znaków. Przykłady: ASCII, Unicode. Różnią się liczbą obsługiwanych znaków. 10. Pozycyjne i niepozycyjne systemy liczbowe: Pozycyjne: wartość cyfry zależy od pozycji (dziesiętny, binarny) Niepozycyjne: każda cyfra ma stałą wartość (rzymski) 11. Różnice między systemami dwójkowym, dziesiętnym i szesnastkowym: System dwójkowy (binarny): Liczby są reprezentowane tylko za pomocą cyfr 0 i 1. System dziesiętny: Jest to system powszechnie stosowany w życiu codziennym, używający 10 cyfr (0, 1, 2, 3, 4, 5, 6, 7, 8, 9). System szesnastkowy (heksadecymalny): Używa 16 cyfr: 0-9 i A-F, gdzie A=10, B=11, C=12, D=13, E=14, F=15. Czy każda liczba może być reprezentowana w każdym systemie?  Tak, każda liczba może być reprezentowana w każdym z tych systemów, chociaż liczba 1 w systemie dziesiętnym może być zapisana w różny sposób w innych systemach, w zależności od bazy (np. binarnie jako 1, heksadecymalnie jako 1). Cyfry w systemach: W systemie binarnym: 0, 1. W systemie dziesiętnym: 0-9. W systemie szesnastkowym: 0-9, A-F. 12. Zamiana liczb: Z binarnej na dziesiętną: Aby zamienić liczbę binarną na dziesiętną, przekształcamy ją według pozycji bitów: np. 11010101 = 12^7 + 12^6 + 02^5 + 12^4 + 02^3 + 12^2 + 02^1 + 12^0 = 213. Z dziesiętnej na binarną: Dzielimy liczbę przez 2 i zapisujemy reszty w odwrotnej kolejności: np. 213 dzielimy przez 2, otrzymujemy reszty 1, 0, 1, 0, 1, 0, 1 (od końca). Z binarnej na szesnastkową: Grupujemy bity po cztery od prawej, a każdą grupę zamieniamy na odpowiednią cyfrę szesnastkową: np. 11010101 = D5 w systemie szesnastkowym. 13. Błędy przepełnienia i niedomiaru: Błąd przepełnienia: Występuje, gdy wynik operacji przekracza zakres reprezentacji danej liczby (np. dodawanie liczb w systemie o ograniczonej liczbie bitów). Błąd niedomiaru: Występuje, gdy wynik operacji jest zbyt mały, by go poprawnie reprezentować w systemie liczbowym. 14. Dodawanie dwóch liczb binarnych: Dodawanie odbywa się podobnie jak w systemie dziesiętnym, z tym że operujemy tylko na 0 i 1, uwzględniając przeniesienie. Przykład: 01010101 + 00111011=10001100 15. Zapis ułamków w naturalnym kodzie dwójkowym: Ułamki w systemie dwójkowym zapisujemy poprzez rozwinięcie liczby w postaci sumy potęg liczby 2, zaczynając od 1 miejsc po przecinku (części ułamkowej). Każda cyfra po przecinku to wartość , gdzie n to pozycja cyfry. 2𝑛 16. Dodawanie liczb rzeczywistych w kodzie dwójkowym: Dodawanie liczb rzeczywistych w systemie dwójkowym polega na dodaniu części całkowitej i ułamkowej oddzielnie, stosując odpowiednie zasady dodawania binarnego, a następnie uwzględniając przeniesienia. Przykład: 10101.1112 +11011.00112 Dodajemy część całkowitą (10101 + 11011). Dodajemy część ułamkową (111 + 0011). Po wykonaniu operacji i uwzględnieniu przeniesień, uzyskujemy wynik. 17. Zapis liczby w kodzie uzupełnieniowym do dwóch: Aby zapisać liczbę w notacji uzupełnieniowej do dwóch, używamy n-bitowego systemu, gdzie najstarszy bit (MSB - most significant bit) oznacza znak (0 - liczba dodatnia, 1 - liczba ujemna). Dla liczby ujemnej najpierw zapisujemy jej wartość bezwzględną w binarnym zapisie, a potem wykonujemy operację uzupełnienia do dwóch (inwersja bitów + dodanie 1). Przykład: Dla -7 w systemie 4-bitowym: Zapisz 7 w systemie binarnym: 0111. Inwertuj bity: 1000. Dodaj 1: 1001. Więc -7 w 4-bitowym kodzie uzupełnieniowym do dwóch to 1001. 18. Oznaczanie znaku w notacji uzupełnieniowej do dwóch: W notacji uzupełnieniowej do dwóch znak liczby oznaczany jest przez najstarszy bit: 0 oznacza liczbę dodatnią. 1 oznacza liczbę ujemną. 19. Zależności między ciągami bitów w kodzie uzupełnieniowym do dwóch: Ciąg bitów reprezentujący liczbę ujemną w kodzie uzupełnieniowym do dwóch jest odwrotnością ciągu bitów liczby dodatniej (po dodaniu 1). Aby uzyskać wartość przeciwną, należy: Zainwertować wszystkie bity.  Dodać 1. 20. Wartość liczbowa w notacji uzupełnieniowej do dwóch: Aby obliczyć wartość liczby w kodzie uzupełnieniowym do dwóch: Jeśli najstarszy bit to 0, liczba jest dodatnia, a wartość jest równa binarnemu zapisowi liczby. Jeśli najstarszy bit to 1, liczba jest ujemna. Trzeba najpierw odwrócić bity, dodać 1 i pomnożyć przez -1. Przykład dla 1100 w 4-bitowym systemie: Inwertujemy bity: 0011. Dodajemy 1: 0100. Otrzymujemy 4, więc liczba jest -4. 21. Dodawanie liczb ze znakiem w notacji uzupełnieniowej do dwóch: Dodawanie liczb w kodzie uzupełnieniowym do dwóch odbywa się jak w przypadku liczb bez znaku, z tym, że uwzględniamy także przeniesienie w przypadku liczb ujemnych. W przypadku przepełnienia (wynik wykracza poza zakres reprezentacji), oznacza to, że doszło do błędu. 22. Dlaczego odejmowanie można sprowadzić do dodawania w systemie z uzupełnieniem do dwóch: W notacji uzupełnieniowej do dwóch, odejmowanie liczby to dodanie jej przeciwnika (negacji). Ponieważ negacja liczby w tym systemie to jej uzupełnienie do dwóch, odejmowanie sprowadza się do dodawania liczby uzupełnionej. 23. Przepełnienie i wykrywanie przepełnienia: Przepełnienie występuje, gdy wynik operacji matematycznej wykracza poza zakres reprezentacji (np. dodawanie dwóch dużych liczb w systemie o ograniczonej liczbie bitów). Można je wykryć, obserwując przeniesienia przy operacjach dodawania i odejmowania. 24. Zapis liczby w notacji z nadmiarem: Notacja z nadmiarem (ang. excess) polega na dodaniu do liczby pewnej stałej wartości (nadmiaru), co pozwala na reprezentację liczb ujemnych. Na przykład dla nadmiaru 8 (ang. excess-8): −7 w systemie z nadmiarem 8 zapisujemy jako 8+(−7) =1. 0 zapisujemy jako 8+0=8. 25. Elementy ciągu bitów w notacji zmiennopozycyjnej: W notacji zmiennopozycyjnej liczba składa się z trzech głównych elementów: Mantysa – liczba, która przechowuje znaczące cyfry liczby. Wykładnik – określa, na jaką potęgę liczby 2 (lub innej podstawy) należy pomnożyć mantysę. Znak – określa, czy liczba jest dodatnia czy ujemna. 26. Wartość w notacji zmiennopozycyjnej: Wartość w notacji zmiennopozycyjnej obliczamy jako mantysa x podstawawykładnik. Jeśli mamy liczbę w postaci binarnej, jest to mantysa x 2wykładnik Przykład: Dla liczby 11010010 w notacji zmiennopozycyjnej: Mantysa: 1.1010010 Wykładnik: 7 (przemieszczenie przecinka o 7 miejsc) Więc wynik to 1.1010010×27 27. Zapis liczby w notacji zmiennopozycyjnej: Aby zapisać liczbę w notacji zmiennopozycyjnej, musimy ją przedstawić w postaci mantysy i wykładnika. Dla przykładu: 2 Dla liczby 2 (czyli 2.75) w systemie dziesiętnym: 3 Przedstawiamy liczbę w formie dziesiętnej: 2.75. Przekształcamy ją do postaci binarnej: 2.75=10.112 W postaci zmiennopozycyjnej to 1.0112 ×21. 28. Postać znormalizowana liczby: Postać znormalizowana oznacza zapis liczby w taki sposób, aby mantysa była większa lub równa 1, ale mniejsza od 2 (w systemie binarnym). Dla liczb zmiennopozycyjnych w systemie binarnym zawsze staramy się przesunąć przecinek na początek mantysy. 29. Błędy zaokrąglenia: Błąd zaokrąglenia występuje, gdy liczba jest reprezentowana w systemie o ograniczonej precyzji (np. w komputerze mamy tylko ograniczoną liczbę bitów do przechowywania liczby). Zaokrąglenie powoduje, że wynik nie jest dokładny, a błąd zależy od liczby bitów w reprezentacji.  Przykład: Jeśli chcemy zapisać liczbę 0.1 w systemie binarnym, nie możemy jej zapisać dokładnie w skończonym systemie bitowym, co prowadzi do błędu zaokrąglenia. 30. Kolejność wykonywania operacji w notacji zmiennopozycyjnej: W systemie zmiennopozycyjnym, z racji na reprezentację liczb z ograniczoną precyzją, kolejność wykonywania operacji może mieć wpływ na dokładność wyników. Operacje, które zmieniają wykładnik, mogą prowadzić do utraty precyzji, dlatego ważne jest, aby przeprowadzać operacje w odpowiedniej kolejności, szczególnie przy dużych liczbach. 31. Techniki reprezentacji obrazów: Istnieje wiele metod reprezentacji obrazów, w tym: Reprezentacja rastrowa (bitmapowa) – obrazy są reprezentowane przez siatkę pikseli, każdy z przypisaną wartością koloru (np. JPEG, PNG). Reprezentacja wektorowa – obrazy są opisane za pomocą figur matematycznych (np. SVG, EPS). Reprezentacja oparta na transformatach – np. reprezentacja obrazu w przestrzeni częstotliwości (np. użycie transformacji Fouriera). 32. Cel kompresji danych: Celem kompresji danych jest zmniejszenie objętości danych, co pozwala zaoszczędzić miejsce w pamięci lub przyspieszyć przesyłanie danych. Kompresja może być bezstratna (gdzie dane po dekompresji są identyczne z oryginałem) lub stratna (gdzie część informacji jest tracona, ale zmniejsza to objętość, np. w przypadku zdjęć, audio). 33. Metoda kodowania grupowego: Kodowanie grupowe polega na grupowaniu podobnych elementów danych (np. powtarzających się wartości) i zapisaniu ich jako pojedynczą jednostkę, co pozwala na zaoszczędzenie miejsca. Przykładem jest kodowanie RLE (Run- Length Encoding), gdzie powtarzające się znaki są reprezentowane jako liczba i wartość. 34. Kodowanie względne (relatywne, różnicowe): Kodowanie względne polega na zapisywaniu różnicy między kolejnymi wartościami, a nie samych wartości. Metoda ta daje najlepsze wyniki, gdy wartości danych są bliskie siebie, ponieważ różnice są mniejsze i wymagają mniej bitów do zapisu. 35. Kodowanie zależne od częstości wystąpień: Kodowanie zależne od częstości wystąpień polega na przypisywaniu krótszych kodów do bardziej powszechnych symboli, a dłuższych kodów do rzadziej występujących symboli. Przykład: kodowanie Huffmana. 36. Kodowanie słownikowe (Lempela-Ziva): Kodowanie Lempel-Ziv polega na tworzeniu słownika z powtarzających się fragmentów danych. Zamiast przechowywać te fragmenty, zapisuje się odwołania do słownika. Popularne algorytmy oparte na tej metodzie to LZW (Lempel-Ziv-Welch), stosowane w GIF-ach i TIFF-ach. 37. Sposoby kodowania obrazów: Do kodowania obrazów stosuje się różne metody, zależnie od wymagań dotyczących jakości i rozmiaru pliku. Przykłady: JPEG – kompresja stratna, idealna do zdjęć. PNG – kompresja bezstratna, stosowana w grafice internetowej. GIF – kompresja bezstratna, ograniczona do 256 kolorów, wykorzystywana w animacjach. Różne formaty są stosowane, ponieważ różne aplikacje mają różne potrzeby związane z jakością obrazu, rozmiarem pliku i szybkością przetwarzania. 38. Techniki kodowania filmów: Kodowanie filmów obejmuje kompresję zarówno obrazu, jak i dźwięku. Najczęściej stosowane techniki to: MPEG-4 – kompresja obrazu i dźwięku, popularna w filmach i transmisjach strumieniowych. H.264 – nowoczesny standard kompresji wideo o wysokiej jakości i niskim rozmiarze pliku. HEVC (H.265) – nowa generacja kompresji, oferująca lepszą jakość w mniejszych plikach. 39. Kodowanie dźwięku: Kodowanie dźwięku, podobnie jak obrazów, może być stratne lub bezstratne. Kodowanie stratne, takie jak MP3 czy AAC, pozwala na znaczne zmniejszenie rozmiaru pliku kosztem pewnej utraty jakości. Kodowanie bezstratne (np. FLAC) zachowuje pełną jakość, ale pliki są większe. Kompresja dźwięku jest ważna, szczególnie w przypadku transmisji strumieniowej (np. w muzyce online), ponieważ zmniejsza obciążenie sieci i oszczędza miejsce w pamięci. 40. Jak można uporać się z błędami komunikacji? Błędy komunikacji mogą występować na różnych poziomach (fizycznym, łącza, aplikacji) i mogą wynikać z różnych przyczyn, takich jak zakłócenia sygnału, błędy w transmisji czy problemy z synchronizacją. Aby je zminimalizować, stosuje się różne techniki: Kody wykrywania błędów (np. suma kontrolna, CRC) – umożliwiają wykrycie błędów w przesyłanych danych. Kody korekcji błędów (np. kody Hamminga, kody Reed-Solomon) – umożliwiają nie tylko wykrycie błędów, ale i ich korekcję. Redundancja – przesyłanie tych samych danych kilkoma ścieżkami lub w różnych momentach, aby zredukować ryzyko utraty informacji. Protokół retransmisji – w przypadku wykrycia błędu, dane są ponownie wysyłane. 41. Jednostki używane do opisywania wielkości danych: Wielkości danych wyrażane są w jednostkach takich jak: Bajt (B) – podstawowa jednostka w informatyce, zwykle reprezentująca 8 bitów. Kilobajt (KB) – 1024 bajty. 42. Ile bajtów zawiera 12kB lub 2MB? 12 KB = 12 * 1024 bajtów = 12,288 bajtów. 2 MB = 2 * 1024 * 1024 bajtów = 2,097,152 bajtów. 43. Na co ma wpływ typ danych? Typ danych ma wpływ na sposób przechowywania i operacji na danych. Wybór odpowiedniego typu danych decyduje o: Rozmiarze pamięci – różne typy danych zajmują różną ilość pamięci (np. int zajmuje mniej miejsca niż double w większości języków programowania). Zakresie wartości – różne typy mają różne zakresy przechowywanych wartości (np. int może przechować liczby całkowite, ale ma określony zakres, podczas gdy long ma większy zakres). Szybkości obliczeń – operacje na różnych typach danych mogą wymagać różnej mocy obliczeniowej, np. operacje na liczbach zmiennoprzecinkowych są zwykle wolniejsze niż operacje na liczbach całkowitych. Precyzji – niektóre typy danych, jak np. liczby zmiennoprzecinkowe (float, double), mają różną precyzję i mogą wprowadzać błędy zaokrąglenia. 44. Jakie elementy systemu są niezbędne do wykonania algorytmu? Aby wykonać algorytm, niezbędne są: Sprzęt: komputery i urządzenia, które wykonują operacje obliczeniowe (procesory, pamięć). Oprogramowanie: system operacyjny, kompilatory, interpretery, które umożliwiają uruchomienie algorytmu oraz dostarczają odpowiednie środowisko do jego wykonania. Bez odpowiedniego sprzętu i oprogramowania algorytm nie może zostać uruchomiony. 45. Czym zajmuje się algorytmika? Algorytmika to dziedzina informatyki, która zajmuje się opracowywaniem, analizowaniem i optymalizowaniem algorytmów. Celem algorytmiki jest tworzenie efektywnych metod rozwiązywania problemów obliczeniowych, z uwzględnieniem takich aspektów jak czas i pamięć. 46. Przykład czynności, w której realizacji posługujesz się algorytmem? Każde działanie, które wymaga ustalonej procedury krok po kroku, to algorytm. Przykładem może być: Przepis na przygotowanie posiłku: zaczynasz od przygotowania składników, następnie wykonujesz kolejne kroki (np. mieszanie, gotowanie), a na końcu otrzymujesz gotowe danie. Sortowanie książek na półce: zaczynasz od podzielenia książek na kategorie, a potem sortujesz je według autora lub tytułu. 47. Jaki poziom szczegółowości jest niezbędny, by poprawnie zdefiniować algorytm? Aby poprawnie zdefiniować algorytm, należy określić: Szczegółowy opis kroków – każdy krok algorytmu powinien być jasny i jednoznaczny. Warunki brzegowe – należy uwzględnić przypadki wyjątkowe, które mogą wystąpić podczas działania algorytmu. Wejście i wyjście – algorytm musi być zdefiniowany w kontekście danych wejściowych i oczekiwanych wyników. 48. Co to są akcje podstawowe i po co należy je uzgadniać?  Akcje podstawowe to najmniejsze, nierozkładające się operacje, które algorytm wykonuje. Może to być np. porównanie dwóch liczb, dodanie ich czy przypisanie wartości. Uzgadnianie akcji podstawowych jest ważne, aby algorytm był spójny i działał poprawnie na każdym etapie. 49. Z jakich elementów składa się zadanie algorytmiczne? Zadanie algorytmiczne składa się z: Danych wejściowych – dane, które algorytm będzie przetwarzał. Kroki algorytmu – procedury i operacje, które algorytm wykonuje na danych. Danych wyjściowych – rezultaty, które algorytm zwraca po przetworzeniu danych wejściowych. 50. Dlaczego kolejność wykonywania akcji w algorytmie ma znaczenie? Kolejność wykonywania akcji w algorytmie ma kluczowe znaczenie, ponieważ zmiana kolejności operacji może prowadzić do różnych wyników lub błędów. Często algorytmy są projektowane w taki sposób, aby każde działanie opierało się na wynikach poprzednich operacji. Zmiana kolejności może wpłynąć na poprawność działania algorytmu, szczególnie w przypadku operacji zależnych od wyników wcześniejszych kroków. 51. Jakie znasz struktury przepływu sterowania? Struktury przepływu sterowania to mechanizmy, które decydują o kolejności wykonywania instrukcji w algorytmie: Warunkowe – np. instrukcja if, która wykonuje operację, gdy spełniony jest określony warunek. Pętle – np. for, while, które pozwalają powtarzać operacje do momentu spełnienia określonego warunku. Przerwania – np. break, które mogą natychmiastowo zakończyć pętlę lub blok kodu. 52. Jak działa sortowanie bąbelkowe? Sortowanie bąbelkowe to jeden z najprostszych algorytmów sortowania. Polega na porównywaniu par sąsiednich elementów w liście i ich zamianie, jeśli są w złej kolejności. Ten proces powtarza się wielokrotnie, aż lista będzie posortowana. Choć jest łatwe do zaimplementowania, jest mało wydajne (ma złożoność czasową O(n 2)). Przykład: Porównaj pierwszy i drugi element. Jeśli są w złej kolejności, zamień je miejscami. Powtarzaj ten proces dla wszystkich par sąsiednich elementów. Wykonaj krok 1 i 2 aż do momentu, gdy cała lista będzie posortowana. 53. Co to są schematy blokowe? Z jakich elementów je składamy? Podaj przykład. Schematy blokowe to graficzne przedstawienie algorytmów, w którym każdemu działaniu przypisany jest określony symbol. Używa się kilku podstawowych elementów: Prostokąty – reprezentują operacje (np. przypisanie, obliczenie). Równoległoboki – reprezentują operacje wejścia/wyjścia (np. wczytanie danych, wypisanie wyniku). Romb – reprezentuje decyzję, czyli warunek (np. if). Strzałki – wskazują przepływ sterowania. 54. Do czego w programach mogą się przydać podprogramy? (Jakie są korzyści z ich użycia?) Podprogramy (funkcje, procedury) w programach mają kilka ważnych zalet: Modularność – pozwala na podzielenie programu na mniejsze, bardziej zarządzalne części. Wielokrotne użycie – jeden podprogram może być wywoływany w różnych częściach programu. Łatwiejsza konserwacja – zmiany w jednej funkcji nie wymagają zmiany całego programu. Testowanie i debugowanie – mniejsze części programu są łatwiejsze do testowania i debugowania. 55. Co to jest rekurencja i do czego można ją wykorzystać? Rekurencja to technika, w której funkcja wywołuje sama siebie. Jest używana do rozwiązywania problemów, które można podzielić na mniejsze podproblemy o tej samej strukturze. Rekurencja jest często używana w: Sortowaniu – np. algorytm quicksort. Wyszukiwaniu – np. algorytm binarny. Obliczeniach matematycznych – np. obliczanie silni. Rekurencja wymaga, aby każde wywołanie miało warunek zakończenia (tzw. warunek podstawowy), aby uniknąć nieskończonego wywoływania funkcji. 56. Na czym polegają analityczna i syntetyczna metoda budowy algorytmów? Metoda analityczna polega na analizowaniu istniejących problemów i poszukiwaniu algorytmu, który efektywnie je rozwiązuje. Często polega na podziale problemu na mniejsze, łatwiejsze do rozwiązania podproblemy.  Metoda syntetyczna to podejście, w którym algorytm tworzymy od podstaw, uwzględniając specyfikę problemu i projektując odpowiednią strukturę rozwiązywania. 57. Dlaczego z typem danych związane są akcje podstawowe? Typ danych określa, jakie operacje są dozwolone i jak są one przechowywane w pamięci. Na przykład: Liczby całkowite – możemy na nich wykonywać operacje dodawania, odejmowania, mnożenia, dzielenia. Liczby zmiennoprzecinkowe – umożliwiają operacje na liczbach z częścią dziesiętną, ale wprowadzają większe ryzyko błędów zaokrąglenia. Tablice – operacje na tablicach obejmują dostęp do elementów przez indeks, dodawanie lub usuwanie elementów. Dlatego wybór typu danych ma bezpośredni wpływ na to, jakie operacje są dozwolone i jakie mają one właściwości. 58. Co to są zmienne i do czego można je wykorzystać w algorytmach? Zmienne to miejsca w pamięci, w których przechowywane są wartości, które mogą się zmieniać w trakcie działania programu. Zmienne są wykorzystywane w algorytmach do: Przechowywania wyników obliczeń. Reprezentowania danych wejściowych i wyjściowych. Przechowywania stanów w pętlach i warunkach. 59. Jak zorganizowane są dane, które możemy przechowywać w tablicach jednowymiarowych? Podaj przykłady. Tablice jednowymiarowe to struktury danych, które przechowują kolekcję elementów tego samego typu, zorganizowanych w liniowy sposób. Przykłady: Tablica liczb całkowitych: int numbers[] = {1, 2, 3, 4, 5}. Tablica znaków: char letters[] = {'A', 'B', 'C'}. Tablice są przydatne, gdy chcemy przechować wiele danych w jednej zmiennej i uzyskać do nich szybki dostęp za pomocą indeksów. 60. Jak zorganizowane są dane, które możemy przechowywać w tablicach dwuwymiarowych? Podaj przykłady. Tablice dwuwymiarowe to struktury danych, które przechowują dane w postaci tabeli, składającej się z wierszy i kolumn. Można je traktować jako tablicę tablic. Dane przechowywane w tablicy dwuwymiarowej są dostępne za pomocą dwóch indeksów (indeks wiersza i indeks kolumny). 61. Co to jest drzewo i do czego może się przydać? Drzewo to struktura danych, która składa się z węzłów połączonych krawędziami. Jeden z węzłów jest korzeniem, a pozostałe są jego potomkami. Drzewa są wykorzystywane w wielu różnych zastosowaniach, takich jak: Przechowywanie danych w bazach danych (np. drzewa binarne, B-drzewa). Reprezentacja hierarchii (np. systemy plików, organizacja katalogów). Algorytmy przeszukiwania (np. algorytm przeszukiwania drzewa w głąb – DFS, przeszukiwanie w szerz – BFS). Wyszukiwanie (np. drzewa poszukiwań binarnych do szybkiego wyszukiwania danych). 62. Opisz metodę sortowania drzewiastego. Sortowanie drzewiaste jest oparty na strukturze drzewa, najczęściej na drzewie binarnym. Jednym z przykładów jest sortowanie za pomocą drzewa binarnego poszukiwań (BST). W takim drzewie dla każdego węzła: Wartości w lewym poddrzewie są mniejsze. Wartości w prawym poddrzewie są większe. Algorytm polega na dodaniu elementów do drzewa w sposób taki, że po każdym dodaniu drzewa pozostają posortowane. Następnie wykonuje się in-order traversal (przejście w porządku in-order) po drzewie, aby uzyskać elementy w kolejności rosnącej. 63. Co to są listy LIFO i FIFO? LIFO (Last In, First Out) – "ostatni na wejściu, pierwszy na wyjściu". Jest to struktura danych, w której ostatni dodany element jest pierwszym, który zostanie usunięty. Przykładem jest stos (stack), gdzie operacje odbywają się poprzez push (dodanie na szczyt stosu) i pop (usunięcie z wierzchołka). FIFO (First In, First Out) – "pierwszy na wejściu, pierwszy na wyjściu". W tej strukturze pierwszy dodany element jest pierwszym, który zostanie usunięty. Przykładem jest kolejka (queue), w której operacje odbywają się za pomocą enqueue (dodanie na koniec kolejki) i dequeue (usunięcie z przodu kolejki). 64. Dlaczego programy wymagają precyzyjnej składni? Co zawiera formalna składnia języka programowania?  Precyzyjna składnia w językach programowania jest niezbędna, aby komputer mógł poprawnie zinterpretować i wykonać program. Składnia określa, w jaki sposób należy zapisać instrukcje, zmienne, operacje i inne elementy języka, aby były zrozumiane przez komputer. Formalna składnia języka programowania obejmuje: Reguły dotyczące słów kluczowych – np. if, else, for. Zasady używania nawiasów, średników i innych znaków interpunkcyjnych. Definicje typów danych – np. jak deklarować zmienne typu int, float, string. Struktury kontrolne – jak zapisywać warunki, pętle, funkcje itp. Składnia zapewnia jednoznaczność interpretacji kodu przez kompilator lub interpreter, eliminując możliwość błędów wynikających z niejednoznaczności w zapisie programu. 65. Jakie znasz sposoby przedstawiania reguł składniowych? Podaj przykłady. Reguły składniowe języka programowania mogą być przedstawiane na kilka sposobów: Drzewa składniowe – graficzne przedstawienie składni, gdzie korzenie i węzły reprezentują reguły gramatyki, a liście – terminale (np. zmienne, liczby, operatory). Opis za pomocą przykładów – np. zamiast formułowania reguł składniowych w sposób formalny, przedstawiamy przykłady kodu, które ilustrują prawidłową składnię. 66. Dlaczego oprócz składni i interpunkcji w języku programowania ważna jest semantyka? Semantyka języka programowania odnosi się do znaczenia instrukcji i operacji w programie, a nie tylko do ich poprawnego zapisu. Choć składnia określa poprawny sposób zapisywania instrukcji, semantyka określa, co ta instrukcja faktycznie robi. Dwa przykłady: Składnia: Instrukcja jest poprawnie zapisana (np. brak błędów interpunkcyjnych). Semantyka: Instrukcja działa zgodnie z oczekiwaniem (np. zmienna jest zainicjowana prawidłową wartością, pętla kończy się po odpowiednim czasie). Błąd składniowy sprawia, że program się nie kompiluje, podczas gdy błąd semantyczny sprawia, że program kompiluje się, ale wykonuje się niepoprawnie (np. wykonuje złe operacje). 67. Jakie etapy są niezbędne, by przejść od programu w języku programowania do jego wykonania przez komputer? Jakie znasz sposoby wykonywania programu przez komputer? Aby przejść od programu w języku programowania do jego wykonania przez komputer, należy wykonać następujące etapy: Pisanie programu – Programista tworzy kod w języku wysokiego poziomu. Kompilacja – Program w języku wysokiego poziomu jest przetwarzany przez kompilator, który tłumaczy go na kod maszynowy (lub kod pośredni, jak w przypadku języków takich jak Java). W wyniku powstaje plik wykonywalny. Linkowanie – Kompilator łączy poszczególne moduły i biblioteki w jeden plik wykonywalny. Uruchomienie programu – Program wykonywalny jest uruchamiany na komputerze, gdzie procesor wykonuje instrukcje zapisane w kodzie maszynowym. W zależności od języka programowania, istnieją różne sposoby wykonywania programu: Kompilacja – Języki takie jak C, C++ używają kompilatora do przekształcenia kodu źródłowego w kod maszynowy. Interpretacja – Języki takie jak Python czy Ruby używają interpretera, który wykonuje program bezpośrednio na etapie interpretacji kodu źródłowego, linia po linii. Kompilacja i interpretacja – Języki takie jak Java używają podejścia pośredniego, gdzie kod źródłowy jest najpierw kompilowany do kodu bajtowego, a następnie interpretowany przez maszynę wirtualną (JVM). 68. Czym różnią się od siebie kompilacja i interpretowanie programów? Kompilacja – Proces polega na tłumaczeniu całego programu na kod maszynowy przed jego uruchomieniem. Kompilator przetwarza cały kod źródłowy, tworząc plik wykonywalny, który można uruchomić na komputerze. Zaletą jest szybkie wykonanie programu po skompilowaniu, ponieważ nie wymaga on już dalszej analizy. Przykłady języków kompilowanych to C, C++, Rust. Interpretacja – Program jest tłumaczony i wykonywany linia po linii przez interpreter. Interpreter analizuje kod źródłowy w czasie rzeczywistym, co może spowolnić działanie programu, ponieważ każda linia musi być tłumaczona przed wykonaniem. Przykłady języków interpretowanych to Python, Ruby, JavaScript. 69. Co to jest język adresów symbolicznych? Język adresów symbolicznych (ASM, czyli Assembly Language) to język programowania o bardzo niskim poziomie, który bezpośrednio odwzorowuje instrukcje procesora. Używa on symbolicznych nazw dla operacji procesora (np.  MOV, ADD) oraz dla adresów pamięci, zamiast używać bezpośrednich wartości numerycznych. Język asemblera jest często używany w programowaniu systemowym oraz w przypadku, gdy potrzebna jest optymalizacja pod względem wydajności. 70. Dlaczego nie istnieje jeden uniwersalny język programowania, którego wszyscy mogliby się nauczyć i posługiwać przez całe życie? Nie istnieje jeden uniwersalny język programowania, ponieważ: Różne potrzeby i zastosowania – Różne języki programowania są dostosowane do różnych zastosowań, np. Python jest idealny do nauki, analizy danych i sztucznej inteligencji, podczas gdy C++ jest stosowany w programowaniu systemów operacyjnych i gier. Wydajność – Niektóre języki są bardziej wydajne w kontekście dużych aplikacji (np. C, C++), podczas gdy inne są bardziej zwięzłe i łatwiejsze w użyciu, ale mniej wydajne (np. Python). Ewolucja technologii – Języki programowania ewoluują w odpowiedzi na zmiany w technologii i wymaganiach rynku. Stąd pojawiają się nowe języki, które lepiej spełniają aktualne potrzeby. Preferencje programistów – Programiści często wybierają języki, które najlepiej odpowiadają ich doświadczeniu, preferencjom oraz rodzajowi projektów, które realizują. 71. Na czym polega metoda „dziel i rządź”? Metoda „dziel i rządź” polega na dzieleniu problemu na mniejsze, łatwiejsze do rozwiązania podproblemy. Te podproblemy są następnie rozwiązywane niezależnie, a wyniki są łączone, aby uzyskać rozwiązanie całego problemu. Metoda ta jest stosowana w wielu algorytmach, takich jak: Sortowanie szybkie (Quicksort) – dzieli tablicę na mniejsze części, sortuje je rekurencyjnie, a następnie łączy wyniki. Sortowanie przez scalanie (Merge sort) – dzieli tablicę na połowy, sortuje je, a następnie scala posortowane części. 72. Na czym polega metoda zachłanna? 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. Zachłanność polega na tym, że podejmujemy decyzję na każdym etapie, nie patrząc na całość problemu. Jest to efektywne w przypadku niektórych problemów, takich jak: Kruskal's algorithm do znajdowania minimalnego drzewa rozpinającego. Algorytm Dijkstry do znajdowania najkrótszej ścieżki w grafie. 73. Co to jest graf? Co oznacza, że graf jest skierowany, spójny, acykliczny? Graf to struktura danych składająca się z wierzchołków (nodów) i krawędzi (połączeń między wierzchołkami). Grafy są używane w wielu dziedzinach, od reprezentowania sieci komputerowych po analizę zależności w bazach danych. Graf skierowany – Graf, w którym krawędzie mają kierunek. Krawędź prowadzi od jednego wierzchołka do drugiego (np. zależności w systemie). Graf spójny – Graf, w którym istnieje ścieżka między każdą parą wierzchołków. Graf acykliczny – Graf, w którym nie istnieją cykle, tzn. nie ma ścieżki, która prowadzi z wierzchołka do tego samego wierzchołka. 74. Na czym polega planowanie dynamiczne? Planowanie dynamiczne (ang. dynamic programming) to 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. Jest to metoda optymalizacji, która eliminuje konieczność wielokrotnego rozwiązywania tych samych podproblemów, co przyspiesza algorytm. Zastosowanie znajduje w problemach, takich jak: Problem plecakowy. Obliczanie liczb Fibonacciego. 75. Czy istnieją ogólne sposoby konstruowania algorytmów? Uzasadnij. Tak, istnieją ogólne podejścia do konstrukcji algorytmów, takie jak: Podział na mniejsze podproblemy (np. metoda „dziel i rządź”). Optymalizacja lokalna (np. metoda zachłanna). Zastosowanie dynamicznego programowania.  Rekurencja – szczególnie w przypadku problemów, które mają strukturalną rekurencję (np. drzewo binarne). Te metody są uniwersalne i można je stosować do różnych typów problemów, chociaż nie każda metoda będzie odpowiednia dla każdego problemu. Wybór odpowiedniej metody zależy od konkretnego przypadku. 76. Dlaczego należy szacować złożoność projektów? Jakie czynniki mają największy wpływ na tę złożoność? Szacowanie złożoności algorytmów i projektów jest ważne, ponieważ pozwala na ocenę, czy rozwiązanie będzie wystarczająco efektywne w kontekście zasobów, które będą potrzebne do jego wykonania. Pomaga to w podejmowaniu decyzji 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. Czynniki wpływające na złożoność algorytmu: Czas działania algorytmu – okrśla, ile czasu potrzebuje algorytm na wykonanie obliczeń, w zależności od rozmiaru danych wejściowych. Mierzymy go zwykle za pomocą notacji O(). Zużycie pamięci – określa, ile pamięci RAM algorytm wymaga do przechowywania danych podczas swojego działania. Rodzaj danych – w zależności od typu danych (np. liczby, łańcuchy znaków, macierze), algorytmy mogą działać inaczej. Optymalizacja – różne implementacje algorytmu mogą mieć różne zużycie zasobów, dlatego wybór odpowiednich struktur danych i algorytmów wpływa na wydajność. 77. Na czym polega transformacja optymalizująca? Transformacja 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ą – np. poprzez zmianę struktury danych, użycie algorytmów o lepszej złożoności czasowej. Optymalizację pamięciową – zmniejszenie zużycia pamięci przez użycie bardziej efektywnych struktur danych. Optymalizację kompilatora – np. kompilator może przeprowadzić pewne optymalizacje kodu źródłowego, takie jak usuwanie niepotrzebnych obliczeń lub wykorzystanie instrukcji procesora, które przyspieszają działanie programu. 78. Omów notację O(). Notacja O (znana jako notacja dużego 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. Określa ona, jak algorytm skaluje się w miarę wzrostu rozmiaru danych. W skrócie: O(1) – Czas wykonania algorytmu jest stały, niezależnie od rozmiaru danych. O(n) – Czas wykonania rośnie liniowo w zależności od rozmiaru danych. O(n^2) – Czas wykonania rośnie kwadratowo, co jest typowe dla algorytmów oparte na podwójnych pętlach. O(log n) – Czas wykonania rośnie logarytmicznie, np. w przypadku algorytmu wyszukiwania binarnego. O(n log n) – Czas wykonania rośnie w sposób logarytmiczno-liniowy, np. w algorytmach sortujących takich jak Quicksort i MergeSort. Notacja ta pomaga w ocenie wydajności algorytmu w dużych zbiorach danych, gdyż koncentruje się na najistotniejszym czynniku (np. rosnącej liczbie operacji w zależności od rozmiaru danych). 79. Omów algorytm wyszukiwania binarnego. Algorytm wyszukiwania binarnego służy do znajdowania elementu w posortowanej tablicy (lub liście). Działa na zasadzie dzielenia problemu na pół: Sprawdzamy element w środku tablicy. Jeśli szukany element jest mniejszy, przeszukujemy tylko lewą połowę. Jeśli szukany element jest większy, przeszukujemy tylko prawą połowę. Powtarzamy ten proces dla połowy, aż znajdziemy element lub zdamy sobie sprawę, że elementu nie ma w tablicy. Czas działania algorytmu wynosi O(log n), ponieważ z każdym krokiem zmniejszamy rozmiar problemu o połowę, co daje szybsze wyszukiwanie niż w przypadku przeszukiwania liniowego (O(n)).