To jest stara, nieaktualizowana już wersja portalu wydziałowego. Zapraszamy na www.mimuw.edu.pl.
Wydział MIM Uniwersytet WarszawskiFaculty of MIM University of Warsaw

Wyszukiwarka

Pomiń menu

Zagadnienia na egzamin magisterski

Ta część dokumentu zawiera spis pytań wraz z krótkimi objaśnieniami do każdego z nich. Sformułowania pytań nie są doskonałe, jednak komentarze do nich powinny pozwalać na zrozumienie ich intencji i zakresu zagadnień, jakich one dotyczą. Zakresy tematyczne niektórych pytań częściowo się na siebie nakładają, nie da się tego jednak uniknąć jeśli chce się mieć pytania wyczerpujące dość bogaty zakres tematyczny, a jednocześnie w jakimś stopniu interdyscyplinarne.



Języki formalne, automaty i ich zastosowania

Języki formalne można uznać za podstawę informatyki, gdyż pojęcie to obejmuje zarówno wszystkie języki używane do zapisu algorytmów (języki programowania), jak też języki używane do opisu własności algorytmów (logiki programów). Pytanie obejmuje w szczególności pojęcie języków formalnych używane w teorii obliczeń, klasyfikację takich języków, metody ich definiowania i automatycznego rozpoznawania (języki i gramatyki regularne, bezkontekstowe, kontekstowe i inne, automaty skończone, automaty ze stosem, wreszcie automaty na strukturach nieskończonych -- choć to ostatnie pojęcie nie jest częścią obowiązkowego programu studiów), a także języki programowania traktowane jako języki formalne (a więc metody definiowania i automatycznego rozpoznawania składni tych języków).



Literatura

  • Hopcroft, Ullman Wprowadzenie do teorii automatów, języków i obliczeń



Modele obliczalności

