Информатика.Основополагающее введение. Теоретическая информатика, алгоритмы и структуры данных, логическое программирование, объектная ориентация: В 4-х ч. Ч. 4

Description

Первые три главы данной, заключительной части Введения в информатику посвящены основным теоретическим аспектам информатики: теории формальных языков (основные понятия отношений и графов), формальным языкам и их классификации по Хомскому, различным способам задания грамматик и их соотношениям, понятиям вычислимости и сложности вычислений. В гл. 4 рассматривается ряд классических алгоритмов (сортировка данных, нахождение путей в графах и др.) с оценкой их сложности, а также избранные структуры данных, ориентированные на хранение больших множеств данных, и эффективные методы работы с ними (в частности, специальные древовидные структуры и хэш-таблицы). Гл. 5 посвящена формализмам спецификаций, базам данных и информационным системам, а также - дополнительно к рассмотренным в предыдущих частях стилям программирования - кратко рассматривается логическое и объектно-ориентированное программирование. Наконец, в гл. 6 даются заключительные замечания к информатике, касающиеся ее современного состояния и перспектив развития, а также обсуждаются некоторые специфичные аспекты информатики (правовые, социальные, экономические, философские и др.).