Wstęp do informatyki Flashcards
Wstęp do informatyki
Omów podstawowe elementy komputera von Neumanna i cykl jego pracy. Czym jest licznik rozkazów i do czego służy?
P230
Elementy:
* CPU = ALU (jednostka arytmetyczno-logiczna) + jednostka sterujaca, kontrolująca przepływ informacji w komputerze
* Pamięć - magazynuje dane i instrukcje. Jest jednorodna - przechowuje zarówno dane jak i programy
* Urządzenia IN/OUT
* Magistrala - system połączeń zapewniający komunikację między
Cykl pracy:
1. Pobranie instrukcji
2. Dekodowanie
3. Pobranie danych
4. Wykonanie instrukcji
5. Zapis wyników
6. Aktualizacja licznika rozkazów
Licznik rozkazów:
Licznik rozkazów, znany również jako rejestr instrukcji, to specjalny rejestr w CPU, który przechowuje adres (lokalizację w pamięci) instrukcji, która ma być jako następna wykonana przez procesor.
Jest to kluczowy element w procesie kontrolowania przepływu programu, a jego aktualizacja jest niezbędna do ciągłego wykonywania ciągu instrukcji
Wstęp do informatyki
Podaj definicję maszyny Turinga-Posta, czym jest uniwersalny program Turinga-Posta?
P231
Jest to teoretyczny model obliczeń / matematyczna abstrakcja komputera służy do analizowania możliwości algorytmów oraz formalnych języków.
Maszyna składa się:
* Taśmy - nieskończona taśma podzielona na komórki, w których przechowywane sa symbole
* Głowica - element odczyt-zapis, może znajdować się na jednej z komórek taśmy
* Zestaw stanów - skończona liczba stanów wewnętrznych maszyny
* Tablica instrukcji - określa dla każdego stanu i symbolu na taśmie -> jaki symbol ma zostać zapisany na taśmie, kierunek przesunięcia, jaki ma być następny stan maszyny
Uniwersalny program Turinga-Posta
program symulujący działanie dowolnej maszyny Turinga-Posta; Możliwe bo program potrafi odczytać opis maszyny z taśmy oraz wykonać instrukcje maszyny na danych wejściowych. Pokazuje, że istnieje jeden program, który może wykonać obliczenia dowolnego innego programu.
Wstęp do informatyki
Omów stos (Stack), jako strukturę danych. Wymień operacje na stosie. Przedstaw implementację tych operacji poprzez operacje na liście.
P232
Liniowa struktura danych, na której operacje dodawania i usuwania odbywają się na jednym końcu - LIFO (Last In, First Out).
Operacje:
* Push(el) - dodaje element na wierzch stosu
~~~
self.list.insert(0, el)
~~~
* Pop() - usuwa element z wierzchu i zwraca jego wartość
~~~
return self.list.pop(0)
~~~
* Peek() - Zwraca wartość el z wierzchu, bez usuwania
~~~
return self.list[0]
~~~
* IsEmpty()
~~~
return len(self.list)==0
~~~
* Size() - liczba el. na stosie
~~~
len(self.list)
~~~
Wstęp do informatyki
Jakie jest założenie wstępne dotyczące wyszukiwania połówkowego (binary search)? Jakiego rzędu jest złożoność tego algorytmu? Przedstaw klasyfikację problemów algorytmicznych wg ich złożoności. W jakiej klasie tej klasyfikacji znajduje się algorytmu wyszukiwania połówkowego?
P233
Założenie wstępne - zbiór danych musi być posortowany!
Złożoność tego algorytmu to O(log n) - klasa P
Klasyfikacje problemów:
* P - deterministyczny wielomianowy
* NP - niedeterministyczny wielomianowy
* NP-hard - co najmniej tak trudne jak najtrudniejsze problemy NP; da sie je sprowadzić/zredukować w czasie wielomianowym
* NP-complete - najtrudniejsze problemy w klasie NP (zarówno w NP i NP-hard)
Wstęp do informatyki
Porównaj tablicową i wskaźnikową implementację listy. Przedstaw wady i zalety każdej z nich.
P234
Tablicowa implementacja
Plusy:
* prosta implementacja
* dostęp do elementów po indeksie
* Szybki dostęp do elementów w pamieci
Wady:
* Statyczny, ustalony z góry, rozmiar
* Czasochłonne usunięcie el ze środka tablicy
* Marnowanie pamięci jeśli lista nie jest ‘wypełniona’
Wskaźnikowa implementacja
Zalety:
* Dynamiczny rozmiar listy
* Edycja elementów w srodku jest szybka
* Wykorzystuje tyle pamięci ile potrzebuje
Wady:
* Bardziej złożona implementacja
* Wolniejszy dostęp do elementów po indeksie
* Mniejsza wydajność cache
