Программа экзамена по программированию для потока фит, осваивающего образовательную программу бакалавра по направлению Информатика и вычислительная техника в сокращенные сроки

Вид материала

Программа

Содержание Оценка сложности вычислительных алгоритмов Список литературы Структура экзаменационного билета. Список вопросов

Подобный материал:

• Образовательный стандарт по направлению 552800 «Информатика и вычислительная техника», 166.41kb.
• Программа государственного экзамена по направлению 230100 «Информатика и вычислительная, 60.5kb.
• Рабочая учебная программа по дисциплине «Информатика» Направление №230100 «Информатика, 91.73kb.
• Образовательный стандарт по направлению 552800 «Информатика и вычислительная техника», 168.8kb.
• Образовательный стандарт по направлению бакалавриата 552800 (230100) «Информатика, 288.84kb.
• Образовательный стандарт по направлению бакалавриата 552800 (230100) «Информатика, 198.39kb.
• Образовательный стандарт По направлению 552800 «Информатика и вычислительная техника», 114.27kb.
• Образовательный стандарт по направлению 552800 «Информатика и вычислительная техника», 199.12kb.
• Образовательный стандарт по направлению 230100. 62 Информатика и вычислительная техника, 328.94kb.
• Рабочая программа дисциплины «Компьютерная графика» по направлению подготовки дипломированного, 108.6kb.

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ


ФАКУЛЬТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ


Программа экзамена по ПРОГРАММИРОВАНИЮ для потока ФИТ, осваивающего образовательную программу бакалавра по направлению Информатика и вычислительная техника в сокращенные сроки


В программе представлены основные темы, содержание тем, список рекомендуемой литературы, структура экзаменационного билета, список вопросов для экзаменационных билетов


Тематический план

РАЗДЕЛ 1. Основы программирования. Базовые алгоритмы и структуры данных.

1. Представление информации в ЭВМ
   
2. Элементы комбинаторики
   
3. Задачи поиска и сортировки
   
4. Оценка сложности вычислительных алгоритмов
   
5. Динамические структуры данных
   

РАЗДЕЛ 2. Практика программирования – методы и инструменты

6. Методы решения задач на абстрактных структурах данных
   
7. Язык программирования высокого уровня (Си)
   
8. Динамическое программирование
   

РАЗДЕЛ 3. Основы технологии разработки программ.

9. Организация процесса разработки программ. Базовые элементы технологии программирования.
   

Содержание разделов и тем


РАЗДЕЛ 1. Основы программирования. Базовые алгоритмы и структуры данных.

1. Представление информации в ЭВМ
   
   1. Общие методы решения вычислительных задач.
      

• Итерационный метод: множество перебираемых значений с произвольно задаваемым порядком; операция генерации "следующего по порядку"; перебор от "минимального" к "максимальному" по всем.
  
• Метод "разделяй и властвуй": разбиение задачи на несколько подзадач меньшего размера; для задач тривиального размера строится тривиальное решение.
  
• Рекурсия как общий метод сведения задачи к самой себе. Примеры рекурсивных формул, данных, алгоритмов. Правила задания рекурсии: рекурсивный переход, условия выхода. Преобразование хвостовой рекурсии в итерацию (простой цикл). Ветвящаяся рекурсия (на примере алгоритмов, строящих древовидные процессы решений).
  
• Рекурсивное определение чисел Фибоначчи. Факториал. Рекурсивное и итеративное вычисление факториала. Характер роста факториала, как функции n.
  

2. Элементы теории чисел
   

• Алгоритмы вычисления последовательности простых чисел: прямой перебор с проверкой делимости, решето Эратосфена; приемы их ускорения.
  
• Принцип однозначности разложения числа на простые множители.
  

3. Системы счисления (с.с.).
   

• Запись чисел цифрами и числовые значения. С.с. как система правил записи чисел.
  
• Правила записи значений целых и действительных чисел в позиционных с.с. по основанию b (b-с.с.).
  
• Функции перевода "число-запись" и "запись-число" и алгоритмы их вычисления для произвольной b-с.с. Вычисления по схеме Горнера с минимальным числом операций.
  
• Алгоритмы перевода целых чисел из одной b-с.с. в другую:
  
• из произвольной b-c.с. в 10-с.с.;
  
• из 10-с.с. в произвольную b-с.с.;
  
• из произвольной b1-с.с в произвольную b2-с.с.;
  