W pytaniu tym chodzi o przedstawienie różnych modeli obliczalności (maszyny Turinga, poza tym np. funkcje rekurencyjne) i związaną z nimi tezę Churcha-Turinga, przedstawienie informacji o zadaniach teoretycznie nierozwiązywalnych przy użyciu komputerów (bądź z powodu nierozstrzygalności, bądź też z powodu ich zbyt wysokiej złożoności (ang. intractable problems) oraz o metodach praktycznego rozwiązywania takich zadań (algorytmy heurystyczne, aproksymacyjne, probabilistyczne). Pytanie obejmuje w naturalny sposób zarówno zagadnienia klasycznej teorii obliczalności jak i teorii złożoności obliczeniowej.



Literatura

  • Hopcroft, Ullman Wprowadzenie do teorii automatów, języków i obliczeń

  • Arbib, Kfoury, Moll A programming approach to computability

  • Balcazar, Diaz, Gabarro Structural complexity I, II



Algorytmy a programy, wpływ struktur danych na złożoność

To pytanie dotyczy związków między pojęciami algorytmu oraz programu, który taki algorytm realizuje. Dotyczy ono także pojęć złożoności czasowej i pamięciowej problemów (własność zadania) oraz złożoności programów rozwiązujących te problemy (własność konkretnego rozwiązania), oraz związków między tymi pojęciami. W szczególności istotne jest wyjaśnienie wpływu wyboru struktur danych na złożoność algorytmu, omówienie sytuacji, w których algorytmy asymptotycznie optymalne okazują się gorsze od algorytmów prostszych, za to mających wyższą złożoność, a także wpływu różnych ograniczeń na własności zadań (np. sortowanie zbioru liczb z ustalonego, niewielkiego zakresu może być realizowane za pomocą algorytmów o złożoności liniowej -- np. sortowania kubełkowego, co nie jest możliwe w przypadku problemu sortowania w pełnej jego ogólności).

Ważnym, a dość odrębnym zagadnieniem są również algorytmy równoległe. Niektóre zadania dla dostatecznie szybkiego ich rozwiązywania za pomocą komuterów wymagają stosowania algorytmów równoległych. Algorytmy takie są zwykle projektowane dla wyidealizowanych, nie istniejących w praktyce komputerów równoległych. Ważne jest, by zrozumieć, jak taki, wydawałoby się całkowicie niepraktyczne, algorytmy da się jednak implementować na istniejącym sprzęcie, a także kiedy da się je stosować, a kiedy nie (nie w każdym przypadku zastosowanie komputera równoległego musi dać jakiekolwiek korzyści). Prócz architektur komputerów równoległych trzeba też znać mechanizmy języków programowania, które umożliwiają lub ułatwiają zapisywanie algorytmów równoległych. Warto też wspomnieć o miarach wydajności takich algorytmów, które są dla nich specyficzne i nie mają odpowiedników w świecie algorytmów sekwencyjnych.

  • Banachowski, Kreczmar Elementy analizy algorytmów

  • Banachowski, Diks, Rytter Algorytmy is struktury danych

  • Cormen, Leisserson, Rivest Introduction to algorithms



Paradygmaty programowania

Istnieje kilka powszechnie uznanych paradygmatów programowania: programowanie imperatywne, programowanie funkcyjne, programowanie w logice, programowanie obiektowe. Paradygmaty te w istotny sposób wpływają na sposób pisania programów. Choć niektóre z nich można zastosować w każdym niemal języku programowania, to na ogół używa się języków, które są wyposażone w mechanizmy specyficzne dla poszczególnych paradygmatów. Pytanie dotyczy zatem wyjaśnienia natury poszczególnych paradygmatów, inspiracji ich powstania, mechanizmów językowych i konkretnych języków programowania, które można z nimi powiązać, a także omówienia ich związków wzajemnych oraz obszarów zastosowań.



Rekurencja (w matematyce i informatyce)

Jest to ogólne, przekraczające ramy poszczególnych przedmiotów, pytanie dotyczące określenia oraz przejawów i zastosowań uniwersalnego zjawiska, które odgrywa ważną rolę w praktyce informatyki (w postaci podejścia do opisu oraz realizacji algorytmów), a także w jej teorii (np. teoria rekursji jako podstawa teorii obliczeń), logice matematycznej, ale również w tak zwanej ``twardej'' matematyce (w teorii układów dynamicznych), fizyce (zastosowania fraktali), biologii, muzyce, sztukach plastycznych (np. obrazy Eschera) i wielu innych kontekstach.



Współbieżność i jej zastosowania

To pytanie dotyczy bardzo istotnego w obecnych czasach zagadnienia, jakim jest teoria i praktyka współbieżności. W epoce powszechnego stosowania małych, dużych i ogromnych sieci komputerowych coraz ważniejsze staje się tworzenie oprogramowania, które może pracować w sposób rozproszony. Za przykłady mogą posłużyć współczesne systemy baz danych oraz nowoczesne systemy operacyjne. Oprogramowanie takie składa się na ogół z wielu modułów, które wykonują się równolegle, niekiedy na osobnych komputerach połączonych siecią transmisji danych, wymieniając między sobą informacje za pomocą rozmaitych mechanizmów komunikacyjnych. Tworzenie programów współbieżnych i rozproszonych wymaga także rozwiązywania nowych problemów algorytmicznych, które nie pojawiają się przy tworzeniu programów tradycyjnych (sekwencyjnych). Od naszych absolwentów powinniśmy wymagać znajomości podstawowych problemów, które powstają przy tworzeniu oprogramowania współbieżnego (np. zagadnień żywotności, blokady, wzajemnego wykluczania) oraz algorytmów, które są używane do ich rozwiązywania, a także specyficznych mechanizmów występujących w językach programowania współbieżnego, potrzebnych do realizacji wzajemnej współpracy osobnych procesów.

Zjawiska związane ze współbieżnością są daleko bardziej skomplikowane niż w przypadku programowania sekwencyjnego, dlatego też oprócz specyficznych problemów algorytmicznych wymagają też istotnie odmiennych technik opisu formalnego i wnioskowania o nich. Teoria związana ze współbieżnością jest bardzo bogata, warto znać przynajmniej niektóre podejścia do formalnego opisu języków programowania współbieżnego i metod dowodzenia poprawności algorytmów równoległych.



Literatura

  • Andrews Concurrent programming
  • Ben-Ari Podstawy programowania współbieżnego
  • Weiss, Gruźlewski Programowanie współbieżne i rozproszone w przykładach i zadaniach
  • Hoare Communicating sequential processes
  • Milner Communication and concurrency
  • Reisig Sieci Petriego
  • Starke Sieci Petriego
  • Diekert, Rosenberg (eds.) The book of traces



Formalny opis języków programowania

To pytanie dotyczy metod definiowania składni i semantyki języków programowania. Dotyczy zatem takich zagadnień, jak gramatyki bezkontekstowe (a także kontekstowe i dwupoziomowe, choć o tym być może studenci nic nie wiedzą?), metody analizy składniowej programów, powodów, dla których opis bezkontekstowy nie jest adekwatny. Jeśli chodzi o semantykę, to należy opowiedzieć o poszczególnych metodach jej definiowania (np. denotacyjnej, operacyjnej, aksjomatycznej, algebraicznej), o różnych zastosowaniach formalnych definicji języków programowania i o tym, które metody opisu do jakiego rodzaju zastosowań pasują. Jeśli chodzi o zastosowania definicji formalnych, to trzeba wspomnieć przynajmniej o tym, że bez niej trudno jest przystępować do implementacji języka, nie da się mówić o poprawności implementacji czy też ich porównywać. Ścisła definicja jest oczywiście niezbędna do formalnego rozumowania o zachowaniu programów, tworzenia formalnych specyfikacji i dowodzenia zgodności konkretnych programów z takimi specyfikacjami.



Literatura

  • Gordon Denotacyjny opis języków programowania



Czemu służą specyfikacje?

Po co specyfikujemy programy? Jakie rodzaje specyfikacji nadają się do poszczególnych zastosowań (np. do porozumienia się z klientem zamawiającym program, do wyjaśnienia zadania zespołowi programistów którzy mają napisać program, do dowodzenia poprawności gotowego programu...)? Jakie języki są używane do tworzenia poszczególnych rodzajów specyfikacji? Jakiego rodzaju narzędzia programistyczne mogą być pomocne przy pracy nad różnymi rodzajami specyfikacji?



Czemu tak dużo jest programów, a tak mało dowodów poprawności?

Programów komputerowych jest bardzo dużo -- wystarczy rozejrzeć się dokoła. Niestety, nie wszystkie działają całkiem tak, jak tego byśmy oczekiwali -- z powodu błędów. Wiadomo powszechnie, że tworzenie dużych, a jednocześnie bezbłędnych programów jest niezwykle trudne, a często graniczy z niemożliwością.

Najpewniejszą metodą walki z błędami jest zaopatrywanie programów w formalne dowody poprawności. Są do tego potrzebne systemy logiczne pozwalające na wyrażanie własności programów i dowodzenie, że programy posiadają odpowiednie własności. Przynajmniej niektóre z tych systemów powinny być znane naszym absolwentom (np. logika Hore'a czy logika dynamiczna) -- oczywiście wraz z ich podstawowymi własnościami (pełność, rozstrzygalność, siła wyrazu).

Jednak tworzenie formalnych dowodów poprawności jest na ogół zadaniem bardzo trudnym. Jednym ze sposobów na rozwiązanie tego problemu jest stosowanie oprogramowania wspomagającego tworzenie dowodów własności programów. Drugie podejście polega na stosowaniu metod alternatywnych do formalnej weryfikacji. Przychodzą tu na myśl rozwiązania takie jak stosowanie właściwej metodologii programowania, mechanizmy języków programowania zabezpieczające programistę przed niektórymi rodzajami błędów, systematyczne i rygorystyczne testowanie gotowych programów. Studenci powinni zdawać sobie sprawę z tego, jakie metody powinni stosować, aby tworzyć oprogramowanie niezawodne i poprawne oraz jakie są wzajemne związki między poszczególnymi metodami, które można w tym celu wykorzystać.



Architektury i działanie komputerów

Pytanie to dotyczy zasad, które stoją za wszystkimi niemal stosowanymi obecnie architekturami komputerów -- są one oparte na modelu maszyny z wewnętrznym sterowaniem, zwanej maszyną von Neumanna. Należy objaśnić strukturę logiczną i funkcjonalną klasycznego komputera, podać cykl wykonania rozkazu i przykład prostej listy rozkazów. Warto jednak zdawać sobie sprawę z tego, że architektura von Neumanna nie jest idealna ani jedyna możliwa (inną możliwą architekturą jest np. architektura maszyny sterowanej przepływem danych), a także, że w niektórych zastosowaniach przejawia ona istotne wady.

Poza teoretycznym, wyidealizowanym modelem komputera, pytanie to dotyczy również elementów budowy rzeczywistych komputerów -- systemu przerwań, stronicowania i segmentacji, pamięci wirtualnej, ochrony pamięci, trybach pracy procesora (tryb użytkownika i tryb nadzorcy), portów wejścia-wyjścia i dostępu do rejestrów urządzeń, mechanizmów komunikacji urządzeń zewnętrznych z pamięcią z ominięciem procesora, oraz architektury nowoczesnych procesorów -- zestawu rozkazów typu RISC oraz CISC, wielopoziomowej pamięci podręcznej (ang. cache), wieloetapowego i równoległego wykonywania rozkazów (ang. instruction pipelining), przewidywania skoków (ang. branch prediction), wykonywania na zapas (ang. speculative execution) i innych.



Systemy operacyjne -- struktura i rodzaje

To pytanie dotyczy roli, jaką pełni system operacyjny, struktury takiego systemu, mechanizmów i algorytmów stosowanych przez systemy operacyjne (np. zarządzanie procesami i procesorem, pamięcią operacyjną i dyskową, zapobieganie blokadom, strategie przydziału zasobów), a także różnych rodzajów systemów operacyjnych i ich zastosowań, do których poszczególne rodzaje się nadają (np. systemy czasu rzeczywistego, zwykłe systemy wielozadaniowe, systemy dla serwerów baz danych, systemy o podwyższonej niezawodności, systemy rozproszone). Wiedza o roli i funkcjach systemu operacyjnego pozwala na wybór systemu odpowiedniego do danych zastosowań, a także -- w przypadku możliwości wyboru spośród wielu systemów o podobnej funkcjonalności -- na świadomy wybór na podstawie racjonalnych kryteriów.



Literatura

  • Silberschatz, Peterson, Galvin Podstawy systemów operacyjnych

  • Bach Budowa systemu operacyjnego Unix

  • Lister, Eager Wprowadzenie do systemów operacyjnych

  • Tanenbaum Distributed Operating Systems

  • Coulouris, Dollimore, Kindberg Distributed Systems: Concepts and Design

  • Ben-Ari Podstawy programowania współbieżnego i rozproszonego

  • Rochkind Programowanie w systemie Unix dla zaawansowanych

  • Stevens Programowanie zastosowań sieciowych w systemie Unix

  • Brown Unix Distributed Programming

  • Gabassi, Dupouy Przetwarzanie rozproszone w systemie Unix

  • Comer Sieci komputerowe TCP/IP. Zasady, protokoły i architektura



Rodzaje implementacji języków programowania i ich zastosowania

To pytanie dotyczy metod implementacji języków programowania -- interpretacji, kompilacji oraz metod mieszanych, obszarów zastosowania poszczególnych technik implementacyjnych, stosowanych przy tym technik i algorytmów. Dotyczy ono zatem zagadnień analizy składniowej (co wiąże się z gramatykami bezkontekstowymi i ich szczególnymi klasami -- takimi jak \( \text{LL}(k) \)\( \text{LR}(k) \), automatami, a także narzędziami programistycznymi, które ułatwiają realizację tych zadań), analizy semantycznej, generacji i optymalizacji kodu lub też interpretacji programu, odwzorowania struktur danych (tablice, rekordy, obiekty) i struktur sterowania (rekursja, funkcje wyższego rzędu, wyjątki, kontynuacje) języka programowania na struktury bliskie maszynie, a także mechanizmów związanych z wykonaniem wygenerowanego kodu na maszynach rzeczywistych bądź wirtualnych.



Literatura

  • Aho, Sethi, Ullman Compilers: Principles, Techniques and Tools
  • Waite, Goos Konstrukcja kompilatorów



Kompozycjonalność

Jest to ogólne, przekraczające ramy poszczególnych przedmiotów, pytanie dotyczące określenia oraz przejawów i zastosowań uniwersalnego zjawiska, które manifestuje się na przykład w semantyce języków programowania (semantyka denotacyjna), technikach kompilacji (kompilacja sterowana składnią), w metodologii budowy dużych systemów oprogramowania (modularność), w algebrze ogólnej (homomorfizmy struktur algebraicznych), w logice (ekstensjonalność, składanie systemów logicznych). Pozwala się wykazać pomysłowością i wiedzą z wielu dziedzin.



Sieci komputerowe

W tym punkcie oczekiwania względem magistranta powinny ewoluować wraz z wprowadzaniem nowego programu studiów, w którym pojawi się nowy wykład kursowy ,,Systemy rozproszone''. Tym niemniej można już teraz oczekiwać znajomości typów sieci (lokalne, miejskie, rozległe) oraz charakterystycznych dla nich problemów. Istotne są tutaj zarówno aspekty sprzętowe (fizyczne podstawy funkcjonowania sieci, w tym znajomość funkcji elementów typu bramki, rutery itp. oraz kart sieciowych), jak i programowanie (rodziny protokołów, model ISO/OSI i TCP/IP, zagadnienia wyboru trasy itd.). Nie wypada nie wiedzieć na jakiej zasadzie funkcjonuje Ethernet, czy jak działa system nazw w Internecie. Ważna jest znajomość kwestii poufności i bezpieczeństwa w sieci i związanych z tym algorytmów kryptograficznych. Można pytać ogólnie o wady i zalety włączenia własnego komputera do sieci (dostęp do ,,globalnych zasobów'' kosztem narażenia bezpieczeństwa ,,własnych zasobów''), czy podanie przykładów nowych zastosowań komputerów -- wyszukiwanie informacji w dużych sieciach i tekstowe bazy danych, mobile intelligent agents i tym podobne zagadnienia.



Literatura

  • Tanenbaum Distributed Operating Systems

  • Coulouris, Dollimore, Kindberg Distributed Systems: Concepts and Design

  • Ben-Ari Podstawy programowania współbieżnego i rozproszonego

  • Comer Sieci komputerowe TCP/IP. Zasady, protokoły i architektura

  • Stevens Programowanie zastosowań sieciowych w systemie Unix

  • Brown Unix Distributed Programming

  • Gabassi, Dupouy Przetwarzanie rozproszone w systemie Unix



Obliczenia numeryczne -- najważniejsze zagadnienia

Od magistranta oczekuje się znajomości podstawowych pojęć dotyczących obliczeń numerycznych, do których należą:

  • reprezentacja i działania na liczbach (zmiennopozycyjnych i stałopozycyjnych)
  • stabilność numeryczna
  • poprawność numeryczna
  • uwarunkowanie zadania
oraz wiedza na temat typowych zadań numerycznych, do których należą:
  • aproksymacja
  • kwadratury
  • obliczenia macierzowe
  • rozwiązywanie układów równań liniowych i nieliniowych
przy czym jedno z wymienionych zadań numerycznych magistrant powinien omówić szczegółowo.



Literatura

  • Jankowscy Przegląd metod i algorytmów numerycznych I, II


Bazy danych -- główne zagadnienia

Od magistranta oczekuje się znajomości najważniejszych zagadnień związanych z teorią i praktyką baz danych. Magistrant powinien poruszyć następujące zagadnienia:

  • języki i metody dostępu do baz danych
  • narzędzia CASE w projektowaniu i analizie baz danych
  • relacyjne bazy danych
  • spójność baz danych
i rozwinąć jedno z nich.



Literatura

  • według zaleceń wykładowcy przedmiotu ,,Bazy danych'' w danym roku akademickim



Duże programy i metodyka ich wytwarzania

Oprogramowanie używane w praktyce, często zwane systemami, różni się dość zasadniczo od programów będących realizacjami algorytmów rozwiązywania dobrze określonych zadań. Najbardziej rzuca się w oczy różnica rozmiaru: systemy liczą często wiele set tysięcy wierszy kodu. Inną istotną różnicą jest znacznie mniejsze znaczenie ,,problemu stopu'', np. dobrze skonstruowane systemy operacyjne nigdy nie ,,zatrzymują się''. Jeszcze inna różnica polega na tym, że programu tego typu rzadko kiedy można uznać za skończone raz na zawsze: pełniąc określone funkcje użytkowe ewoluują one wślad za ewolucją wymagań użytkowych, same na taką ewolucję zresztą wpływają.

W pytaniu chodzi o wykazanie różnic między ,,małymi'' i ,,dużymi'' programami, o wykazanie znajomości modeli cyklu życia (przynajmniej dwu: kaskadowego i spiralnego), problemów ewolucji dużych programów oraz o wykazanie znajomości podstawowych problemów wytwarzania dużych programów, takich jak: organizacja pracy zespołów programistycznych, kontroli jakości, zarządzania wersjami, rozkładu kosztów wytwarzania, roli testowania i problematyki scalania, tworzenia dokumentacji technicznej i użytkowej, rozkładu i klasyfikacji błędów, zależności od specyfikacji.

Magistrant powinien też przedstawić zarys informacji o dostępnych narzędziach wspomagających wytwarzanie dużych programów.



Literatura

  • notatki do wykładu



Matematyka dyskretna i jej zastosowania w informatyce

Każda nauka, a taką niewątpliwie jest informatyka, potrzebuje formalnego języka do opisu pojawiających się w niej problemów, jak również formalnych metod pozwalających na ich rozwiązywanie. Matematyka dyskretna obejmuje te działy matematyki, które oprócz teorii mnogości i logiki są podstawowe dla informatyki. Należą do nich kombinatoryka, teoria grafów, algebra, teoria liczb, (dyskretny) rachunek prawdopodobieństwa.

Magistrant powinien potrafić dać przykłady zastosowań tych działów matematyki w różnych dziedzinach informatyki, jak np.:

  • semantyka i weryfikacja programów -- logika, algebra;
  • projektowanie i analiza algorytmów -- kombinatoryka, teoria grafów, rachunek prawdopodobieństwa;
  • systemy operacyjne -- kombinatoryka, rachunek prawdopodobieństwa;
  • metody projektowania i realizacji języków programowania -- kombinatoryka, teoria grafów, algebra;
  • języki formalne i teoria obliczeń -- kombinatoryka, teoria grafów, algebra, teoria liczb;
  • bazy danych -- logika, algebra, teoria liczb.



Literatura

  • Graham, Knuth, Patashnik Matematyka konkretna

  • Lipski Kombinatoryka dla programistów



Metody reprezentacji wiedzy i ich zastosowanie w różnych działach sztucznej inteligencji.

Spośród istniejących paradygmatów reprezentacji wiedzy, studenci powinni wymienić przede wszystkim logikę pierwszego rzędu, w tym reprezentację klauzulową i regułę rezolucji, a to prowadzi do Prologu. Następnie, powinni wiedzieć co to są systemy produkcyjne i wnioskowanie progresywne, a także widzieć w tym kontekście ramy i sieci produkcyjne. Wybór adekwatnej metody reprezentacji wiedzy zależy oczywiście od zastosowania: czy są to systemy doradcze (ogólniej systemy z bazą wiedzy), systemy agentowe (ogólniej wieloagentowe), robotyka itd. W ramach tych zastosowań należy widzieć zagadnienia planowania, wnioskowanie o działaniach, czy przetwarzanie języka naturalnego, w tym maszynowe tłumaczenie.

Mówiąc o różnych paradygmatach reprezentacji wiedzy studenci powinni mieć świadomość heurystycznego, a nie tylko algorytmicznego charakteru wiedzy znajdującej zastosowanie w różnych działach sztucznej inteligencji.