Н вирт алгоритмы и структуры данных: Алгоритмы и структуры данных. Новая версия для Оберона | Вирт Н.

Алгоритмы и структуры данных. Новая версия для Оберона » LITMY.RU

Алгоритмы и структуры данных. Новая версия для Оберона

Название: Алгоритмы и структуры данных. Новая версия для Оберона
Автор: Вирт Н.
Издательство: М.: ДМК Пресс
Год: 2010
Cтраниц: 272
Формат: pdf
Размер: 14 мб
Язык: русский

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

Скачать с облака

НЕ РАБОТАЕТTURBOBIT.NET? ЕСТЬ РЕШЕНИЕ, ЖМИ СЮДА!

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

Информация
Посетители, находящиеся в группе Гости, не могут оставлять комментарии к данной публикации.

Н.Вирт АЛГОРИТМЫ + СТРУКТУРЫ ДАННЫХ = ПРОГРАММЫ Монография известного швейцарского специалиста по системному программированию, знакомого советским

1. Организационно-методический раздел.

ОФОРМЛЕНО НЕ ПО ТРЕБОВАНИЯМ 1. Организационно-методический раздел. 1.1 Название курса. Программирование на языке высокого уровня Направление — 552800 Информатика и вычислительная техника. Раздел обще профессиональные

Подробнее

1. Организационно-методический раздел.

1. Организационно-методический раздел. 1.1 Название курса. Программирование на языке высокого уровня Направление — 552800 Информатика и вычислительная техника. Раздел обще профессиональные дисциплины Компонент

Подробнее

ПРОГРАММА ПО ИНФОРМАТИКЕ

Министерство образования и науки Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Уральский федеральный университет имени первого

Подробнее

СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ В ЭВМ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Томский государственный университет систем управления и радиоэлектроники»

Подробнее

Глава 2. Однопроходные алгоритмы 47

Содержание Предисловие 13 От издательства Диалектика 15 Глава 1. Разминка (понемногу о разном) 17 1.1. Три простые задачи 17 1.1.1. Совпадения стрелок часов 17 1.1.2. Последовательности с одинаковыми суммами

Подробнее

Кафедра информационных технологий

Министерство образования и науки Российской Федерации НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЭКОНОМИКИ И УПРАВЛЕНИЯ «НИНХ» Кафедра информационных технологий МЕТОДИЧЕСКОЕ РУКОВОДСТВО ПО ОРГАНИЗАЦИИ САМОСТОЯТЕЛЬНОЙ

Подробнее

Задания учебную практику

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

Подробнее

СТРУКТУРЫ ДАННЫХ В ЭВМ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ «МИНСКИЙ ГОСУДАРСТВЕННЫЙ ВЫСШИЙ РАДИОТЕХНИЧЕСКИЙ КОЛЛЕДЖ» ПОДЛЕЖИТ ВОЗВРАТУ УТВЕРЖДАЮ Проректор по учебной работе П. И. Кирвель «14»

Подробнее

СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ В ЭВМ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Томский государственный университет систем управления и радиоэлектроники»

Подробнее

Информатика и ИКТ. 9 класс

урока Тема урока 1 Компьютерные сети: виды, структура, принципы функционирования. Аппаратное и программное обеспечение работы глобальных компьютерных сетей. Скорость передачи. 2 Работа в локальной сети

Подробнее

Содержание. I Основы 23. Предисловие 14

Содержание Предисловие 14 I Основы 23 Введение 24 1 Роль алгоритмов в вычислениях 26 1.1 Что такое алгоритмы 26 1.2 Алгоритмы как технология 32 2 Приступаем к изучению 38 2.1 Сортировка вставкой 38 2.2

Подробнее

Структуры и алгоритмы обработки данных в ЭВМ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Томский государственный университет систем управления и радиоэлектроники»

Подробнее

Классификация языков и грамматик 30

Содержание Предисловие 11 Введение 13 Глава 1. Формальные языки и грамматики 15 Языки и цепочки символов. Способы задания языков 15 Цепочки символов. Операции над цепочками символов 15 Понятие языка. Формальное

Подробнее

Вопросы для самопроверки

Вопросы для самопроверки Программирование на языке С 11 ноября 2014 г. Лекция 1. Вводная 1. Какие существуют аспекты разработки ПО? Подходы к разработке? 2. Какие признаки характеризуют любительский подход?

Подробнее

ТРЕБОВАНИЯ К УРОВНЮ ПОДГОТОВКИ ОБУЧАЮЩИХСЯ

2 ТРЕБОВАНИЯ К УРОВНЮ ПОДГОТОВКИ ОБУЧАЮЩИХСЯ В результате освоения курса информатики и ИКТ в 9-м классе обучающиеся получат представление: о системах счисления и принципах кодирования информации; о моделировании

Подробнее

Пояснительная записка

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

Подробнее

Шифр направления

2 1. Цели и задачи дисциплины Целью изучения дисциплины «Алгоритмы и анализ сложности» является изложить классификацию алгоритмических задач и алгоритмов, основанную на их сложности. Основные задачи дисциплины:

Подробнее

1. Планируемые результаты освоения предмета

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

Подробнее

Контроль знаний студента

Контроль знаний студента Перечень теоретических вопросов по дисциплине «Структуры данных»: 1. Классификация структур данных. 2. Массивы. Функция адресации. 3. Линейные списки. Основные процедуры по ведению

Подробнее

Рабочая программа Информатика 9 класс

Петровский филиал Муниципального бюджетного общеобразовательного учреждения Сатинской средней общеобразовательной школы Рассмотрена и рекомендована «УТВЕРЖДЕНА» к утверждению пед.советом Приказ от от протокол

Подробнее

Задачи по базовым алгоритмам

