Лекции по алгоритмам и структурам данных и структурам данных и алгоритмам их обработки (учебник)

Лекции Структуры
и алгоритмы обработки данных

Фундаментальная теоретическая база

Тем, кто уже программирует и хочет повысить свой профессиональный уровень

Тем, кто не знаком с этой темой и хочет в ней разобраться на хорошем уровне

Описание

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

Программа дисциплины

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

Цель освоения дисциплины

1-й курс, 3, 4 модуль

для всех кампусов НИУ ВШЭ

«Алгоритмы и структуры данных» направлен на изучение подходов к решению задач из различных областей. Лекционный материал состоит из теоретического описания алгоритмов и структур данных для решения алгоритмических задач. Семинары представляют собой применение и реализацию описанного на лекции материала. Цель: дать слушателям представление о ходе работы алгоритмов, способах представления и использования различных структур данных, а также научить реализовывать их на произвольном языке программирования.

Структуры данных и алгоритмы 6

1.1.
Понятие структур данных и алгоритмов 6

1.2.
Информация и ее представление 7

1.2.3.
Классификация структур данных 8

1.3.
Операции над структурами данных 9

1.5.
Структурность данных и технологии
программирования 11

2.
Простые структуры данных 12

3.
Объектные типы данных 24

3.1.
Объявление и реализация классов 24

3.4.
Структурированная обработка ошибок 27

4.
Статические структуры данных 32

4.6.
Операции над статическими структурами 43

5.
Полустатические структуры данных 65

5.1.1.
Стеки в вычислительных системах 66

5.2.1.
Очереди с приоритетами 67

5.2.2.
Очереди в вычислительных системах 67

5.3.1.
Деки в вычислительных системах 68

5.4.1.
Операции над строками 69

5.4.2.
Представление строк в памяти 70

6.
Динамические структуры данных 74

6.1.
Связное представление данных в памяти 74

6.2.
Связные линейные списки 75

6.2.1.
Машинное представление связных линейных
списков 75

6.2.2.
Реализация операций над связными
линейными списками 76

6.2.3.
Применение линейных списков 83

6.3.
Нелинейные разветвленные списки 85

6.3.2.
Представление списковых структур в
памяти 87

6.3.3.
Операции обработки списков 87

6.4.
Язык программирования LISP 88

6.5.
Управление динамически выделяемой
памятью 88

7.
Нелинейные структуры данных 90

7.1.
Графы и деревья 90

7.2.
Машинное представление графов 92

7.3.1.
Представление бинарных деревьев 97

7.3.2.
Прохождение бинарных деревьев 99

7.4.
Алгоритмы на деревьях 100

7.4.1.
Сортировка с прохождением бинарного
дерева 101

7.4.2.
Сортировка методом турнира с выбыванием 101

7.4.3.
Применение бинарных деревьев для сжатия
информации 103

7.4.4.
Представление выражений с помощью
деревьев 105

8.
Методы ускорения доступа к данным 108

8.1.2.
Оценка качества хеш-функции 110

8.1.3.
Методы разрешения коллизий 111

8.1.4.
Переполнение таблицы и рехеширование 116

8.2.
Организация данных для поиска по
вторичным ключам 117

1.
Создание и управление списковыми
объектами 119

2.
Алгоритмы поиска и сортировки 121

3.
Моделирование работы стека 134

4.
Создание и редактирование бинарных
деревьев 137

5.
Создание и редактирование сильноветвящихся
деревьев 139

Задания
для самостоятельной работы 142

1. Структуры данных и алгоритмы

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

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

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

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

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

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

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

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

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

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

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

Этот курс может оплатить ваш работодатель

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

Вы можете учиться своём темпе, срок обучения не ограничен.

Мы рекомендуем выделять 15-20 часов в неделю. Так с одной стороны обучение будет достаточно интенсивным, чтобы не растягивать его надолго, а с другой — достаточно комфортным, чтобы совмещать с работой и успевать отдыхать.

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

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

Тогда вы можете обучаться вместе с наставником.

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

Наставник помогает справляться с трудностями, отвечает на вопросы и делает ревью проектов.

Мы принимаем карты Visa, MasterCard и МИР любого банка, валюта счёта тоже может быть любой.

Если решите учиться самостоятельно, оформите подписку на план «Базовый». Доступ ко всем трекам откроется сразу после оплаты.

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

Оглавление

1Структуры
данных и алгоритмы 3

1.1Понятие структур
данных и алгоритмов 3

1.2Информация и
ее представление в памяти 5

1.3.3Изображение
чисел в позиционной системе счисления 9

1.3.4Перевод чисел
из одной системы счисления в другую 9

1.5Операции над
структурами данных 13

1.6Структурность
данных и технология программирования 14

2.1.4Операции над
числовыми типами 26

2.7.2Представление
указателей в языках программирования 34

3.5Представление
стека и очередей в виде списков 50

4Задачи
поиска в структурах данных 54

4.2Поиск делением
пополам (двоичный поиск) 55

4.3Поиск в таблице 57

4.3.2Алгоритм Кнута,
Мориса и Пратта 59

4.3.3Алгоритм Боуера
и Мура 62

5Методы
ускорения доступа к данным 65

5.1.2Переполнение
таблицы и рехеширование 71

5.2Организация
данных для ускорения поиска по вторичным
ключам 76

6Представление
графов и деревьев 80

6.4.1Сортировка с
прохождением бинарного дерева 89

6.4.2Сортировка
методом турнира с выбыванием 90

6.4.3Применение
бинарных деревьев для сжатия информации 93

