Wydział MIM UW - Pytania na egzamin licencjacki dla studentów kończących ZSI

Zawodowe Studia Informatyki

Zestaw pytań na egzamin licencjacki oraz rozmowę kwalifikacyjna na magisterskie studia uzupelniajace

Postać trygonometryczna liczb zespolonych i jej zastosowania.
Układy równań liniowych i sposoby ich rozwiązywania oraz twierdzenie Kroneckera-Capelli'ego.
Baza przestrzeni liniowej i jej własności.
Wartości i wektory własne przekształceń liniowych, diagonalizacja macierzy kwadratowych.
Iloczyn skalarny i wielkości, które się przezeń wyrażają.

Analiza
Definicja granicy ciągu, warunek Cauchy'ego, arytmetyczne własności granicy, zbieżność ciągów monotonicznych.
Definicja funkcji ciągłej. Własności funkcji ciągłej określonej na przedziale - przyjmowanie kresów, przyjmowanie wartości pośrednich.
Pojęcie szeregu i szeregu zbieżnego. Kryteria zbieżności: ilorazowe (d'Alemberta), pierwiastkowe (Cauchy'ego) i Leibniza.
Szeregi potęgowe: przedział zbieżności i promień zbieżności, rozwinięcia funkcji expx, ln(1+x), sinx.
Pojęcie pochodnej cząstkowej i gradientu.

Wstęp do matematyki
Reguły zaprzeczania, koniunkcji, alternatywy i implikacji.
Relacja równoważności. Tworzenie klas abstrakcji.
Relacja porządku. Dobre uporządkowanie. Zasada indukcji.
Zbiory przeliczalne i nieprzeliczalne.
Definicja funkcji. Różne rodzaje funkcji (monotoniczna, okresowa, parzysta, nieparzysta). Przykłady.

Wstęp do logiki
Twierdzenie o pełności dla klasycznego rachunku predykatow i pojęcia w nim występujące.
Rozpoznawanie tautologii i formuł spełnialnych pierwszego rzędu.
Twierdzenie o dedukcji i jego zastosowania.

Elementy matematyki dyskretnej
Podstawowe obiekty kombinatoryczne (podzbiory, funkcje, permutacje, podziały zbioru) i metody ich zliczania.
Równania rekurencyjne i sposoby ich rozwiązywania.
Podstawowe Twierdzenie Arytmetyki.
Asymptotyka funkcji liczbowych; notacja O.
Istnienie cykli Eulera i Hamiltona w grafach; warunki wystarczające i/lub konieczne.

Meotdy numeryczne
Podstawowe pojęcia związane z numerycznym rozwiązywaniem zadań w arytmetyce maszyny cyfrowej (uwarunkowanie zadania, numeryczna poprawność algorytmu).
Numeryczna realizacja algorytmu eliminacji Gaussa rozwiązywania skończonych układów równań liniowych.
Ogólne zadanie interpolacji i szczególny przypadek interpolacji wielomianowej.
Co to sa kwadratury numeryczne? Różne rodzaje kwadratur.
Metody iteracyjne bisekcji i siecznych (Newtona) rozwiązywania skalarnych równań nieliniowych.

Wstęp do programowania
Problem algorytmiczny - Algorytm - Program. Charakterystyka różnic między tymi pojeciami i związków między nimi.
Metoda niezmienników dowodzenia poprawności pętli.
Podstawowe struktury danych w Pascalu. Ograniczenia w ich stosowaniu.
Procedury i funkcje. Implementacja, widoczność zmiennych, rola parametrów.
Rekurencja.

Techniki programowania
Listy. Metody implementacji. Listy 2-kierunkowe, cykliczne. Przykłady zastosowań.
Kolejki, stosy, kolejki priorytetowe. Przykłady zastosowań.
Metody reprezentacji grafów. Podstawowe algorytmy grafowe.
Drzewa. Zastosowanie drzew binarnych. Rownoważenie drzew.
Problem słownika.

Algorytmy i struktury danych
Podstawowe charakterystyki algorytmu i metody ich określania.
Algorytmy dynamiczne i zachłanne.
Sortowanie.
Wyszukiwanie i selekcja.
Problem Find-Union.

Rachunek prawdopodobieństwa
Pojęcie prawdopodobieństwa; definicja aksjomatyczna i klasyczna.
Przykłady rozkładów prawdopodobieństwa.
Niezależność i schemat Bernoulliego.
Prawa wielkich liczb i przykłady ich zastosowań.
Centralne twierdzenie graniczne; przykłady zastosowań.
Najpoważniejsze różnice między zagadnieniami rachunku prawdopodobieństwa i statystyki (przykłady).

Metody optymalizacji
Warunki konieczne i dostateczne optymalności w programowaniu liniowym.
Dualne zadania programowania liniowego.
Metoda sympleks.
Zadanie transportowe.
Metoda podziału i ograniczeń.

Analiza algorytmów
Techniki projektowania algorytmów równoległych.
Sieci sortujące Batchera.
Algorytm KMP wyszukiwania wzorca.
Algorytm Grahama znajdowania otoczki wypukłej.
Algorytmy aproksymacyjne dla problemów NP-zupełnych.

Systemy operacyjne
Rozwój systemów operacyjnych jest związany z rozwojem sprzętu. Jakie mechanizmy sprzętowe są potrzebne do realizacji wielodostępnych, wieloprocesowych systemów operacyjnych.
Co to jest pamięć wirtualna? Jakie sa cechy charakterystyczne różnych technik realizacji pamięci wirtualnej? Jakie problemy wymagają rozwiązania?
Warunki konieczne występowania zastoju i możliwe strategie zapobiegania zastojowi.
Algorytmy szeregowania procesów. Wady i zalety tych algorytmów z punktu widzenia określonych kryteriów szeregowania.
Funkcje i sposoby realizacji systemu plików.

