Алгоритмы

Содержание

Введение в анализ алгоритмов


Это второе, полностью обновленное и переработанное издание книги.

«Введение в анализ алгоритмов» будет отличным учебным руководством и справочником как студентов, так и для разработчиков, ориентированных на создание надежного кода. Материал в книге изложен достаточно сжато, но, тем не менее, он охватывает все необходимые основы.

В книге рассмотрены традиционные для информатики алгоритмы, такие как жадный алгоритм, динамическое программирование, «разделяй и властвуй». Но кроме того автор рассматривает два класса алгоритмов, которые часто выпадают из поля зрения, — рандомизированные и онлайн-алгоритмы (с упором на сами алгоритмы). И это очень кстати, ведь первые повсеместно применяются в криптографии, а вторые необходимы в очень многих областях, от создания ОС до прогнозирования фондового рынка.

Остались вопросы?

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

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

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

  • Под каждым уроком и заданием есть мини-форум, где ученики могут общаться с преподавателем и друг с другом. Если у вас возникли вопросы, то смело задавайте их через форум и вам обязательно помогут.

  • 5. Сколько стоит обучение?

    Наши курсы стоят от 700 до 4900 рублей в зависимости от объема и сложности. Все цены, включая пакетные предложения и скидки, доступны после регистрации.

Задача

Сформулируем основную задачу, которую хочется решить. Для этого сначала запишем операции над алгоритмами, которые программист выполняет в ходе написания своего проекта:

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

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

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

Сразу возникает масса вопросов к этому определению:

  • Что такое правило?
  • Как, кому и для кого это правило можно задать?
  • Что есть объединение совокупностью?
  • Каким образом правила соотносятся с задачей?
  • Что формирует класс задачи?
  • Определяется ли способ формирования совокупности правилами и задачами?

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

  • Какова структура набора?
  • Какие есть варианты действий и исполнителей?
  • Существуют ли минимально возможное действие, минимальный набор необходимых действий?
  • Каким образом действия встроены в исполнителя?
  • Какие есть способы создания копии исполнителя (например, если исполнитель — человек)?
  • Как действия зависят друг от друга в упорядоченном выполнении?
  • Что есть задача кроме того, что она выполняется последовательностью действий?
  • Как задача соотносится с исполнителем и с действиями?
  • Возможно ли использовать решение задачи в качестве действия?
  • Какие возможны варианты указания порядка действий?
  • Если воспроизведение патефоном записи звуков леса является алгоритмом, то какова структура этой задачи?
  • Если репликация ДНК является алгоритмом, то каков её исполнитель?
  • Если исполнителем является Машина Тьюринга, то как с её использованием решить механическую задачу, например, воспроизведение звука?

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

Хочешь сделать хорошо — сделай это сам

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

Задача 1

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

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

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

Дерево отрезков дает возможность обновлять данные за O(logN), получать показатели для последовательной группы людей тоже за О(logN). Да, нагрузка на память увеличилась за счет того, что нужно хранить два таких дерева (для максимума и для суммы), и они занимают в 4 раза больше места, чем массив с данными. Но в моем случае это было не критично.

Почему не использовать готовую реализацию?

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

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

Результат

Как я знаю от бывших коллег, это работает и модифицируется до сегодняшнего дня. Хотя было написано меньше чем за день (вместе с тестами). Если бы в команде никто не слышал о таком алгоритме, то на его поиски и реализацию ушли бы недели.

Задача 2


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

Решение

При решении схожей задачи у меня не было представления о линейной алгебре и транспортной задаче. Но я слышал об алгоритме Min Cost Max Flow.

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

С изменениями, но для решения этого применялся алгоритм поиска минимальной стоимости максимального потока.

Сомневаюсь, что данный алгоритм пригодится мне еще хоть один раз. Но он также интересен тем, что в базовом варианте объединяет три других: BFS, Форда-Фалкерсона и Белмана-Форда.