• между кратными с.с.
  
• Модификации этих алгоритмов для перевода действительных чисел.
  
• Кратные с.с. Приемы использования кратных с.с. для ускорения перевода чисел между произвольными b-с.с.
  
• Универсальные алгоритмы вычисления арифметических операций для произвольных b-с.с.
  
• Достаточное условие конечности представления рациональной дроби в произвольной b-с.с.
  
• Понятие символьных вычислений. Формальное определение вычислений как преобразование цепочек символов по заданным правилам (на примере определения арифметических операций таблицами значений). Базовые операции символьных вычислений (выборка, идентификация, сравнение и подстановка).
  

4. Модели машинной арифметики с конечной разрядностью.
   

• Модель машинной памяти как однородного линейно-адресуемого массива ячеек фиксированной разрядности. Влияние разрядности шин адреса и данных на размеры машинного слова и адресуемой памяти.
  
• Понятие разрядной сетки; ее модель (линейно индексируемый массив цифр) и характеризующие параметры (разрядность и формат).
  
• Особенности представления чисел и арифметики в конечной разрядной сетке:
  
• ограничения ширины представимого интервала чисел;
  
• ограничения точности представления (для действительных чисел).
  
• Модель целых чисел конечной разрядности: вычеты (классы чисел, сравнимых по модулю). Арифметика вычетов. Понятие переполнения.
  
• Модель действительных чисел конечной точности: интервалы (классы чисел, сравнимых с заданной точностью). Арифметика интервалов. Понятие погрешности (потери точности). Накопление погрешности при вычислениях.
  
• Модель беззнаковых целых чисел конечной разрядности. Формулы для min и max.
  
• Модель целых чисел со знаком. Знаковый разряд. Формулы для min и max. Несимметричность представляемого диапазона.
  
• Проблемы выбора представления для отрицательного диапазона (сужение интервала, два нуля, усложнение операций). Правила представления чисел и арифметика в дополнительном коде.
  
• Единообразие правил знаковой и беззнаковой арифметики. Примеры, иллюстрирующие зависимость результатов вычислений только от способа интерпретации представлений.
  
• Модель вещественной арифметики с фиксированной точкой (равномерная точность представления). Формулы для max и точности. Арифметика с фиксированной точкой: сведение к целочисленной арифметике со сдвигом. Округление, как способ повышения точности.
  
• Модель вещественной арифметики с плавающей точкой (неравномерная точность представления).
  
• Экспоненциальное (нормализованное, с плавающей точкой) представление вещественного числа. Мантисса и порядок, их вид. Нормализация. Особенности арифметики с плавающей точкой:
  

• денормализация аргументов при сложении;
  
• нормализация результата;
  
• расширение разрядной сетки при денормализации и округлении.
  

• Представление вещественного числа в нормализованной форме как пары целых. Разрядность мантиссы и порядка. Формулы для max, E1 (минимальное ненулевое число, абсолютная точность), E2 (относительная точность).
  
• Источники погрешности при арифметике с плавающей точкой:
  

• бесконечность представления числа в данной с.с.;
  
• потеря точности при денормализации меньшего аргумента;
  
• потеря точности при округлении;
  
• потеря точности при записи результата в память;
  
• потеря точности при переводе в с.с., используемую для вывода.
  

• Параметры, характеризующие модели представления чисел в используемых вычислительных средствах. Характеристики числовых типов в Паскале и Си для процессоров Intel (integer, word, real, double и др.)
  
• Умножение длинных целых чисел по методу "разделяй и властвуй".
  

2. Элементы комбинаторики
   

• Перестановки набора. Подсчет числа перестановок.
  
• Наборы, упорядоченные заданной операцией порядкового сравнения. Перестановки. Инверсии. Число инверсий, как мера сложности упорядочения набора.
  
• Таблицы инверсий. Алгоритм восстановления перестановки по таблице инверсий. Таблица инверсий как число в особой с.с. Итерационный алгоритм генерации всех таблиц инверсий.
  
• Алгоритмы перебора перестановок:
  

• рекурсивный,
  
• итерационный через перебор таблиц инверсий,
  
• итерационный (Дейкстры) с лексикографическим упорядочением.
  

• Применение итерационного метода к задаче перебора всех подмножеств из заданного набора.
  

