Teoria informatyki

Kilka słów (wstępu) o programowaniu

Generalnie programowanie jest czynnością polegającą na pisaniu programów ... czyli chodzi o to aby zmusić komputer do zrobienia czegoś. Wystarczy spojrzeć na hasło Język programowania w Wikipedii aby przekonać się jak bardzo wiele jest różnych języków programowania, jednak wymienienie tych istotnych nie jest większym problemem:

Asembler (zobacz w Sieci: Art of Assembly Language Programming and HLA by Randall Hyde, Asembler @ Wikibooks);
C, C++, Fortran;
C#, Java, JavaScript (zobacz skrypt rozwijanego menu i współpracujący arkusz CSS), Object Pascal, Objective-C, Visual Basic;
AWK, sh,
Perl, PHP, Python, Ruby, Tcl/Tk;
za języki programowania uważa się także niekiedy:
- znacznikowe języki formatowań: SGML, XML, HTML/XHTML (wraz z arkuszami styli CSS) - zobacz layout beztabelkowy źródła tej strony :-) a także zobacz zobacz w Sieci: opis składni języka HTML, Kurs języka HTML - poradnik webmastera, Pełny kurs HTML, XHTML i CSS z przykładami, HTML @ Wikibooks, CSS @ Wikibooks, SVG @ Wikibooks
- języki skaładu tekstu oraz inne języki specjalistyczne (np. zapytań baz danych): TeX (zobacz artykuł na temat (La)TeX'a), SQL (zobacz w Sieci: SQL ..., Bazy danych @ Wikibooks).

Jednak umiejętność programowania to nie jest znajomość jakiegoś języka, jest to raczej umiejętność logicznego myślenia, myślenia "jak zrobiłby to komputer" i znajomość (dość uniwersalnych) podstaw; dlatego też jeżeli umie się programować w jednym języku to umie się praktycznie w każdym (można bardzo łatwo się nauczyć). Więcej o podstawach programowania i o tym dlaczego warto używać bibliotek, korzystać z istniejących projektów/fragmentów kodu w wstęp do techniki.

Zainteresowanym polecam także wykłady dotyczące konstrukcji kompilatorów z strony domowej Jana Pustelnika.

Wprowadzenie do systemów operacyjnych

System operacyjny jest oprogramowaniem odpowiedzialnym za zarządzanie zasobami systemu komputerowego (sprzętem, ale nie tylko) oraz uruchomionymi na nim aplikacjami. Do najistotniejszych zadań systemu operacyjnego zalicza się podział czasu procesora i szeregowanie zadań oraz zarządzanie pamięcią - w szczególności obsługa pamięci wirtualnej, najczęściej z wykorzystaniem mechanizmu stronicowania.

Oprócz tego system zajmuje się także zarządzaniem plikami, wejściem/wyjściem (najczęściej jest ono realizowane w oparciu o przerwania, ale znane są także modele programowego we/wy polegającego na aktywnym czekaniu), obsługą sieci, itd. Część zadań realizowana jest z minimalnym udziałem procesora (a więc także i systemu) jest to na przykład transfer danych w trybie DMA polegający na tym iż dane kopiowane są całymi blokami bez udziału procesora do/z pamięci (system zajmuje się tylko inicjacją transmisji). Należy tu jednocześnie zaznaczyć iż w przypadku nie stosowania tej technologii dane też kopiowane są pomiędzy dyskiem a procesorem całymi blokami (minimum sektor) gdyż dysk (w odróżnieniu od pamięci operacyjnej) nie jest bezpośrednio dostępny dla procesora.

Współczesne systemy korzystają z co najmniej dwóch poziomów pracy - uprzywilejowanego poziomu "nadzorcy" w którym działa jądro systemu operacyjnego oraz trybu użytkownika (zobacz też tryb chroniony). Operacje I/O muszą odbywać się w trybie uprzywilejowanym. Również pamięć posiada obszar chroniony, w którym umieszczany jest m.in. wektor przerwań (inaczej zmiana adresu w tym wektorze mogłaby doprowadzić do przejęcia systemu w trybie uprzywilejowanym). Istotną rolą systemu operacyjnego w zarządzaniu procesami (obok czynności administracyjnych jak ich tworzenie powielanie, usuwanie, czy też wstrzymywanie itp) jest zapewnienie ochrony pamięci (każdy proces może pisać po swojej i ewentualnie współdzielonej gdy dostał do tego prawo) oraz procesora (przerwanie zegarowe powoduje wywołanie planisty, który ustala jaki proces dostanie następny kwant czasu procesora). Niektóre systemy wyróżniają obok procesów także wątki, które różnią się od nich współdzieloną (między wątkami jednego procesu) pamięcią i zasobami (np. otwartymi plikami). System operacyjny zapewnia także zestaw usług i funkcji (wywołań) systemowych zapewniających pośrednictwo między interfejsem trybu użytkownika a sprzętem.

Istotnym zadaniem systemu operacyjnego jest przeciwdziałaniem tzw. blokadom, czyli sytuacji gdy dwa lub więcej procesów blokują się wzajemnie w oczekiwaniu na zasoby (a ma zasób X, którego potrzebuje b aby zwolnić zasób Y, którego potrzebuje a do zwolnienia X). Realizowane to może być na kilka sposobów:

zapobieganie blokadzie (czyli niedopuszczenie do zajścia warunków koniecznych) - np. poprzez konieczność deklarowania wszystkich zasobów na początku, zwalniania przydzielonych zasobów przez zgłoszeniem zapotrzebowania na następne
unikanie blokady (czyli określamy maksymalne zapotrzebowanie i tak przydzielamy zasoby aby uniknąć zajścia blokady) - np. poprzez kontrolę czy po spełnieniu żądania dalej będziemy działać w stanie "bezpiecznym", tj takim że istnieje sekwencja (zwana bezpieczną) w której maksymalne zapotrzebowanie każdego procesu może być spełnione w oparciu o zasoby zwolnione przez procesy będące wcześniej w tej sekwencji oraz zasoby wolne, zobacz też: algorytm bankiera
wykrywanie i usuwanie blokady gdy do niej doszło

Planista procesora, czyli fragment systemu odpowiedzialny za przydzielanie procesora procesom, może pracować w trybie z wywłaszczaniem lub bez. W tym pierwszym wypadku proces otrzymuje kwant czasu procesora który może wykorzystać w całości (wtedy przejdzie z stanu wykonywania w stan gotowości) lub z niego wcześniej zrezygnować (gdy np. czeka na I/O, wtedy przejdzie z stanu wykonywania w stan oczekiwania). W drugim przypadku proces wykonuje swój kod do momentu aż sam odda procesor. Forma ta zbliżona jest do wykorzystywanej w szeregowaniu czasu rzeczywistego - proces będzie wywłaszczony tylko przez proces o wyższym priorytecie i będzie to natychmiastowe (przy najbliższym przerwaniu zegarowym) - zobacz priorytety.c. Istnieje wiele algorytmów szeregowania takich jak:

FCFS - pierwszy zgłoszony = pierwszy obsłużony
SJF - najkrótszy zgłoszony będzie pierwszym wykonanym (wersja z wywłaszczaniem - SRTF - gdy nowy najkrótszy pozostały), algorytm raczej nie do zastosowania praktycznego - trzeba by przewidywać długość wykonania
priorytetowe - zawsze o najwyższym priorytecie (jak wspomniałem wyżej wykorzystywane w systemach real-time
rotacyjne - każdy po kawałku, potem na koniec kolejki
kolejki wielopoziomowe - system z priorytetami, podziałem czasu pomiędzy kolejki, przenoszeniem procesów między kolejkami, ...

Drugą podstawową funkcją systemu operacyjnego, wspomnianą na początku, jest zarządzanie pamięcią. Zarządzanie pamięcią polega na odpowiednim mapowaniu adresów logicznych (używanych przez procesy) na adresy fizyczne (używane przez procesor), korzysta ono z wsparcia sprzętowego ze strony procesora. Jest to najczęściej realizowane w oparciu o wspomniany mechanizm stronicowania. Polega to na podziale pamięci dostępnej pamięci fizycznej na jednakowe bloki zwane ramkami oraz podziale pamięci logicznej na jednakowe bloki (o tej całej wielkości co ramki) zwane stronami. Strony które są wykorzystywane przez program są mapowane na dowolne ramki pamięci fizycznej (w przypadku gdy dana strona nie zamapowania - w zależności od okoliczności błąd braku strony lub błąd ochrony strony). Rozwiązuje to problem fragmentacji zewnętrznej, polegającej na braku spójnego obszaru pamięci o żądanej długości pomimo iż łączna ilość wolnej pamięci jest dostateczna, jednak nie rozwiązuje problemu fragmentacji wewnętrznej, polegającej na przydzielaniu zbyt dużych fragmentów pamięci dla procesu (a wręcz można powiedzieć że go pogłębia). Mechanizm ten wymaga trzymania tablicy wolnych ramek, tablicy stron dla każdego procesu (zawierającej przypisania mapowań stron danego procesu na ramki) oraz wykonywania tłumaczenia adresów logicznych (strona + przesunięcie na stronie). Także sama tablica stron procesu procesu może być stronicowania (mamy tablicę która informuje nas że przypisania stron w danym zakresie adresów są przechowywane w jakiejś ramce).

Strony i ramki mogą być współdzielone pomiędzy procesami (np. przy rozgałęzianiu procesu strony są kopiowane dopiero gdy zajdzie taka potrzeba). W przypadku braku miejsca w pamięci fizycznej wybrane strony nieaktywnego aktualnie procesu mogą być umieszczane na dysku (swap). Niekiedy może to powodować szamotanie procesu polegające na zbyt dużej liczbie wymian stron. Zawsze jednak prowadzi to do konieczności ustalania które strony najlepiej jest przenieść na dysk. Optymalne byłoby przenoszenie tych które najdłużej nie będą potrzebne (jednak z oczywistych względów jet to praktycznie nie do zrealizowania). Stosuje się różne algorytmy tego wyboru:

FIFO - usuwamy najdłużej będącą w pamięci
LRU - usuwanie tej do której najdawniej się odwoływano (licznik czasu, bit odniesienia, bit odniesienia w określonym czasie, bit modyfikacji)
LFU - usuwamy z najmniejszą liczbą odwołań
MFU - usuwamy z dużą liczbą odwołań

Alternatywną (i mniej wymagającą) wobec stronicowanie metodą zarządzania pamięcią jest segmentacja. W przypadku architektury x86 jest ona zawsze wykorzystywana jednak może być przykryta dużym segmentem na którym wykorzystujemy stronicowaniem. Wspomniany już mechanizm pamięci wirtualnej często rozumiany jest tylko jako stronicowaniem (lub segmentacja) na żądanie. Polega to na tym iż strony mapowane są na ramki dopiero w momencie zapisu do segmentu pamięci należącego do

Podstawy technologii baz danych

Modele danych są zbiorami zasad dotyczących: definicji danych, operowania danymi oraz integralności danych. Wyróżnić możemy hierarchiczny, sieciowy, relacyjny i obiektowy model danych. Oprócz nich mamy często też doczynienia z prostymi modelami danych (np. plik tekstowy o ustalonej strukturze jednak bez odniesień do zawartości innych plików).

W modelu hierarchicznym mamy doczynienia z związkami pomiędzy rekordami (nadrzędność i podrzędność), różnymi typami rekordów, rekordy posiadają klucze (unikalne identyfikatory). Dane w tym modelu mają strukturę drzewiastą, utworzoną przez rekordy nadrzędne i podrzędne, nie da się usunąć rekordu bez usuwania rekordów podrzędnych wobec niego. Przykładem takiej bazy danych jest system plików. W modelu sieciowym oprócz zwykłych pól posiadamy pola kolekcji zawierające odniesienia do innych rekordów.

W modelu relacyjnym (RDBMS) relacje zazwyczaj reprezentowane są przez tabele stanowiące nieuporządkowany zbiór rekordów o atrybutach określonych w kolumnach. Kolumny, również stanowiące nieuporządkowany zbiór, określają typy wartości pól. Pola są wartościami atomowymi lub wartością NULL. Wyróżnia się klucze główne (stanowiące unikalny identyfikator rekordu w tabeli) oraz klucze obce stanowiące powiązania pomiędzy tabelami - kolumny będące kluczami obcymi muszą mieć ten sam typ co klucz główny tabeli do której mają prowadzić klucze obce. Powiązania takie tworzy się przez wstawianie do kolumny klucza obcego odpowiednich wartości klucza głównego. Operacje na danych opisuje algebra relacyjna możliwa jest:

selekcja
rzut - wybór podzbioru wierszy
iloczyn kartezjański - w sensie teorii mnogości, w wyniku otrzymujemy iloczyn ilości wierszy i sumę ilości kolumn
równo-złączenie - z iloczynu kartezjańskiego wybieramy tylko wiersze spełniające równość pomiędzy dwiema kolumnami o tym samym typie z dwóch tabel (klucz główny = klucz obcy)
złączenie naturalne - z równo-złączenia usuwamy powtórzenia kolumn
złączenie zewnętrzne - podobnie jak złączenie naturalne tyle że gdy nie ma pasującego to wstawiamy wiersz z tabeli uprzywilejowanej a w miejscu pól z drugie wstawiamy NULL
suma - w sensie teorii mnogości
przecięcie - w sensie teorii mnogości
różnica - w sensie teorii mnogości

Baza zapewnia także integralność danych, w szczególności integralność referencyjną - dotyczącą kluczy głównych i obcych (nie jest możliwe usunięcie wiersza na który wskazują klucze obce bez usuwania wierszy wskazujących, nie jest możliwe dodanie wiersza z kluczem obcym wskazującym na nieistniejący wiersz, nie jest możliwe dodanie wiersza powodujące zduplikowanie klucza głównego. Z zachowaniem poprawnością danych w modelu relacyjnym związane są więzy. Są to narzucone przez projektanta ograniczenia i dodatkowe relacje które muszą być spełniane przez wartości danego pola.

W modelu obiektowym występuje niejednorodna struktura danych zawierająca (obok wartości - atrybutów) także procedury. W modelu tym występuje "jednoznaczna tożsamość", oznacza to że mamy te same atrybuty i metody, ale różne obiekty (danego typu). Procedury związane związane z obiektem nazywane są metodami. Wzorce wg których tworzone są obiekty (typ obiektu) określany jest mianem klasy. Model ten umożliwia dziedziczenie, czyli tworzenie klas potomnych na bazie już istniejących przez ich modyfikację oraz zapewnia enkapsulację czyli ukrycie szczegółów implementacji tak aby nie były dostępne z zewnątrz ("to co w środku nieważne").

Drugą sprawą z teorii baz danych, którą trzeba poruszyć jest normalizacja danych i tzw. postać normalna. Ma to na celu unikanie powtórzeń, redukcję anomalii w modyfikacji danych oraz uproszczenie reguł integralności. Anomaliami nazywamy efekt uboczny modyfikacji, wstawiania lub usuwania danych pociągający za sobą zbyt duże zmiany. Wyróżnia się kilka postaci normalnych, każda kolejna jest tą bliższą ideałowi:

1NF - każdy atrybut niekluczowy jest funkcyjnie zależny od klucza głównego ("bez powtórzeń ...")
2NF - dodatkowo każdy atrybut niekluczowy jest w pełni zależny od klucza głównego ("... pola zależą od klucza ...")
3NF - dodatkowo każdy atrybut niekluczowy jest bezpośrednio zależny od klucza głównego ("... od całego klucza ...")

Wprowadzenie do sieci neuronowych

Sieci neuronowe są systemami zdolnymi do przetwarzania danych w problemach trudno algorytmizowalnych. Cechują się odpornością na zniekształcenia danych, zdolnością do uczenia w oparciu o przykłady, zdolnością generalizacji (uogólniania). Dane przetwarzane są w sposób równoległy. Zobacz też: Sztuczna inteligencja.

Budowa sieci wielowarstwowych nie ma sensu w przypadku sieci liniowych, czyli takich w których wektor odpowiedzi y jest liniowo zależy od wektora wejściowego x. Dla pojedynczego neuronu wygląda to w sposób następujący - wyjście jest sumą iloczynu wartości wejścia i wagi odpowiedniego wejścia:

$y^{(m)} = W^{(m)} \ast x = \sum_{i=1}^n w_i^{(m)} x_i$

Dzieje się tak dlatego że każde odwzorowanie liniowe możemy zapisać jako macierz, a wynikiem mnożenia dwóch macierzy przez siebie (co odpowiada kolejnemu wykonaniu pierwszej i drugiej warstwy) jest macierz (czyli pojedyncza warstwa). Uczenie neuronu polega na modyfikacji macierzy wag W tak aby uzyskiwać lepszą odpowiedź. W przypadku uczenia z nauczycielem w oparciu o regułę delta chcemy minimalizować funkcję błędu 9w sensie najmniejszych kwadratów). Musimy zatem zmieniać wagi w kierunku przeciwnym do gradientu funkcji błędu:

$W' = W + \eta \delta X \qquad \delta = z -y$
$\frac{\partial Q}{\partial y} = -(z-y) = - \delta \qquad \frac{\partial y}{\partial W} = x \qquad \frac{\partial Q}{\partial W} = \frac{\partial Q}{\partial y} \frac{\partial y}{\partial W} = - \delta x_i$

Możliwe jest także uczenie bez nauczyciela (bez wiedzy o tym jaki powinien być wynik), w metodzie tej wzmocnieniu ulegają wagi dla których odpowiedź jest duża gdy sygnał pobudzający jest duży.

Celem możliwości tworzenia bardziej zaawansowanych odwzorowań wprowadza się elementy nieliniowe, w których wyjście jest funkcją ważonej sumy elementów wejściowych). Najprostszą realizacją nieliniowości jest y = {1, 0} w zależności od znaku pobudzenia.Uczenie odbywa się na podobnej zasadzie jak w przypadku sieci liniowej. Jednowarstwowa sieć nie jest na przykład w stanie realizować odwzorowania XOR, jednak trój-warstwowa sieć (a kolejne warstwy mają sens tylko dla sieci nieliniowych) jest w stanie reprezentować dowolny podział płaszczyzny, zatem także funkcję XOR. Uczenie sieci wielowarstwowych odbywa się poprzez rzutowanie błędu na wszystkie neurony stanowiące wejście mnożąc go przez wagę danego wejścia. Należy zaznaczyć iż więcej neuronów w warstwach ukrytych daje więcej płaszczyzn decyzyjnych, jednak nie zawsze przyczynia się to do lepszego wyniku. W uczeniu sieci nieliniowych spotkać się możemy także z problemem lokalnych minimów do których będą zbiegały wektory wag (pomimo iż nie jest to właściwe rozwiązanie).

Celem usprawnienia procesu uczenia stosuje się różne metody dodatkowe takie jak:

zanikanie wag - w każdym kolejnym kroku od wag odejmowany jest pewien czynnik
bezwładność - wartość zmiany z poprzednich iluś kroków wpływa na wartość obecnej zmiany
kontrola czy zmiana faktycznie przyczyniła się do zmniejszenia funkcji błędu jak nie to cofamy
drgania termiczne - dodawanie losowej zmiany (zapobiega to wpadaniu w minima lokalne)
stosowanie wstępnej obróbki danych
stosowanie innych procedur minimalizacji

Szczególnym rodzajem są sieci przesyłające żetony (CP) - jest to dwuwarstwowa sieć, w której pierwsza warstwa klasyfikuje otrzymany wektor (z pierwszej warstwy wybieramy tylko wynik z jednego neuronu - największy), każdy neuron drugiej warstwy na swoim wejściu dostaje tylko jedyną liczbę i produkuje w oparciu o nią wektor skojarzony. Sieć taka działa jak tablica przeglądowa. Sieci tego typu stosowane są np. do kompresji danych, analizy statystycznej, rozpoznawania mowy, itp.

Kolejnym typem sieci są sieci RBF. Sieci te posiadają pola receptorowe, trafienie w które powoduje aktywacje danej jednostki wejściowej, oczywiście pola te mogą na siebie nachodzić wtedy pobudzeniu ulega kilka jednostek. Warstwa wejściowa dokonuje klasyfikacji bodźców, a wyjściowa wykonuje operację liniową. Sieci te charakteryzują się dobrą interpolacją lecz kiepską ekstrapolacją.

Ostatnim omówionym tutaj rodzajem sieci są sieci Hopfielda. Są to sieci o połączeniach każdy z każdym (wektor wyjść podawany na wejścia). Sieci te mogą służyć do realizacji pamięci adresowanej treścią, do realizacji takiej koncepcji korzystamy z symetrycznych wag, wyjść mających wartości 1 i -1 i danych zależnością:

$S_i' = \textrm{sgn} \left( \sum_j w_{ij} s_j \right)$

Aktualizacja stanów jest asynchroniczna i realizowana poprzez aktualizację (losowo wybrana jednostka dokonuje aktualizacji). Sieci te korzystają z funkcji energetycznej danej zależnością:

$H=- {1 \over 2} \sum_{ij} w_{ij} s_i s_j$

Zobacz też: Sieci neuronowe (wykład na FUW).