Skip to content

Instantly share code, notes, and snippets.

@kamilturek
Last active January 28, 2021 15:23
Show Gist options
  • Save kamilturek/82a2afdb99ed1b1d55aedd5a77c7c618 to your computer and use it in GitHub Desktop.
Save kamilturek/82a2afdb99ed1b1d55aedd5a77c7c618 to your computer and use it in GitHub Desktop.
INF-IMT

1. Struktury medycznych systemów informatycznych - porównanie, wady i zalety

Wyróżniane struktury systemów informatycznych to systemy jednolite i systemy modułowe.

Systemy jednolite

Dostarczane w całości przez jednego dostawcę, który jest wyłącznym gwarantem ich niezawodności. Skupiają wszystkie funkcje użytkowe w obrębie jednego systemu.

Zalety

  • wysoki poziom integralności
  • łatwość konfiguracji
  • prosta koordynacja, utrzymanie i zarządzanie systemem

Wady

  • potencjalnie duże koszty
  • uzalenienie od twórcy systemu
  • mniejsza moliwość adaptacji do indywidualnych potrzeb placówki

Systemy modułowe

Zbudowane z pojedynczych komponentów oferowanych przez różnych dostawców. Moduły komunikują się ze sobą, tworząc w pełny funkcjonalny system.

Zalety

  • niskie koszty
  • niezaleność od dostawców
  • niezaleność w doborze platformy sprzętowej
  • moliwosć kompletacji systemu najlepiej dostosowanego do indywidualnych potrzeb placówki

Wady

  • zaawansowana konfiguracja
  • niski poziom integralnośći
  • trudniejsza koordynacja i zarządzanie oprogramowaniem
  • potencjalne niekompatybilności pomiędzy modułami

2. Gromadzenie informacji medycznych - klasyfikacje, rekordy pacjenta

Klasyfikacje

Uporządkowany zbiór pojęć odnoszący się do określonej dziedziny, posiadający formalne słownictwo.

Wymagania klasyfikacji

  • kompletność pojęć
  • niepowtarzalność nazw
  • jednolitość uporządkowania
  • jasne kryteria określające, rozdzielające klasy
  • kompletna i zrozumiała instrukcja użytkownika
  • odpowiedni poziom szczegółowości

Istnieje kilka zunifikowanych systemów klasyfikacji danych medycznych:

  • ICF (International Classification of Functioning, Disability and Health) - międzynarodowa klasyfikacja funkcjonowania, niepełnosprawności i zdrowia
  • ICD (International Classification of Diseases) - międzynarodowa klasyfikacja chorób
  • LOINC - uniwersalne nazwy i kody obserwacji medycznych

Rodzaje informacji medycznych

  • dane opisowe - historia chorób, zapisy przebiegów leczenia, wywiad z pacjentem
  • dane liczbowe - wyniki badań laboratoryjnych oraz pomiarów lekarskich (np. pomiar żelaza we krwi, waga, temperatura)
  • sygnały - dane w formie ciągłej, uzyskiwane przy pomocy medycznej aparatury pomiarowej (np. puls, częstość oddechu)
  • obrazy - uzyskiwane z urządzeń diagnostycznych (np. RTG, USG)

Rekordy pacjenta

  • papierowy rekord medyczny - archiwa, historie chorób
  • skomputeryzowany rekord medyczny - dokumentacja utworzona w postaci papierowej odwzorowana cyfrowo z zachowaniem atrybutów dokumentu papierowego (podpisy, daty, pieczątki)
  • elektroniczny rekord medyczny - dynamiczna kolekcja danych w formie elektornicznej tworzona przez personel medyczny, w celu umoliwienia realizacji opieki medycznej nad pacjentem
  • elektroniczny rekord pacjenta - elektroniczny rekord medyczny + dane kliniczne pacjenta, przebieg leczenia oraz diagnostyczne i terapeutyczne wyniki wykonywanych procedur
  • elektroniczny rekord zdrowotny - elektroniczny rekord pacjenta + dane środowiskowe, nawyki zdrowotne

3. Metody tworzenia harmonogramu projektu

Harmonogram to opis czynności wykonywanych w ramach projektu względem czasu. Jest najwaniejszą częścią projektu z punktu widzenia jego realizacji. Pozwala odpowiednio rozłoźyć zadania w czasie i oszacować budżet.

Metody sieciowe