3. Задачи поиска и сортировки
   
   1. Постановка задач П/С записей в произвольном наборе данных. Формализация: ключи как абстракции записей; требования к ключам (сравнимость по заданной порядковой функции); внешняя и внутренняя постановка задачи П/С (при не/доступности всего набора). *Простые и мульти-ключи. Сведение лексикографических (словарных) П/С по мультиключу к П/С по простому ключу с помощью функции сравнения.
      
   2. Методы простого поиска в массиве:
      

• линейный поиск,
  
• бинарный поиск.
  

Оценки сложности (min, max, ave).

3. Методы поиска подстроки в строке:
   

• алгоритм прямого перебора,
  
• алгоритм Бойера-Мура.
  

Оценки сложности в среднем.

4. Метод совместного поиска min и max в массиве по методу "разделяй и властвуй".
   
5. Методы сортировки массива:
   

• метод простого подсчета для различных чисел;
  
• метод простых вставок;
  
• метод бинарных вставок;
  
• метод двухпутевых вставок;
  
• метод Шелла;
  
• метод простого выбора;
  
• метод "пузырька";
  
• шейкер-сортировка;
  
• быстрая сортировка Хоара;
  
• пирамидальная сортировка;
  
• сортировка слиянием;
  
• сортировка распределением.
  

Оценки сложности (min, max, ave) с примерами входных данных.

Нижняя оценка сложности сортировки с помощью попарных сравнений.

6. Сортировка файлов методом двухпутевого слияния
   

Файлы в Си:

• Классификация, способы представления информации, описание.
  
• Дисциплина и средства работы, буферизация.
  
• Файлы прямого и последовательного доступа.
  

7. Сравнительный анализ эффективности алгоритмов сортировки и причин, влияющих на нее. Достоинства организации исходного набора в виде древовидной структуры для совместного решения задач П/С.
   

4. Оценка сложности вычислительных алгоритмов
   

• Понятие вычислительного процесса, как дискретной последовательности состояний памяти вычислителя. Функции перехода. Представление о программе как о преобразователе, задающем семейство исполнений (процессов преобразования входных данных в выходные), управляемом входными данными.
  
• Размер задачи как характеристика объема входных данных. Параметры, влияющие на размер задачи.
  
• Временная и емкостная сложность программы как функции размера задачи. Верхняя, нижняя и средняя оценки. Асимптотическая оценка, как поведение "в общем случае".
  
• Классы вычислительной сложности алгоритмов: примеры задач, допускающих решение за логарифмическое, линейное, квадратичное, полиномиальное, экспоненциальное время. Нижние и верхние оценки для изученных классов задач (генерация перестановок, поиск, сортировка).
  
• Практические приемы оценки вычислительной сложности алгоритмов:
  
• изучение структуры и глубины циклов и рекурсии в программе;
  
• формальный анализ входных данных и количества операций.
  

5. Динамические структуры данных
   
   1. Динамическая память
      

• Способы распределения памяти (не включая динамику): статический, автоматический. Какие виды констант, переменных и параметров в Паскале и СИ распределяются данными способами.
  
• Статическое и динамическое распределение памяти: отличия по способу описания переменных, времени создания, способу и дисциплине доступа.
  
• Куча. Реализация кучи в Паскале. Администратор кучи. Основные процедуры и функции.
  
• Способы доступа к данным: прямой, последовательный, индексная и косвенная разновидности.
  
• Буферизация как прием совмещения различных способов доступа к данным, примеры ее использования.
  
• Указатели, как средство организации данных с динамической структурой; средства работы с ними в Си.
  
• Использование приведений указательных типов для описания неоднородных структур.
  

2. Классические модели динамической памяти
   

• Список.
  
• Стек. Преобразование инфиксной формы записи выражения в постфиксную и вычисление значения полученного выражения.
  
• Очередь. Реализация ширинного обхода дерева.
  
• Дек.
  
• Основные операции.
  
• Способы реализации на различных базовых представлениях.
  

РАЗДЕЛ 2. Практика программирования – методы и инструменты

6. Методы решения задач на абстрактных структурах данных
   
   1. Абстрактные структуры данных.
      

• Абстрагирование.
  
  • Абстрагирование как прием построения модели данных задачи.
    
  • Некоторые приемы абстрагирования: разбиение данных на компоненты, анализ свойств однородности, статичности, способов доступа, числовое кодирование.
    

