Teoria obliczeń to dział informatyki. Jedną z gałęzi tego działu jest teoria złożoności obliczeniowej. W uproszczeniu można powiedzieć, że zajmuje się ona oszacowaniem wydajności czasowej i pamięciowej algorytmów. Teoria złożoności obliczeniowej bazuje na wielu modelach, które służą do łatwego porównywania algorytmów.

W n-elementowym zbiorze Z znaleźć element, którego wartość występuje więcej niż n/2 razy.

Element o takich własnościach nosi nazwę lidera. Lidera można znaleźć przy pomocy jednego z opisanych w poprzednim rozdziale algorytmów wyszukiwania najczęstszej wartości w zbiorze. Po znalezieniu takiej wartości sprawdzamy, czy liczba jej wystąpień jest większa od liczby połowy elementów zbioru Z. Jeśli tak, to mamy lidera. Jeśli nie, to zbiór Z nie posiada lidera.

Binarne:

Wyznaczymy element środkowy zbioru. Sprawdzimy, czy jest on poszukiwanym elementem. Jeśli tak, to element został znaleziony i możemy zakończyć poszukiwania. Jeśli nie, to poszukiwany element jest albo mniejszy od elementu środkowego, albo większy. Ponieważ zbiór jest uporządkowany, to elementy mniejsze od środkowego będą leżały w pierwszej połówce zbioru, a elementy większe w drugiej połówce.

Tablice z haszowaniem

W strukturach drzewiastych takich jak drzewa binarnych poszukiwań czy kopce, pozycja elementu w drzewie zależy od relacji zachodzącej między nim, a innymi elementami. W metodach haszujących (mieszających) pozycja elementu jest wyliczana na podstawie wartości elementu lub tzw. klucza, związanego z elementem.  Funkcję wyliczającą pozycję elementu w zbiorze nazywa się funkcją mieszającą lub haszującą (od ang. hash function). Własnością szczególną metod haszowania jest, że pozwalają one wykonać operacje wstawiania, usuwania i wyszukiwania elementu, z kosztem niezależnym od liczby elementów w zbiorze, tzn. z kosztem stałym ze względu na rozmiar danych. Struktury danych oparte na metodach haszowania nazywamy tablicami haszującymi (lub tablicami z haszowaniem, tablicami z mieszaniem). Są one najczęściej używanymi modelami abstrakcyjnej struktury słownika, o której była mowa w poprzednim punkcie wykładu.

Podstawowe operacje na drzewach to:

wyliczenie wszystkich elementów drzewa,

wyszukanie konkretnego elementu,

dodanie nowego elementu w określonym miejscu drzewa,

usunięcie elementu.

Stos (ang. Stack) – liniowa struktura danych, w której dane dokładane są na wierzch stosu i z wierzchołka stosu są pobierane (bufor typu LIFO, Last In, First Out; ostatni na wejściu, pierwszy na wyjściu). Ideę stosu danych można zilustrować jako stos położonych jedna na drugiej książek – nowy egzemplarz kładzie się na wierzch stosu i z wierzchu stosu zdejmuje się kolejne egzemplarze. Elementy stosu poniżej wierzchołka można wyłącznie obejrzeć, aby je ściągnąć, trzeba najpierw po kolei ściągnąć to, co jest nad nimi.

Kolejka (ang. queue) – liniowa struktura danych, w której nowe dane dopisywane są na końcu kolejki, a z początku kolejki pobierane są dane do dalszego przetwarzania (bufor typu FIFO, First In, First Out; pierwszy na wejściu, pierwszy na wyjściu).

Operacje związane z kolejką zwyczajowo nazywa się enqueue („zakolejkuj”) oraz dequeue („odkolejkuj”)[1]. Kolejka działa tak jak kolejka w sklepie i ma podobną strukturę. Składa się z początku (Front, Head) oraz końca (Back, Tail). Nowy element zawsze dodawany jest na końcu, analogicznie do klienta, który zawsze staje na końcu kolejki. Usunięcie z kolejki odpowiada obsłużeniu klienta w sklepie, czyli osoby, która aktualnie czekała najdłużej (tj. znajduje się z przodu kolejki).

