University of Warsaw - Central Authentication System
Strona główna

(in Polish) Algorytmy matematyki dyskretnej

General data

Course ID: 1000-135AMD
Erasmus code / ISCED: 11.1 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0541) Mathematics The ISCED (International Standard Classification of Education) code has been designed by UNESCO.
Course title: (unknown)
Name in Polish: Algorytmy matematyki dyskretnej
Organizational unit: Faculty of Mathematics, Informatics, and Mechanics
Course groups: Elective courses for 1st degree studies in mathematics
ECTS credit allocation (and other scores): 6.00 Basic information on ECTS credits allocation principles:
  • the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS;
  • the student’s weekly hourly workload is 45 h;
  • 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes;
  • weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS;
  • work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load.
view allocation of credits
Language: Polish
Type of course:

elective courses
Short description: (in Polish)

Wykład jest wprowadzeniem do algorytmiki opartym na prezentacji wybranych problemów obliczeniowych oraz algorytmów związanych z klasycznymi strukturami matematyki dyskretnej takimi jak grafy, drzewa, sieci przepływowe oraz języki regularne.
Full description: (in Polish)

  1. Algorytmy - przypomnienie (przykłady, złożoność czasowa, analiza).
  2. Abstrakcyjne struktury danych: stosy, kolejki, kolejki priorytetowe.
  3. Przeszukiwanie i sortowanie.
  4. Podstawy teorii grafów.
  5. Przeszukiwanie grafów. Algorytmy: BFS, DFS, problem spójności grafu, znajdowanie składowych spójnych grafu.
  6. Drzewa. Minimalne drzewa rozpinające w grafie. Algorytmy Kruskala i Prima.
  7. Najkrótsze ścieżki w grafach. Algorytmy Dijkstry i Bellmana-Forda. Algorytm Floyda-Warshalla.
  8. Sieci przepływowe. Algorytm Fulkersona-Floyda.
  9. Języki regularne i automaty skończone. Algorytmy związane z automatami i wyrażeniami regularnymi.
Bibliography: (in Polish)

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wprowadzenie do algorytmów, PWN, 2012.
Learning outcomes: (in Polish)

* Wiedza

Absolwent zna i rozumie:

- podstawy i ograniczenia technik obliczeniowych i programowania, wspomagających pracę matematyka (K_W08),

- cywilizacyjne znaczenie matematyki i jej zastosowań (K_W10),

- podstawowe zagadnienia prawne i etyczne związane z pracą zawodową matematyka (K_W11),

- podstawowe pojęcia z zakresu prawa autorskiego i ochrony wartości intelektualnej (K_W12).

* Umiejętności

Absolwent potrafi:

- rozpoznawać problemy, w tym zagadnienia praktyczne, które można rozwiązać algorytmicznie i dokonać specyfikacji takiego problemu (K_U27),

- posługiwać się różnymi konstrukcjami programistycznymi i strukturami danych, układać algorytmy i określać ich własności (K_U28),

- uruchomić i testować napisany samodzielnie program komputerowy w wybranym języku programowania (K_U29),

- dostrzegać ograniczenia własnej wiedzy i konieczność jej ciągłego uzupełniania i aktualizowania (K_U42).

* Kompetencje społeczne

Absolwent jest gotów do:

- przestrzegania zasad etyki i uczciwości intelektualnej i docenienia ich znaczenia w działaniach własnych i innych osób (K_K05).
Assessment methods and assessment criteria: (in Polish)

Egzamin pisemny i/lub egzamin ustny.

Classes in period "Summer semester 2024/25" (future)

Time span: 2025-02-17 - 2025-06-08
Selected timetable range:
Navigate to timetable
Type of class:
Classes, 30 hours more information
Lecture, 30 hours more information
Coordinators: Paweł Siedlecki
Group instructors: Paweł Siedlecki
Students list: (inaccessible to you)
Examination: Examination
Course descriptions are protected by copyright.
Copyright by University of Warsaw.
Krakowskie Przedmieście 26/28
00-927 Warszawa tel: +48 22 55 20 000 https://uw.edu.pl/ contact accessibility statement USOSweb 7.0.3.0 (2024-03-22)