Результат

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

Задача 3. Разбор логов сервера

Дано: Файл логов 100 МБ+. Нужно наладить быстрый поиск по этому файлу. Слова и фразы поиска — это коды, тексты ошибок и ID пользователей (короткие строки).

Стандартные средства уже не удовлетворяли запросы проекта и нужно было придумать более быстрый способ. И снова помог алгоритм, который я видел до этого — Ахо-Корасик. Про результаты лучше всего расскажет график:

Результат

Это было не так давно, но есть подозрение, что эта реализация прослужит еще пару лет. Если инфраструктуру и процессы не изменят раньше.

Отношения. Часть I

Формальная теория моделирования использует алгебраические отношения, включая их в сигнатуры моделей алгебраических структур, которыми описывает реальные физические, технические и информационные объекты, процессы их функционирования. К числу последних я отношу, например, базы данных (реляционные базы данных (РеБД))

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

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

Алгоритмы: разработка и применение

Авторы: Джон Клейнберг, Эва Тардос. Год издания: 2016.

Авторы этой книги — профессора теории вычислительных систем в Корнелльском университете. Клейнберг специализируется на алгоритмах, связанных со структурой сетей и информации. Его работы лежат в основе поисковых систем интернета. Тардос специализируется на графах и сетевых задачах.

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

В книге рассматриваются (среди прочих) такие темы как основы анализа алгоритмов, графы, жадные алгоритмы, алгоритмы «разделяй и властвуй», динамическое программирование, NP-полнота, аппроксимирующие и рандомизированные алгоритмы.

Связный список

  • Односвязный список (однонаправленный)
  • Двусвязный список (двунаправленный)

Простейшие операции со связными списками:

  • InsertAtEnd — Вставляет заданный элемент в конце связного списка
  • InsertAtHead — Вставляет заданный элемент в начале (с головы) связного списка
  • Delete — Удаляет заданный элемент из связного списка
  • DeleteAtHead — Удаляет первый элемент в связном списке
  • Search — Возвращает заданный элемент из связного списка
  • isEmpty — Возвращает true, если связный список пуст

Вопросы о связных списках, часто задаваемые на собеседованиях:

  • Обратите связный список
  • Найдите петлю в связном списке
  • Возвратите N-ный узел с начала связного списка
  • Удалите из связного списка дублирующиеся значения

О курсе

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

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

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

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

Требования


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

Для прохождения курса требуется любой общедоступный компилятор одного из следующих языков программирования:

  • Java: версия 8 (ссылка для скачивания на сайте Oracle)
  • C, C++: MinGW версии 5.1 (для Windows, для Linux можно использовать GCC аналогичной версии), а также Microsoft Visual Studio C++ 2013 (скачать Visual Studio Express можно здесь).
  • C#: Microsoft Visual Studio C# 2013 (скачать Visual Studio Express можно здесь).
  • Python: версия 3.5 (ссылка для скачивания на сайте python.org)
  • Scala: версия 2.11 (ссылка для скачивания на сайте scala-lang.org)
  • Kotlin: версия 1.0 (ссылки на инструкции по установке компилятора, плагинов в IntelliJ IDEA и в Eclipse).

Серьезный курсдля будущих профессионалов

Алгоритмы — основа любой программы, а умение писать алгоритмы — ключевой навык современного разработчика.

Мы подготвили продуманные HD-уроки с большим количеством практики, чтобы вы не только понимали как работают алгоритмы и устроены структуры данных, но и могли самостоятельно их проектировать, анализировать и оптимизировать.

2000слайдов и схем

Каждый урок содержит подробную схему и описание работы алгоритма.

100анимаций

В особо сложных и важных местахмы добавлии анимацию.

200исходников

Крем схем и графиков,все алгоритмы содержат хорошо документированные исходникина языке Python.

Совершенный алгоритм. Основы