Opierają się na specjalnych wykresach zwanych sieciami czynności. Wykorzystywane do harmonogramowania i kontroli złożoności przedsięwzięć gospodarczych, technicznych i organizacyjnych. Wykres sieciowy ilustruje przebieg całego przesięwzięcia bazując na dwóch zasadniczych elementach: czynnościach i zdarzeniach.

Czynności, czyli elementy pochłaniające zasoby, przedstawione są w formie prostych, siatki lub wektorów.

Zdarzenia, czyli momenty zakończenia jednej czynności, a rozpoczęcia następnej obrazowane są w formie punktów na przecięciach prostych.

Wyrózniamy kilka rodzajów zaleności pomiędzy zdarzeniami:

  • FS (ang. finish to start) - po zakończeniu czynności A zaczyna się czynność B
  • SS (ang. start to start) - zadanie B może zacząc się, gdy zacznie się zadanie A
  • FF (ang. finish to finish) - zadanie B może skończyć się dopiero po zakończeniu zadania A
  • SF (ang. start to finish) - zadanie A nie może zakończyć się przed rozpoczęciem zadania B

Metoda ścieżek krytycznych

Ścieka krytyczna to ciąg zdarzeń, w którym opóźnienie jednego powoduje opóźnienie kolejnych. Pozwala to w prosty sposób ustalić terminy zakończenia zadań w najgorszym i najlepszym przypadku. W planowaniu określa się:

  • ES (ang. early start) - najwcześniejszy moment rozpoczęcia zadania
  • EF (ang. early finish) - najwczesniejszy moment zakończenia zadania
  • LS (ang. late start) - najpóźniejszy moment rozpoczęcia zadania
  • LF (ang. late finish) - najpóźniejszy moment zakończenia zadania

Wykres Gantta

Graficzne przedstawienie zadań na osi czasu wraz z wykorzystywanymi przez nie zasobami. Ułożenie i podział ustala się według następujących kroków:

  1. Podział na cele (etapy)
  2. Ustalenie czasu trwania etapów i całego projektu
  3. Określenie kolejności etapów
  4. Definicja miejsca realizacji każdego z etapów
  5. Rozmieszczenie etapów na osi czasu

4. Zarządzanie ryzykiem i jakością w projekcie

Ryzyko

Procesem zarządzania ryzykiem nazywamy czynności podejmowane w celu identyfikacji, analizy oraz reagowania na nieprawidłowości występujące podczas przebiegu projektu. Ich zadaniem jest maksymalizacja zysku ze zdarzeń pozytywnych oraz minimalizacja start ze zdarzeń negatywnych.

Wśród podejmowanych czynności wyróżnia się:

  • identyfikację ryzyka - rozpoznanie problemu
  • kwalifikację ryzyka - określenie stopnia zagrożenia
  • zapobieganie ryzyku - wykorzystanie szans i unikanie zagrożeń
  • kontrolę ryzyka - obserwacja istniejących zagrożeń oraz przewidywanie nowych

Jakość

Jakością nazywamy stopień realizacji początkowych założeń projektu. Zarządzaniem jakością okresla się taki zbiór czynnośći jak:

  • planowanie jakości - określenie standardów jakie spełniać ma projekt
  • zapewnienie jakości - dostosowanie procesu projektowego w celu spełnienia standardów
  • kontrola jakości - kontrolowanie przebiegu projektu oraz śledzenie czynników mogących obniżyć jakość

Międzynarodowe standardy procesu zarządzania jakością określa norma ISO 9001, a zarządzania ryzykiem - ISO 31000.

5. Wymień składowe matematycznego modelu opisującego obraz cyfrowy wraz z krótkim ich opisem

Obrazem cyfrowym nazywamy dwuwymiarowy obszar zakodowany w postaci binarnej w taki sposób, że możliwa jest jego konwersja do postaci analogowej, widocznej na ekranie. Zasadniczo wyróżnia się dwa rodzaje obrazów cyfrowych:

  • grafika rastrowa - format zapisu obrazów, bazujący na określaniu koloru każdego z pikseli (bitmapa); zapisywany w postaci dyskretnej funkcji dwóch zmiennych

F = f(x, y)

F - kolor piksela
x, y - polożenie piksela w osi X, Y f - funkcja mogąca zwracać wartości różnego typu, np. zmienną [0, 255] w obrazach czarno-białych lub wektor RGB w przypadku obrazów kolorowych

  • grafika wektorowa - format przechowujący w formie opisanych w układzie współrzędnych figur geometrycznych; obraz dzielony jest na mniejsze elementy, które można zapisać jako zbiór podstawowych funkcji płaszczyzn dwuwymiarowych