Задачи по базовым алгоритмам Алгоритмы с массивами 1. Нахождение максимума, минимума, второго максимума, второго минимума в массиве за один проход. Нахождение вторых максимумов/минимумов как с учётом повторяющихся

Подробнее

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Программа по информатике и ИКТ для 9 классов основной школы (далее Программа) составлена на основе федерального компонента государственного образовательного стандарта основного общего

Подробнее

Упражнения Программные проекты… 85

Оглавление Введение… 18 Второв издание… 18 Дополнительные тем ы… 18 Вопросы… 19 Упражнения… 19 Программные проекты… 19 О чем эта книга… 19 Чем эта книга отличается от других… 20 Доступность…

Подробнее

Оглавление 1. Перечень компетенций с указанием этапов их формирования в процессе освоения образовательной программы… 3 2. Описание показателей и критериев оценивания компетенций на различных этапах их

Подробнее

литература по веб-технологиям, алгоритмам и структурам данных, углубленному программированию на С++ / Блог компании Mail.ru Group / Хабр

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

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

Книга: «Компьютерные сети»

Авторы: Виктор Олифер, Наталия Олифер

Виктор и Наталья совместно создали и разработали более 22 учебных курсов, в течение многих лет вели курс лекций в МИРЭА, МГТУ им. Н.Э. Баумана, а также в Центре информационных технологий.

Книга «Компьютерные сети. Принципы, технологии и протоколы» рекомендована Министерством образования РФ. Издание подойдет для тех, кто хотел бы получить базовые знания о принципах построения компьютерных сетей, понять особенности традиционных и перспективных технологий локальных и глобальных сетей, изучить способы создания крупных составных сетей и управления ими.

Книга: «DNS and BIND»

Авторы: Крикет Ли, Пол Альбитц

Крикет Ли — выпускник Калифорнийского университета в Беркли. После учебы он устроился в Hewlett-Packard, где проработал девять лет. В 1997 г. покинул HP и основал компанию Acme Byte & Wire, осуществляющую консультации и обучение в области DNS. На протяжении одного года Крикет работал директором по DNS-продуктам в Verisign Global Registry Services. В марте 2003 г. перешел в компанию Infoblox, создающую DNS- и DCHP-устройства, где занял пост вице-президента.

Пол Альбитц получил степень бакалавра наук в университете Висконсина и магистра наук в университете Пердью. Работал в Hewlett-Packard над версиями BIND для системы HP-UX версий 7.0 и 8.0. Он создал инструменты, используемые для управления доменом hp.com.

Книга «DNS and BIND» — словно Библия для системных администраторов. Материал в ней подается простым, доступным языком. Издание посвящено BIND 9.3.2 и BIND 8.4.7. BIND 9.3.2 включает усовершенствования безопасности и поддержки IPv6, а также ENUM, SPF, и использование доменных имен, содержащих буквы национальных алфавитов.

Здесь вы найдете всю необходимую информацию о принципах работы DNS, о структуре пространства доменных имен, об установке и настройке серверов имен, о программировании при помощи функций библиотеки DNS-клиента и о многом-многом другом.

Книга: «SQL для простых смертных»

Автор: Мартин Грабер

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

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

Книга: «Основы реляционных баз данных»

Авторы: Дженнифер Уидом, Джеффри Д. Ульман

Дженнифер Уидом — доцент факультетов информатики и электротехники Стэнфордского университета, активный участник исследований в области гетерогенных и полуструктурированных баз данных (БД), методов хранения данных и активных систем БД.

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

Книга «Основы реляционных баз данных» будет полезна всем, кто изучает базы данных. В ней рассмотрены стандарты SQL2, SQL3, ODMG, ODL/OQL, традиционный метод проектирования баз данных, а также анализируется множество аспектов программирования на языке SQL.

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

Книга: «jQuery. Подробное руководство по продвинутому JavaScript»

Авторы: Беэр Бибо, Иегуда Кац

Беэр Бибо — веб-разработчик с более чем 30-летним стажем программирования. Один из авторов книг «jQuery in Action», «Ajax на практике», «Ajax: библиотеки Prototype и Scriptaculous в действии».

Иегуда Кац разрабатывал веб-сайты для New York Times, Allure Magazine, Architectural Digest, Yoga Journal. Участник основной команды проекта jQuery, принимал участие в разработке Merb (альтернативы Ruby on Rails).

Издание «jQuery. Подробное руководство по продвинутому JavaScript» — действительно подробное справочное руководство по платформе для разработки веб-приложений, в котором описывается, как выполнять обход документов HTML, обрабатывать события, добавлять поддержку технологии Ajax в свои веб-страницы, воспроизводить анимацию, взаимодействие другими инструментами, платформами и методами создания модулей расширения для jQuery. Книга предназначена для тех, кто уже знаком с JavaScript и Ajax.

Книга: «Изучаем Python»

Автор: Марк Лутц

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

Четвертое издание «Изучаем Python» содержит основные типы объектов в языке, порядок их создания и работы с ними, а также включает методы работы с модулями и дополнительными объектно-ориентированными инструментами — классами. Приводятся описания моделей и инструкций обработки исключений, а также обзор инструментов разработки.

Дополнительные материалы:

• 3-е издание «Learn Python the Hard Way» содержит хорошие курсы для начального изучения Питона и закрепления освоенного материала: http://learnpythonthehardway.org/.
• Вы новичок в Django или программировании? Все, что вам надо знать о Django: http://www.djbook.ru/rel1.7/
• Учебник по созданию сайтов для начинающих, содержащий простые и легкие в освоении материалы: www.htmlbook.ru.

Книга: «Информатика. Основополагающее введение. Часть I»

Автор: Манфред Бой

