Computer Science

​​Data Science | Machinelearning - самый большой русскоязычный канал с полезными материалами на такие темы как, Machine Learning, Data Science, Алгоритмы. Так же часто публикуются крутые 🔥 вакансии. Ссылка: @devsp А если вам нравится читать статьи на английском языке то вам на этот канал Добро пожаловать!

Сортировка пузырьком  Один из самых известных и простых алгоритмов сортировки. Его суть заключается в просматривании значений соседних элементов, если предыдущий элемент оказывается больше последующего, то меняем их местами.  Этот алгоритм почти не применяется на практике из-за низкой эффективности. Однако на нем основаны многие другие методы. Сложность по времени: Худшее время: O(n^2) Среднее время: O(n^2) Лучшее время: O(n) Затраты на память: O(1)

Все знают, что без элементарных знаний терминологии в айти делать нечего.  Самые опытные IT терминологи создали свой канал, где дают чёткие определения понятиям программирования.  Терминалоджи – самый простой и удобный способ выучить все IT термины и не только.  Подпишись: @it_terms

Суть кэширования процессора  Так как скорость работы процессора отличается от скорости работы оперативной памяти, то возникают простои и страдает производительность, чтобы этого избежать, появляется маленькая, но быстрая память под названием кэш. Суть кэширования заключается в сокращении задержек доступа, касающиеся взаимодействия с оперативной памятью.  Кэш память, которая меньше по объему оперативы примерно в 1000 раз, но по скорости работы сопоставима со скоростью работы процессора отлично вписалась в общую модель работы компьютера, ничего при этом не сломав. Вообще кэш по прежнему можно рассматривать, как обычную ОП, только в уменьшенном размере. И там, и там используется двоичная адресация, хранятся те же самые данные. И к той, и той памяти идет обращение, как на получение данных, так и на их запись. Логика в том, что если данные будут находится в кэше, а не в оперативе, то это и избавит нас от задержек.

Сетевая модель OSI The Open Systems Interconnection model - сетевая модель стека сетевых протоколов OSI/ISO. Посредством данной модели различные сетевые устройства могут взаимодействовать друг с другом. Модель определяет различные уровни взаимодействия систем. Выделяют 7 уровней взаимодействия:  1. Физический — работа со средой передачи, сигналами и двоичными данными  2. Канальный — физическая адресация  3. Сетевой — определение маршрута и логическая адресация  4. Транспортный — прямая связь между конечными пунктами и надёжность  5. Сеансовый — управление сеансом связи  6. Представления — представление и шифрование данных  7. Прикладной — доступ к сетевым службам

Домены Имена в DNS (Domain Name System) называются доменными именами или доменами. Они состоят из текстовых меток, разделенных точками. Метки могут использовать 26 букв от а до z, цифры от 0 до 9, а также дефис (­-). Например: home-3.coding.exemple — это домен с тремя метками.    Точки обозначают иерархические поддомены. Это домены, контролируемые более коротким родительским доменом: home-3.coding.exemple является поддоменом coding.exemple. Кроме того, coding.exemple является поддоменом однокомпонентного домена exemple. Домены нечувствительны к регистру: coding.exemple и CoDing.eXamplE идентичны.  Домены из одной метки, такие как com, net, а также exemple, называются доменами высшего уровня (Top Level Domains, TLDs). Благодаря своему устройству DNS наиболее эффективен при ограниченном количестве TLD. По этой причине создание новых TLD представляет сложность.

Рекурсия В программирование рекурсия — вызов функции самой себя. Это используется для реализации большого спектра самых разнообразных задач связанных с перебором (перебор чисел, букв, объектов, файлов и тд). Чтобы понять как работает рекурсия, желательно понимать как работает стек, так как реализация рекурсивных вызовов функций опирается на механизм стека вызовов — адрес возврата и локальные переменные функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за счёт этого работает корректно.  Оборотной стороной этого довольно простого по структуре механизма является то, что на каждый рекурсивный вызов требуется некоторое количество оперативной памяти компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнения стека вызовов.

Динамическая структура данных — Односвязный список  Односвязный список - это динамическая структура данных, состоящая из узлов. Каждый узел будет иметь некоторое значение и указатель на следующий узел. При использовании связного списка элементы размещаются где угодно в памяти. И так как в каждом элементе хранится адрес следующего элемента списка, то набор произвольных адресов памяти объединяется в цепочку. Связные списки очень хорошо справляется со вставкой. Чтобы добавить новый элемент в список, просто разместите его по любому адресу и сохраните этот адрес в предыдущем элементе. Со связными списками ничего в памяти перемещать не нужно. Время выполнения основных операций: Чтение - O(n) Вставка - O(1) Удаление - O(1)