• Списки.
  
  • Список, как универсальная модель линейно упорядоченных структур данных последовательного доступа.
    
  • Разновидности списков: статические, динамические, одно/двусвязные, циклические, упорядоченные, иерархические.
    
  • Операции над списками.
    
  • Алгоритмы поиска и включения для списков, анализ их эффективности.
    
  • Способы реализации списков (статика, динамика).
    
  • Реализация алгоритма топологической сортировки на иерархических списках
    

• Графы.
  
  • Граф как наиболее общая модель данных последовательного доступа.
    
  • Пути и маршруты по графу.
    
  • Определения различных типов графов: (не)ориентированного,
    
  • (а)циклического, много/односязного.
    
  • Представление графа, как отношения на множестве вершин.
    
  • Модели представления в ЭВМ.
    
  • Mатрицы смежности, инцидентности.
    
  • Динамическая структура со списками дуг. Табличное представление.
    
  • Помеченные графы.
    

• Деревья.
  
  • Дерево, как частный вид графа.
    
  • Эквивалентные определения дерева характеристическими свойствами.
    
  • Терминология для деревьев: отец, сын, корень, лист, глубина и др.
    
  • Классические типы деревьев: корневые, бинарные, упорядоченные, уравновешенные.
    
  • Деревья двоичного поиска. Создания орфографического словаря по заданному набору слов.
    
  • Инфиксное, префиксное и постфиксное кодирование деревьев.
    
  • Левое\правое скобочное представление деревьев.
    
  • Специальные представления однородных деревьев в ЭВМ.
    
  • Пример повышения эффективности поиска и сортировки выбором структуры организации данных:
    
  • Деревья поиска, алгоритмы поиска.
    
  • Алгоритмы включения и удаления.
    
  • Сравнение их эффективности с известными алгоритмами на массивах.
    

1. Алгоритмы перебора на абстрактных динамических структурах.
   

• Способы перебора. Итерационный, полный, с отсечением. Примеры.
  
• Классические задачи на графах: транзитивное замыкание, задача коммивояжера (размеченные дуги), раскраска графа (размеченные вершины). Задачи, сводимые к данным алгоритмам.
  
• Классические задачи с отсечением: задача о рюкзаке, об устойчивых браках.
  
• Алгоритмы с возвратом — обход шахматной доски конем.
  
• Классические задачи на деревьях: обработка арифметических выражений, * перебор вариантов в алгоритмах игровых стратегий.
  
• Методы решения задач на графах и деревьях. Метод разметки. Метод волны. Метод замазывания тупиков в лабиринтах.
  
• Понятие полного перебора путей, его особенности для деревьев и графов общего вида.
  
• Обходы деревьев (в ширину, в глубину, в пре/пост/инфиксном порядке, слева направо).
  
• Обход всех вершин графа — метод поиска в глубину.
  
• Алгоритмы поиска компонент связности в графе и точек сочленения.
  
• Эйлеров граф. Способ определения Эйлерова цикла. Задачи, сводимые к Эйлеровым циклам.
  
• Рекурсивная реализация, связь стратегии обхода со способом организации рекурсии, стековая реализация, нерекурсивная реализация с пометкой пройденных путей.
  
• Решение классических задач перебора с помощью перебора перестановок вершин в путях.
  
• Алгоритмы генерации перестановок: рекурсивный, итерационный.
  
• Анализ эффективности алгоритмов перебора: экспоненциальная оценка временной сложности.
  

7. Язык программирования высокого уровня (Си)
   

• Препроцессор Си: include, define.
  
• Основные структуры данных. Основные управляющие конструкции языка.
  
• Программа как набор функций, функция main(). Основные типы данных, объявление глобальных и локальных переменных. Функции в Си, способы передачи параметров.
  
• Выражения, оператор присваивания. Включение заголовочных файлов, вывод текста на экран функцией printf(). Основные инструкции: if, for, while, do while. Возврат значения из функции (return).
  
• Работа с одномерными массивами. Массивы и строки в Си
  

8. Динамическое программирование
   

• Динамическое программирование как решение задач с помощью табличной техники.
  
• Задачи об умножении матриц, о преобразовании строки, о расстановке скобок в выражении.
  

РАЗДЕЛ 3. Основы технологии разработки программ

9. Процесс разработки программ. Базовые элементы технологии программирования
   

• Программа как объект труда. Типизация Фокса. Абстрактный характер. Проблема корректности. Эффект большого масштаба (три признака сложности).
  
