Темы для подготовки

Обозначения:

* - понимать как работает, но глубоко не вдаваться (если речь про алгоритм, то не реализовывать)

** - достаточно знать, что такое существует и для чего

Структуры данных

Понимать как устроено. Знать, как выполняются простейшие операции (поиск, вставка, удаление и т.д.). Знать сложность этих операций

1. Массив (статический, динамический*)
2. Список (односвязный, двухсвязный*)
3. Стэк/Очередь
4. Деревья
    * Двоичное дерево. Двоичное дерево поиска
    * Сбалансированные деревья (красно-черное дерево, АВЛ-дерево)**
5. Хэш-таблица
    * Хэш-функция
    * Коллизия
    * Идеальное хэширование*
    * Методы разрешения коллизий: открытая адресация, метод цепочек*
6. Двоичная куча**

Алгоритмы

Понимать как работет. Знать сложность в лучшем, среднем, худшем случае, и затраты памяти. Написать работающую реализацию.

1. Бинарный поиск
2. Сортировки
    i. Квадратичные сортировки
        * выбором (selection sort)
        * пузырьковая (bubble sort)
    ii. Эффективные сортировки 
        * быстрая (quick sort)*
        * слиянием (merge sort)*
        * пирамидальная (heap sort)**
    iii. Сортировки, основанные не на сравнениях
        * подсчётом (counting sort)
        * поразрядная (radix sort)**
    iv. Внешняя сортировка (n-way merge sort)* (знать обязательно, но глубоко не копать!)

Python

1. Декоратор
2. Генератор
3. Модули
    i. Collections
        * defaultdict
        * Counter
        * namedtuple
    ii. Itertools
        * groupby
        * chain
        * izip_longest
    iii. Copy
        * функция copy
        * функция deepcopy
        _Почитать про разницу поверхностного и глубокого копирования_

PostgreSQL

1. Базовые операции:
    * SELECT, FROM, WHERE
    * DISTINCT
    * LIKE
    * UNION/INTERSECT
    * JOIN, LEFT JOIN, RIGHT JOIN
    * Аггрегация (MAX, MIN, SUM, COUNT,...)
    * GROUP BY
    * HAVING
    * Подзапросы и ANY/ALL
2. Как устроены индексы/какие виды бывают?
3. Порешать задачи с сайта http://sql-ex.ru (разбор некоторых задач [тут](http://www.sql-tutorial.ru/ru/book_computers_database.html))