6. Metody filtracji liniowych w przetwarzaniu obrazów cyfrowych

Filtracja liniowa w kontekście obrazów cyfrowych polega na uśrednieniu wartości pikseli sąsiadujących, względem piksela środkowego. Każdy piksel posiada również swoją wagę, co umożliwia stworzenie maski. Spośród filtrów liniowych wyróżnić można:

  • filtry dolnoprzepustowe - pozbywają się lub minimalizują wysokie częstotliwości, przepuszczając te niskie; pozwala to na odszumienie obrazu lub wprowadzenie efektu rozmycia

  • filtry górnoprzepustowe - przepuszczają wysokie częstotliwości, służą do wydobywania składników powodujących szybkie zmiany jasności, powodują wyostrzanie obrazu, zwiększenie kontrastu oraz wzmocnienie kolorów

  • filtry przesuwające - wykonują przesunięcie obrazu, a następnie odjęcie go od swojej kopii, co pozwala na wykrycie krawędzi umieszczonych na nim obiektów; w zależności od kierunku przesunięcia wykrywane są krawędzie poziome lub ukośne

  • filtr Gaussa - opiera się na wartościach funkcji gaussowskich, pozwala wygenerować efekt wygładzenia obrazu

W przypadku fltrów liniowych pojawia się problem dla elementów brzegowych obrazu, jako że metody te do obliczeń używają wartości pikseli sąsiednich. By zaradzić temu problemowi, stosuje się następujące metody:

  • splot obliczany jest tylko w punktach, w których maska nie wystaje poza obraz; obraz po filtracji jest mniejszy od oryginalnego
  • splot obliczany jest tylko w punktach, w których maska nie wystaje poza obraz; piksele brzegowe przepisuje się bez zmian
  • wartość pikseli poza obszarem jest równa zero; obraz zachowuje rozmiar, ale pojawiają się zafałszowania na brzegach
  • uzupełnia się brakujące wartości np. metodą lustrzanego odbicia krawędzi obrazu; mniejsze zafałszowania niż w przypadu poprzedniej metody

7. Modelowanie procesów farmakokinetycznych

Farmakokinetyka to nauka zajmująca się badaniem rozchodzenia się leku w organizmie człowieka. Modelowanie farmakokinetyczne bazuje na osiągnięciach tej nauki, zajmując się modelowaniem oraz analizą zależności pomiędzy stężeniem leku a efektem jego działania na organizm. Uwzględnia ono trzy podstawowe rodzaje modeli:

  • model kompartmentowy - abstrakcyjny model, który zakłada, że organizm zbudowany jest ze zbiorników wypełnionych różnego rodzaju płynem. W obszarze takiego zbiornika (kompartmentu) lek będzie rozprzestrzeniał się równomiernie, mając również możliwość przenikania do innego zbiornika. Sumę strumienii wpływających i wypływających można wyznaczyć tworząc odpowiednie równanie różniczkowe. W zależności od liczby kompartmentów wyróżnić można:
    • model 1-kompartmentowy - jest najprostszym rodzajem modelu, w którym eliminacja leku oznacza całkowite wydalenie go z ustroju; opisuje na przykład układ krwionośny
    • model 2-kompartmentowy - bardziej zaawansowany model, używany przykłądowo do opisu dobrze ukrwionych tkanek. Pomiary i podanie leku są jednak przeprowadzane tylko w jednym kompartmencie. Cechuje się znacznie większą złożonością obliczeniową.
  • model perfuzyjny - opisuje przepływ krwi i przenoszenie leku do poszczególnych narządów
  • model perfuzyjno-kompartmentowy - stanowi połączenie dwóch pozostałych modeli

8. Sztuczne sieci neuronowe

Sztuczna sieć neuronowa jest układem złożonym z bardzo prostych elementów zwanych sztucznymi neuronami, działającymi w trybie równoległym i mającym zdolnośc uczenia się na podstawie przykładów oraz gromadzenia i stosowania tak uzyskanej wiedzy do przyszłych, nieznanych sytuacji. Z praktycznego punktu widzenia sztuczna sieć neuronowa jest systemem podejmowania decyzji, wyznaczającym wartość wielkości wynikowej (decyzyjnej) na podstawie wielkości wejściowych (cech, przesłanek), którego umiejętności są kształtowane w procesie uczenia.