• Признаки сложности создания программных изделий по Кауфману. Технологический разрыв. Семантический разрыв. Незнание реального мира.
  
• Жизненный цикл программного обеспечения (ЖЦПО). Модели ЖЦПО. Достоинства и недостатки моделей водопада/каскадной, итерационной, спиральной. Условия применения моделей ЖЦПО.
  
• Эксплуатация программного обеспечения. Кривая Лемана и экспоненциальный рост сложности программы. Валидация и верификация программной системы.
  
• Определение требований пользователя к программному изделию. Типы требований (функциональные, надежность, программно-аппаратная платформа, совместимость с другими программами, переносимость, интерфейс пользователя и пр.). Примеры требований.
  
• Спецификация требований пользователя. Примеры. Правила предотвращения ошибок при проектировании интерфейса пользователя.
  

СПИСОК ЛИТЕРАТУРЫ


Основная литература

1. В.А.Цикоза, Т.Г.Чурина. Методическое пособие к курсу “Методы программирования” (часть первая). Новосибирск: ВКИ НГУ, 1999.
   
2. Т.В.Нестеренко Методическое пособие к курсу «Методы программирование» часть 1 . Лабораторные работы. Новосибирск: ВКИ НГУ, 2008
   
3. Вирт Н. Алгоритмы и структуры данных. М.:Мир, 1989.-360с.
   
4. Дейкстра Э. Дисциплина программирования. М, 1978.
   
5. Дал У.,Дейкстра Э., Хорр К. Структурное программирование. М.:Мир, 1975.
   
6. А.Ахо, Д.Хопкрофт, Д. Ульман. Структуры данных и алгоритмы. М.: Издательский дом “Вильямс”, 2000.
   
7. В.В. Подбельский, С.С. Фомин. Программирование на языке Си. Москва: Финансы и статистика, 2007.-600 с.
   
8. Т.А. Павловская. С/С++ Программирование на языке высокого уровня – Спб.:Питер, 2005.-461 с.
   
9. Фокс Дж. Программное обеспечение и его разработка. М.: Мир, 1985. – 359 с.
   
10. Боэм Б. Инженерное проектирование программного обеспечения. М.: Радио и связь, 1985. – 512 с.
    

Дополнительная литература

1. А.Ахо, Д.Хопкрофт, Д. Ульман. Построение и анализ вычислительных алгоритмов. М.:Мир, 1979.
   
2. Вирт Н. Алгоритмы + Структуры Данных = Программы. М, 1985.
   
3. Кнут Д. Искусство Программирования для ЭВМ. Т.3. Сортировка и Поиск. М, 1978.
   
4. Кнут Д. Искусство Программирования для ЭВМ. Т.1. Основные алгоритмы. М, 1978.
   
5. Кормен Т., Лейзерсон Ч. ,Ривест Р. Алгоритмы: Построение и анализ (пер. с англ. под ред. Шеня А. ) - 960 с. {Классические учебники: Computer science} ISBN 5-900916-37-5 ~90. 04. 01/166, М: МЦНМО 01-99
   
6. Хэзфилд Р. , Кирби Л. Искусство программирования на C: Фундаментальные алгоритмы, структуры данных и примеры приложений (пер. с англ. ) - 736 с. {Энциклопедия программиста} ISBN 966-7393-82-8/0-672-31896-2 ~91. 07. 24/014. К: ДиаСофт 2001.-736 с.
   
7. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. М.: Изд-во Бином, СПб.: Невский диалект, 1999. – 560 с.
   
8. Бадд Т. Объектно-ориентированное программирование в действии. СПб.: Питер, 1997. – 464 с.
   

СТРУКТУРА ЭКЗАМЕНАЦИОННОГО БИЛЕТА.

Экзаменационный билет состоит из трех теоретических вопросов. Первый вопрос из Раздела 1 (см. выше содержание программы). Второй вопрос из Раздела 2. Третий вопрос из раздела 3.


СПИСОК ВОПРОСОВ ДЛЯ ЭКЗАМЕНА

РАЗДЕЛ 1. Основы программирования. Базовые алгоритмы и структуры данных

1. Число и запись числа. Система счисления как система правил записи чисел. Правила записи значений целых и действительных чисел в позиционных системах счисления по основанию b (b-с.с.).
   
2. Функции перевода "число-запись" и "запись-число" и алгоритмы их вычисления для произвольной системы счисления для целых чисел. Вычисления по схеме Горнера с минимальным числом операций
   