Programowanie obiektowe
Podejście obiektowe w analizie i projektowaniu.
Podstawowe konstrukcje obiektowe w językach obiektowych.
Różnice między podejściem obiektowym a strukturalnym w programowaniu.
Polimorfizm w językach obiektowych - na czym polega, jakie ma zastosowanie.
Pojęcie dziedziczenia.

Programowanie współbieżne
Problem wzajemnego wykluczania się rejonów krytycznych. Warunki, które musi spełniać poprawne rozwiązanie tego problemu.
Na czym polega poprawność programu współbieżnego i jakie przyjmuje się podstawowe zalożenia? Przyklady naruszenia własności poprawności.
Notacje do zapisu programów współbieżnych w systemach scentralizowanych i rozproszonych.
Klasyczne problemy współbieżności (problem producenta-konsumenta, czytelników i pisarzy, 5 filozofów).

Architektura komputerów
Co to są układy sekwencyjne i kombinacyjne? Czym sie różnią? Przyklady.
Poszczególne fazy cyklu rozkazowego procesora.
Typowe tryby adresowe stosowane we współczesnych procesorach.
Na czym polega mikroprogramowanie? Jaki zbiór mikrooperacji opisuje pojedyncza mikroinstrukcja?
Co to jest przerwanie? Jakie są rodzaje przerwań? Na czym polega maskowanie przerwań?
Na czym polega koncepcja RISC architektury procesora?

Metody realizacji języków programowania
Podział zadań związanych z analizą programów między analizator leksykalny, składniowy i kontekstowy.
Porównanie metod LL i LR analizy składniowej.
Budowa rekordu aktywacji w zależności od języka źródłowego i maszyny docelowej.
Reprezentacje w pamięci danych typów prostych i złożonych oraz zarządzanie pamięcią podczas wykonania programu.
Podstawowe optymalizacje programów z uwzględnieniem podziału na optymalizacje lokalne i globalne.

Języki i automaty
Wyrażenia regularne - pojęcie i zastosowania.
Gramatyki bezkontekstowe - pojęcie i zastosowania.
Problemy nierozstrzygalne - definicja i przykłady.
Twierdzenie Kleenego.
Modele obliczeń (automaty) równoważne gramatykom bezkontekstowym.

Bazy danych
Czym jest relacyjna baza danych?
Rodzaje więzów spójności w bazach danych.
Do czego służą diagramy zwiazków-encji?
Rodzaje złączeń tabel bazodanowych.
Efektywne sposoby wykonywania skomplikowanych zapytań do bazy danych, przykłady.

Sieci komputerowe
Rodzaje topologii sieci komputerowych.
Różnice między protokołami TCP i UDP.
Zadania protokołu IP.
Metody kontroli przepływu danych w protokole TCP.
Sposoby powiadamiania o błędach w protokołach pakietu TCP/IP.

Systemy rozproszone
Model ISO/OSI architektury sieci i funkcje wykonywane przez każdą warstwę.
Sieciowy system operacyjny i rozproszony system operacyjny, przykłady.
Działanie systemu NFS.
Różne sposoby realizacji pamięci dzielonej w systemach rozproszonych.
Przykłady algorytmów rozproszonych (wzajemnego wykluczania, elekcji).

Sztuczna inteligencja i systemy doradcze
Heurystyczne metody przeszukiwania przestrzeni stanów.
Algorytm minimax.
Automatyczne dowodzenie twierdzeń przy użyciu metody rezolucji.
Logika domniemań.
Planowanie w systemie STRIPS.

Wytwórstwo oprogramowania
Podaj przykład systematycznego podejścia do tworzenia oprogramowania, od specyfikacji wymagań do implementacji oraz zasady przejścia między wybranymi poziomami.
Omów dwa z poniższych terminów podając dla każdego z nich dwie odmienne interpretacje:
- wersja pilotowa oprogramowania,
- wdrożenie,
- wada ukryta oprogramowania,
- dokumentacja użytkownika.
Metody specyfikacji
Rola metod formalnych w procesie tworzenia oprogramowania.
Omów wybraną metodę specyfikacji programów.
Metody dowodzenia częściowej i całkowitej poprawności programów.

Technologia produkcji systemów informacyjnych
Jaka jest różnica między narzędziem a metodologią? Dlaczego w organizacji realizujacej wiele projektów ważne jest ustalenie spójnej metodologii?
Metodologia strukturalna wyróżnia szereg faz budowy systemow informatycznych. Wymień je i krótko scharakteryzuj.
Jaki jest główny cel analizy? Jakie typy modeli sa w niej wykorzystywane?
Do czego służy diagram przepływu danych? Z czego jest zbudowany?
Jakie jest przeznaczenie diagramu zwiazków encji? Jakie są jego podstawowe składniki?
Do czego służy środowiskowy model systemu? Co ma z nim wspólnego diagram kontekstowy?
Co jest celem projektowania? Opisz główne kroki budowy projektu systemu.
Podaj powody, dla których kierownicy projektów potrzebują modeli związanych z przebiegiem budowy systemu. Opisz krótko sieci PERT i diagramy Gantta. Co to jest ścieżka krytyczna?
Do czego służą narzędzia zarządzania wersjami oprogramowania (np. SCCS)?

Problemy społeczno-prawne rozwoju informatyki
Główne zasady prawa autorskiego w odniesieniu do programów komputerowych.
Rodzaje umów dotyczących oprogramowania i ich najważniejsze cechy.

Janina Mincer-Daszkiewicz
e-mail: jmd@mimuw.edu.pl