Uniwersytet Warszawski University of Warsaw
Menu
Wyszukiwarka
 W bieżącym katalogu

PYTANIA NA EGZAMIN LICENCJACKI

Rok akademicki 2000/2001
Opracował zespól pracowników Wydziału Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego.

KIERUNEK INFORMATYKA

WSTĘP DO TEORII MNOGOŚCI

  1. Relacja równoważności i jej własności.
  2. Liczby kardynalne.
  3. Porządki częściowe i ich własności. Twierdzenie o punkcie stałym.
  4. Liczby porządkowe i indukcja.

LOGIKA

  1. Relacja konsekwencji semantycznej w logice pierwszego rzędu i jej związek z pojęciem formalnego dowodu.
  2. Przykłady opisu własności struktur matematycznych w logice pierwszego rzędu.
  3. Pojęcie rozmaitości algebr.
  4. Homomorfizmy i kongruencje algebr.

ELEMENTY MATEMATYKI DYSKRETNEJ

  1. Liczby szczególne występujące w kombinatoryce.
  2. Równania rekurencyjne i funkcje tworzące.
  3. Drzewa i cykle w grafach.
  4. Grafowe problemy optymalizacji i algorytmy dla nich.
  5. Planarność i kolorowanie grafów.
  6. Liczby pierwsze i ich własności.
  7. Ciała skończone.
  8. Dyskretne zmienne losowe i ich rozkłady.
  9. Nierówności probabilistyczne.
  10. Łańcuchy Markowa i błądzenie losowe.

ANALIZA MATEMATYCZNA

  1. Ciągłość funkcji i najważniejsze własności funkcji ciągłych.
  2. Pochodna funkcji jednej zmiennej, interpretacja geometryczna i mechaniczna.
  3. Twierdzenie o wartości średniej w rachunku różniczkowym funkcji jednej zmiennej, jego interpretacja geometryczna i niektóre konsekwencje (monotoniczność, wklęsłość, wypukłość, szacowanie przyrostów).
  4. Wzór Taylora dla funkcji jednej zmiennej, zastosowania do obliczeń przybliżonych, rozwijanie funkcji w szeregi potęgowe.
  5. Pojęcie zbieżności ciągów liczbowych i funkcyjnych, twierdzenia o przejściu do granicy pod znakiem pochodnej i całki.
  6. Ekstrema funkcji.
  7. Funkcja pierwotna, całka oznaczona. Zastosowania geometryczne.
  8. Całka Riemanna.

ALGEBRA LINIOWA I JEJ METODY OBLICZENIOWE

  1. Definicja grupy i grupy przemiennej.
  2. Przestrzeń liniowa nad ciałem K. Baza przestrzeni liniowej.
  3. Niezmienniki przekształceń liniowych.
  4. Rozwiązywanie układów równań liniowych.
  5. Numeryczna poprawność, numeryczna stabilność i uwarunkowanie zadania.

METODY NUMERYCZNE

  1. Interpolacja i aproksymacja numeryczna - przykłady.
  2. Metody numeryczne rozwiązywania układów równań algebraicznych liniowych.
  3. Rozwiązywanie równań i układów równań nieliniowych. Metody iteracyjne.

WSTĘP DO PROGRAMOWANIA

  1. Reprezentacja w pamięci danych typów prostych i złożonych.
  2. Arytmetyka stałopozycyjna i zmiennopozycyjna.
  3. Rekurencja i jej realizacja.
  4. Mechanizmy strukturalizacji programów.

METODY PROGRAMOWANIA

  1. Listy, drzewa i ich zastosowania.
  2. Stosy i kolejki.
  3. Metody przeszukiwania grafów. Zastosowania.
  4. Metody projektowania algorytmów (dziel i rządź, programowanie dynamiczne i algorytmy zachłanne).

ALGORYTMY I STRUKTURY DANYCH

  1. Kryteria oceny efektywności algorytmów.
  2. Koszt zamortyzowany.
  3. Podstawowe algorytmy sortowania.
  4. Słowniki i metody ich realizacji.
  5. Kolejki priorytetowe i metody ich realizacji.

SEMANTYKA I WERYFIKACJA PROGRAMÓW

  1. Weryfikacja poprawności programów. Metoda niezmienników. Logika Hoare'a.
  2. Metoda kolejnych uściśleń (ang. stepwise-refinment) specyfikacji i weryfikacji programów.
  3. Metoda denotacyjna definiowania semantyki języków programowania.
  4. Przekazywanie parametrów w procedurach i reguły widoczności zmiennych.