Тим Рафгарден — профессор информатики, член института Data Science при Колумбийском университете. Серия книг «Совершенный алгоритм» (англ. Algorithms Illuminated) написана им на основе онлайн-курсов, которые он ведет на платформах Coursera и edX.

Первая часть серии представляет собой доступное введение в основы алгоритмов. Объяснение не привязано к каком-либо языку программирования. В этой книге автор рассматривает асимптотический анализ алгоритмов и нотацию О-большое (а также Омега-большое и Тета-большое), парадигму «разделяй и властвуй», рандомизированные алгоритмы и, конечно, несколько самых известных алгоритмов сортировки.

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

Стеки

Придумал Алан Тюринг.

Основные операции

  • Push-вставляет элемент сверху
  • Pop-возвращает верхний элемент после удаления из стека
  • isEmpty-возвращает true, если стек пуст
  • Top-возвращает верхний элемент без удаления из стека

Вопросы

  • Реализовать очередь с помощью стека
  • Сортировка значений в стеке
  • Реализация двух стеков в массиве
  • Реверс строки с помощью стека

Очереди

Основные операции

  • Enqueue—) — вставляет элемент в конец очереди
  • Dequeue () — удаляет элемент из начала очереди
  • isEmpty () — возвращает значение true, если очередь пуста
  • Top () — возвращает первый элемент очереди

Вопросы

  • Реализовать cтек с помощью очереди
  • Реверс первых N элементов очереди
  • Генерация двоичных чисел от 1 до N с помощью очереди

Связанный список

ОднонаправленныйДвунаправленныйКруговой

Основные операции

  • InsertAtEnd — Вставка заданного элемента в конец списка
  • InsertAtHead — Вставка элемента в начало списка
  • Delete — удаляет заданный элемент из списка
  • DeleteAtHead — удаляет первый элемент списка
  • Search — возвращает заданный элемент из списка
  • isEmpty — возвращает True, если связанный список пуст

Вопросы

  • Реверс связанного списка
  • Определение цикла в связанном списке
  • Возврат N элемента из конца в связанном списке
  • Удаление дубликатов из связанного списка

Графы

Вопросы

  • Реализовать поиск по ширине и глубине
  • Проверить является ли граф деревом или нет
  • Посчитать количество ребер в графе
  • Найти кратчайший путь между двумя вершинами

Деревья

  • N дерево
  • Сбалансированное дерево
  • Бинарное дерево
  • Дерево Бинарного Поиска
  • AVL дерево
  • 2-3-4 деревья

«Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. » — Procs

Три способа обхода дерева

  • В прямом порядке (сверху вниз) — префиксная форма.
  • В симметричном порядке (слева направо) — инфиксная форма.
  • В обратном порядке (снизу вверх) — постфиксная форма.

Вопросы

  • Найти высоту бинарного дерева
  • Найти N наименьший элемент в двоичном дереве поиска
  • Найти узлы на расстоянии N от корня
  • Найти предков N узла в двоичном дереве

Trie ( префиксное деревое )

Вопросы

  • Подсчитать общее количество слов
  • Вывести все слова
  • Сортировка элементов массива с префиксного дерева
  • Создание словаря T9
  • Функции хеширования
  • Размера хэш-таблицы
  • Метода борьбы с коллизиями

Вопросы

  • Найти симметричные пары в массиве
  • Найти, если массив является подмножеством другого массива
  • Описать открытое хеширование

Проблема

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

В результате программированию учишься по наитию. Лишь немного в этом труде помогают сборники алгоритмов, прикладных техник и шаблонов проектирования. Общая совокупность предлагаемых ими рецептов выстраивается длинным списком, и его длина грозит каждому из прочитанных приемов быть позабытым (как была забыта 53-яя личная группа в «телеге» до введения разбиения по каталогам). Но даже тот прием, который остался в памяти, чаще всего просто является описанием прикладной задачи, в которой было успешно его использование.

