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

WYDZIAŁ MATEMATYKI INFORMATYKI I MECHANIKI
UNIWERSYTETU WARSZAWSKIEGO

SPRAWDZIAN DLA POWRACAJĄCYCH
NA STUDIA NA WYDZIALE MIM

Opracował zespól pracowników
Wydziału Matematyki, Informatyki i Mechaniki
Uniwersytetu Warszawskiego.

Rok akademicki 2000/2001

KIERUNEK INFORMATYKA

WSTĘP DO TEORII MNOGOŚCI

  1. Relacja równoważności i jej własności.
  2. Porządki częściowe i ich własności.
  3. Indukcja.

Literatura:

H.Rasiowa "Wstęp do matematyki współczesnej"

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. Liczby pierwsze i ich własności.
  5. Dyskretne zmienne losowe i ich rozkłady.

Literatura:

W. Lipski "Kombinatoryka dla programistów"

T.H. Cormen, C.E. Leiserson, R.L.Rivest "Wprowadzenie do algorytmów"

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 rachunków 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.

Literatura:

F.Leja "Rachunek różniczkowy i całkowy"

ALGEBRA LINIOWA I JEJ METODY OBLICZENIOWE

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

Literatura:

A.Kiełbasiński - Notatki do wykładu (Można otrzymać w kiosku na terenie Wydziału)

METODY NUMERYCZNE

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

Literatura:

J.M. Jankowscy, M.Dryja "Przegląd metod i algorytmów numerycznych"

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.

Literatura:

L.Banachowski, A.Kreczmar "Elementy analizy algorytmów"

T.H. Cormen, C.E. Leiserson, R.L.Rivest "Wprowadzenie do algorytmów"

N.Wirth "Wstęp do programowania systematycznego"

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).

Literatura:

T.H. Cormen, C.E. Leiserson, R.L.Rivest "Wprowadzenie do algorytmów"

ALGORYTMY I STRUKTURY DANYCH

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

Literatura:

N.Wirth "Wstęp do programowania systematycznego"

SEMANTYKA I WERYFIKACJA PROGRAMÓW

  1. Weryfikacja poprawności programów. Metoda niezmienników. Logika Hoare'a.
  2. Przekazywanie parametrów w procedurach i reguły widoczności zmiennych.

Literatura:

M.Gordon "Denotacyjny opis języków programowania"

JĘZYKI, AUTOMATY I OBLICZENIA

  1. Automaty skończone i wyrażenia regularne.
  2. Gramatyki bezkontekstowe i automaty ze stosem.
  3. NP-zupełność.

Literatura:

J.E.Hopcroft, J.D.Ullman "Wprowadzenie do teorii automatów, języków i 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. Metody wirtualne. Przykład ilustrujący ich użyteczność.
  4. Konstruktory i destruktory. Rodzaje konstruktorów w C++.

Literatura:

P.Coad, J Nicolla "Programowanie obiektowe"

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.

Literatura:

J.Ullman, J.Vidom "Podstawowy wykład baz danych"

PROGRAMOWANIE WSPÓŁBIEŻNE

  1. Poprawność programu współbieżnego.
  2. 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.

Literatura:

Ben-Ari "Programowanie współbieżne i rozproszone"

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).

Literatura:

A.Silberschatz, P.B.Galvin "podstawy systemow operacyjnych"

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?
  2. Relacja (częściowego) porządku.
  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.

Literatura:

H.Rasiowa "Wstęp do matematyki współczesnej"

ANALIZA MATEMATYCZNA

  1. Ciągi liczb rzeczywistych. Zbieżność ciągu, warunek Cauchy'ego, zupełność zbioru liczb rzeczywistych.
  2. Szeregi liczbowe i funkcyjne, zbieżność bezwzględna, warunkowa, jednostajna. 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łą na przedziale domkniętym.
  4. Pochodna funkcji. Pochodne cząstkowe. Obliczanie pochodnych.
  5. Twierdzenia o wartości średniej rachunku różniczkowego funkcji jednej zmiennej (twierdzenie Rolle'a i Lagrange'a). Przykład zastosowania.
  6. Szeregi potęgowe; przedział zbieżności, różniczkowanie i całkowanie szeregu potęgowego, przykłady.
  7. Ekstrema funkcji:
    1. jednej zmiennej;
    2. wielu zmiennych.
    Warunki konieczne i dostateczne.
  8. Całka funkcji jednej zmiennej. Całka nieoznaczona i oznaczona. Zasadnicze twierdzenie rachunku różniczkowego i całkowego. Obliczanie całek funkcji jednej i wielu zmiennych.

Literatura:

F.Leja "Rachunek różniczkowy i całkowy"

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.
  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. Iloczyny skalarne: definicja, przykłady, kryterium Sylvestera. Przestrzenie euklidesowe. Izometrie.

Literatura:

Maria Moszyńska, Joanna Święcicka "Geometria z algebrą liniową"

Andrzej Białynicki - Birula "Algebra liniowa z geometrią"

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 $P \neq NP$?
  7. Reprezentacja i arytmetyka liczb rzeczywistych w komputerze.

Literatura:

Niklas Wirth "Algorytmy + struktury danych = programy"

ALGEBRA

  1. Pojęcia grupy, podgrupy, homomorfizmu i izomorfizmu grup. Przykłady grup (grupy permutacji, grupy izometrii, grupy macierzy), twierdzenie Cayley'a.
  2. Związki pomiędzy rzędem grupy i rzędami podgrup, twierdzenia Lagrange'a, Cauchy'ego i Sylowa.
  3. Pierścienie: definicja i przykłady. Homomorfizmy pierścieni, ideały pierwsze i maksymalne.
  4. Dzielniki zera, elementy odwracalne w pierścieniach. Konstrukcja ciała ułamków dziedziny całkowitości.
  5. Konstrukcje ilorazowe na przykładzie grup i pierścieni. Twierdzenia o izomorfizmie.

Literatura:

J.Browkin "Wybrane zagadnienia z algebry"

J.Browkin "Teoria ciał"

A.Białynicki - Birula "Zarys algebry"

TOPOLOGIA

  1. Pojęcie przestrzeni topologicznej. Topologia przestrzeni. Czy każda topologia pochodzi od jakiejś metryki?
  2. Definicja ciągłości funkcji dla przestrzeni metrycznych i dla przestrzeni topologicznych. Równoważność tych definicji w przypadku przestrzeni metrycznych.
  3. Przestrzenie zwarte: definicja, przykłady. Metryczny warunek zwartości. Zwarte podzbiory przestrzeni $R^n,$ 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 takie)?
  5. Spójność i łukowa spójność przestrzeni topologicznych. Czy któraś z tych własności implikuje drugą?
  6. Homeomorficzność przestrzeni topologicznych, przykłady.

Literatura:

K. Janich "Topologia"

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.

Literatura:

I.Pietrowski "Równania różniczkowe zwyczajne"

RACHUNEK PRAWDOPODOBIEŃSTWA

  1. Przestrzeń probabilistyczna. Aksjomaty teorii prawdopodobieństwa. Klasyczna definicja prawdopodobieństwa. Prawdopodobieństwo geometryczne.
  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ń.

Literatura:

S.Zubrzycki "Wykłady z rachunku prawdopodobieństwa i statystyki matematycznej"

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.

Literatura:

J.M.Jankowscy, M.Dryja "Przegląd metod i algorytmów numerycznych" TI,II

Ta strona została stworzona na podstawie pliku w formacie LaTeX2e przy użyciu konwertera Latex2HTML
Piotr Krzyżanowski 2000-12-01