Том I четырехтомника выдающегося немецкого ученого Манфреда Боя, лауреата премии Лейбница в области информатики, посвящен базовым понятиям информации и различным формам ее обработки. Манфред дает подробное объяснение алгоритмов (включая их классификацию, описание и исполнение), методов программирования, машинно-ориентированных языковых элементов. Книга содержит исчерпывающие объяснения по вопросам представления и обработки информации.

Книга: «Алгебраическая алгоритмика. С упражнениями и решениями»

Авторы: Клод Китте, Патрис Ноден

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

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

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

Автор: Никлаус Вирт

Про таких людей обычно говорят: в представлении не нуждается. Мы все же кратко заметим, что Никлаус Вирт — ученый, инженер, лауреат премии Тьюринга, один из известнейших в мире теоретик языков программирования, создатель языков Паскаль, Модула-2, Оберон.

Книги Вирта по структурному программированию в образовании считаются обязательным стандартом.

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

Книга: «Структуры данных и алгоритмы»

Авторы: Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман

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

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

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

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

Книги:
«Фундаментальные алгоритмы на C. Части 1—5. Анализ. Структуры данных. Сортировка. Поиск. Алгоритмы на графах»
«Алгоритмы на C++»

Автор: Роберт Седжвик

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

«Алгоритмы на C++» — это и продолжение, и переосмысление описания алгоритмов и структур данных, на этот раз выполненное на C++, хотя приведенные сведения являются фундаментальными и применимы к программированию на любом языке. В книгу добавлены новые алгоритмы, иллюстрации, комментарии и т.д.

Книга: «Структуры данных и алгоритмы в Java»

Автор: Роберт Лафоре

Роберт Лафоре пишет книги по программированию уже 30 лет. Благодаря его книгам неисчислимое количество программистов овладели технологиями объектно-ориентированного программирования.

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

Книга: «Дискретный анализ»

Автор: Иосиф Романовский

Иосиф Романовский — в нашей подборке редкий представитель отечественных авторов. Профессор кафедры исследования операций СПбГУ, автор целого ряда эффективных алгоритмов для решения оптимизационных задач, включая компьютерную реализацию этих алгоритмов, написал популярные лекционные курсы по оптимальному программированию и программированию на ЭВМ алгоритмов оптимизации.

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

Книга: «Конкретная математика. Основание информатики»

Авторы: Роналд Грэхем, Дональд Эрвин Кнут, Орен Паташник

Почти «катехизический документ» по алгоритмике, рассматривающий математические основы анализа алгоритмов. В названии «Конкретная математика» содержится игра слов: КОНтинуальная и дисКРЕТНАЯ. В книге представлен материал об оперировании с дискретными объектами, имеющий сходство с традиционными методами математического анализа.

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

Книга: «Алгоритмы. Построение и анализ»

Авторы: Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн

Целая плеяда авторов подготовила издание, охватывающее огромный объем материала.

Клиффорд Штайн — профессор, специалист в области компьютерных наук.

Рональд Линн Ривест — специалист по криптографии, автор симметричных алгоритмов шифрования RC2, RC4, RC, один из авторов алгоритма RSA.

Чарльз Эрик Лейзерсон — профессор Массачусетского технологического института, специализируется на теории параллельных, распределенных вычислений и практическом ее применении.

Томас Кормен — профессор, преподает в Дартмутском колледже, также занимает должность директора по написанию программ в этом учреждении.

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

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

Книга: «Искусство программирования. Том 1—4»

Автор: Дональд Эрвин Кнут

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

«Искусство программирования» — фундаментальная монография, посвященная важнейшим алгоритмам, используемым в информатике. Книга признана одной из 12 лучших физико-математических монографий столетия.

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

Книга: «Analytic Combinatorics»

Авторы: Филипп Флажоле, Роберт Седжвик

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

Книга «Analytic Combinatorics» является одним из наиболее свежих подходов к проблеме обеспечения возможности точных количественных предсказаний свойств больших комбинаторных структур. Авторы (среди которых и уже знакомый нам Роберт Седжвик) дают полный объем необходимой базовой математики, а также тщательно рассматривают как классические, так и современные приложения теории аналитической комбинаторики. В книге содержатся наглядные примеры приложений, упражнения и примечания.

Книга: «Комбинаторика для программистов»

Автор: Витольд Липский

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

Книга: «Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология»

Автор: Дэн Гасфилд

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

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

Книга: «Методы и алгоритмы вычислений на строках»

Автор: Билл Смит

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

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

Книга: «Алгоритмические трюки для программистов»

Автор: Генри С. Уоррен мл.

Генри Уоррен более 40 лет проработал в IBM. Он трудился над рядом военных командно-управляющих систем и над проектом языка программирования SETL. С 1973 г. Уоррен занимается компиляторами и архитектурой компьютеров в исследовательском подразделении IBM.

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

Книга: «Дискретная математика для программистов»

Автор: Федор Новиков

Федор Александрович Новиков — доцент кафедры прикладной математики Санкт-Петербургского государственного политехнического университета и кафедры технологий программирования Санкт-Петербургского государственного университета информационных технологий, механики и оптики. В учебнике «Дискретная математика для программистов» изложены основные разделы дискретной математики и описаны важнейшие алгоритмы на дискретных структурах данных.

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

Книга: «Дискретная математика для инженера»

Автор: Олег Кузнецов

Олег Петрович Кузнецов — заведующий сектором Института проблем управления РАН, доктор технических наук. В книге «Дискретная математика для инженера» изложены основные понятия теории множеств, общей алгебры, логики, теории графов, теории алгоритмов и формальных систем, теории автоматов. Издание представляет интерес для инженеров, специализирующихся в области автоматизированного управления и проектирования, вычислительной техники, информационных технологий и передачи информации.

Книга: «Приемы объектно-ориентированного проектирования. Паттерны проектирования»