Składnia oznacza reguły tworzenia wyrażeń języka z elementarnych symboli (alfabetu).

Z podanych trzech aspektów języka najbardziej zrozumiała jest składnia. Oznacza ona reguły tworzenia wyrażeń języka z elementarnych symboli (alfabetu). Z matematycznego punktu widzenia składnia jest (zwykle nieskończonym) zbiorem ciągów symboli alfabetu. Taka definicja składni (często spotykana w podręcznikach pisanych przez matematyków) jest niekompletna i mało wartościowa z punktu widzenia definicji języka. Istotną cechą składni są reguły składniowe określające sposób budowania wyrażeń języka. Jakkolwiek reguły te rzeczywiście określają zbiór poprawnych ciągów alfabetu, stanowią one nieodłączny element definicji języka, niezbędny do definicji jego dalszych cech. W szczególności, może się zdarzyć, że różne zestawy reguł składniowych R₁ i R₂generują dokładnie taki sam zbiór ciągów symboli alfabetu, ale zestaw R₁ jest poprawny z punktu widzenia definicji tego języka, podczas gdy zestaw R₂ jest niepoprawny. Powodem poprawności bądź niepoprawności składni jest semantyka przypisana do konstrukcji składniowych.

Semantyka określa znaczenie wyrażeń języka, czyli stosunku napisów tego języka do rzeczy, które te napisy wyrażają lub oznaczają.

Ogólna definicja semantyki nie jest tak prosta jak definicji składni, gdyż wymaga co najmniej zdefiniowania wspomnianych „rzeczy”, czyli pewnej dziedziny znaczeń, pewnego uniwersum dyskusji o znaczeniach. Definicja takiej dziedziny nie jest jednoznaczna i zależy od tego, na jakim poziomie definiujemy semantykę, kto jest odbiorcą naszej definicji i jaki jest cel definicji.

Rekurencja jest to sytuacja, w której funkcja (czy też w naszym przypadku metoda) wywołuje samą siebie w celu rozwiązania pewnego problemu – stąd m.in. słynne już powiedzenie żeby zrozumieć rekurencję, trzeba zrozumieć rekurencję. W wielu sytuacjach pozwala w znaczny sposób uprościć zapis iteracyjnego rozwiązania naszego problemu (na przykład skomplikowanej pętli) – jednak jak się później dowiesz, nie zawsze jest to dobry pomysł. W tym momencie może Ci się także wydawać, że metoda wywołując samą siebie doprowadzi do sytuacji typu nieskończona pętla – i tak może się zdarzyć, jednak dzięki odpowiedniemu zapisowi można się przed tym zabezpieczyć.

Kod uzupełnień do dwóch (w skrócie U2 lub ZU2) – system reprezentacji liczb całkowitych w dwójkowym systemie pozycyjnym. Jest obecnie najpopularniejszym sposobem zapisu liczb całkowitychw systemach cyfrowych. Jego popularność wynika z faktu, że operacje dodawania i odejmowania są w nim wykonywane tak samo jak dla liczb binarnych bez znaku. Z tego też powodu oszczędza się na kodach rozkazów procesora.

Nazwa kodu wzięła się ze sposobu obliczania liczb przeciwnych. Dla jednobitowej liczby wartość przeciwną obliczamy odejmując daną liczbę od 2 (uzupełniamy jej wartość do dwóch). Analogicznie, dla liczb n-bitowych wartości przeciwne uzyskujemy odejmując liczbę od dwukrotnej wagi najstarszego bitu (2·2ⁿ⁻¹ = 2ⁿ). W analogiczny sposób można stworzyć np. kod uzupełnień do jedności. Zaletą tego kodu jest również istnienie tylko jednego zera. Przedział kodowanych liczb nie jest przez to symetryczny. W U2 na n bitach da się zapisać liczby z zakresu: {\displaystyle [-2^{n-1}\quad ,\quad 2^{n-1}-1]}Dla reprezentacji 8-bitowej (jednobajtowej) są to liczby od −128 do 127. Liczba −2ⁿ⁻¹ nie ma liczby przeciwnej w n-bitowej reprezentacji kodu U2.

Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów.