JĘZYKI, AUTOMATY I OBLICZENIA

  1. Automaty skończone i wyrażenia regularne.
  2. Gramatyki bezkontekstowe i automaty ze stosem.
  3. Lematy o pompowaniu dla języków regularnych i bezkontekstowych. Przykłady zastosowań.
  4. Zbiory obliczalne a zbiory częściowo obliczalne.
  5. Hierarchia językow formalnych wg Chomsky'ego.
  6. NP-zupełność. Odpowiedniość gramatyk i modeli obliczeń.

PROGRAMOWANIE OBIEKTOWE

  1. Pojęcia klasy i obiektu. Przykład klasy i kilku obiektów tej klasy.
  2. Dziedziczenie. Przykład hierarchii klas.
  3. Standardowe kolekcje w Smalltalku.
  4. Metody wirtualne. Przykład ilustrujący ich użyteczność.
  5. Konstruktory i destruktory. Rodzaje konstruktorów w C++.

BAZY DANYCH

  1. Struktura relacyjnej bazy danych.
  2. Zależności funkcyjne zbiorów atrybutów.
  3. Spójność referencyjna baz danych.
  4. Podstawowe konstrukcje języka SQL.
  5. Trzecia postać normalna baz danych.

PROGRAMOWANIE WSPÓŁBIEŻNE

  1. Poprawność programu współbieżnego.
  2. Notacje/języki do zapisu programów współbieżnych w systemach scentralizowanych i rozproszonych.
  3. Klasyczne problemy współbieżności (problem rejonu krytycznego, problem producenta-konsumenta, czytelników i pisarzy, 5 filozofów) i przykłady ich rozwiązania.
  4. Modele komunikacji i synchronizacji procesów w systemach rozproszonych na przykładzie CSP, Ady, Lindy.

SYSTEMY OPERACYJNE

  1. Mechanizmy sprzętowe potrzebne do realizacji wielodostępnych, wieloprocesowych systemów operacyjnych.
  2. Pamięć wirtualna. Cechy charakterystyczne różnych technik realizacji pamięci wirtualnej.
  3. Algorytmy szeregowania procesów.
  4. Funkcje systemowe do obsługi plików z poziomu użytkownika (czynności wykonywane przez system operacyjny, struktury danych).
  5. Sposoby realizacji pamięci dzielonej w systemach rozproszonych (wieloprocesorowych i wielokomputerowych).

ARCHITEKTURA KOMPUTERÓW I PROGRAMOWANIE NISKOPOZIOMOWE

  1. Sposoby współpracy procesora ze sterownikami urządzeń zewnętrznych.
  2. Metody obsługi przerwania.
  3. Mechanizm ochrony pamięci. Pamięć wirtualna.
  4. Działanie interfejsu równoległego i szeregowego.
  5. Typowy cykl wykonania instrukcji przez procesor.

SIECI KOMPUTEROWE

  1. Protokół Ethernet.
  2. Warstwy protokołów modelu OSI.
  3. Mechanizm trasowania (ang. routing) pakietów w Internecie.
  4. Mechanizm retransmisji pakietów w protokole TCP.

INŻYNIERIA OPROGRAMOWANIA

  1. Przykłady modeli cyklu tworzenia oprogramowania (wodospadowy, spiralny, szybkie prototypowanie).
  2. Strukturalne modelowanie danych (diagram ERD).
  3. Szacowanie kosztów wykonania programu.
  4. Zarządzanie jakością w przedsięwzięciu informatycznym.

KIERUNEK MATEMATYKA

WSTĘP DO MATEMATYKI

  1. Relacje równoważności, klasy abstrakcji. Jaki związek łączy relacje równoważności w zbiorze z podziałami tego zbioru? Przykłady konstrukcji ilorazowej (w algebrze, topologii lub w innej dziedzinie).
  2. Relacja (częściowego) porządku. Przykłady własności zbiorów liniowo uporządkowanych, których nie musi mieć każdy zbiór (częściowo) uporządkowany, i własności zbiorów dobrze uporządkowanych, których nie musi mieć każdy zbiór liniowo uporządkowany. Lemat Kuratowskiego-Zorna, przykłady zastosowań.
  3. Równoliczność zbiorów. Co to znaczy, że moc zbioru A jest mniejsza od mocy zbioru B? Przykłady zbiorów przeliczalnych i nieprzeliczalnych. Czy każdy zbiór nieprzeliczalny jest równoliczny ze zbiorem wszystkich liczb rzeczywistych? Czy istnieje zbiór o największej mocy?
  4. Obraz i przeciwobraz wyznaczony przez funkcję, własności. Rozdzielność funkcji obrazu (przeciwobrazu) względem działań na zbiorach. Uzasadnij, że obraz zbioru A wyznaczony przez funkcję jest równoliczny z pewnym zbiorem ilorazowym zbioru A.