Cechy

  • zdolność do działania w nieznanych sytuacjach
  • adaptacja, zdolność uczenia przez dostosowywanie parametrów
  • równoległość obliczeń
  • nieliniowość, zdolność modelowania nieliniowych zależności pomiędzy wejściema wyjściem
  • odporność na błędy i uszkodzenia

Struktura sieci neurnowej

  • neurony wejściowe - służą do wprowadzania danych wejściowych
  • neurony ukryte - nie kontaktują się bezpośrednio z wejściem/wyjściem, służą do analizy i przetwarzania danych wewnątrz sieci
  • neurony wyjściowe - wyprowadzają wartości zmiennych decyzyjnych

Ze względu na budowę możemy wyróżnić dwa rodzaje sieci:

  • jednokierunkowe - charakteryzują się przepływem informacji w jednym kierunku
  • rekurencyjne - występują sprzężenia zwrotne; wyjście neuronu jest połaczone z wejściem tej samej warstwy bądź poprzedniej

9. Omówić warstwy modelu hurtowni danych

Hurtownie danych budowane są w architekturze warstwowej, gdzie każda z warstw spełnia oddzielne zadanie. Zasadniczo wyróżnia się:

  • źródło danych (ang. data source) - zazwyczaj w postaci bazy danych, zawiera dane o zróżnicowanej strukturze, rozmiarach oraz jakości
  • obszar przejściowy (ang. data staging) - oczyszcza i dostosowuje dane do wymagań hurtowni. Warstwa ta nie jest dostępna dla użytkownika końcowego, należą do niej narzędzia integracyjne ETL
  • warstwa metadanych (ang. data layer) - stanowi centralne repozytorium danych w standardzie odpowiednim dla hurtowni. W zależności od typu systemu, może mieć format tabeli wymiarów, data martu, agregatu, tabeli faktów lub mapowania danych od systemu źródłowego. Często stanowi również magazyn danych operacyjnych ODS (ang. operational data store).
  • warstwa prezentacji (ang. presentational layer) - udostępnia dane użytkownikowi bądź oprogramowaniu końcowemu w czytelnej i spójnej formie. Umożliwia tworzenie kwerend i zapytań.

10. Przedstawić modele logiczne hurtowni danych

Modelem logicznym hurtowni danych określamy opis definiujący elementy baz danych oraz procesów zachodzących w hurtowni. Podstawowymi pojęciami wykorzystywanymi w modelach hurtowni są:

  • Fakt - Pojedyncze zdarzenie będące podstawą analiz. Fakty opisane są poprzez wymiary i miary
  • Wymiar - Cecha opisująca dany fakt, pozwalająca powiązać go z innymi pojęciami. Wymiary są opisywane przy pomocy atrybutów.
  • Atrybut - Cecha wymiaru, przechowująca dodatkowe informacje na temat faktu.
  • Miara - Liczbowa wartość, powiązana bezpośrednio z faktem.

Najpopularniejsze modele logicznych hurtowni danych:

  • Model gwiazdy - Opiera się na stworzeniu centralnej tablicy faktów, z którą powiązane są tablice opisujących je wymiarów. Topologia układu jest podobna do sieci komputerowej o gwieździstej strukturze. Atrybuty wymiarów reprezentowane są przez kolumny w odpowiadających im tabelach, natomiast sama tablica faktów przechowuje jedynie schemat fakt - miara.
  • Model płatka śniegu - Stanowi rozwinięcie modelu gwiazdy, powstając przez normalizację umieszczonych w nim baz danych. Model ten zachowuje hierarchię wymiarów, czyli zakłada sytuację, w której jeden wymiar może mieć wiele stopni szczegółowości, które modelowane są przez osobne tabele.
  • Model konstelacji - Wykorzystywany w sytuacjach, kiedy konieczne jest przechowywanie w hurtowni różnego typu faktów. Pozwala on na współdzielenie tabel wymiarów (oraz przypisanych do nich atrybutów) pomiędzy tabelami faktów.

1. Paradygmaty programowania obiektowego

Programowanie obiektowe opisuje wzorzec tworzenia programu oparty o obiekty, czyli elementy łączące ze sobą dane i operaujące na nich funkcje zwane metodami. Obiektowy program komputerowy wyrażony jest jako zbiór takich obiektów komunikujących się ze sobą.