Złożoność obliczeniową określamy jako funkcję danych wejściowych algorytmu. Mierzymy więc zatem liczbę operacji wykonanych na modelu. Następnie próbujemy znaleźć funkcję, która będzie opisywała liczbę operacji w zależności od wejścia algorytmu. Funkcje te możemy porównywać ze sobą.

Semantyka językoznawcza (gr. σημαντικός, sēmantikós – ’ważny, znaczący’) – dział językoznawstwa ogólnego, część semiotyki (ogólnej dyscypliny zajmującej się systemami znakowymi) badający problem znaczenia w języku, a także relacji formy znaku do treści oznaczanej, w ujęciu synchronicznym i diachronicznym. Semantyka bada ponadto relacje między znaczeniem podstawowym wyrazu a jego znaczeniem w konkretnym wypowiedzeniu.

Fleksja – to dział gramatyki zajmujący się opisem odmiany wyrazów.

Algorytm Levenshteina, służy do liczenia odległości edycyjnej (odległości Levenshteina). Jest to najmniejsza liczba działań prostych, przeprowadzająca jeden napis w drugi.
Działania proste to:

• wstawienie nowego znaku
• usuniecie znaku
• zamiana na inny znak

Idea algorytmu to stworzenie tablicy dwuwymiarowej, o wymiarach n+1 na m+1 gdzie n i m to odpowiednio długości porównywanych słów.
Pierwszy wiersz i kolumnę uzupełniamy wartościami od 0 do, odpowiednio n i m.
Następnie bierzemy po kolei wartości wiersza i porównujemy literkę dotyczącą tego wiersza z literą dotyczącą kolumny. Dokonujemy porównania liter na zasadzie każdy z każdym. Przy każdym porównaniu wykonujemy poniższą procedurę. Jeśli literki są identyczne, ustawiamy koszt na 0, jeśli nie, na 1. Teraz musimy daną komórkę wypełnić wartością, którą będzie minimum z:

• wartości komórki leżącej bezpośrednio nad naszą aktualną komórka zwiększonej o 1,
• wartości komórki leżącej bezpośrednio w lewo od naszej aktualnej komórki + 1
• wartości komórki leżącej bezpośrednio w lewą-górna stronę od aktualnej komórki + koszt

Po wykonaniu wszystkich porównań, naszą odległością edycyjną będzie wartość w komórce [n+1, m+1].

Odległość Levenshteina pomiędzy napisami identycznymi, np.

pies

pies

jest zerowa – skoro są identyczne, to potrzeba zero działań, by jeden z nich przeprowadzić na drugi.

Odległość Levenshteina pomiędzy napisami:

granat

granit

wynosi 1, ponieważ do przeprowadzenia pierwszego na drugi wystarcza jedno działanie: zamiana litery a na i.

Prawo Zipfa lub prawo Estoupa-Zipfa – prawo opisujące zasadę częstotliwości użycia w dowolnym języku poszczególnych wyrazów. Głosi ono, że jeżeli dla jakiegokolwiek tekstu lub grupy tekstów ustala się wykaz wyrazów ułożonych w malejącym porządku częstotliwości ich występowania, to ranga rośnie w miarę zwiększania się numeru na wykazie (czyli w miarę zmniejszania się częstotliwości). Oznacza to, że częstotliwość jest odwrotnie proporcjonalna do rangi czyli iloczyn częstotliwości i rangi powinien być wielkością stałą^[1].

nazwa dla powszechnie stosowanego w informatyce abstrakcyjnego typu danych, który przechowuje pary (unikatowy klucz, wartość) i umożliwia dostęp do wartości poprzez podanie klucza. Formalnie typ tablicy asocjacyjnej odpowiada zbiorowi skończonych funkcji częściowych z typu klucza tablicy w typ wartości tablicy. Wiele złożonych danych jest naturalnie reprezentowanych przez tego typu tablice – np. drzewa plików, nagłówki poczty, a nawet wszystkie atrybuty obiektu czy przestrzeń nazw zmiennych.

każda składowa wektora odpowiada jednemu słowu ˙(tokenowi),  wymaga ustalenia pewnego słownika (bazy przestrzeni), umożliwia matematyczne traktowanie tekstu, zachowuje informację o częstotliwości występowania słów, traci informacje o kolejności słów oraz o gramatyce