Авторы: Эрих Гамма, Ричард Хелм, Ральф Джонсон, Джон Влиссидес

Эрих Гамма — программист из Швейцарии, ведущий разработчик фреймворка для выполнения юнит-тестов на джаве JUnit и кросс-платформенной интегрированной среды разработки ПО (Eclipse). Работал в IBM над проектом масштабируемой платформы с открытым кодом от для разработки ПО (Jazz).

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

Третий автор — Ральф Джонсон — профессор в Университете штата Иллинойс, популяризатор объектно-ориентированного языка с динамической типизацией Smalltalk.

Джон Влиссидес работал в Стэнфордском университете, а с 1991 г. — в исследовательском центре IBM. Является автором нескольких книг, многих статей и докладов по объектно-ориентированным технологиям, паттернам проектирования и моделированию программного обеспечения.

Авторы, известные как «банда четырех», подарили миру изящное решение типичных задач, возникающих в ООП. Книга состоит из двух частей: в первой рассказывается о возможностях и недостатках ООП, во второй части описаны 23 классических шаблона проектирования. Приводящиеся в книге примеры написаны на языках программирования C++ и Smalltalk.

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

Книга: «Рефакторинг с использованием шаблонов»

Автор: Джошуа Кериевски

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

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

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

Книга: «Язык программирования C++. Вводный курс»

Авторы: Стенли Б. Липпман, Жози Лажойе, Барбара Му

Стэнли Б. Липпман работал с Бьёрном Страуструпом в исследовательской корпорации Bell Lab на ранних стадиях разработки C++. В 2001 г. Стэнли Липпман стал главным архитектором Visual C++ в Microsoft. Он также работал в Emergent Game Technologies, НАСА, Pixar и 2kQubits.

Жози Лажойе участвовала в работе над компилятором С++ в IBM Canada, а также возглавлял рабочую группу базового языка C++ в составе международной организации по стандартизации ANSI/ISO.

Барбара Му имеет почти 30-летний опыт программирования. На протяжении 15 лет она работала в компании AT&T, сотрудничала с Бьёрном Страуструпом, несколько лет руководила группой разработчиков C++.

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

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

Книга: «STL. Карманный справочник»

Автор: Рэй Лишнер

Рэй Лишнер в первую очередь известен в Delphi-коммьюнити как автор книг «Secrets of Delphi 2», «Hidden Paths of Delphi 3» и многих статей для таких журналов, как «Delphi Informant», «Dr. Dobb’s Journal». Но мы рекомендуем другую его книгу — «STL. Карманный справочник». Это действительно справочник по подмножеству стандартной библиотеки C++. В книге описана библиотека STL в современном виде — алгоритмы, итераторы и контейнеры стандартной библиотеки C++, а также ряд других элементов. Приводится краткая сводка по функциям, классам и шаблонам, образующим STL.

Книга: «Совершенный код. Мастер-класс»

Автор: Стив Макконнелл

Стив Макконнелл — программист, редактор и эксперт в области разработки ПО. Он дважды был удостоен премии Jolt Excellence за лучшую книгу года по разработке софта. По степени влияния на отрасль его сравнивали с Биллом Гейтсом и Линусом Торвальдсом.

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

«Совершенный код» — книга, которую должен прочитать каждый программист. И желательно сделать это несколько раз.

Книга: «C++ и STL. Справочное руководство»

Авторы: Дэвид Р. Мюссер, Жилмер Дж. Дердж, Атул Сейни

Дэвид Р. Мюссер — преподаватель, работал с STL с момента ее зарождения: первая реализация библиотеки разработана при его непосредственном участии. Кроме того, он работал над тем, чтобы STL была включена в стандарт ANSI/ISO C++.

Жилмер Дж. Дердж — президент Toltec Software Services Inc., имеет большой опыт разработки приложений на C++, в том числе семь лет — в фирме General Electric Corporate R&D.

Атул Сейни — президент Fiorano Software Inc., производителя программного обеспечения для высокоскоростного обмена сообщениями, разрабатываемого на C++. Он стал первым, кто увидел коммерческий потенциал STL, и предложил свою компанию для продажи библиотеки еще до того, как она вошла в стандарт C++.

Книга «C++ и STL. Справочное руководство» включает небольшой учебный курс, подробное описание каждого элемента библиотеки и большое количество примеров. Книга содержит исчерпывающее описание итераторов, обобщенных алгоритмов, контейнеров, функциональных объектов и т.д. В ней также дается объяснение, как интегрировать STL с другими объектно-ориентированными методами программирования.

Книги:
«Решение сложных задач на С++»

«Новые сложные задачи на C++»

«Стандарты программирования на С+»

Автор: Герб Саттер

Герб Саттер — признанный эксперт по C++. Начал работать в Microsoft в качестве евангелиста платформы Visual C++ .NET и достиг должности архитектора ПО C++/CLI. 10 лет он был организатором и секретарем комитета по стандартизации ISO C++. Много лет регулярно публиковал нетривиальные задачи на C++ в серии под названием Guru of the Week. Позднее Саттер опубликовал развернутые версии многих задач в своих первых двух книгах «Решение сложных задач на C++».

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

Книга: «Алгоритмы на C++»

Автор: Роберт Седжвик

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

В книге подробно описаны массивы, связные списки, строки, деревья и другие базовые структуры данных. Внимание читателя акцентируется на абстрактных типах данных (АТД), на модульном программировании, на ООП и классах C++, приводится более 100 алгоритмов сортировки, выбора, реализаций АТД очереди с приоритетами и реализаций АТД таблицы символов (для поиска).

Книги:
«Язык программирования С++»

«Программирование. Принципы и практика использования C++»

Автор: Бьёрн Страуструп