Cztery podstawowe założenia programowania obiektowego to:

  • Abstrakcja - Umożliwia wyodrębnienie elementów charakteryzujących dany obiekt, które są istotne dla rozwiązania problemu. Każdy obiekt w systemie służy jako model abstraykcyjnego wykonawcy, który może wykonywać pracę, opisywać i zmieniać swój stan oraz komunikować się z innymi obiektami w systemie, bez ujawniania w jaki sposób zaimplementowano dane cechy.

  • Hermetyzacja - Mechanizm ukrywania informacji przed klasami, które nie potrzebują lub nie powinny mieć do nich dostępu. Pozwala to chronić wewnętrzny stan obiektu przed modyfikacją w nieoczekiwany sposób. Typy udostępniają swój publiczny interfejs, który określa dopuszczalne metody współpracy. Zależnie od języka programowania wyróżnia się kilka rodzajów modyfikatorów dostępu.

  • Dziedziczenie - Pozwala na udostępnienie wybranych cech wspólnych klasom bazującym na klasie nadrzędnej. Umożliwia to tworzenie wyspecjalizowanych typów na podstawie już istniejących. Można wyróżnić dwa rodzaje dziedziczenia - pojedyncze i wielokrotne.

  • Polimorfizm - Mechanizm wielopostaciowowści. W przypadku polimorfizmu statycznego, polega na przeciążaniu operatorów, funkcji lub korzystaniu z szablonów. Polimorfizm dynamiczny opiera się o wykorzystanie referencji lub wskaźników na typ ogólny, których wywołanie powoduje użycie implementacji odpowiedniej dla pełnego typu obiektu.

2. Arytmetyka stało- i zmiennoprzecinkowa

Liczby stałoprzecinkowe

W reprezentacji stałoprzecinkowej każdy bit ma zawsze taką samą wagę (zależącą od swojej pozycji), dlatego też pozycja przecinka jest ustalona arbitralnie. Do kodowania liczb najczęściej wykorzystuje się system uzupełnieniowy do dwóch (U2), pozwalający zapisać zarówno liczby dodatnie, jak i ujemne - oraz czasem kod naturalny binarny (NB), kiedy obliczenia prowadzone są tylko na liczbach dodatnich. Zaletą arytmetyki stałoprzecinkowej jest dokładność obliczeń (w granicach precyzji określanej przez wagę najmłodszego bitu) oraz duża szybkość wykonywania działań. Wadą jest stosunkowo niewielki zakres możliwych do zapisania wartości.

Liczby zmiennoprzecinkowe

W reprezentacji zmiennoprzecinkowej liczby przechowywane są w postaci notacji wykładzniczej:

X = S * M * 2E

S - znak
M - mantysa
E - wykładnik

Wagi poszczególnych bitów (i pozycja przecinka) zależą wiec od wartości wykładnika i mogą się zmieniać. Taka reprezentacja liczby pozwala zapisać liczby ze stosunkowo dużego zakresu, który w reprezentacji stałoprzecinkowej wymagałby bardzo dużej liczby bitów. Wadą arytmetyki zmiennoprzecinkowej jest wolniejsze wykonywanie operacji i mniejsza dokładnośc wykonywania działań, wynikająca z błędów zaokrągleń.

Precyzja obliczeń zmiennoprzecinkowych zależy od liczby bitów przeznaczonych na zapis liczby. Stosowane w informatyce formaty zapisu liczb zmiennoprzecinkowych określone w standardzie IEEE 754:

  • liczby pojedynczej precyzji (float) - 32 bity: 1 bit znaku, 8 bitów wykładnika, 23 bity mantysy
  • liczby podwójnej precyzji (double) - 64 bity: 1 bit znaku, 11 bitów wykładnika, 52 bity mantysy

Istnieją też niestandardowe formaty liczb zmiennoprzecinkowych, np. 80-bitowy format rozszerzonej precyzji, stosowany wewnętrznie w jednostkach zmiennoprzecinkowych (FPU) procesorów x86.

W obliczeniach zmiennoprzecinkowych dochodzi do zjawiska kumulacji błędów. Z tego powodu nie zaleca się stosowania arytmetyki zmiennoprzecinkowej między innymi w obliczneiach finansowych.

3. Normalizacja schematu bazy danych

