Документ взят из кэша поисковой машины. Адрес оригинального документа : http://lib.mexmat.ru/pr/rab_val_3.pdf Дата изменения: Mon Sep 27 07:53:44 2004 Дата индексирования: Sat Dec 22 14:40:55 2007 Кодировка: Windows-1251

РАБОТА НА ЭВМ И ПРОГРАММИРОВАНИЕ. 3 семестр.

http://lib.math.msu.su

РАБОТА НА ЭВМ И ПРОГРАММИРОВАНИЕ
доц. В. Д. Валединский 2 курс, отделение математики Осенний семестр, 48 часов.

1. Структуры представления и хранения данных.
1.1. Стек, дек, очередь. Непрерывные реализации. 1.2. Списки. Ссылочные реализации. Двунаправленный список. Однонаправленный список. Кольцевой список. 1.3. Деревья. Бинарное дерево поиска. Произвольное дерево. Сбалансированное бинарное дерево. Теорема о глубине сбалансированного дерева. Красно-черное дерево. Теорема о глубине красно-черного дерева. B-дерево. Трудоемкость операций с B-деревом. Процедуры поиска, добавления, удаления в каждом типе деревьев. 1.4. Множества. Примитивные реализации множеств. Битовая реализация множества. Хеширование. Хеш-множество на базе массива списков. Хеш-множество по методу последовательных проб. Оценки трудоемкости операций. Примеры хеш-функций. Совершенная (perfect) хеш-функция. 1.5. Графы. Представления графов в памяти. Алгоритмы обнаружения циклов и путей в графе. Конечные автоматы. 1.6. Контейнеры. Контейнер для элементов фиксированного размера. Контейнер для произвольных элементов без операции удаления. Идеи реализации управления памятью в общем случае (функции malloc и free). 1.7. Файловые контейнеры (хранение данных в файловых системах). Файловая система FAT (DOS, Windows). Атрибуты файлов. Области BOOT, FAT, DIR, DATA. Структура записи в каталоге. Алгоритмы для основных файловых операций: захват и освобождение кластера, доступ к требуемой позиции в файле. Файловая система EXT (Unix). Разграничение прав доступа к файлам, типы файлов. Области BOOT, SUPERBLOCK, INODELIST, DATA. Структура Inode, таблица ссылок на блоки. Структура файловкаталогов. Алгоритмы для основных файловых операций: захват и освобождение блока, поиск свободного индекса, доступ к требуемой позиции в файле.

2. Некоторые алгоритмы обработки и преобразования данных.
2.1. Эффективные сортировки. Оценка снизу для трудоемкости сортировки. Быстрая сортировка (quicksort); оценка средней трудоемкости. Турнирная (пирамидальная) сортировка (heapsort); оценка трудоемкости. Сортировки с линейной оценкой трудоемкости. 2.2. Сжатие данных. Алгоритм группового кодирования (RLE), байтовый и битовый варианты. Алгоритм Хаффмена (обычный и адаптивный). Арифметическое кодирование (обычное и адаптивное). Алгоритм LZW. 2.3. Компиляция. Формальные грамматики. Нормальная форма БэкусаНаура. Примеры для арифметических и других выражений. Рекурсивная процедура построения дерева разбора. Понятие о грамматических LR разборах. Процедура LR(1) разбора оператора присваивания. Модельный компилятор модельного алгоритмического языка. Модельный язык (подмножество Basic). Модельный стековый процессор. Разработка системы команд процессора. Реализация модельного компилятора. Компиляция условных и безусловных переходов. Компиляция вызовов функций. Передача параметров функций через стек. Отображение результатов синтаксического разбора на другие архитектуры процессоров.

3. Базовые принципы функционирования вычислительных систем.
3.1. Общая архитектура вычислительной системы. Общая шина и ее составные части. Тактовый генератор и таймер. Интерфейсы внешних устройств и памяти. Адресное пространство. Процесс обмена данными с памятью и дисками. Арбитраж шины.

1


РАБОТА НА ЭВМ И ПРОГРАММИРОВАНИЕ. 3 семестр.

http://lib.math.msu.su

3.2. Общая архитектура процессора. Основные устройства (управления, очередь команд, регистры, интерфейс шины и пр.) Использование регистров, режимы адресации, разнообразные архитектуры и системы команд. Процесс обработки и выполнения команды в процессоре. 3.3. Основные принципы работы операционной системы. Система прерываний. Обработка сигнала прерывания процессором. 3.4. Управление памятью. Страничная организация виртуальной памяти. Структура таблицы страниц. Процесс преобразования виртуального адреса в реальный. Стратегии загрузки и замещения страниц. Кеш-память. Прямое отображение. Ассоциативное отображение. 3.5. Управление процессами. Диаграмма состояний процесса. Приоритеты. Статические приоритеты. Динамические очереди с приоритетами. 3.6. Тупики и критические секции. Обнаружение и предотвращение тупиков. Понятие о семафорах.

2