3. Алгоритм перевода "запись-запись" для вещественных чисел Конечность записи вещественного числа
   
4. Кратные системы счисления.
   
5. Универсальные алгоритмы для арифметических операций в произвольной системе счисления
   
6. Особенности умножения и деления на основание системы счисления. Особенности двоичной арифметики.
   
7. Машинная память как однородный линейно-адресуемый массив ячеек фиксированной разрядности. Понятие разрядности и формата числа.
   
8. Проблема представления произвольного действительного числа в ЭВМ. Модель действительных чисел конечной точности: интервалы (классы чисел, сравнимых с заданной точностью). Арифметика интервалов. Понятие погрешности (потери точности).
   
9. Представление целых чисел без знака в ЭВМ. Арифметика по модулю.
   
10. Модель целых чисел со знаком. Знаковый разряд. Формулы для минимальных и максимальных чисел.
    
11. Проблемы выбора представления для отрицательного диапазона. Правила представления чисел и арифметика в дополнительном коде. Единообразие правил знаковой и беззнаковой арифметики.
    
12. Выполнение арифметических операций в разрядной сетке. Перенос и переполнение.
    
13. Представление вещественных чисел в ЭВМ. Типы погрешностей, связанные с конечным представлением. Правила сравнения вещественных чисел. Минимальное и максимальное числа.
    
14. Модель вещественной арифметики с фиксированной точкой (равномерная точность представления). Формулы для максимального числа и точности.
    
15. Нормализованное ("с плавающей точкой") представление вещественного числа. Мантисса и порядок, их вид.
    
16. Модели представления чисел в ЭВМ и типы данных в языках программирования. Соотношение между ними.
    
17. Перестановки. Инверсии. Инверсионный алгоритм перебора перестановок
    
18. Перестановки. Инверсии. Алгоритм Дейкстры генерации перестановок (по алфавиту).
    
19. Перестановки. Инверсии. Алгоритмы Кнута генерации перестановок.
    
20. Перестановки. Инверсии. Рекурсивный алгоритм перебора перестановок
    
21. Прямой и бинарный поиск в массиве. Анализ и сравнение эффективности.
    
22. Алгоритмы поиска подстроки в строке: прямой и Бойера-Мура. Сравнительный анализ.
    
23. Общая постановка задачи сортировки. Параметры оценки эффективности алгоритмов сортировки. Наилучшие и наихудшие оценки их эффективности
    
24. Методы сортировки вставками: простыми, бинарными, метод Шелла. Оценки эффективности.
    
25. Методы сортировки обменом. “Пузырек” и "Шейкер" сортировка. Быстрая сортировка.
    
26. Сортировка выбором: простая и пирамидальная.
    
27. Сравнительный анализ эффективности методов сортировки
    
28. Методы сортировки слиянием.
    
29. Методы сортировки файлов.
    
30. Рекурсия как общий метод сведения задачи к самой себе. Примеры рекурсивных формул, данных, алгоритмов. Правила задания рекурсии: рекурсивный переход, условия выхода.
    
31. Факториал. Рекурсивное и итеративное вычисление факториала.
    
32. Алгоритмы генерации простых чисел. Их сравнительный анализ.
    
33. Типы данных в языках программирования, назначение, классификация, стандартные операции.
    
34. Структурные типы данных в языке программирования Си.
    
35. Области существования данных, связанные с программой и процедурами. Правила видимости имен из разных областей.
    
36. Процедуры и функции: назначение, различия, правила описания, вызова, локализации переменных, способы передачи параметров и результатов.
    
37. Файл: классификация по структуре и способу доступа, способы описания, операции. Дисциплина работы с файлами.
    
38. Представление массивов и структур в памяти ЭВМ. Вычисление адресов элементов.
    
39. Сложность вычислительных алгоритмов. Методы оценки сложности.
    
40. Классификация алгоритмов по сложности.
    
41. Метод динамического программирования на примере решения одной из задач.
    
42. Модели представления чисел в ЭВМ и типы данных в языках программирования. Соотношение между ними.
    
43. Статическое и динамическое распределение памяти. Способы доступа к данным (прямой, последовательный, индексный, косвенный). Работа с динамической памятью в Си.
    
44. Динамические типы данных в языках программирования: организация, описание, доступ. Указатели.
    

