Работа на ЭВМ и программирование




Скачать 46.4 Kb.
Дата 10.09.2016
Размер 46.4 Kb.
РАБОТА НА ЭВМ И ПРОГРАММИРОВАНИЕ

доц. В.Д. Валединский

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. Общая архитектура вычислительной системы. Общая шина и ее составные части. Тактовый генератор и таймер. Интерфейсы внешних устройств и памяти. Адресное пространство. Процесс обмена данными с памятью и дисками. Арбитраж шины.

3.2. Общая архитектура процессора. Основные устройства (управления, очередь команд. регистры, интерфейс шины и пр.) Использование регистров, режимы адресации, разнообразные архитектуры и системы команд. Процесс обработки и выполнения команды в процессоре.

3.3. Основные принципы работы операционной системы. Система прерываний. Обработка сигнала прерывания процессором.

3.4. Управление памятью. Страничная организация виртуальной памяти. Структура таблицы страниц. Процесс преобразования виртуального адреса в реальный. Стратегии загрузки и замещения страниц. Кеш-память. Прямое отображение. Ассоциативное отображение.

3.5. Управление процессами. Диаграмма состояний процесса. Приоритеты. Статические приоритеты. Динамические очереди с приоритетами.

3.6. Тупики и критические секции. Обнаружение и предотвращение тупиков. Понятие о семафорах.

Весенний семестр, 32 часа.

4. Программирование параллельных процессов.

4.1. Порожденные процессы и нити. Организация параллельной обработки данных порожденными процессами. Синхронизация процессов. Проблема использования общей памяти и обмена данными. Синхронизация параллельных процессов с помощью семафоров.



5. Компьютерные сети.

5.1. Базовые сетевые топологии. Понятие о сетях с коммутацией каналов и пакетов. Понятие протокола и уровня межсетевого взаимодействия. Модель OSI ISO. Модель TCP/IP. Струк­турные элементы локальных и глобальных сетей. Повторитель, разветвитель, мост, шлюз.

5.2. Логика функционирования сетей Token Ring. Токен. Адресация. Дисциплина передачи данных. Восстановление токена. Логика функционирования сетей Ethernet. Адресация. Дисциплина передачи данных. Разрешение коллизий.

5.3. IP адресация. Классы адресов. Широковещательные и другие специальные адреса. Маска подсети. Протоколы ARP и RARP, назначение, принципы работы. Протокол IP, назначение, принципы работы. Функции IP протокола, фрагментация и сборка. Уничтожение пакетов. Маршрутизация. Расширения и отличия IPv6.

5.4. Протокол UDP, назначение, принципы работы. Адресация транспортного уровня. Контроль правильности передачи. Протокол TCP, назначение, принципы работы. Обеспечение надежности передачи. Сегментация данных при отправлении и сборка при получении. Процедуры установления и разрыва соединения. Механизм подтверждений. Таймеры.

5.5. Протокол и система DNS, назначение, принципы работы. Структура доменных имен. Классификация DNS серверов. Формат запроса и ответа. Ресурсная запись. Итеративная, рекурсивная и смешанная процедуры. Поддержка распределенной базы данных DNS.

5.6. Протокол FTP, назначение, принципы работы. Вид запроса и отклика. Процесс передачи файлов. Классификация кодов откликов.

5.7. Протокол HTTP, назначение, принципы работы. Формат запроса и отклика. Процесс передачи файлов. Структура и назначение строк-заголовков (header-lines). Виды соединений. Отличие HTTP/1.0 и HTTP/1.1. Классификация кодов откликов.

5.8. Программирование сетевых взаимодействий. Технология клиент-сервер. Socket-интерфейс. Основные функции и их назначение. Построение модельных TCP и UDP клиента и сервера.

6. Компьютеризация представления данных и информации.

6.1. Язык HTML. Основные концепции и теги. Управление формой представления данных. Организация гиперссылок. Управление реакцией на события. Базовые концепции языка Javascript. Каскадные таблицы стилей CSS.



6.2. Представление документов при помощи языка XML. Общие концепции языка XML. Пространства имен. Определение типа документа. Корректные и состоятельные документы. Преобразования XML-документов. Язык описания преобразований XSLT. Основные концепции и конструкции, XPath выражения. Примеры простейших преобразований и выборок.

6.3. Язык TeX как средство подготовки математических публикаций. Общая структура документа. Основные команды форматирования текста и набора математических формул.


База данных защищена авторским правом ©infoeto.ru 2022
обратиться к администрации
Как написать курсовую работу | Как написать хороший реферат
    Главная страница