Нужны ли программисту алгоритмы?

Прежде всего поймем, что такое алгоритм. Неформально Кармен определяет алгоритм как строго определённую процедуру, которая принимает одно или несколько значений как ввод, и возвращает одно или несколько значений как результат. Таким образом, фактически любой код, который что-то делает, является алгоритмом. Получается, что вопрос «нужны ли программисту алгоритмы» можно перевести как «нужно ли программисту уметь писать код». А точнее «нужно ли программисту в отрасли Х знать N-ые алгоритмы».

Но есть три характеристики алгоритмов, которые каждый программист должен понимать:
1. Определенность - описывает, что каждый шаг точно определен.
2. Эффективная вычислимость - описывает, что каждый шаг может быть выполнен компьютером.
3. Конечность - описывает, что процедура завершается.

Для решения задачи обычно существует множество различных алгоритмов. Один алгоритм может потребовать наименьшего количества шагов. Другой алгоритм может допускать одновременное выполнение некоторых шагов. Компьютер, который позволяет выполнять несколько действий одновременно, часто может решить проблему за меньшее время, даже если общее количество выполняемых шагов увеличилось.

Статическая и динамическая типизации

Отличие статической типизации от динамической — это то, что все проверки типов выполняются на этапе компиляции, а не на этапе выполнения.

Обсуждая эту тему, люди обычно делятся на две группы: одни, кто считает, что статическая типизация слишком ограничена, другие, что динамически типизированные языки — это игра с огнем. Но так ли это?