Невозможно представить подборку книг о C++ без учебников самого автора языка. Бьёрн Страуструп — настоящая легенда, а «Язык программирования C++» является одной из самых широко читаемых книг в своей области. Книги Страуструпа отличает непревзойденное мастерство в области технической документации. Это безусловный канон по возможностям языка.

Первое издание книги «Язык программирования С++» выпущено 29 лет назад. Второе было опубликовано в 1991 г., третье — в 1997 г. Улучшенная версия третьего издания, выпущенная в твердой обложке, получила название «Специальное издание» и отличалась от ранних выпусков третьего издания двумя дополнительными приложениями («Локализация» и «Безопасность исключений и стандартная библиотека»), примерно 1 тыс. исправлений и уточнений, а также дополненным алфавитным указателем. Четвертое издание книги, которая включает в себя C++11, выпущено в 2013 г.

Если вы программируете на С++, то прочесть эту книгу нужно прямо сейчас.

Книга: «Рефакторинг. Улучшение существующего кода»

Авторы: Мартин Фаулер, Кент Бек, Джон Брант, Уильям Апдайк, Дон Робертс

Мартин Фаулер — популярный автор книг и статей по архитектуре ПО, по объектно-ориентированному анализу и разработке, по языку UML, рефакторингу, экстремальному программированию и предметно-ориентированным языкам программирования.

Программист Кент Бек создал такие методологии разработки ПО, как экстремальное программирование и разработка через тестирование. Он является одним из пионеров введения в практику шаблонов проектирования ПО, создания методологии разработки через тестирование, а также коммерческого использования языка Smalltalk. Совместно с Эрихом Гамма создал фреймворк для тестирования JUnit.

Джон Брант и Дон Робертс — авторы Refactoring Browser для Smalltalk. Они также выступают консультантами по вопросам практического и теоретического рефакторинга.

Уильям Апдайк написал докторскую диссертацию по рефакторингу объектно-ориентированных сред (в университете штата Иллинойс), послужившую основой первой крупной публикации на данную тему.

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

«Must read» для всех разработчиков.

Книга: «Полный справочник по C++»

Автор: Герберт Шилдт

Шилдт — писатель, ученый и программист, был членом комитета ANSI, который принимал стандарты С, и комитета ISO, принимавшего стандарты C++. Автор интерпретатора Little C — примера рекурсивного нисходящего парсера.

«Полный справочник по C++» содержит все ключевые слова, функции, классы и свойства языка, соответствующие стандарту ANSI/ISO. В нем освещаются все аспекты языка, включая его основу — язык С.

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

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

Содержание курса в осеннем семестре 2020/21 уч. года

Зачёт по теории

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

Даты: TODO

Обязательная группа вопросов (все вопросы прошлогодние, по итогам этого года возможны изменения в списке):

1. Оценка трудоёмкости и ресурсоёмкости алгоритмов. O большое.
2. Бинарный поиск
3. Сортировка слияниями
4. Хэш-таблицы: принцип работы, основные операции
5. Бинарные деревья поиска: принцип работы, основные операции
6. Структуры данных: графы, варианты представления, применение
7. Графовые алгоритмы: поиск в ширину
8. Графовые алгоритмы: поиск в глубину
9. Графовые алгоритмы: алгоритм Дейкстры
10. Структуры данных Java: List / ArrayList / LinkedList
11. Структуры данных Java: Stack / Queue / Deque / ArrayDeque / LinkedList
12. Структуры данных Java: Set / Map / HashSet / HashMap / LinkedHashSet / LinkedHashMap
13. Структуры данных Java: SortedSet / SortedMap / TreeSet / TreeMap

Дополнительная группа вопросов:

1. Создание алгоритмов (хотя бы два метода из перечисленных)
   1. Рекуррентные алгоритмы
   2. Композиция
   3. Динамическое программирование и мемоизация
   4. Жадные алгоритмы
2. Сложные сортировки (хотя бы одна из перечисленных)
   1. Пирамидальная сортировка
   2. Быстрая сортировка
   3. Сортировки за линейное время (подсчётом, карманная, другие)
3. Хэш-таблицы: варианты реализации, характеристики
4. Бинарные деревья поиска: балансировка, повороты
5. Бинарные деревья поиска: красно-чёрное дерево
6. Префиксные деревья
7. Графовые алгоритмы (хотя бы два из перечисленных)
   1. A-Star
   2. Переборные алгоритмы
   3. Альфа-бета процедура
   4. Топологическая сортировка
   5. Поиск циклов
   6. Поиск мостов
   7. Поиск компонент связности
   8. Поиск минимального остовного дерева
8. Эвристические алгоритмы (хотя бы один из перечисленных)
   1. Генетический алгоритм
   2. Алгоритм колонии муравьёв
   3. Алгоритм имитации отжига
9. Вероятностные структуры данных
10. NP-полные задачи: основные понятия, примеры задач
11. Шифрование с открытым ключом: принцип работы
12. Задачи (хотя бы две из перечисленных)
    1. Задача о поиске подмассива с максимальной суммой
    2. Задача о разрезании стержня
    3. Задача о ранце
    4. Задача коммивояжёра
    5. Задача о сумме подмножеств

Информация о курсе

Занятия в рамках цикла «Программирование» (3-й семестр).

Преподаватели:

Глухих М.И.

Петров М.А.

Гагарский К.А.

Ахин М.Х.

Беляев М.А.

Абдуллин А.М.

Егорова И.А.

Сидорина Т.Л.

Слушатели:

Студенты, обучающиеся по направлениям бакалавриата «Информатика и вычислительная техника» и «Автоматизация и управление»

Литература

• Т. Кормен и др. Алгоритмы. Построение и анализ
• Д. Кнут. Искусство программирования
• Н. Вирт. Алгоритмы + Структуры данных = Программы
• Е. В. Пышкин. Структуры данных и алгоритмы: реализация на C/C++ — книга есть в Интранете
• McDowell, G. L. Cracking the Coding Interview: 150 Programming Questions and Solutions.
• S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani. Algorithms.

Электронные ресурсы

JRE / JDK

Среды разработки (IDE)

Документация

Отчетность:

Два из трёх:

• индивидуальный проект
• соревновательный проект
• упражнения

За каждую из трёх частей студенту ставится оценка от 2.5 до 5 (примерно соответствующая общепринятой пятибалльной системе), или 0 в случае отсутствия данной части или неудовлетворительного её состояния. Далее считается среднее арифметическое из двух лучших оценок, из него выводятся оценки за семестр по следующему принципу:

• От 4.5 до 5 = “Отлично” за курсовой проект, “Зачёт” по теории автоматом (если оценка получена не позднее 28 декабря), или по итогам тестирования и/или собеседования
• От 4 до 4.49 = “Хорошо” за курсовой проект, “Зачёт” по теории автоматом (если оценка получена не позднее 28 декабря), или по итогам тестирования и/или собеседования
• От 3.5 до 3.99 = “Хорошо” за курсовой проект, “Зачёт” по теории по итогам тестирования и/или собеседования
• От 3 до 3.49 = “Удовлетворительно” за курсовой проект, “Зачёт” по теории по итогам тестирования и/или собеседования
• Менее 3, но положительная оценка за соревновательный проект или упражнения = “Неудовлетворительно” за курсовой проект (необходимо улучшать оценку), “Зачёт” по теории по итогам тестирования и/или собеседования
• Менее 3, и отрицательная оценка за соревновательный проект и упражнения = “Неудовлетворительно” за курсовой проект (необходимо улучшать оценку), “Незачёт” по теории (необходимо улучшать оценку)

Допустимые языки для выполнения всех трёх частей практики: Java, Kotlin.

Страницы:

Презентации лекций

Внимание: презентации, помеченные (2019), прошлогодние.

Примеры индивидуальных проектов на осенний семестр 2019/20 уч. год

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

Все задания по умолчанию сдаются в виде репозитория на GitHub с собирающимся проектом и проходящими тестами. Наличие тестов и соблюдение JavaCodeStyle обязательно.

• ИИ для логических игр (все эти темы имеют высокую сложность, особенно для игры в шашки)
  • Реверси
  • Волк и овцы
  • Мельница
  • Шашки русские
  • Шашки американские
• Решатели (тоже темы высокой сложности)
  • Автоматический решатель игры в 15
  • Автоматический решатель кубика или пирамидки Рубика
  • Автоматический решатель сапёра
  • Автоматический решатель тетриса (по выбору: считать, что известна вся последовательность приходящих фигур, или считать, что известно только несколько следующих фигур, например две)
  • Решатель для игры terra incognita
  • SAT-солвер (использовать входные файлы в формате DIMACS)
• Реализация в виде класса на Java одного из видов бинарного дерева поиска с авторегулировкой, например приведённые ниже (темы имеют среднюю сложность). Класс дерева должен реализовывать соответствующий интерфейс Java в обобщённом виде (Set или Map, в более сложном варианте SortedSet или SortedMap). Для усложнения задачи в неё можно добавить визуализацию.
  • АВЛ-дерево
  • Scapegoat tree
  • Splay tree
  • Трип/дерамида (оно же Декартово дерево)
• Реализация в виде класса на Java одного из видов хеш-таблицы, например приведённые ниже (темы имеют среднюю сложность). Класс таблицы должен реализовывать соответствующий интерфейс Java в обобщённом виде (Set или Map). Класс должен обеспечивать возможность неограниченного роста размера таблицы (в пределах памяти компьютера, естественно). Класс может обеспечивать или нет предсказуемый порядок перебора элементов (предсказуемый порядок, естественно, сложнее). Для усложнения задачи в неё можно добавить визуализацию.
  • Хеш-таблица с открытой адресацией
  • Хеш-таблица с двойным хешированием
• Реализация в виде класса на Java одной из прочих структур данных. Точный вид задания согласовывается с преподавателем. Предполагается, как минимум, возможность неограниченного роста структуры данных и максимальная её универсальность. Возможно добавление визуализации
  • Скиплист (он же Список с пропусками, с реализацией List<>, Set<> или SortedSet<> в зависимости от желаемой сложности)
  • 32- или 64- арное дерево поиска для целых чисел (с реализацией Set<>(Map<>) или SortedSet<>(SortedMap<>) в зависимости от желаемой сложности)
  • суффиксное дерево (с алгоритмом Укконена или без него в зависимости от желаемой сложности)
  • бинарная куча
  • фильтр Блума (с произвольным количеством хеш-функций или с фиксированным их количеством в зависимости от желаемой сложности, с реализацией Set<>, частично на заглушках)
• Варианты посложнее:
  • Хеш-дерево (например, hash array-mapped trie, с реализацией Set<> или Map<>)
  • Суффиксный массив с префиксным массивом (с реализацией основных операций для строк, набор можно варьировать, с построением за O(N) для особой сложности)

Соревновательный проект

В качестве соревновательного проекта использована задача с конкурса ICFPC 2019.

Основные правила:

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

Упражнения

Пройдут в срок с 18 сентября по 6 декабря (ориентировочно). Учебный проект с задачами будет здесь. Задания сдаются через систему Котоед.

Восемь уроков:

1. Задачи на сортировку
2. Общие задачи на построение алгоритмов
3. Задачи на бинарные деревья
4. Задачи на префиксные деревья
5. Задачи на хэш-таблицы
6. Задачи на графы
7. Задачи на динамическое программирование
8. Задачи на эвристические алгоритмы

Требуется решить по две задачи из четырёх или пяти имеющихся уроков. Итоговая оценка за упражнения получается делением числа баллов, набранных за задачи в Котоеде (пять лучших уроков, две лучшие в каждом уроке, с учётом штрафов преподавателей) на 12 (60 = отлично, 48 = хорошо и так далее). Решать можно как на Котлине, так и на Java. Допустимая версия Котлина: 1.4.*, допустимая версия JDK: 11 (при использовании других версий JDK могут возникать проблемы с совместимостью версий при проверке на Котоеде).

Требования к решению:

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

Дедлайны:

• 1 ноября 23:59 — дедлайн на задачи из первых трёх уроков

От чего зависит оценка:

• Количество и сложность задач
• Из каждого урока оцениваются две самые сложные задачи
  • Качество кода + Качество алгоритма
  • Правильность оценки алгоритма
  • Полнота тестов

Архив за предыдущие годы

• лекции за год 2019-20 (автор Глухих М.И.) можно посмотреть здесь
• лекции за год 2018-19 (автор Глухих М.И.) можно посмотреть здесь
• лекции за год 2017-18 (автор Глухих М.И.) можно посмотреть здесь
• лекции за год 2016-17 (автор Глухих М.И.) можно посмотреть здесь
• лекции за год 2015-16 (авторы Глухих М.И., Кузнецов А.Н.) можно посмотреть здесь

Обновлено: 28.09.2020 12:53

Алгоритмы и структуры данных — МФТИ

Печать
DOC
PDF

КУРС ЛЕКЦИЙ

АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ. ПРОДВИНУТЫЙ ПОТОК:

Лекция 1. Сортировки

Содержание лекции: 00:07 Сортировка кучей.
00:55 ShiftUp операции.
09:51 Очередь с приоритетом.
15:33 HeapSort.
18:28 Быстрая сортировка Хоара.
20:21 Алгоритм сортировки.
25:02 Реализация.
39:47 Оценка времени работы.
01:04:00 Выбор пивота.
01:10:11 k-ая порядковая статистика.
01:13:34 k-ая порядковая статистика. Альтернативный алгоритм.

Лекция 2. Продолжение сортировок

Содержание лекции: 1:24 kая статистика. Второй алгоритм.
15:26 Оценка времени работы.
20:27 Сортировка Тима Петерса.
33:54 Сортировка Тима Петерса. Вычисление ранов.
36:57 Слияние ранов.
01:07:37 Типы сортировок.
01:10:29 Сортировка подсчётом.

Лекция 3. Продолжение сортировок

Содержание лекции: 01:14 Карманная сортировка.
15:50 Карманная сортировка. Второй алгоритм.
17:55 Поразрядная сортировка, LSD.
25:30 Альтернативная реализация, MSD.
59:32 Внешняя сортировка.
01:08:30 Оценка эффективности.

Лекция 4. Динамический массив

Содержание лекции: 00:06 — Базовые структуры данных.
02:52 — Динамический массив.
09:50 — Динамический массив. Удаление.
11:40 — Реализация.

Лекция 5. Базовые структуры данных

Содержание лекции: 00:07 Начало. Односвязный и двусвязный список.
02:29 Операции в списке и время их работы.
04:56 Удаление из списка.
06:54 Реализация списка.
20:56 Объединение списков.
24:32 Сравнение списка и массива.
29:34 Стек.
32:44 Реализация стека.
34:50 Очередь.
37:53 Дек.
39:15 Вторая реализация для стека.
44:47 Поддержка минимума.
49:21 Персистентнтные структуры данных.
54:45 Очередь из шести стеков.
1:30:22 Реализация очереди из шести стеков.

Лекция 6. Хеш-таблица и k-ичная куча

Содержание лекции: 00:07 — начало.
00:27 — хеш-таблица.
24:50 — реализация.
27:23 — хеш-таблица с открытой адресацией.
36:35 — реализация.
42:01 — вычисление последовательности проб.
52:41 — двойное хеширование для вычисления проб.
56:49 — плюсы и минусы открытой адресации.
01:01:36 — время работы.
01:04:57 — k-ичная куча.

Лекция 7. Деление чисел и многочленов

Содержание лекции: 00:07 начало. Деление чисел.
29:36 перемножение многочленов, улучшенная асимптотика.

Лекция 8. Фибоначчиева куча

Содержание лекции: 15:35 удаление минимума.
17:28 поиск нового минимума.
25:41 код.
32:03 пример работы кода.
39:30 оценка времени работы поиска нового минимума.
48:24 Decrease-Key.
52:32 код.
57:02 анализ времени работы Cascading-Cut и Decrease-Key.

Лекция 9. Деревья поиска

Содержание лекции: 01:00 начало. Деревья поиска.
17:45 определение дерева поиска.
21:48 поиск и вставка.
29:10 минимум/максимум/замена/удаление.
46:00 АВЛ-дерево.
50:00 вращения.
01:13:03 вставка.

123 / PDF / Virt

Зачем изучать структуры данных и алгоритмы?

Эта статья предназначена для тех, кто только начал изучать алгоритмы и задался вопросом, насколько это будет эффективно для повышения их навыков карьеры / программирования. Это также для тех, кто задается вопросом, почему такие крупные компании, как Google, Facebook и Amazon, нанимают программистов, которые исключительно хороши в оптимизации алгоритмов.

Что такое алгоритмы?

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

Например, алгоритм решения проблемы факториалов может выглядеть примерно так:

Задача: найти факториал n

Инициализировать факт = 1
Для каждого значения v в диапазоне от 1 до n:
    Умножьте факт на v
факт содержит факториал n
 

Здесь алгоритм написан на английском языке. Если бы он был написан на языке программирования, мы бы вместо этого назвали его кодом . Вот код для поиска факториала числа в C ++.

  int factorial (int n) {
    int fact = 1;
    for (int v = 1; v <= n; v ++) {
        факт = факт * v;
    }
    вернуть факт;
}
  

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

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

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

Время дорого.

Предположим, Алиса и Боб пытаются решить простую задачу - найти сумму первых 10 ¹¹ натуральных чисел. Пока Боб писал алгоритм, Алиса реализовала его, доказав, что это так же просто, как критиковать Дональда Трампа.

Алгоритм (Боб)

Инициализировать сумму = 0
для каждого натурального числа n в диапазоне от 1 до 1011 (включительно):
    добавить n к сумме
сумма - ваш ответ
 

Код (Алиса)

  int findSum () {
    int sum = 0;
    for (int v = 1; v <= 100000000000; v ++) {
        сумма + = v;
    }
    сумма возврата;
}
  

Алиса и Боб испытывают эйфорию от того, что они могут построить что-то свое в кратчайшие сроки.Давайте проникнем в их рабочее место и послушаем их разговор.

  Алиса:  Давайте запустим этот код и узнаем сумму. 
Боб:  Я запустил этот код несколько минут назад, но он все еще не показывает результат. Что с этим не так? 

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

Два самых ценных ресурса для компьютерной программы - это время и память .

Время, затрачиваемое компьютером на выполнение кода:

Время выполнения кода = количество инструкций * время на выполнение каждой инструкции
 

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

В этом случае общее количество выполненных инструкций (скажем, x) составляет x = 1 + (10 11 + 1) + (10 11 ) + 1 , что составляет x = 2 * 10 11 + 3

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

Время, затраченное на выполнение кода = x / y (более 16 минут)
 

Можно ли оптимизировать алгоритм, чтобы Алисе и Бобу не приходилось ждать 16 минут каждый раз, когда они запускают этот код?

Я уверен, что вы уже угадали правильный способ. Сумма первых N натуральных чисел определяется по формуле:

Сумма = N * (N + 1) / 2
 

Преобразование его в код будет выглядеть примерно так:

int sum (int N) {
    вернуть N * (N + 1) / 2;
}
 

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

Время, необходимое для решения проблемы, в данном случае составляет 1 / год (что составляет 10 наносекунд). Между прочим, реакция синтеза водородной бомбы занимает 40-50 нс, а это означает, что ваша программа будет успешно завершена, даже если кто-то бросит водородную бомбу на ваш компьютер в то же время, когда вы запускаете свой код. 🙂

Примечание. Компьютеры выполняют несколько инструкций (не 1) для вычисления умножения и деления.Я сказал 1 просто для простоты.

Подробнее о масштабируемости

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

Рассмотрим проблему создания класса на 50 учеников. Одно из самых простых решений - забронировать комнату, достать доску, несколько мелков, и проблема решена.

А что, если размер проблемы увеличится? Что, если количество учеников увеличится до 200?

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

Что делать, если количество студентов увеличится до 1000?

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

Что же тогда является масштабируемым решением?

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

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

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

Память дорогая

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

Примеры эффективности алгоритмов

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

Пример 1: Задача возрастной группы

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

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

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

• алгоритм двоичного поиска решит проблему всего за 2 секунды
• наивный алгоритм может занять 1 миллион секунд, что составляет около 12 дней

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

Пример 2: Задача Кубика Рубика

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

Эта симпатичная головоломка имеет 43 252 003 274 489 856 000 позиций, и это всего лишь позиции! Представьте себе, сколько путей можно пройти, чтобы попасть в неправильные позиции.

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

Пример 3: Проблема ДНК

ДНК - это молекула, несущая генетическую информацию. Они состоят из более мелких единиц, представленных латинскими буквами A, C, T и G.

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

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

(количество символов в цепи ДНК) * (количество символов в образце)
 

Типичная цепь ДНК состоит из миллионов таких единиц. Эх! не волнуйся. Алгоритм KMP может сделать это за время, пропорциональное

(количество символов в цепи ДНК) + (количество символов в образце)
 

Оператор * , замененный на + , вносит много изменений.

Учитывая, что шаблон состоял из 100 символов, ваш алгоритм теперь в 100 раз быстрее.Если бы ваш шаблон состоял из 1000 символов, алгоритм KMP был бы почти в 1000 раз быстрее. То есть, если вы смогли найти появление шаблона за 1 секунду, теперь это займет всего 1 мс. Можно сказать и по-другому. Вместо того, чтобы сочетать 1 прядь, вы можете одновременно сопоставить 1000 прядей одинаковой длины.

И таких историй бесконечно ...

Заключительные слова

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

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

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

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

.

Изучите структуры данных и алгоритмы

Зачем изучать DSA?

• Написать оптимизированный и масштабируемый код - После того, как вы узнаете о различных структурах данных и алгоритмах, вы можете определить, какую структуру данных и алгоритм выбрать в различных условиях.
• Эффективное использование времени и памяти - Знание структур данных и алгоритмов поможет вам писать коды, которые работают быстрее и требуют меньше памяти.
• Лучшие возможности трудоустройства - Вопросы о структурах данных и алгоритмах часто задают на собеседованиях в различных организациях, включая Google, Facebook и т. Д.

Как узнать структуру данных и алгоритмы?

Изучите DSA из Programiz

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

Узнайте DSA по книгам

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

Вот несколько книг, которые мы рекомендуем.

• Введение в алгоритмы, Томас Х. Кормен - это одна из лучших книг по алгоритмам, в которой подробно рассматривается широкий спектр алгоритмов
• Алгоритмы, Роберт Седжвик - это ведущий учебник по алгоритмам, широко используемый в колледжах и университетах
• Искусство программирования, Дональд Э.Knuth - эта книга считается лучшей, если вы знаете предмет и ищете более глубокое понимание

Изучите DSA через визуализацию

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

.