Лекции
- циклы(for, while, вложенные) (#1)
- рекурсия (#2)
- динамические структуры данных (#3)
- память в Java (#4)
Видео по модулю
В данном топике собрана информация о "процедурной" части Java. Всего того, что:
1) не специфично исключительно для Java;
2) не связано с наследованием;
3) пригодится нам на дальнейших лекциях (коллекции, исключения);
4) пригодится вам на собеседованиях.
Этот модуль, в определенной степени, "навеян" классическим учебником по алгоритмам и структурам данных:
Никлаус Вирт. "Алгоритмы и структуры данных"
Глава 1. Основные понятия структур данных.
Глава 2. Сортировка.
Глава 3. Рекурсивные алгоритмы.
Глава 4. Данные с динамической структурой.
Глава 5. Преобразования ключей (расстановка).
Источники по синтаксису
while
- [Флэнаган. Справочник] - стр 68
- [Шилдт. Руководство] - стр 125-126
for
- [Флэнаган. Справочник] - стр 69-70,
- [Шилдт. Руководство] - стр 129-137
Массивы одномерные/многомерные
- [Шилдт. Руководство] - стр 88-95
- [Шилдт. Руководство] - стр 182-184
Строки (String)
- [Шилдт. Руководство] - стр 186-188
- [Флэнаган. Справочник] - стр 53.
Инкремент/декремент
- [Флэнаган. Справочник] - стр 54.
if
- [Шилдт. Руководство] - стр 117-120
do ... while
- [Флэнаган. Справочник] стр 69
- [Шилдт. Руководство] - стр 126-128
break, continue
- [Флэнаган. Справочник] стр 70-71
- [Шилдт. Руководство] - стр 138-143
switch
- [Шилдт. Руководство] - стр 120-124
Рекурсия
- ???
Источники по алгоритмам
Бинарный поиск
- ???
Сортировка "пузырьком"
- ???
Сортировка вставками
- ???
Сортировка выборкой
- ???
Сортировка слиянием
- ???
Быстрая сортировка
- ???
Timsort
- ???
Односвязный список
- ???
Двусвязный список
- ???
Бинарное дерево
- ???
История алгоритмов сортировок в стандартных библиотеках
- ???
История с бинарным поиском
- ???
Список вопросов и тем
1) Какие алгоритмы сортировки Вы знаете?
2) Расскажите про сортировку "пузырьком".
3) Расскажите про сортировку вставками.
4) Расскажите про сортировку слиянием.
5) Расскажите про быструю сортировку.
6) Расскажите про рекурсию.
7) Чем инфиксный инкремент отличается от постфиксного?
8) Что такое тернарная условная операция?
9) Что такое бинарный поиск?
10) Какие динамические структуры данных Вы знаете?
11) Расскажите про односвязный список
12) как устроены многомерный массивы в Java?
Словарь
Передача по ссылке, передача по значению, вызов метода, метод, функция, рекурсия, локальная переменная, глобальная переменная, примитивное значение, ссылка, указатель, объект, цикл, цикл с предусловием, цикл с пост условием, префиксный инкремент, постфиксный инкремент, сортировка "пузырьком", сортировка слиянием, сортировка вставкой, "быстрая сортировка", бинарный поиск, орбита преобразования, циклические ссылки, динамические структуры данных, односвязный список, двусвязный список, одномерный массив, многомерный массив, итерация по структуре данных, перебор всех элементов, тернарная условная операция
JDK
java.util.Arrays.binarySearch(int[] a, int key)
java.util.Arrays.binarySearch(T[] a, T key, Comparator<? super T> c)
java.util.Arrays.sort(int[] a)
java.util.Arrays.sort(T[] a, Comparator<? super T> c)
java.util.Collections.binarySearch(List<? extends Comparable<? super T>>
list, T key)
java.util.Collections.binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
java.util.Collections.sort(List<T> list)
java.util.Collections.sort(List<T> list, Comparator<? super T> c)
План
Лекция #1 (циклы)
Канонический цикл for, цикл for растущий/убывающий с не единичным шагом, вложенный for, пирамидальный for.
Безусловное всплытие (первого), всплытие большего, сортировка "пузырьком".
Сортировка вставками. Схожесть с "пузырьком". System.arraycopy(). Бинарный поиск. Лабораторная на оптимизацию сортировки вставками.
Лабораторная на сортировку выборками.
? Алгоритм бинарного поиска - итеративная/рекурсивная форма.
Доп-инфа:
while с постусловием, break, continue.
Тесты:
- вариации на тему цикла for: вверх/вниз, вариации шага
- вариации на тему цикла while: ?
Лабораторная:
Перемножение массивов, инвертирование строки, корректный merge.
Модификация пузырька - ?не всплытие, а утопление, ?двустороннии проходы, ввести флаг окончания, поиск позиции бинарным поиском, смещение через System.arraycopy().
Лекция #2 (рекурсия)
Рекурсия с трассировкой на входе: код, рисунок.
Рекурсия с трассировкой на выходе: код, рисунок.
Рекурсия с трассировкой на выходе: поясняющий код.
Рекурсия с ветвлением - Фибоначчи: код, рисунок.
Фибоначчи: альтернативная укороченная запись.
Алгоритм бинарного поиска - рекурсивная форма.
Сортировка слиянием.
Быстрая сортировка.
?Идея о дуальности сорт слиянием и быстрой.
Доп-код:
Фибоначчи с разворотом и трассировкой на выходе (+альтернативная запись).
Тесты:
- Рекурсия с трассировкой на входе/выходе
Лабораторная:
Сортировка пузырьком в рекурсивной форме.
Лекция #3 (динамические структуры данных)
Рекурсивное объявление типа данных, итеративный обход и распечатка, генерация списка, вставка в отсортированный список нового значения, понятие головы и хвоста списка, FIFO, FILO, stack, deque, queue. LinkedList как двусвязный список. Противопоставление по скорости ArrayList и LinkedList.
Тесты:
- генерация и проход списка
- вставка в список: в голову, в хвост, в середину
- удаление из списка: из головы, из хвоста, из середины
Лабораторная: ?
Расширение списка - бинарное дерево поиска.
Доп-инфа: ?
