lekcii7 (Лекции)

С. С. Гайсарян В. Е. Зайцев ББК 16.2.12 Г147 УДК 519.3 (075.8) 1 1602120000-106 90 094(02)-92 Москва Издатеу " МА И 1993 13ВИ 5-7035-ХХХХ-Х КЪ'РС ИНФОРМАТИКИ Издание 9-е, предварительное, переработанное и дополненное с приложением хресгоматии на компакт-дисках Допущено Министерствобг образования Российской Федерации в качестве учебного пособия длн студентов вузов. обучающихся по специавьносги нПрикладная математика и информатика» Рецензенгтж член-корр. РАЕВА Иванников В. П.

.н .:,, ».(эк,,~,ну д-р. физ.-мат. наук Цейтин Г. С. Гайсаряи С. С., Зайцев В. В. Г147 Курс илфо1ыатики: Учеб. пособие. — Мл Изд-во 1»1АИ, 1993. — 414 сл ил. — с приложением на СВ ВОМ. 1ВВИ 5-7035-ХХХХ-Х Еуин ии '. н «р он Сир и н б 'и ' ~он ну ври куин* куифрн:«б и:брн н о. 1 у усом ин и: ' И Кв ч жи орм у, и ох н 'бн рн»и .

и Г.н -р р р и ин ьи у нт и кии. н ~ нр стороне н» 1 р юу у1 ББК 16.2,12 ©С, С. Гайсаряи 1983 2007. В. и. Зайцев 1993. 2007 Оглавление 7 7 8 9 Введение Предлит курса Структура курса . Рекоыендуемая лш ература 16 16 16 18 19 24 29 30 31 Эле 2.1 Копцвпции языка программирования дли машины фон Неймана 3.1 3.2 2.3 2.4 Основные понятия информатики 1.1 Информация и сообщение . 1.2 Ингерпрешпня сообщений 1.3 Знаки и символы . 1А Когчи1ювание 1.5 Систел|ы счисления 1.6 Обработка сообщений 1.7 Обработка информации 1.8 Автоыатизация обработки информации .

1.9 Конс|руктивное описание процесса обработки дискречпых сообщений 1Д0 Интерпрепщия дискретных сообщений . менты теории алгоритмов Необходимое|в форлшльного определения алгоритма 2.1.1 Рекурсивные функции 2.1.2 Машины Тьюринга 2.1.3 Норл|альные алгоритмы Маркова 2.1.4 Тезис Тьюринга-Черча Машины Тьюринга 2.2.1 Неформальное описание 2.2.2 Математически строгое определение 2.2.3 Диаграммы Тьюринга .

2.2.4 Понятие моделирования 2.2.5 Эквивалентность диаграмм и програмл| МТ, Нормальные алгоритмы Маркова Иоследование гмларитл|ической модели Тьюринга . 2.4.1 '1еореыы Шеннона . 2.4.2 Доказательство 1 ты|ремы Шешюна (К. Шеннон,1956) . 2.4.3 Доказательство 1 чворемы Шеннона (Д. Рисенберг. 2005) 2.4.4 Долвзателы."гяо теоремы 2.4.2 Вычиюшл|ые функции . 39 39 40 40 41 41 42 42 43 46 50 51 53 60 60 62 66 72 75 2.6 2.8 2.9 2.5.1 Понятие функция на лгяолкестве слов 2.5.2 Понятие вычисдимссти 2.6.3 Функции, вычисшлгые по Тыарингу 2.5.4 Нормированные вычислении 2.5.5 Предикаты.

вычислиыые по Тьюрингу Теореыы о сочегвниях алгоритмов 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.1 Пан|мне сб универсальной машине Тьюринга....

2.8.2 Линейная запись схем мешин Тьюринга 2.8.3 Язык описания схем машин Тьюринга Модель фон Неймана 2.9.1 Критика модели вычислений Тьюринга... 2.9.2 Адреаа и иыена 2.9.3 Построение процессора фан Нейл|ана .. 2.9.4 Согласование п1юцессоров 2.9.5 Машина фон Неймана . Элел|енчы дейкстравской вотация 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А Тип вещественный . 3.2.5 Тип |оперный 3.2.6 Согласованяе типов 3.2.7 Небаювые типы данных 3.2.8 Понятие о с|руктурном типе данных... 75 76 76 76 78 79 79 81 82 84 ббг 87 87 92 93 97 .

104 . 104 . 104 . 106 . 107 . 110 . 110 111 . 115 . 117 . 118 120 . 120 . 120 . 123 , 128 130 . 131 . 132 . 135 . 135 140 . 143 . 153 , 169 171 . 172 . 172 5.11 173 174 176 179 182 183 183 184 188 189 191 283 . 285 288 290 . 296 298 301 З.З 3.5 5.12 Графы 5.12.1 Алгоритмы на графах .

параметры Сортировка и поиск 193 . 193 194 200 5 Стр 52 уктуры данных 200 204 205 . 206 . 210 210 , 211 213 2Г5 210 231 233 234 240 242 243 5.4 Методы программирования 7.1 7.2 7.3 255 255 5.7 5.8 5.9 264 207 . 268 . 270 271 272 272 .. 398 .. 406 . 406 . 409 275 .. 277 283 выражений 3.2.9 Тип лтассив 3.2.10 Понятие о записях . 3.211 Понятие о файлах Бтючная структура программ Процедуры и Функции Ззй1 Описанне н испошлование 3.4,2 Вылов функций и процедур. Форлшльные н фактические 3.4.3 Передача параметров 3.4.4 Побочные эффекты 3.4.5 Критика алгоритмической модезн фон Неймана Критика языка Паскаль . 4 Распределение памяти 4.1 Статические и динамические обьекты програмлт 4.2 Ссы ючный тнп Уровни описания структур данных Файл . 5.2.! Функциональная тмецификация .. 5.2.2 Логическое описание н физическое прсдсташтенио Вектор . 6.3.1 Функциональная спецификация 5.3.2 Логическое описание и физическое представление Очередь 5.4.1 Фу.нкциональная спецификация..

5.4.2 Логическое описание и фнзичеакое предсшвление Стек 5.5.1 Функциональная специфиющия 5.5.2 Логическое описание Линейный список 5.6.1 Функциональная спецификации 5.6.2 Логическое описание 5.6.3 Фтшпческое представление Си~~~и абтпего вн;ш Понятие о рекурсии Деревья 5.9.1 Двоичные деревья . 5.9.2 Дызнчная тттперттретвцня дерева общего вида 5.9.3 Функшюнальная спецификация 5.92 Логическое описание 5.10 Алтортпзты обработки деревьев 5.103 Понятие обхода дерева 5.10.2 Алттзритмы обхода двоичных деревьев 5.10.3 Построение н визуализация дерева 5Д0.4 Деревья выраженяй. Разнофиксные формы записи 5.10.5 Обход дерева общего вида 6.1 6.2 6.3 Деревья поиска .

5.11.1 Поиск но дереву с включениями . 5.11.2 Иск.тючепие те деревьев 5.11.3 Сбалансированные деревья 5.11.4 Физическое представление. Отображение на лшсснв. Алгоритмы поиска 6.1.1 Линейный поиск 6.1.2 Двоичный поиск 6.1.3 Поиск в таблице 6.1.4 Поиск по образцу 63.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.4.1 11аследовантте .

7.4.2 Построение объектной технологии . 305 305 305 . 306 309 312 314 320 324 . 326 326 . 328 . 353 355 359 36>0 361 365 . 365 .. 366 .. 381 , . 381 . 382 .. 386 . 391 391 . 392 . 392 393 394 394 397 417 417 417 . 420 Введение Предмет курса ~тйрат тцуэскал Академия) 7А.3 Обьсктно-ориентированное программирование и структурное программирование . 410 7.4.4 ООП в фон Наймановских языках . 411 7.4.5 ООП в абсолютно объектных средах .........

416 8 Языки программирования нв фон Найк»ановских моделей 8.1 Языки реляционного тяпа (8ЕП. 80)Ь) 8.2 Языки логического программирования (РНОЬОС) 8.3 Языки функционального программирования (МВР, АРР) Электронные вычислнгелыняе машины (сокрашенпо ЭВМ) примепяклся почти во всех областях человеческой деятельности: в научных исследавютиях., ва производстве, на транспорте, в торговле, в учебных заведениях, в медицине, в военном деле.

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