Zakres materiału z informatyki

1. Znajomość podstaw języka C i/lub C++:

1.1. Podstawy składni języka:
stałe, zmienne, operatory wbudowane, podstawowe typy danych.

1.2. Instrukcje strukturalne:
instrukcja warunkowa (if),
instrukcja rozgałęzienia (switch),
pętle (while, do while, for);

1.3. Funkcje:
definicja i deklaracja funkcji,
mechanizm przekazywania parametrów,
rekurencja;

1.4. Pojęcie wskaźnika, operacje na wskaźnikach.

1.5. Tablice jedno i wielowymiarowe statyczne i alokowane dynamicznie,
operatory new, delete lub funkcje calloc, malloc, free;

1.6. Struktury i unie:
definicja struktury / unii,
dostęp do składowych (operatory . i ->);

1.7. Strumienie znakowe i binarne, formatowanie wejścia i wyjścia, obsługa plików.

2. Podstawowe algorytmy i struktury danych:

2.1. Znajomość podstawowych struktur danych: stos, kolejka.

2.2. Algorytmy wyszukiwania i sortowania, np. jednoczesne znajdowanie największego i najmniejszego elementu w zbiorze, algorytmy sortowania.

2.3. Algorytmy na liczbach całkowitych, np. reprezentacja liczb w dowolnym systemie pozycyjnym, znajdowanie liczb pierwszych, algorytm Euklidesa, rozkład liczby na czynniki pierwsze, obliczanie wartości liczb Fibonacciego.

2.4. Operacje na tekstach, np. sprawdzanie, czy dany ciąg znaków tworzy palindrom, anagram, porządkowanie alfabetyczne, wyszukiwanie wzorca w tekście.

2.5. Algorytmy numeryczne, np. obliczanie wartości pierwiastka kwadratowego, znajdowanie miejsca zerowego funkcji, obliczanie wartości wielomianu za pomocą schematu Hornera.

2.6. Algorytmy kompresji i szyfrowania, np. kody znaków o zmiennej długości (np. alfabet Morse'a), szyfr Cezara, szyfr przestawieniowy, szyfr z kluczem jawnym (RSA).

2.7. Algorytmy badające własności geometryczne, np. sprawdzanie warunku trójkąta, badanie położenia punktów względem prostej, badanie przynależności punktu do odcinka, przecinanie się odcinków, przynależność punktu do obszaru.

3. Znajomość matematyki – zakres.

 

Polecana literatura

1. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT, Warszawa 1996.
2. J. Bentley, Perełki oprogramowania, WNT, Warszawa 1992.
3. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, WNT, Warszawa 2004.
4. B. Eckel, Thinking in C++. Gliwice: Helion, cop. 2004, ISBN 83-7361-409-5
5. B. Eckel, Thinking in C++, www.mindview.net/Books/TICPP/ThinkingInCPP2e.html (PDF)
6. M. Erwig, Dawno temu był sobie algorytm, Wydawnictwo Naukowe PWN, Warszawa 2018.
7. J. Grębosz, Opus magnum C++11, Helion, 2018, ISBN 978-83-283-3883-8
8. J. Grębosz, Symfonia C++ Standard, Edition 2000 przy współpracy Oficyny Kallimach, 2010
9. J. Grębosz, Pasja C++, Edition 2000 przy współpracy Oficyny Kallimach, 2016
10. B.W. Kernighan, D.M. Ritchie: Język ANSI C, WNT, 1998, ISBN 83-204-2330-9
11. D. E. Knuth, Sztuka programowania, t. 1-3, WNT, Warszawa 2003.
12. D. E. Knuth, Sztuka programowania, t. 4 zeszyt 2, Generowanie wszystkich krotek i permutacji, WNT, Warszawa 2007.
13. K. Loudon, Algorytmy w C, Gliwice: Helion, 2003, ISBN 83-7197-912-6
14. S. Prata, Język C. Szkoła programowania, Gliwice: Wydawnictwo Helion, cop. 2016, ISBN 978-83-283-1470-2
15. H. Schildt, Programowanie C, Warszawa: Wydaw. RM, 2002, ISBN 83-7243-258-9
16. S. S. Skiena, M. A. Revilla, Wyzwania programistyczne, WSiP, Warszawa 2004.
17. P. Stańczyk, Algorytmika praktyczna. Nie tylko dla mistrzów. PWN, Warszawa 2009
18. N. Wirth, Algorytmy + struktury danych = programy, WNT, Warszawa 2004.
19. W poszukiwaniu wyzwań. Wybór zadań z konkursów programistycznych Uniwersytetu Warszawskiego, PWN, Warszawa 2018.
20. W poszukiwaniu wyzwań 2. Zadania z Akademickich Mistrzostw Polski w Programowaniu Zespołowym 2011-2014, Warszawa 2015.
21. Dokumentacja języka C++ na stronie http://www.cplusplus.com/