Виды адресаций В оперативной памяти каждый набор ячеек (байт) имеет свой адрес, по которому процессор может к нему обращаться. Из-за того, что каждый байт имеет свой отдельный адрес, такой вид адресации называется — байтовый. Но существуют компьютеры, у которых размер одной ячейки памяти равняется машинному слову — это максимальное кол-во бит, которыми может оперировать процессор за раз. То есть в 32-х разрядных процессорах размер регистров и размер машинного слова будет равен 32 бита, а в 64-х — 64 бита и тд (такие компьютеры предназначены для научных целей). Из-за того, что процессор обращается не к байту, а к слову, то такая адресация называется словесной адресацией.

Алгоритмы сортировок Алгоритмы сортировок это самая частая тема, которую спрашивают на собеседованиях. Сейчас мы рассмотрим, какие есть и их сложность по времени. Подробно как они работают, рассмотрим в будущих постах.  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)

Структура данных — массив Массив - это структура однотипных данных, расположенная в памяти одним неразрывным блоком. Каждая переменная в массиве является самостоятельной единицей и называется элементом. Каждый элемент имеет свою позицию — свой индекс. Нумерация индексов начинается с 0, а не с 1. Иногда, начинающих программистов это вводит в ступор, но тем не менее выбор нулевой начальной позиции упрощает написание кода по работе с массивами, поэтому разработчики остановились на этом варианте. Работая с массивом вы заранее знаете адрес каждого элемента, поэтому они прекрасно подходят для чтения в произвольных позициях, так как обращение к любому элементу происходит мгновенно. Время выполнения основных операций: Чтение - O(1) Вставка - O(n) Удаление - O(n)

Из чего состоит оперативная память (ОП) Вся оперативная память делится на СТЕК (STACK) и КУЧУ (HEAP). Стек - это отведенная область памяти, где хранятся временные данные. Благодаря ему становится возможно вызывать подпрограммы, они же функции. За стеком располагается весь остальной код, который есть в ОП По другому его называют аппаратным стеком, потому что помимо него, стек еще является структурой данных Куча - это область памяти, где находятся все работающие на данный момент программы (включая ОС). Все данные в куче располагаются линейно в строну увеличения адресов. В стеке же все наоборот, он растет в сторону уменьшения адресов. Это необходимо, для того чтобы стек не затирал данные, которые идут за ним, в случае своего переполнения.

Оперативная память. Бит и байт Представляет собой огромный набор ячеек. Одна ячейка может хранить в себе один бит. Бит - минимальная единица хранения информации, которая может быть выражена 0 или 1 (что является абстракцией над наличием или отсутствием тока) Ячейки (биты) объединяются в группы по 8 штук и получаются байты. Дело в том, что процессор может обращаться только к какому-то определенному байту в памяти (байт - минимальная ячейка адресации) В каждой группе ячеек, самый правый бит называется младшим битом, а самый левый — страшим. Какая такая группа имеет свой адрес, по которому процессор может к ней обращаться.

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

Алгоритм, который каждый программист должен знать! Бинарный поиск - это алгоритм поиска элемента в отсортированном массиве, который возвращает индекс этого элемента в данном массиве. Представьте, у вас есть массив, где находится миллион чисел, и вы хотите найти какое-то конкретное и извлечь его индекс. Используя линейный поиск, вы бы начали сначала и на каждой итерации последовательно сравнивали бы искомое значение со значениями в массиве. И если вы например ищете число 3, то вам крупно повезло и вам понадобится всего 3 итерации, но в худшем случае, когда вы ищите число миллион, вам придется перебирать весь массив, следовательно это миллион итераций (очень много). Но если использовать бинарный поиск, то все становится проще. Нам нужно поделить массив пополам и сравнить искомое значение с серединным, если оно меньше, то мы отбрасываем вторую половину массива и ищем уже только в первой. И так далее, пока не найдем искомое значение. При бинарном поиске каждый раз исключается половина чисел. Сложность бинарного поиска: логарифмическая

Машина Тьюринга (МТ) и какое отношение она имеет к программированию МТ — это модель для формализации понятия алгоритма. МТ состоит из бесконечной ленты, разделенной на ячейки и управляющего устройства. Это устройство может перемещаться влево и вправо, читать и писать различные символы определенного алфавита с конечным числом символов. Оно работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной МТ. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния МТ могут быть помечены как терминальные, и переход в любое из них означает конец работы, то есть, остановку алгоритма. В общем, МТ - способ определить некоторый класс алгоритмов: ⁃ некоторые задачи можно решить конечным автоматом; ⁃ для некоторых потребуется конечный автомат со стековой памятью; ⁃ для других достаточно МТ

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

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