lekcii5 (Лекции)

С. С. Гайсарян В. Е. Зайцев КУРС ИНФОРМАТИКИ Изчание 9-е, предварительное, переработанное и дополненное с приложением хрестоматии на компакт-дисках Допущено Министерством образовапия Российской Федерации в качестве учебного пособия ьсля студентов вузов, обучающихся по специальности «Прикладная математика и информатика» Москва Издательство МАИ 1993 ББК 16.2.12 Г147 УДК 519.3 (075.8) Рецензенты: член-корр. РАН Иванников В. П. х-а.

Ф а: . «у«, а ф. 'г?К:д:м: К. К. д-р. физ.-мат. наук Цейтин Г. С. Гайсарян С. С., Зайцев В. Е. Г147 Курс информатики: Учеб. пособие. - Мс Изд-во МАИ, 1993. -- 414 сс ил. - - с приложением на С1) КОМ. 1ВВХ 5-7035-ХХХХ-Х Фувдамснтальг|ыс основы соврсмснной ин4эорыатякв излагаются на баас надъязыкового ьгатсматичсско~о подхода. Учсбнос пособис прсдназначсно для студснтов спсциальнсстсй, прсдгю- лагающггх уливсрситстскую долготовку ао информатика, н можст быть полезно для самообразования с цслью углублснвя тсорстнчсскнх знаний. Курс сопровождастся практикумом, описанном н отдсльном пособии. В прнлагасмую к пособию хрсстоматин~ на компакт-диско вьлючсны мно- гочислснныс оригннальныс и свободно-распространясмыс свстсмы, ста- тьи, докумснты и матсрналы которыс могут примсняться при изучсвви ку рса.

Г 1602120000 106-90 094(02)-92 ББК 16.2.12 1ЯВМ 5-7035-ХХХХ-Х ©С. С. Гайсарян 1983--2007, В. Е. Зайцев 1993-2007 Оглавление Введение Предмет курса Структура курса . Рекомендуемая литература 7 7 8 9 1 Основные понятия информатики 1.1 Информация и сообщение . 1.2 Интерпретация сообщений 1.3 Знаки и символы . 1.4 Кодирование 1.5 Системы счисления 1.6 Обработка сообщений 1.7 Обработка информации . 1.8 Автоматизация обраоотки информации 1.9 Конструктивное описание процесса обработки дискретных сообщений 1.10 Интерпретация дискретных сооощений 2 Элементы теории алгоритмов 2.1 Необходимость формального определения алгоритма .. 2.1.1 Рекурсивные функции 2.1.2 Машины Тьюринга 2,1.3 Нормальные алгоритмы Маркова 2.1.4 Тезис Тьюринга-Черча 2.2 Машины Тьюринга 2.2.1 Неформальное описание 2.2.2 Математически строгое определение 2.2.3 Диаграммы Тьюринга .

2.2.4 Понятие моделирования 2.2.5 Эквивалентность диаграмм и программ МТ 2.3 Нормальные алгоритмы Маркова 2.4 Исследование алгоритмической модели Тьюринга .. 2.4.1 Теоремы Шеннона . 2.4.2 Доказательство 1 теоремы Шеннона (К. Шеннон,1956) .. 2.4.3 Доказательство 1 теоремы Шеннона. (Д. Рисенберг, 2005) 2.4.4 Доказательство теоремы 2.4.2 2.5 Вычислимые функции 16 16 16 18 19 24 30 31 36 39 39 40 40 41 41 42 42 43 46 50 51 53 60 60 62 66 72 75 2.6 2.7 2.8 2.9 2.5.1 Понятие функции на множестве слов . 2.5.2 Понятие вычислимости 2.5.3 Функции, вычислимые по Тьюрингу 2.5.4 Нормированные вычисления 2.5.5 Предикаты, вьгпгслимыс по '!'ьн>рингу "1еОремы О сОчетаниях алгОритмОв .

2.6.1 Теорема о композипии . 2.6.2 Теорема о ветвлении . 2.6.3 Следствие из теоремы о ветвлении 2.6.4 Пример итеративного алгоритма 2.6.5 Теорема о цикле 2.6.6 Обобщенная теорема о цикле . Схемы машин Тьюринга 2.7.1 Конструирование мапшн Тьюринга «сверху вниз» 2.7.2 Определение схемы машины Тьюринга .

