Informatyka

Na czym polega metoda zachłanna?

Polega na podejmowaniu decyzji optymalnej w danym kroku. Nie rozważa się, jak wybór wpłynie na kolejne kroki.

Podaj przykład problemu rozwiązywanego algorytmem zachłannym.

Np. problem wydawania reszty

Czy algorytm zachłanny zawsze daje rozwiązanie optymalne? Uzasadnij.

Nie, ponieważ nie rozważa jak wybór wpływa na kolejne kroki.

Na czym polega sortowanie szybkie (QuickSort)?

Polega na podzieleniu danych na takie fragmenty, aby każdy element pierwszego fragmentu był mniejszy lub równy każdemu elementowi drugiego fragmentu. Podział trzeba zaplanować tak, żeby do jego przeprowadzenia wystarczyło jednokrotne przejrzenie danych

Jak wybierany jest element pivot w QuickSort?

jako pierwszy element, ostatni element, element środkowy, losowy element lub medianę trzech elementów (pierwszego, środkowego i ostatniego). Najlepsze rozwiązanie to mediana z 3 losowych elementów aby minimalizowac ryzyko najgorszego przypadku.

Podaj złożoność QuickSort w najlepszym, średnim i najgorszym przypadku.

– najlepszy przypadek: O(n log n) (równy podział danych), – średni przypadek: O(n log n) (z wysokim prawdopodobieństwem), – najgorszy przypadek: O(n²) (pivot dzieli dane bardzo nierówno, np. gdy tablica jest posortowana).

Dlaczego QuickSort jest efektywny w praktyce?

cechuje się małymi narzutami pamięciowymi, wykonuje niewiele operacji porównań i zamian oraz dobrze wykorzystuje lokalność pamięci podręcznej procesora. średnia złożoność przy bardzo korzystnych stałych czasowych sprawia że jest szybszy niz inne sorty

Co to jest programowanie dynamiczne (i na czym polega jego idea?)

to metoda algorytmiczna w której problem rozwiązuje się poprzez rozwiązanie podproblemów dla mniejszych danych, w kolejności od najmniejszych od największych i odpowiednie wykorzystanie otrzymanych wyników

(Co to jest programowanie dynamiczne) i na czym polega jego idea?

Polega na znajdowaniu optymalnego rozwiązania na podstawie wcześniej znalezionych najlepszych rozwiązań dla pośrednich wartości danych

Podaj przykład problemu rozwiązywanego programowaniem dynamicznym.

problem plecakowy

Wyjaśnij różnicę między metodą 'dziel i zwyciężaj' a programowaniem dynamicznym.

diz rozwiązuje podproblemy które są od siebie niezależne, a ich wyniki wykorzystuje się tylko raz Programowanie dynamiczne stosuje się wtedy, gdy podproblemy nakładają się = te same podproblemy występują wielokrotnie dzięki czemu opłaca się je zapamiętać

Na czym polega działanie Sita Eratostenesa?

Polega na usunięciu ze zbioru liczb całkowitych z zakresu od 2 do n wszystkich liczb złożonych aby pozostały tylko liczby pierwsze

Jakie jest zastosowanie Sita Eratostenesa w informatyce?

Sito stosuje się do szybkiego generowania dużych zbiorów liczb pierwszych, szczególnie w kryptografii, algorytmach opartych na teoriach liczb, w zadaniach konkursowych oraz wszędzie tam, gdzie wymagane jest szybkie sprawdzanie pierwszości.

Co to jest anagram? Podaj przykład.

Anagram to słowo powstałe poprzez permutację liter innego słowa, przy zachowaniu tej samej liczby wystąpień każdej litery. Przykład: „listen” – „silent”, „ryba” – „bary”.

Jak można sprawdzić, czy dwa słowa są anagramami?

Można posortować znaki obu słów i porównać wyniki lub policzyć, ile razy dana litera występuje w każdym słowie. Jeśli dla każdej litery liczby są identyczne — słowa są anagramami.

Na czym polega szyfr Cezara?

Szyfr Cezara jest klasycznym szyfrem podstawieniowym, w którym każda litera alfabetu przesuwana jest o ustaloną wartość (np. o 3) w prawo lub lewo. Alfabet się zapętla więc po „a” zwróci się „z”

Jakie są wady szyfru Cezara?

Łatwość złamania – istnieje tylko 26 możliwych przesunięć w alfabecie łacińskim Brak bezpieczeństwa dla dużych wiadomości – powtarzające się litery i wzorce w tekście są łatwe do wykrycia Prostota – nie chroni przed nowoczesnymi metodami kryptoanalizy

Podaj przykład zastosowania szyfru Cezara w praktyce.

Praktyczne zastosowanie szyfru cezara jest edukacyjne lub zabawowe, np. kody w grach lub łamigłówkach, proste notatki prywatne Nie jest wykorzystywany w nowoczesnej kryptografii bo jest zbyt prosty

Co to jest podciąg w ciągu znaków?

Wybrane elementy ciągu wyjściowego zachowujące kolejność występowania

Wyjaśnij różnicę między podciągiem a podzbiorem.

Podciąg musi zachować kolejnośc występowania o podzbiór nie

Podaj przykład algorytmu wyszukiwania najdłuższego wspólnego podciągu.

Algorytm dynamiczny LCS

Na czym polega problem plecakowy?

Problem plecakowy polega na wybraniu podzbioru przedmiotów o określonych wartościach i wagach tak, aby zmieściły się w plecaku o ograniczonej pojemności, a suma wartości była maksymalna.

Jakie są metody rozwiązania problemu plecakowego?

Programowanie dynamiczne, metoda zachlanna, brute force

Podaj przykład zastosowania problemu plecakowego w praktyce.

pakowanie ładunku w samochodzie dostawczym

Co oznacza pojęcie 'lider' w tablicy liczb?

Lider (majority element) to element, który występuje w tablicy więcej niż n/2 razy.

Jak można znaleźć lidera w tablicy?

Posortować tablicę, sprawdzić czy element środkowy występuje więcej niż n/2 razy, jeśli tak to jest liderem

Co oznacza pojęcie 'idol' w kontekście algorytmów?

Idol to osoba, która jest znana przez wszystkie pozostałe osoby, ale sama nie zna nikogo.

Jakie są warunki istnienia idola w zbiorze osób?

1. jest znana przez wszystkie inne osoby, 2. nie zna żadnej innej osoby. Spełnienie obu warunków jest konieczne i wystarczające.

Podaj złożoność algorytmu wyszukiwania lidera.

Jeśli sprawdza się każdy element po kolei: n^2 Jeżeli przez sortowanie to złożoność jest zalezna od metody sortowanua

Dlaczego analiza złożoności jest ważna w projektowaniu algorytmów?

Analiza złożoności jest ważna, bo pozwala przewidzieć, jak szybko i efektywnie algorytm będzie działał wraz ze wzrostem rozmiaru danych.

Podaj przykład algorytmu o złożoności O(n²).

Buble sort Wyszukiwanie lidera przez sprawdzenie każdego elementu tablicy