Информатика. Основополагающее введение. В 4-х частях

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