6.4.4Представление
выражений с помощью деревьев 95

Структуры
данных и алгоритмы служат теми материалами,
из которых строятся программы. Более
того, сам компьютер состоит из структур
данных и алгоритмов. Встроенные структуры
данных представлены теми регистрами и
словами памяти, где хранятся двоичные
величины. Заложенные в конструкцию
аппаратуры алгоритмы – это воплощенные
в электронных логических цепях жесткие
правила, по которым занесенные в память
данные интерпретируются как команды,
подлежащие исполнению. Поэтому в основе
работы всякого компьютера лежит умение
оперировать только с одним видом данных
– с отдельными битами, или двоичными
цифрами. Работает же с этими данными
компьютер только в соответствии с
неизменным набором алгоритмов, которые
определяются системой команд центрального
процессора.

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

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

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

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

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

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

Структура
данных относится, по существу, к
“пространственным” понятиям: ее
можно свести к схеме организации
информации в памяти компьютера. Алгоритм
же является соответствующим процедурным
элементом в структуре программы – он
служит рецептом расчета.

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

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

Испытания

Это практические задания, которые мы советуем выполнить после завершения курса. Задания помогут вам получить дополнительный опыт в программировании и закрепить полученные навыки. Обычно мы рекомендуем выполнить 3-5 испытаний. Но если не получается, не отчаивайтесь. Просто вернитесь к ним позже

Оформите подписку

3 900 ₽

Получите доступ к треку и всем курсам Хекслета

Краткая программа курса

Введение в алгоритмы и структуры данныхОпределение асимптотики, оценка времени работы программы, оценка затраченной памятиОдносвязные и двусвязные списки, работа с ними

Реализация игрушечного менеджера памяти при помощи LRU и LFU кэша

Рекурсия и комбинаторика. 1 неделя

Рекурсивные переборы, переборы всех комбинаторных объектовПерестановки, разбиение на слагаемые, строки ФибоначчиПеребор битовых масок

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

Сортировки и поиск. 2 недели

Сортировки, использование встроенной функции sort в языкахАлгоритм бинарного поиска. Бинарный поиск по ответу

Сортировка больших файлов с данными, потенциально не помещающихся в оперативную память

3 недели

Принцип хеширования. Парадокс дней рождения. Известные алгоритмы хеширования.Полиномиальное хешированиеАлгоритмы на строкахХеш-таблица, встроенная реализация, собственная реализация

Генератор magnet-ссылок для файлов и папок

Графы. Представление графов и алгоритм DFSГрафы. Задача о поиске кратчайшего пути в графе, алгоритм BFSАлгоритм Дейкстры

Travel planner — постройка кратчайшего маршрута для путешествия

5 недель

Графы. Представление деревьев. Алгоритмы на деревьяхКучиБинарное дерево поиска, работа с нимКрасно-черное дерево, AVL-деревоДеревья Хаффмана

Реализация алгоритма Liquid Resize

Фишки прохождения технических собеседований в крупные IT-компанииMock-интервью «Собеседование в Amazon»

Москва 2007

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

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

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

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

Включено в курс

9 уроков (видео и/или текст)

13 упражнений в тренажере

27 проверочных тестов

Доступ к остальным курсам платформы

Программа обучения

1.3.3Изображение
чисел в позиционной системе счисления 8

1.5Операции над
структурами данных 12

2.1.4Операции над
числовыми типами 25

2.7.2Представление
указателей в языках программирования 33

3.5Представление
стека и очередей в виде списков 48

4Задачи
поиска в структурах данных 53

4.2Поиск делением
пополам (двоичный поиск) 54

4.3Поиск в таблице 56

4.3.2Алгоритм Кнута,
Мориса и Пратта 58

4.3.3Алгоритм Боуера
и Мура 61

5Методы
ускорения доступа к данным 64

5.1.2Переполнение
таблицы и рехеширование 70

5.2Организация
данных для ускорения поиска по вторичным
ключам 75

6Представление
графов и деревьев 79

6.4.1Сортировка с
прохождением бинарного дерева 88

6.4.2Сортировка
методом турнира с выбыванием 89

6.4.3Применение
бинарных деревьев для сжатия информации 92

6.4.4Представление
выражений с помощью деревьев 94

Продолжительность 11 часов

Формат обучения

Курс состоит из учебных модулей с уроками и проектами

Мы воссоздали реальное рабочее пространство программиста. Прочувствуйте разработку «как есть» — с установкой софта, запуском кода, чтением ошибок и консольными командами

Проходите уроки самостоятельно в любое удобное время

Чему вы научитесь

Студентов учатся ежемесячно

Нашу платформу часто рекомендуют студенты

Проекты в портфолио

Портфолио с выполненными проектами Хекслета — сильное преимущество при трудоустройстве как для опытных, так и для начинающих разработчиков

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

Изучите структуры данных в поисковых системах, освойте ключевые методы поиска и метрики релевантности, а также постройте обратный индекс.

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

Алгоритмы и структуры данных

Получите фундаментальные знания в Computer Science и научитесь решать любую задачу эффективно с помощью знаний алгоритмов

Трек можно пройти на JavaScript, Python, PHP, Java

Что вас ждет на курсе

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

Решаем упражнения различной сложности, в том числе олимпиадные задания и бизнес-задачи

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

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

Домашние задания и обратная связь

Задачи динамического программирования. Базовые применения. Префиксные суммыЗадачи динамического программирования. Сложные задачи. Задача о рюкзакеКонечные автоматы. Регулярные выражения

Понравилась статья? Поделиться с друзьями:
ТВОЙ ВК
Добавить комментарий