Normalizacja to bezstratny proces organiowania danych w tabelach, mający na celu zmniejszenie ilości skłądowanych w bazie danych oraz wyeliminowanie nadmiarowości i niespójnych zaleności. Normalizacja baz danych jest dobrą praktyką, jednak nie zawsze jest konieczna lub wskazana (np. w przypadku hurtowni danych). Wyróżnia się kilka postaci normalnych:

  • 1NF - pierwsza postać normalna - dane w kolumnach są atomowe i nie ma możliwości ich dalszego podziału na mniejsze elementy
  • 2NF - druga postać normalna - wymaga spełnienia 1NF, dane w kolumnach są całkowicie uzależnione funcyknie od klucza głównego (Partial Dependency)
  • 3NF - trzecia postać normalna - wymaga spełnienia 2NF, dane w kolumnach niebędących częscią klucza głównego są od siebie wzajemnie niezalene (Transitive Dependency)
  • BCNF (3.5NF) - postać normalna Boyce-Codd'a - wymaga spełnienia 3NF, każda kolumna, od której zależy inna, musi być unikatowym kluczem tabeli
  • 4NF - czwarta postać normalna - wymaga spełniania 3NF - zakłada implementację osobnego przechowywania zależności wielowartościowych
  • 5NF - piąta postać normalna - wymaga spełnienia 4NF - tabele tworzone są w taki sposób, że nie jest możliwy ich odwracalny rozkład na mniejsze tabele

4. Model warstwowy TCP/IP

Model TCP/IP to warstwowy model struktury protokołów komunikacyjnych stosowanych w sieciach komputerowych. Składa się z następujących warstw:

  • warstwa aplikacji - najwyższy poziom, w którym pracują aplikacje tj. serwery WWW, przeglądarki internetowe, klienci pocztowi, serwery DNS; protokoły: HTTP, DNS, FTP, SSH, SMTP
  • warstwa transportowa - odpowiada za kanał komunikacyjny, kieruje właściwe informacje do odpowiednich aplikacji, wykorzystując numery portów określane dla każdego połączenia; warstwa transportowa nawiązuje, utrzymuje i zrywa połączenia pomiędzy urządzeniami; wykorzystywane protokoły to TCP (połąceniowy, gwarantujący niezawodność) oraz UDP (bezpołączeniowy, szybszy, bez gwarancji dostarczenia danych)
  • warstwa internetowa - odpowiada za wyznaczanie najlepszej trasy (routing) i przekazywanie pakietów do kolejnych sieci pomiędzy urządzeniem źródłowym a docelowym; podstawowym protokołem tej warstwy jest IP
  • warstwa dostępu do sieci - najniższa warstwa, realizujaca transmisję danych przez fizyczne łącza pomiędzy urządzeniami sieciowymi (Ethernet, WiFi, DSL)

Każda z warstw jest niezależna od pozostałych. Pozwala to na wykorzystanie w sieci różnych technologii, bez wywierania wpływu na pozostałe warstwy. Sam model jak i zestaw protokołów TCP/IP został zaprojektowany w otwartej architekturze i nie jest ograniczony żadnymi patentami.

5. Ocena złożoności algorytmów

W celu oszacowania złożoności algorytmu konieczne jest określenie następujących cech:

  • problem - zbiór danych wejściowych, ich definicja oraz zadanie do wykonania
  • instancja problemu - określenie konkretnych danych wejściowych i problemu
  • algorytm - lista kroków prowadząca do rozwiązania określonego problemu

Złożoności, które dotyczą algorytmu:

  • złożoność pamięciowa - oszacowanie pamięci potrzebnej do wykonania algorytmu zależnej od ilości danych wejściowych
  • złożonośc czasowa - oszacowanie czasu potrzebnego do wykonania algorytmu zależnego od ilości danych wejściowych

Do opisu złożoności w sposób ogólny wykorzystuje się Notację Dużego O, której celem jest określenie złożoności jako funkcji zależnej od rozmiarów danych wejściowych problemu, przykładowo:

  • O(n) - złożoność liniowa
  • O(n2) - złożoność kwadratowa
  • O(log n) - złożoność logarytmiczna

Ponieważ zużycie zasobów w algorytmie jest zależne od postaci przetwarzanych danych, złożoność może występować w trzech odmianach:

  • optymistyczna - dla najbardziej korzystnego przypadku danych
  • pesymistyczna - dla najmniej korzystnego przypadku danych
  • średnia (oczekiwana) - dla losowego przypadku danych

6. Język UML w projektowaniu oprogramowania