Почему конкретный прием был успешен в задаче-образце? Будет ли он успешен в твоём проекте? Какие признаки проекта дают понять, что использование приёма уместно?

В личном опыте существования в профессии не раз отмечено, что каждый Junior борется с одинаковыми ветряными мельницами и постигает методы создания программ основываясь только на своих ошибках. Но ведь такие ошибки совершили уже очень многие. Почему до сих пор не создана система правил программирования, которая поможет обойти новоиспеченному кораблю-программисту подводные прибрежные камни? Ну, например, объяснение вреда использования метода «Copy-Paste» для развития кода. Если такие правила получится объяснить малым набором причин, их сформировавшим, то это объяснение обеспечит их запоминание и последующее использование в практике, тем самым поможет уклониться от бесчисленных грабель, разложенных тут и там.

Для компактного и полезного набора объяснений нужно:

  • систематизировать методы работы с кодом;
  • разобрать по группам приёмы работы с алгоритмами, которые являются главной целью написания любого кода;
  • выделить простые признаки применения шаблонов проектирования;
  • разработать универсальные правила и наборы эффективных способов построения сложных алгоритмов.

Если обобщить, то нужны алгоритмы для написания и развития алгоритмов.

Задуманная серия статей не претендует на полное решение указанной проблемы. Предпринимается небесспорная попытка сделать первый шаг на пути к этому решению. Этот шаг состоит в выделении структуры и свойств главного кирпичика программиста — Алгоритма.

1 Практика для начинающих

«Метро» — задача на логику, с нее хорошо начать свой путь в спортивном программировании. Для решения задачи вам нужно освоить тему «Ветвеление«, и уметь работать с файлами (хотя бы «по образцу»). «Сжимающий оператор» — простейшая задача на геометрию, а также прекрасный пример для иллюстрации проблемы потери точности при работе с дробными числами. «Загадка» — хорошая задача для первой практики в анализе сложности алгоритмов — приводятся три варианта решения с оценками сложности O(n*n), O(n) и O(1). Разбирая задачу — подумайте о том, какие максимальные значения можно подать на вход первого решения, второго и третьего. «Кругляши» — демонстрация улучшения кода за счет применения стандартных алгоритмов STL. Мы пишем меньше кода, а значит — допустим меньше ошибок

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

Проблема выбора между чистотой кода и эффективностью постоянно возникает при программировании, ее описывали Маерс и Саттер — чаще всего стоит выбирать наиболее простое решение, обратное часто называется «Преждевременной оптимизацией«. «Нули» — в этой задаче вы можете применить алгоритмы STL, однако решение от этого, скорее всего, станет более запутанным — это хороший пример неудачного рефакторинга. Для закрепления навыков работы с STL можно порешать ряд других несложных задач: «Домашнее задание» — . «Линии Жизни» идиома Erase-remove, алгоритмы и . «Азартный Шрэк«- . «Автобусная экскурсия» — алгоритм с итераторами файловых потоков, и . «Перепись» — использование алгоритма для считывания структур (с перегрузкой оператора потокового ввода).

Программа курса

  1. Оценка времени работы алгоритмов
  2. Алгоритмы сортировки, основанные на сравнении (сортировка слиянием, быстрая сортировка, нижняя оценка на время работы алгоритмов сортировки)
  3. Алгоритмы сортировки с линейным временем выполнения (сортировка подсчетом, цифровая сортировка, карманная сортировка)
  4. Элементарные структуры данных (стек, очередь, связанные списки)
  5. Алгоритмы, основанные на двоичной куче (сортировка кучей, очередь с приоритетами)
  6. Введение в алгоритмы поиска (двоичный поиск в отсортированном массиве, двоичное дерево поиска)
  7. Сбалансированные деревья поиска (обзор сбалансированных деревьев, АВЛ-дерево, Splay-дерево)
  8. Хеширование (хеш-таблицы с закрытой и открытой адресацией)
  9. Введение в поиск подстрок (простейший алгоритм поиска подстрок, алгоритм Рабина-Карпа)
  10. Поиск подстрок (алгоритм Кнута-Морриса-Пратта, Z-функция, алгоритм Бойера-Мура)

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

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