2.7.3 Эквивалентность схем и диаграмм 2.7.4 Доказательство теоремы о нормированной вычислимости 2.7.5 Некоторые фундаментальные результаты теории алгоритмов Развитие алгоритмической модели Тьюринга 2.8.! Понятие об универсальной мап>ипе Тьюринга 2.8.2 Линейная за.лись схем ма,шин Тьюринга 2.8.3 Язык описания схем машин Тьюриша Модель фоп Нейгиапа 2.9.1 Критика модели вычислений Тьюринга . 2.9.2 Адреса и имена 2.9.3 Построение щ>оцсссора, с1>он Неймана 2.9А Согласование процессоров 2.9.5 Машина, фон Неймана.

75 76 76 76 78 79 79 80 81 82 84 85 87 87 92 93 97 104 104 104 106 107 110 110 111 115 117 П8 3 Концепция языка программирования для машины фон Неймана Элементы дейкстровской нотации 3.1.1 Требования к структуре программ для машины фон Неймана, 3.1.2 Обобщенная инструкция присваивания 3.1.3 Обобщенная инструкция композиции 3.1.4 Охраняемые инструкции 3.1.5 Обобщенная инструкция ветвления 3.1.6 Обобщенная инструкция цикла Типы данных 3.2.1 Определение типа данных 3.2.2 Т>ш логический 3.2.3 Тип целый 3.2.4 Тип вещественный . 3.2.5 Тип литерный 3.2.6 Согласование типов 3.2.7 Пебазовыс типы данных 3.2.8 Понятие о структурном типе данных 120 .

120 . 120 . 123 128 . 130 131 . 132 . И5 . 135 . 140 143 . 169 . 171 . 172 . 172 173 174 176 179 182 183 183 184 188 189 191 параметры 193 . 193 . 194 5 Ст 5.1 200 руктуры данных 200 204 5.7 5.9 5.10 277 3.2.9 'Гип массив 3.2.10 Понятие о записях . 3.2.11 Понятие о файлах Ьлочная ст1эуктура прог1эамм Процедуры и функции ЗА.1 Описание и использование ЗА.2 Вызов функций и процедур. Формальные и фактические 3.4.3 Передача параметров ЗАА Побочные эффекты ЗА.5 Критика алгоритмической модели фон Неймана Критика языка Паскаль .

4 Распределение памяти 4.1 Статические и динамические объекты программ 4.2 Ссылочпый тип Уровни описания структур данных Файл 5.2.1 Функциональная спсцификапия. 5.2.2 .11огическое описание и физическое представление Вектор . 5.3 1 Функциональная спецификация 5.3.2 Логическое описание и физическое представление Очередь . 5.4.1 Функциональная спецификация. 5А.2,11огическое описание и физическое представление Стек 5.5.1 Функциональная спецификация 5.5.2 Логическое описание Линейный список 5.6.1 Функциональная спецификация 5.6.2 Логическое описание 5.6.3 Физическое представление Списки общего вида .

11опятие о рекурсии Деревья 5.9.1 Двоичные деревья 5.9.2 Двоичная интерпретация дерева общего вида 5.9.3 Функциональная спецификация 5.9А Логическое описание Алгоритмы обработки деревьев 5.10.1 Понятие обхода, дерева 53 0.2 Алгоритмы обхода двоичных деревьев 5.10.3 Построение и визуализация дерева 5.10.4 Деревья выражений. Разнофиксньи; формы записи выражений 530.5 Обход дерева общего вида 205 206 210 210 211 213 215 216 231 233 234 240 242 243 244 255 264 267 268 270 271 272 272 273 275 . 283 .

290 . 296 . 298 . 301 5.11 5.12 6 Сортировка и поиск 7 Методы программирования в расши- 6.1 6.2 6.3 7.1 7.2 7.3 7А Деревья поиска . 5.11.1 Поиск по дереву с вклю и ниями 5.11.2 Исключение из деревьев 5.11.3 Сбалансированные деревья . 53 1.4 Физическое представление. Отображение на массив. Графы .. 5.12.1 Алгоритмы на графах Алгоритмы поиска . 6.1.1 Линейный поиск 6.1.2 Двоичный поиск 6.1.3 Поиск в таблице 6.1.4 Поиск тю образцу 6.1.5 Алгоритм Кнута-Мориса-Пратта 6.1.6 Алгоритм Бойера-Мура 6.1.7 Ллгоритм Рабина-Карпа Алгоритмы сортировки 6.2.1 Введение 6.2.2 Сортировка массивов 6.2.3 Сравнение методов внутренней сортировки 6.2.4 Внешние сортировки Таблицы с прямым доступом .