Język UML (ang. Unified Modeling Language) to (pół-formalny) język, wykorzystywany do opisu modelu reprezentującego projekt informatyczny. UML jest prezentowany w postaci graficznej, czyli ustandaryzowanych diagramów, do których między innymi należą:

  • Diagramy struktur - reprezentujące struktury danych, ich zbiory oraz cechy
    • Diagram klas
    • Diagram obiektów
    • Diagram pakietów
  • Diagramy zachowań - reprezentujące akcje podejmowane przez uytkownika systemu bądź sam system
    • Diagram przypadków użycia
    • Diagram czynności
    • Diagram sekwencji

Jest niezależny od docelowego języka, w jakim tworzone będzie oprogramowanie. Pozwala on też na wygodną i jednoznaczną komunikację członków zespołu programistycznego.

7. Generowanie realistycznych scen obrazów 3D za pomocą metody śledzenia promieni

Śledzenie promieni (ang. ray tracing) to technika pozwalająca na generowanie fotorealistycznych obrazów i scen 3D, przy wykorzystaniu analizy promieni światła padających bezpośrednio na obserwatora. Jej zadaniem jest odtworzenie w uproszczeniu sposobu, w jaki ludzkie oko postrzega światło odbite od fizycznych obiektów.

Zasada działania algorytmu w podstawowej wersji wygląda następująco:

  1. Z punktu, w którym znajduje się obserwator, wyprowadzany jest promień pierwotny, który przecina rzutnię.
  2. Wyznaczany jest najbliższy punkt przecięcia z obiektem znajdującym się na scenie.
  3. Następnie dla każdego źródła światła wyznaczany jest poziom jasności w tym punkcie, zgodnie z przyjętym modelem oświetlenia (np. Lamberta lub Phonga).

Śledzenie promieni nie jest jednak metodą idealną. Duża ilość obliczeń wymaga znacznych zasobów komputera, przez co do niedawna rzeczywiste wykorzystanie tego algorytmu nie było możliwe poza specjalistycznym sprzętem. Przedstawiona procedura musi zostać wykonana dla każdego piksela.

Dodatkowo, ze względu na zasadę działania, algorytm ten nie jest w stanie obsługiwać światła rozproszonego, symulować dyfrakcji lub rozszczepienia światła.

8. Mechanizmy systemu operacyjnego wspomagające synchronizację procesów

Synchronizacja procesów dotyczy w głównej mierze problemu współdzielenia zasobów, kiedy to tylko jeden proces może w danym momencie modyfikować wspóldzielone dane. Jednoczesna ich modyfikacja przez dwa lub więcej procesy może doprowadzić do uszkodzenia lub powstania nieprawidłowych danych.

Mechanizmy synchronizacji:

  • Semafor - metoda synchronizacji procesów operta na chronionej zmiennej lub abstrakcyjnym typie danych (zazwyczaj typ całkowity). Wartość zmiennej określa liczbę żądan dostępu do wybranego zasobu. Implementowane bezpośrednio w jądrze systemu operacyjnego.

  • Mutex - modyfikacja semafora, posiadająca dwa stany: dostępny i zablokowany. Jego stan może zmienić tylko proces będący jego właścicielem. Konieczne jest więc manualne zwalnianie zasobów po zakończeniu korzystania z nich.

  • Monitor - strukturalny mechanizm synchronizacji, występujący w językach programowania wysokiego poziomu. Są one rodzajem abstrakcyjnej klasy, która spełnia zadanie sekcji krytycznej, pozwalając na tylko jeden aktywny proces korzystający z zasobu. Pozostałe procesy są umieszczane w tymczasowej kolejce. Ich zaletą jest brak konieczności ręcznego zarządzania procesami - zasoby są automatycznie zwalniane, kiedy proces opuści sekcję krytyczną.

  • Kolejka komunikatów - metoda synchronizacji oparta o kolejkę FIFO, której zadaniem jest przechowywanie komunikatów żądania zasobów wysyłanych przez procesy. Proces może dodać lub usunąć tylko należące do niego żądanie. W przypadki kiedy kolejka jest pełna, następuje oczekiwanie na zwolnienie miejsca. W przeciwieństwie do semafora, pozwala on na selektywne zarządzanie żądaniami.

9. Programowalne scalone układy cyfrowe PLD, CPLD oraz FPGA

Układy PLD, CPLD oraz FPGA należą do specjalizowanych scalonych układów cyfrowych konfigurowalnych przez użytkownika - w odróżnieniu od typowych układów konfigurowanych maską przez producenta na zamówienie użytkownika. Układy programowalne mogą być dzięki temu produkowane i sprzedawane masowo.