РАЗДЕЛ 2. Практика программирования – методы и инструменты

45. Разновидности списков: статические, динамические, одно/двусвязные, циклические, упорядоченные, иерархические. Операции над списками.
    
46. Алгоритмы поиска и включения для списков, анализ их эффективности.
    
47. Классические модели динамических структур данных: стек, очередь, дек. Основные операции, способы реализации. Примеры применения.
    
48. Алгоритм перевода выражения из инфиксной формы в постфиксную. Вычисления на стеке.
    
49. Граф как форма представления отношения. Типы графов. Смежность и инцидентность. Пути и маршруты
    
50. Представление графов в ЭВМ. Матрицы смежности, инцидентности. Динамическая структура со списками дуг. Табличное представление. Сравнение различных способов представления
    
51. Поиск пути по графу. Алгоритм транзитивного замыкания, его эффективность.
    
52. Топологическая сортировка. Реализация с помощью иерархических списков.
    
53. Топологическая сортировка. Реализация с помощью матрицы смежности.
    
54. Топологическая сортировка. Реализация методом поиска в глубину.
    
55. Алгоритм Дейкстры поиска минимального пути от одного источника.
    
56. Поиск всех минимальных путей в графе. Алгоритм Флойда.
    
57. Дерево как частный вид ациклического графа. Основные определения.
    
58. Классификация обходов деревьев. Инфиксный, префиксный и постфиксный порядки обхода деревьев. Рекурсивная реализация.
    
59. Обход дерева в ширину. Реализация с помощью очереди.
    
60. Классические задачи на деревьях: обработка арифметических выражений, связь с обходом деревьев.
    
61. Левое/правое скобочное представление деревьев
    
62. Деревья двоичного поиска: назначение, представление, алгоритмы вставки и поиска элементов, оценки их эффективности.
    
63. Бинарный поиск по массиву и дереву. Условие осуществимости. Сортировка включением в дерево бинарного поиска.
    
64. Сбалансированные деревья поиска. Алгоритм включения в сбалансированное дерево двоичного поиска.
    
65. Обходы графа. Обход всех вершин графа методом поиска в глубину.
    
66. Каркас графа (остовное дерево). Построение каркаса методом поиска в глубину.
    
67. Помеченные графы и их каркас. Задача и алгоритмы построения минимального каркаса.
    
68. Двусвязность. Алгоритм поиска в графе двусвязных компонент и точек сочленения.
    
69. Классические переборные задачи. Коммивояжер, рюкзак, устойчивые бракосочетания. Способы их решения (обзорно).
    
70. Классические переборные задачи. Задача коммивояжера.
    
71. Алгоритмы с возвратом — обход шахматной доски конем.
    
72. Алгоритмы с возвратом — задача о ферзях.
    
73. Нахождение оптимальной выборки. Задача о рюкзаке.
    
74. Задача об устойчивых браках.
    
75. Задача о раскраске графа (раскраска вершин). Примеры эвристического и переборного алгоритмов решения. Примеры задач, сводимых к раскраске.
    
76. Задачи о лабиринтах. Сведение их к модельным задачам на графах.
    
77. Эйлеров граф. Способ определения Эйлерова цикла. Задачи, сводимые к Эйлеровым циклам.
    
78. Гамильтоновы циклы. Поиск всех гамильтоновых циклов в графе. Задачи, сводимые к гамильтоновым циклам.
    
79. Виды операторов цикла в языке программирования Си.
    
80. Работа со строками в Си.
    

РАЗДЕЛ 3. Основы технологии разработки программ

81. Специфика программного изделия как объекта туда. Признаки сложности программ и процесса их разработки по Фоксу.
    
82. Кривая Лемана – причины экспоненциального роста сложности программы при эксплуатации, меры борьбы с ростом сложности.
    
83. Проблемы организации процесса разработки программ. Подходы к их решению. Три источника этих проблем по Кауфману.
    
84. Модели жизненного цикла программного обеспечения (ЖЦПО). Краткая характеристика моделей водопада, каскадной, спиральной, итерационной.
    
85. Условия применимости модели водопада.
    
86. Условия применимости спиральной модели.
    
87. Условия применимости итерационной модели.
    
88. Типы требований к программной системе.
    
89. Примеры спецификации требований к программной системе.
    
90. Примеры защитного программирования. Правила предотвращения ошибок при внешней спецификации программы.
    
91. Валидация и верификация программ.