6.3.1 Выбор хеш-функпии . 6.3.2 Рехеширование .. Модульное программирование 7.1.1 Модули в раслпирениях языка Паскаль 7.1.2 Экстторт и импорт объектов Программирование в абстрактных типах данных 7.2.1 Методы абстракции в языках программирования 7.2.2 Виды абстракции в языках программирования Типовые абстракции . 7.3.1 Типизация языка 7.3.2 Контроль титюв 7.3.3 Преобразование и передача титюв 7.3.4 Адресный тип 7.3.5 Родовые модули 7.3.6 Полиморфизм 7.3.7 Процедурный тип 7.3.8 Элементы объектно-ориентированного программирования рсниях языка Паскаль Об ьектно-ориентированное программирование 7А.1 Наследование 7А.2 Построение объектной технологии . 305 . 305 . 305 .

306 . 309 . 312 . 314 . 320 . 324 .. 326 353 3Г>5 . 359 . 360 365 365 . 366 . 381 . 381 . 3т)! . 392 . 393 . 394 . 397 . 406 . 406 . 409 7 4.3 Обьектно-ориентированное программирование и структурное программирование 7А.4 ООП в фон Неймановских языках . 7.4.5 ООП в абсолютно обьектных средах 410 411 416 8 Языки программирования не фон Неймановских моделей 8.1 Языки реляционного типа (8ЕТ1, Я1 ) 8.2 Языки логического программирования (РКОПОС) 8.3 Языки функционального программирования (Ы8Р, АГР) 417 . 417 . 417 . 420 Введение Предмет курса Электронные вычислительные машины (сокращенно ЭВМ) применяются почти во всех областях человеческой деятельности: в научных исследованиях, на ллроизводстве, на транспорте, в торговле, в у"лебных заведениях, в медицине, в военном деле, в делопроизводстве, в спорте.

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

Вместе с ЭВМ развивается «наука об ЭВМ» информатика, которая является предметом наплего изучения. Информатика объединяет несколько более или менее независимых дисшлплин. Одной из таких дисциплин является программирование. Изучению основных принципов и приемов программирования, задач обработки информации для ЭВМ посвялцается оолыпая часть курса. Остальные разделы информатики будут изучаться лишь в той мере, которая необходима, для сознательного усвоения методов программирования. Информатику определяют как науку об автоматической обработке информации с поклощью ЭВЛт1: ~1~ Информатика,: наука об осущестпвяяемой преимущественно с помощью автоматпическах средств целесообразной обработке, информации, рассматпривае.- мой как представление знаний и сообщений в технических, экоттомических и сотлиалаилтях областях.

(Фратлйузскоя Акаделлия) Ь'11»тЕОЛ11лАТ1Я11Ет Яслеттсе Не 1гайетпеп1 га1топтье1, по1аттеп1 раг тас1ттпев аи1ота1щиев, ае Гтп1огта1топ сопвлйегее сотпте 1е виррог~ дев сопнатввапсев Ьитатпев е1 аев соттиптсаИопв, аапв 1ев аоталпев 1есттплуиев, есопоттт1иев е1 воста1в (Асйдетле Ргапсалве) Д. Кнут в своей статье «Информатика и ее связь с математикой» ~34~ пишет: «Лучший с моей точки зрения, способ определить информатику --- это сказать, что она занимается изучением алгоритмов». Дональд Кнут Дональд оп Кнут (Попа14 Е. Кппсй) выдан>шийся американский ученый в области информатики, профессор Стенфордского университета, автор монументальной серии монографий «Искусство программирования», создатель системы компьютерной полиграфии ТЕХ, в которой подготовлен оригинал-макет этой книги.

В последнее время вышли новые книги Дональда Кнута: «Конкретная математика» (в соавторстве с Грэхемом и Паташником), «Компьютерная типография» др Дональд Кнут является почетным членом ълногих академий, почетным доктором ряда университетов, в том лиепе Санкт- Петербургского. Дональд Кнут удостоен национальной научной медали США в 1979 году Оба эти определения не очень понятны, так как они содержат еще не определенные понятия, такие, как «информация», «алгоритм». С изучения этих понятий мы и начнем. Отметим, что информатика использует многие математические ълетоды и во многом подобна математике. Так же, как и математика, информатика изучает законы, созданные человеком и поддающиеся «доказательству», в отличие от естественных законов (изучаемых такими науками, как физика, химия, биология и т.