Рассмотрим преимущества этих двух типизаций
Статическая (C, Java, C#):
⁃ Проверки типов происходят только один раз — на этапе компиляции.
⁃ Скорость выполнения.
⁃ При некоторых дополнительных условиях, позволяет обнаруживать потенциальные ошибки уже на этапе компиляции.
⁃ Ускорение разработки при поддержке IDE

Динамическая (Python, JavaScript, Ruby):
⁃ Простота создания универсальных коллекций
⁃ Удобство описания обобщенных алгоритмов.
⁃ Языки с динамической типизацией обычно очень хороши для того, чтобы начать программировать

Машина Тьюринга (МТ) и какое отношение она имеет к программированию

МТ — это модель для формализации понятия алгоритма.

МТ состоит из бесконечной ленты, разделенной на ячейки и управляющего устройства.
Это устройство может перемещаться влево и вправо, читать и писать различные символы определенного алфавита с конечным числом символов.

Оно работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной МТ. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния МТ могут быть помечены как терминальные, и переход в любое из них означает конец работы, то есть, остановку алгоритма.

В общем, МТ - способ определить некоторый класс алгоритмов:
⁃ некоторые задачи можно решить конечным автоматом;
⁃ для некоторых потребуется конечный автомат со стековой памятью;
⁃ для других достаточно МТ

Алгоритм, который каждый программист должен знать!

Бинарный поиск - это алгоритм поиска элемента в отсортированном массиве, который возвращает индекс этого элемента в данном массиве.

Представьте, у вас есть массив, где находится миллион чисел, и вы хотите найти какое-то конкретное и извлечь его индекс.

Используя линейный поиск, вы бы начали сначала и на каждой итерации последовательно сравнивали бы искомое значение со значениями в массиве. И если вы например ищете число 3, то вам крупно повезло и вам понадобится всего 3 итерации, но в худшем случае, когда вы ищите число миллион, вам придется перебирать весь массив, следовательно это миллион итераций (очень много).

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

Сложность бинарного поиска: логарифмическая

Память компьютера

Память - компонент компьютера, способный хранить в себе различную информацию (под информации можно понимать буквально все: программы, картинки, текст и тд), которая представляется в двоичном виде.

Иерархия памяти (от самой маленькой, но быстрой до самой большой, но медленной)
1. регистры - ячейки памяти, которые находятся на самом процессоре
2. кэш-память - хранилище для часто используемых процессором данных
3. оперативная память - именно та память, в которой находятся программы, выполняющиеся данный момент времени.
4. внешняя память - флешки, жесткие диски и тд.

Оперативная память. Бит и байт

Представляет собой огромный набор ячеек.

Одна ячейка может хранить в себе один бит. Бит - минимальная единица хранения информации, которая может быть выражена 0 или 1 (что является абстракцией над наличием или отсутствием тока)

Ячейки (биты) объединяются в группы по 8 штук и получаются байты. Дело в том, что процессор может обращаться только к какому-то определенному байту в памяти (байт - минимальная ячейка адресации)

В каждой группе ячеек, самый правый бит называется младшим битом, а самый левый — страшим.

Какая такая группа имеет свой адрес, по которому процессор может к ней обращаться.

Структура данных — массив

Массив - это структура однотипных данных, расположенная в памяти одним неразрывным блоком.

Каждая переменная в массиве является самостоятельной единицей и называется элементом. Каждый элемент имеет свою позицию — свой индекс.

Нумерация индексов начинается с 0, а не с 1. Иногда, начинающих программистов это вводит в ступор, но тем не менее выбор нулевой начальной позиции упрощает написание кода по работе с массивами, поэтому разработчики остановились на этом варианте.

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

Время выполнения основных операций:
Чтение - O(1)
Вставка - O(n)
Удаление - O(n)

Алгоритмы сортировок

Алгоритмы сортировок это самая частая тема, которую спрашивают на собеседованиях. Сейчас мы рассмотрим, какие есть и их сложность по времени. Подробно как они работают, рассмотрим в будущих постах.

 1. Сортировка пузырьком 
Худшее время - O(n^2) | Лучшее время - O(n)

 2. Сортировка перемешиванием 
Худшее время - O(n^2) | Лучшее время - O(n)

 3. Сортировка расческой 
Худшее время - O(n^2) | Лучшее время - O(n log n)

 4. Сортировка вставками 
Худшее время - O(n^2) | Лучшее время - O(n) или O(1)

 5. Сортировка выбором 
Худшее время - O(n^2) | Лучшее время - O(n^2)

 6. Быстрая сортировка 
Худшее время - O(n^2) | Лучшее время - O(n) 

 7. Сортировка слиянием 
Худшее время - O(n log n) | Лучшее время - O(n log n) 

 8. Пирамидальная сортировка 
Худшее время - O(n log n) | Лучшее время - O(n log n) или O(n)

Динамическая структура данных — Односвязный список 

Односвязный список - это динамическая структура данных, состоящая из узлов. Каждый узел будет иметь некоторое значение и указатель на следующий узел.

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

Связные списки очень хорошо справляется со вставкой. Чтобы добавить новый элемент в список, просто разместите его по любому адресу и сохраните этот адрес в предыдущем элементе. Со связными списками ничего в памяти перемещать не нужно.

Время выполнения основных операций:
Чтение - O(n)
Вставка - O(1)
Удаление - O(1)

Сетевая модель OSI

The Open Systems Interconnection model - сетевая модель стека сетевых протоколов OSI/ISO. Посредством данной модели различные сетевые устройства могут взаимодействовать друг с другом. Модель определяет различные уровни взаимодействия систем.

Выделяют 7 уровней взаимодействия:

 1. Физический — работа со средой передачи, сигналами и двоичными данными

 2. Канальный — физическая адресация

 3. Сетевой — определение маршрута и логическая адресация

 4. Транспортный — прямая связь между конечными пунктами и надёжность

 5. Сеансовый — управление сеансом связи

 6. Представления — представление и шифрование данных

 7. Прикладной — доступ к сетевым службам

Сортировка пузырьком 

Один из самых известных и простых алгоритмов сортировки. Его суть заключается в просматривании значений соседних элементов, если предыдущий элемент оказывается больше последующего, то меняем их местами. 

Этот алгоритм почти не применяется на практике из-за низкой эффективности. Однако на нем основаны многие другие методы.

Сложность по времени:
Худшее время: O(n^2)
Среднее время: O(n^2)
Лучшее время: O(n)

Затраты на память: O(1)

Быстрая сортировка

Ей уже 60 лет, но она до сих пор работает быстро.

За основу, была взята классическая сортировка пузырьком и преобразована таким образом:

 1. на очередном шаге выбирается опорный элемент — им может быть любой элемент массива
 2. Все остальные элементы массива сравниваются с опорным и те, которые меньше него, уставляться слева от него, а которые больше или равны — справа
 3. Далее для двух получившихся блоков массива выполняется пункт 1 и 2.

Особенность алгоритма в том, что так как в пункте 3 мы разбиваем массив на два и для каждой части делаем то же самое, и так снова и снова, то это значит, что в нём используется рекурсия.

Сложность по времени:
Худшее время: O(n^2)
Среднее время: O(n log n)
Лучшее время: O(n)

Затраты на память: O(n)

Криптография

В прошлом сохранение информации в тайне в значительной степени опиралось на принцип «безопасность через неясность», предполагающий сокрытие сообщения или отсутствие у противника ключей для его расшифровки.

В основе современной криптографии лежит математика. Мы предпочитаем использовать криптосистему, спроектированную таким образом, что, даже имея копию зашифрованного текста и зная, как именно он был зашифрован, злоумышленник все равно не сможет прочитать сообщение, не зная общего секретного ключа. Наличие этого ключа позволяет расшифровать сообщение и восстановить исходный текст

Физический уровень модели OSI

Всего в модели сетевого взаимодействия выделяют 7 уровней, рассмотрим первый из них.

Физический уровень — нижний уровень модели OSI.
Описывает способы передачи бит (не пакетов данных) через физические среды линий связи (кабели), соединяющие сетевые устройства.
Битовый поток может быть сгруппирован в кодовые слова или символы и преобразован в физический сигнал.

Один из основных стандартов среди технологий физического уровня – Ethernet.

Сортировка расческой

Сортировка расческой — улучшенная версия сортировки пузырьком. 

Проблема пузырьковой сортировки в том, что если в массиве в начале будет много больших элементов, то в ходе алгоритма будет очень много перестановок, которые тормозят скорость работы алгоритма.

Чтобы уменьшить их кол-во, можно перекидывать элементы не на соседнее место, а подальше. Но отправлять каждый большой элемент в конец массива очень самонадеянно, т.к. мы не знаем на сколько он большой по сравнению с другими, поэтому в сортировке расческой сравниваются элементы, которые находятся на каком-то расстоянии друг от друга.

Опытным путём программисты установили оптимальное расстояние между элементами — это длина массива, поделённая на 1,247

Сложность по времени:
Худшее время: O(n^2)
Среднее время: O(n^2 / 2^p), где p - кол-во инкрементов
Лучшее время: O(n log n)

Затраты на память: O(1)

Канальный уровень модели OSI (2)

Data link layer предназначен для обмена данными между узлами, находящимися в том же сегменте локальной сети, путем передачи специальных блоков данных, которые называются кадрами (frame).

В процессе формирования кадров данные снабжаются служебной информацией (заголовком), необходимой для корректной доставки получателю, и, в соответствии с правилами доступа к среде передачи, отправляются на физический уровень.

На уровне условно выделяют следующие подуровни управления:
⁃ уровень управления логическим каналом (logical link control, LLC)
⁃ уровень доступа к среде (media access layer, MAC)

Устройствами второго уровня считаются мосты и коммутаторы.

Сортировка выбором

Идея сортировок выбором в том, что в неотсортированном подмассиве ищется локальный максимум(минимум), потом найденный максимум (минимум) меняется местами с последним (первым) элементом в подмассиве, и если в массиве остались неотсортированные подмассивы, то процедура повторяется.

Сортировка простым выбором представляет из себя грубый двойной перебор. 

Сложность по времени:
Худшее время: O(n^2)
Среднее время: O(n^2)
Лучшее время: O(n^2)

Затраты на память: O(1) вспомогательной, O(n) основной

Можно провести несколько модификаций и получим двухстороннюю сортировку выбором. 

Похожая идея используется в сортировке перемешиванием. Проходя по неотсортированной части массива, мы кроме максимума также находим и минимум. Минимум ставим на первое место, максимум на последнее. 

Может показаться, что это ускоряет алгоритм в 2 раза, но это не так, т.к. в этом случае кол-во сравнений увеличилось в два раза. Двойной выбор лишь незначительно увеличивает скорость алгоритма