Отношения. Часть II

Формальная теория моделирования использует алгебраические отношения, включая их в сигнатуры моделей алгебраических структур, которыми описывает реальные физические, технические объекты и процессы их функционирования. Эта публикация является продолжением предшествующей, прочтение которой желательно, так как многие понятия и термины, используемые здесь, описываются там. Предлагается изложение не в традиционном (стрелочном) стиле, а так, как мне самому пришлось всю эту кухню представлять и осваивать и по учебникам/пособиям, и по журнальным статьям. Особенно полезной вещью считаю созданный мной каталог, он позволяет выделить практически любое пространство и представить его элементы в удобном виде: матрицей, графом и др. Сразу видишь с чем имеешь дело и свойства (они уже выписаны) проверять часто не требуется.

Как я пришел к изучению алгоритмов и советы

Честно признаюсь, мне повезло. Я пришел в разработку и начал осваивать архитектурные и технические подходы после изучения алгоритмов и решения 1000+ задач на различных ресурсах. И мой путь выглядел примерно так: видишь задачу -> не знаешь, как решать -> изучаешь, реализовываешь, модифицируешь подходящий алгоритм.

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

При подготовке к прохождению интервью, два самых популярных ресурса это:

  • LeetCode. Тут собрано много задач и подборок от easy до hard уровня. Для каждой задачи доступен discuss, где люди делятся идеями решений и реализацией на различных языках.
  • InterviewBit. Здесь задачи разделены по уровням и темам. Также можно установить количество дней до интервью и видеть свой прогресс. Плюс для каждой задачи представлены подсказки и решения.

Существуют также ресурсы, которые предлагают обучение в более игровой форме. Например: Codewars или Code in game.

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

А также абсолютно всем советую ознакомиться с книгой «Алгоритмы. Построение и анализ» Томаса Кормена. В ней подробно описаны большинство популярных алгоритмов. К тому же, книга написана понятным языком и легко читается, как в оригинале, так и в переводе.

Требования

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

  • Java: версия 8 (ссылка для скачивания на сайте Oracle)
  • C, C++: MinGW версии 5.1 (для Windows, для Linux можно использовать GCC аналогичной версии), а также Microsoft Visual Studio C++ 2013 (скачать Visual Studio Express можно здесь).
  • C#: Microsoft Visual Studio C# 2013 (скачать Visual Studio Express можно здесь).
  • Python: версия 3.5 (ссылка для скачивания на сайте python.org)
  • Scala: версия 2.11 (ссылка для скачивания на сайте scala-lang.org)
  • Kotlin: версия 1.0 (ссылки на инструкции по установке компилятора, плагинов в IntelliJ IDEA и в Eclipse).

Алгоритмы для начинающих

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

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

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

Список ресурсов

  • medium.freecodecamp.org/the-top-data-structures-you-should-know-for-your-next-coding-interview-36af0831f5e3
  • www.geeksforgeeks.org/commonly-asked-data-structure-interview-questions-set-1
  • prog-cpp.ru/data-list
  • habr.com/post/267855
  • habr.com/post/273687
  • habr.com/post/150732
  • ruhighload.com/%D0%A7%D1%82%D0%BE+%D1%82%D0%B0%D0%BA%D0%BE%D0%B5+%D1%85%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D1%8B+%D0%B8+%D0%BA%D0%B0%D0%BA+%D0%BE%D0%BD%D0%B8+%D1%80%D0%B0%D0%B1%D0%BE%D1%82%D0%B0%D1%8E%D1%82
  • ru.wikipedia.org

О курсе

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

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

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

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


С этим читают