ANALIZA MATEMATYCZNA

  1. Ciągi liczb rzeczywistych. Zbieżność ciągu, warunek Cauchy'ego, zupełność zbioru liczb rzeczywistych.
  2. Szeregi liczbowe, zbieżność bezwzględna i warunkowa. Przykłady kryteriów zbieżności i ich zastosowań.
  3. Ciągłość i jednostajna ciągłość funkcji i odwzorowań. Twierdzenie o osiąganiu kresów przez funkcję ciągła na przedziale domkniętym. Przykład funkcji ciągłej niejednostajnie ciągłej.
  4. Pochodna funkcji:
    • zmiennej rzeczywistej;
    • odwzorowania.
Pochodne cząstkowe. Obliczanie pochodnych.
  • Twierdzenia o wartości średniej rachunku różniczkowego funkcji jednej zmiennej (twierdzenie Rolle'a i Lagrange'a). Przykład zastosowania.
  • Szeregi potęgowe; przedział zbieżności, różniczkowanie i całkowanie szeregu potęgowego, przykłady.
  • Ekstrema funkcji:
    • jednej zmiennej;
    • wielu zmiennych.
    Warunki konieczne i dostateczne. Przykład wyznaczania ekstremum.
  • Całka funkcji jednej zmiennej. Całka nieoznaczona i oznaczona. Zasadnicze twierdzenie rachunku różniczkowego i całkowego. Obliczanie całek.
  • Całki iterowane (twierdzenie Fubiniego). Przykłady obliczania całek iterowanych.
  • Wzór na całkowanie przez podstawienie:
    • dla funkcji jednej zmiennej;
    • dla funkcji wielu zmiennych.
    Przykład zastosowania.
  • Twierdzenie o zmajoryzowanym przechodzeniu do granicy w teorii całki Lebesgue'a. Przykład zastosowania.
  • Przykład wzoru zamieniającego całkę po obszarze na płaszczyźnie na całkę po brzegu tego obszaru.

    GAL

    1. Rozwiązywanie układów równań liniowych. Elementarne operacje na macierzach, metoda eliminacji Gaussa. Twierdzenia Kroneckera-Cappelli'ego i Cramera.
    2. Ciała: definicja, przykłady. Liczby zespolone: własności, postać trygonometryczna, pierwiastkowanie, zasadnicze twierdzenie algebry.
    3. Przestrzenie liniowe: definicja, przykłady. Układy liniowo niezależne, bazy, wymiar przestrzeni liniowej.
    4. Przekształcenia liniowe: definicja, przykłady, macierz przekształcenia liniowego. Monomorfizmy, epimorfizmy, izomorfizmy. Jądro i obraz przekształcenia liniowego.
    5. Przestrzenie własne i wartości własne endomorfizmów liniowych, sposoby ich znajdowania. Podobieństwo macierzy, diagonalizowalność, postać Jordana macierzy, twierdzenie Jordana.
    6. Rząd, wyznacznik i ślad macierzy. Sposoby obliczania. Przykłady zastosowań.
    7. Przestrzenie przekształceń liniowych. Funkcjonały liniowe, przestrzeń sprzężona do przestrzeni liniowej, baza sprzężona.
    8. Formy dwuliniowe i kwadratowe: definicje, przykłady, macierz formy dwuliniowej. Diagonalizacja form dwuliniowych i kwadratowych, twierdzenie o bezwładności.
    9. Iloczyny skalarne: definicja, przykłady, kryterium Sylvestera. Przestrzenie euklidesowe, miary, kąty. Izometrie.

    WSTĘP DO INFORMATYKI

    1. Problem algorytmiczny i jego rozwiązanie. Przykłady.
    2. Funkcje i procedury rekurencyjne. Przykłady.
    3. Metoda programowania "dziel i rządź". Zastosowania.
    4. Sposoby reprezentacji grafu, przeszukiwanie grafu wszerz i w głąb. Zastosowania.
    5. Złożoność obliczeniowa algorytmu.
    6. Co wiesz o hipotezie PNP?
    7. Reprezentacja i arytmetyka liczb rzeczywistych w komputerze.

    ALGEBRA

    1. Pojęcia grupy, podgrupy, homomorfizmu i izomorfizmu grup. Przykłady grup (grupy permutacji, grupy izometrii, grupy macierzy), twierdzenie Cayley'a.
    2. Pierścienie: definicja i przykłady.

      Homomorfizmy pierścieni, ideały pierwsze i maksymalne.

    3. Konstrukcje ilorazowe na przykładzie grup i pierścieni. Twierdzenia o izomorfizmie.
    4. Związki pomiędzy rzędem grupy i rzędami podgrup, twierdzenia Lagrange'a, Cauchy'ego i Sylowa.
    5. Iloczyn prosty grup, klasyfikacja skończonych grup abelowych.
    6. Dzielniki zera, elementy odwracalne w pierścieniach. Konstrukcja ciała ułamków dziedziny całkowitości.

    TOPOLOGIA

    1. Pojęcie przestrzeni topologicznej. Topologia przestrzeni. Czy każda topologia pochodzi od jakiejś metryki? (wyjaśnij użyte pojęcia, podaj przykłady)
    2. Definicja ciągłości funkcji dla przestrzeni metrycznych i dla przestrzeni topologicznych. Równoważność tych definicji w przypadku przestrzeni metrycznych (z uzasadnieniem)
    3. Przestrzenie zwarte: definicja, przykłady. Metryczny warunek zwartości. Zwarte podzbiory przestrzeni Rn, funkcje ciągłe określone na przestrzeni zwartej.
    4. Przestrzenie metryczne zupełne: definicje, przykłady. Czy przestrzeń metryczna zwarta jest zupełna, czy przestrzeń zupełna i ograniczona jest zwarta (dlaczego tak/nie)?
      Twierdzenie Baire'a. Dlaczego nie można opuścić żadnego z założeń tego twierdzenia?
    5. Spójność i łukowa spójność przestrzeni topologicznych. Czy któraś z tych własności implikuje drugą? (przykład na brak wynikania w którąś stronę, wyjaśnij użyte pojęcia, podaj przykłady).
    6. Homeomorficzność przestrzeni topologicznych, przykłady. Czy z istnienia ciągłej bijekcji f: X -> Y wynika istnienie homeomorfizmu? Czy takie wynikanie ma miejsce przy jakichś szczególnych założeniach o przestrzeniach?

    RÓWNANIA RÓŻNICZKOWE ZWYCZAJNE

    1. Istnienie rozwiązań równań różniczkowych. Zagadnienie Cauchy'ego, istnienie rozwiązań lokalnych, jednoznaczność rozwiązań, przykłady.
    2. Przedłużalność rozwiązań. Zachowanie rozwiązania przy przedłużaniu.
    3. Własności rozwiązań układów równań liniowych. Rozwiązania układu jednorodnego, przestrzeń rozwiązań, układ fundamentalny, wyznacznik Wrońskiego, konstrukcja rozwiązania układu niejednorodnego.
    4. Układy liniowe o stałych współczynnikach. Konstrukcja rozwiązań, wykorzystanie postaci Jordana macierzy.
    5. Klasyfikacja punktów osobliwych układów liniowych na płaszczyźnie. Postać kanoniczna układu liniowego na płaszczyźnie, punkty osobliwe stabilne i niestabilne, węzeł, ognisko, środek, siodło.

    RACHUNEK PRAWDOPODOBIEŃSTWA

    1. Model doświadczenia losowego. Aksjomaty teorii prawdopodobieństwa. Klasyczna definicja prawdopodobieństwa. Prawdopodobieństwo geometryczne. Paradoksy w teorii prawdopodobieństwa.
    2. Prawdopodobieństwo warunkowe. Wzór na prawdopodobieństwo całkowite i wzór Bayesa. Przykłady zastosowań obu wzorów.
    3. Niezależność zdarzeń i zmiennych losowych. Model probabilistyczny dla ciągu niezależnych doświadczeń. Schemat Bernoulliego i twierdzenie Poissona.
    4. Zmienne losowe i rozkłady prawdopodobieństwa. Dystrybuanty, gęstości. Typy rozkładów (dyskretne, ciągłe). Parametry rozkładów (wartość oczekiwana i wariancja).
    5. Ważniejsze rozkłady prawdopodobieństwa (Bernoulliego, Poissona, wykładniczy, gaussowski). Przykłady zagadnień, w których pojawiają się poszczególne rozkłady.
    6. Twierdzenia graniczne: prawa wielkich liczb, twierdzenie de Moivre'a-Laplace'a i centralne twierdzenie graniczne. Przykłady zastosowań.

    MATEMATYKA OBLICZENIOWA

    1. Numeryczne rozkłady macierzy: trójkątno-trójkątny (LU) i ortogonalno-trójkątny (QR). Zastosowania do rozwiązywania układów równań algebraicznych liniowych. Koszt, własności numeryczne.
    2. Normy wektorowe i macierzowe oraz ich własności. Wrażliwość numerycznych rozwiązań układu równań liniowych na zaburzenia danych.
    3. Metody numerycznego rozwiązywania równań nieliniowych skalarnych. Szybkość i warunki zbieżności tych metod.
    4. Metody numerycznego rozwiązywania zagadnienia własnego macierzy symetrycznej. Zbieżność i koszt tych metod.
    5. Kwadratury interpolacyjne i złożone dla numerycznego całkowania funkcji jednej zmiennej. Zbieżność kwadratur złożonych.
    6. Interpolacja. Aproksymacja w przestrzeniach unitarnych oraz jednostajna. Zastosowania w matematyce obliczeniowej.