„Ala ma kota” i „Kot ma Alę” (po sprowadzeniu do form podstawowych) mają taką samą reprezentację, stosowane głównie w przypadku kolekcji dokumentów

System informacyjny – posiadająca wiele poziomów struktura pozwalająca użytkownikowi na przetwarzanie, za pomocą procedur i modeli, informacji wejściowych w wyjściowe. Natomiast system informatyczny jest wydzieloną, skomputeryzowaną, częścią systemu informacyjnego

W podejściu strukturalnym dąży się do formalnej analizy systemu.
W wyniku tej analizy tworzone są hierarchiczne struktury, których
elementami są: procesy, dane. związki zachodzące między nimi.
Cechą charakterystyczną tego podejścia jest oddzielne modelowanie
danych i procesów, wykorzystujące diagramowe i macierzowe
metody i techniki. Jest stosowana dla systemów informacyjnych organizacji lub dla dobrze widocznej dziedziny problemowej

Diagram klas, procesowy, relacyjny

To diagram w którym widzimy przepływ danych i tworzy się go żeby widzieć procesy zachodzące.

• Wymagania produktowe- Określają zachowanie produktu. Przykładami są
• wymagania efektywnościowe dotyczące szybkości działania systemu i jegozapotrzebowania na pamięć, wymagania niezawodności.

• Wymagania organizacyjne – Wynikają ze strategii i procedur w firmie klienta i w firmie wytwórcy.

• Wymagania zewnętrzne I Ta szeroka kategoria mieści wszystkie wymagania wynikające z czynników zewnętrznych. Obejmują m.in. wymagania współpracy, które definiują interakcje systemu z systemami innych firm i wymagania prawne.

Tendencji centralnej to dominanta,mediana i srednia.

Rozrzutu – rozstep, wariancje,odchylenie standardowe

Tworzenie przedzialu z okreslonym prawdopodobienstwem bliskim jendosci ktory bedzie zawieral nieznana prawdziwa wartosc parametru z ogolnej populacji

sprawdzanie sadow populacji poprzez jej wycinek,  wycinamy obszar krytyczny, nadajemy etapy weryfikacji (zalozenia, ustalenie H0 i HA, statystyka testowa etc), ustalamy prawdopodobienstwa, nadajemy hipoteze

Srednia wazona ilosci informacji w wiadomosci gdzie wagami prawdopodobienstwa nadania poszczegolnych wiadomości

Jest to strategia zachłanna ktora kompresuje dane w sposob zastepowania znakow pliku krotszymi kodami przez co mozna wykorzystac mniej bitow

Translacja- Tłumaczenie programu na język wewnętrzny komputera, wykonywane za pomocą wyspecjalizowanego programu, tzw. translatora. wyróżniamy dwa typy translacji:

Kompilacja- Przetłumaczenie programu w całości na język zrozumiały dla procesora tak, by mógł on być wykonywany przez komputer przy każdorazowym jego uruchomieniu. Jeśli kompilacja przebiegnie poprawnie, można uruchomić program. Raz skompilowany program nie wymaga już powtórnej operacji tłumaczenia. Do wykonania kompilacji służą programy narzędziowe – kompilatory

Interpretacja- Tłumaczenie programu tworzonego w jednym z języków programowania instrukcja po instrukcji, tak by każda wywołana instrukcja była wykonana przez komputer. Tłumaczenie następuje każdorazowo przy uruchomieniu programu.

analiza leksykalna – grupowanie ciągu znaków w tokeny które razem maja jakieś znaczenie
automat skocznony – iteracyjny model zachowania systemu – diagram stanów
wyrażenie reguralne – wzorce ktore opisuja lancuchy symboli

analiza syntaktyczna grupuje symbole leksykalne w hierarchie
automat ze stosem – skonczony automat ktory moze odkladac na stos
gramatyka – zbior symboli

Kod posredni pozwala odpalac to na wielu masyznach wirtualnych celem testow

konwersja z liczb calkowitych jest wykonywana jednorazowao
zmienna uzywana jednokrotnie moze byc usunieta