Nadawanie funkcjonalności odbywa się w sposób analogiczny do programowania komputerowego. Są one programowane przy przy pomocy dedykowanych języków HDL (tj. Verilog, VHDL), co pozwala na łatwą konfigurację i modyfikację ich zastosowań. Potrafią one realizować proste funkcje pracując w jednym z dwóch trybów:

  • sekwencyjnie - stan wyjść układu zależy od stanu wejścia oraz poprzedniego stanu wyjścia
  • kombinacyjnie - stan wyjść układu zależy tylko i wyłacznie od stanu wejścia

Najstarszym i najprostszym rodzajem omawianych układów są układy PLD (Programmable Logic Device), wykorzystywane do tworzenia nieskomplikowanych układów. Składają się z dwóch matryc bramek logicznych, AND-OR.

Występują w trzech odmianach:

  • PAL - z programowalną matrycą AND (najpowszechniejsze)
  • PLE - z programowalną matrycą OR
  • PLA - z programowalnymi matrycami AND i OR

Jako ich rozwinięcie opracowano układy CPLD (Complex PLD), bazujące na makrokomórkach (połączeniach multiplekserów i bramek XOR), które łączone w grupy stanowią bloki funkcyjne. Każda makrokomórka pełni prostą funkcję logiczną, jednak zwiększenie zasobów pozwala na realizowanie bardziej złożonych funkcji niż w przypadku poprzednika.

Układy FPGA (Field Programmable Gate Array) to najbardziej złożone układy programowalne, opracowane pierwotnie przez firmę Xilinx, bazujące na macierzy bramek z możliwością bezpośredniego programowania. Dodatkowo zawierają bloki RAM, pozwalające na tworzenie wartości LUT (look-up table). Zawierają znacznie większe ilości bramek logicznych od innych typów PLD, a dodatkowo bloki IOB (input-output bound), które również oferują możliwości programowania.

10. Optyczne nośniki informacji

Nośnikiem informacji nazywamy fizyczny obiekt, na którym możliwe jest zapisanie i odczytanie informacji. Nośniki optyczne służą do przechowywania informacji w postaci, którą odczytuje się przy pomocy wiązki światła (promienia lasera). Pierwszym optycznym nośnikiem danych były płyty LaserDisc o średnicy około 30 cm, opracowane w latach 70. w Stanach Zjednoczonych do zapisu wideo (obraz w formacie analogowym, dźwięk w formacie analogowym lub cyfrowym).

Współcześnie jako optyczne nośniki danych wykorzystuje się płyty o średnicy 12 cm, przechowujące dane w postaci cyfrowej:

  • CD - najstarszy standard (1982), do odczytu wykorzystuje falę o długości 780 nm (podczerwień), pozwala zapisać 700 MB danych lub 80 minut stereofonicznego dźwięku
  • DVD - standard z 1995, do odczytu wykorzystuje falę o długości 650 nm (światło czerwone), dzięki czemu uzyskano większą gęstość zapisu - mieści 4.7 GB danych na jednej warstwie; na płytach dwuwarstwowych mieszczących 8.5 GB danych wybór warstwy odbywa się poprzez odpowiednie zogniskowanie wiązki laserowej (pierwsza warstwa częściowo przepuszcza światło)
  • Blu-ray - standard z 2006, do odczytu wykorzystuje falę o długości 405 nm (światło niebieskie), jeszcze wyższa gęstość zapisu, pozwala na zapisanie 25 GB danych na jednej warstwie, podobnie jak DVD możliwy jest zapis dwuwarstwowy (50 GB), a w rozszerzonej wersji standardu zwanej BXDL nawet ośmiowarstwowy (200 GB)

Dane cyfrowe są zapisywane na płytach w spiralnej ścieżce od środka nośnika do zewnętrznej kwawędzi w postaci fragmentów powierzchni odbijających (land) lub pochłaniających (pit) wiązkę światła lasera.

Płyty te mogą być fabrycznie zapisywane (CD-ROM), ale mogą też być dostosowane do jednokrotnego zapisu (CD-R) lub wielokrotnego zapisu (CD-RW) przez użytkownika przy pomocy nagrywarki. Szczególnie duże znaczenie miały tutaj płyty CD-RW przed upowszechnieniem się nośników pamięci USB.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment