Учебник "Практика и теория программирования"

• Вводный курс по Computer Science с практикой на язык C (не C++), с уклоном в сторону алгоритмов и структур данных.
• Целевая аудитория: студенты младших курсов.
• Авторы: Ворожцов А.В., Винокуров Н.А.
• Книгу можно купить в Физматкниге:
  • Книга 1
  • Книга 2

См. также:

• Контрольная работа по языку Си. Базовые конструкции языка. Простейшие алгоритмические задачи

Содержание

Исполнители и вычислимые функции

• Общее понятие алгоритма
• Машина Тьюринга
• Алгорифмы Маркова. Вычислительная эквивалентность исполнителей
• Языки и метаязыки

Язык Си

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

Алгоритмы

• Рекурсия и итерации
• Рекурсивные и нерекурсивные алгоритмы перебора множеств
• Сортировка, оценка времени работы алгоритмов
• Жадные алгоритмы
• Структуры данных: хеш-таблицы
• Структуры данных: двоичная куча
• Структуры данных: метод деления пополам, двоичное дерево поиска
• Структуры данных: методы балансировки деревьев, АВЛ-деревья
• Структуры данных: красно-чёрные деревья
• Алгоритмы на графах: обход графа в ширину и в глубину
• Жадные алгоритмы на графах

Дополнительные лекции

• Алгебра булевых функций
• Теорема Геделя
• Сложность вычислений
• Методы синтаксического разбора
• Продукционное программирование и регулярные выражения языка Perl
• Функциональное программирование на примере языка Haskell
• Виртуализация. Архитектура компьютера

Отзывы

На кафедре информатики мы давно ожидали выхода книг "Практика и теория программирования".

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

Петров Игорь Борисович,
зав. кафедры информатики МФТИ

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

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

Евгений Барский,
первый читатель

Аннотация

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

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

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