Задачи для экзамена
1. Задача Ады Лавлейса. Вычисление чисел Бернулли
Первая программа для вычислительной машины (машины Бэббеджа) была создана графиней Адой Лавлейс, дочерью поэта лорда Байрона. Ада Лавлейс по праву считается первым в мире программистом. В ее честь назван язык программирования «Ада». День ее рождения отмечается как день программиста. Программа, которую написала Ада Лавлейс, позволяла считать числа Бернулли, широкое применяемые в разных областях математики.
Якоб Бернулли, представитель славной семьи математиков и физиков, ввел понятие чисел Бернулли, изучая суммы степеней целых чисел. Вот формула, выведенная Якобом Бернулли:
Здесь 
- биномиальный коэффициент, а Bm – число Бернулли.
Биномиальный коэффициент задает число сочетаний k предметов, выбранных из n предметов, определяется как:
Рекуррентное соотношение
Числа Бернулли можно рассчитать, используя следующую рекуррентную формулу:
(1)
Свойства чисел Бернулли:
· B0 = 1;
· Все нечетные числа, за исключением B1 равны 0.
· Четные числа меняют знак.
· С ростом m числа Бернулли по модулю возрастают.
Вот как выглядит последовательность первых чисел Бернулли:
B0 = 1; B1 = -1/2; B2 = +1/6; B3 = 0; B4 = -1/30; B5 = 0; B6 = +1/42; B8 = -1/30; B10 = +5/66;
B12 = -691/2730; B14 = +7/6; B16 = -3617/510;
Сходящийся ряд
Значения модулей четных чисел Бернулли можно вычислять, используя соотношение, включающее быстро сходящийся ряд:
(2)
При таком определении последовательность чисел Бернулли выглядит следующим образом:
B1 = +1/6; B2 = 1/30; B3 = 1/42; B4 = 1/30; B5 = 5/66; B6 = 691/2730; B7 = 7/6; B8 = 3617/510;
Задание на программирование
Постройте проект, включающий два метода вычисления чисел Бернулли, используя соотношения (1) и (2). Постарайтесь построить оптимальную по времени реализацию методов.
Проведите сравнительный анализ эффективности методов по времени выполнения.
2. Задача «Точки на плоскости»
На плоскости задан выпуклый N-угольник – D и точка P. Определить является ли точка P внешней или внутренней (граничной) точкой многоугольника D.
Задание на программирование
Постройте Windows Form проект, дающий решение задачи. Постройте графический образ задачи.
На входе:
N + 1 точка. Первые N точек задают вершины многоугольника. Последняя точка – точка P, принадлежность которой внутренней области многоугольника проверяется.
На выходе:
Ответ и рисунок, иллюстрирующий корректность ответа.
Указание:
Можно использовать любой известный Вам алгоритм принадлежности точки выпуклому многоугольнику. Например, можно проверять, равна ли сумма площадей треугольников Ti площади многоугольника D. Треугольники Ti одной из вершин имеют точку P, две другие вершины – это вершины многоугольника с номерами i и i+1. Для внутренних точек равенство выполняется, для внешних – сумма площадей больше площади многоугольника.
3. Задача «Семейный банковский счет»
Семья может иметь единый банковский счет. Все члены семьи могут положить деньги на счет и снять деньги со счета при условии, что на счете имеется достаточная сумма. Операции над счетом могут выполняться независимо и одновременно.
Задание на программирование
Создайте класс Account, позволяющий выполнять операции со счетом. Постройте потокобезопасное решение, моделирующее работу со счетом членов семьи.
4. Задача «Банковский сейф»
Тема: Эффективный алгоритм
В банке города N появился новый сейф с кодовым замком. Код состоит из 2* m цифр. Для открытия сейфа необходимо, чтобы два исполнительных директора набрали свою половину кода из m цифр. Каждый директор независимо задает свой код. Единственное ограничение – сумма цифр кода каждого директора должна быть одинаковой. О значении этой суммы директора предварительно договариваются. Злоумышленники знают об этом ограничении и хотят подобрать нужный код путем перебора. Сколько времени понадобится злоумышленникам для полного перебора при заданном значении m? Ответ укажите в минутах с точностью до минуты. Учтите, что за минуту злоумышленники проверяют 10 комбинаций.
Напишите эффективную по времени программу, производящую этот подсчет.
Тестовый пример: m = 2; ответ: 67
5. Задача «Управление проектом»
Тема: Эффективный алгоритм
При управлении программным проектом часто используют такой инструмент, как восходящая диаграмма выполнения. Предположим, что мы можем оценить трудоемкость выполнения предстоящих работ в некоторых единицах. Пусть значение трудоемкости всей работы в целом равно N. Срок выполнения всех работ также известен и равен T. Ход выполнения работ можно представить в виде графика (восходящей диаграммы выполнения) с осью абсцисс, задающей время, и осью ординат, задающей объем выполненных работ. На этом графике прямая линия, соединяющая точку (0, 0) и точку (T, N), характеризует среднюю скорость выполнения работ. Отметки на графике реально выполненной работы позволяют судить о том, как идут дела. Точки под прямой свидетельствуют об отставании от «нормального» процесса выполнения. Точки над прямой свидетельствуют о превышении планов.
Подобные диаграммы встречаются при управлении различными производственными процессами.
Задание на программирование
Сформулируем задачу. Дана конечная точка (T, N) и последовательность текущих точек (Tk, Nk), где
k = 1, 2, … m; 0 < Tk-1 < Tk <= T; 0 < Nk-1 < = Nk <=N;
Требуется определить максимальный интервал успешного управления – интервал [Ti, Tj], на котором суммарное превышение работ максимально.
Тестовый пример: T = 20; N = 100: Tk = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
Nk ={8, 16, 35, 45, 60, 60, 66, 80, 95, 100}; ответ:[6, 20]
Тестовый пример: T = 20; N = 100: Tk = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
Nk ={8, 16, 35, 45, 60, 60, 64, 78, 92, 100}; ответ:[6, 10]
6. Задача о фонде «Скол»
Тема: Файлы и эффективный по времени и памяти алгоритм
В фонд «Скол» по поддержке малого бизнеса поступило N заявок на получение грантов. В каждой заявке указана требуемая сумма P для реализации проекта. Фонд располагает фиксированной суммой денег M, предназначенной для выдачи грантов. Цель фонда: Отобрать максимальное число проектов, не превосходящее L – верхней границы для числа отбираемых проектов.
Задание на программирование
Постройте решение, соответствующее цели фонда, с учетом следующих ограничений:
На входе:
Файл, содержащий 3N + 3 строки. В первой строке – сумма денег у фонда - M, во второй – верхняя граница числа отбираемых проектов –L, в третьей – число заявок–N. Далее идут 3N строк, по три строки на каждый проект - запрашиваемая сумма денег, ID – идентификационный номер и краткое описание проекта.
На выходе:
Файл, содержащий K + 2 строки. В первой строке K – число отобранных проектов, во второй – сумма потраченных фондом денег, далее следуют K строк с ID отобранных проектов.
Тестовый пример:
Входной файл:
1200; 3; 5
400; 1; все
350; 2; лучшее
300; 3; инновации
350; 4; нано
300; 5; Супер
Выходной файл:
3; 950
3; 5; 2
7. Задача «Сортируем отсортированное»
Тема: Сортировка и универсальные типы
В областной центр статистики из районных центров поступают отчеты. Данные отчетов сливаются в единый массив. Данные можно рассматривать как элементы структуры, содержащей два поля – поле ключа типа K и информационное поле типа T. Типы K и T могут меняться в зависимости от требуемых отчетов. Отчеты, поступающие из районов, упорядочены по полю ключа.
Задание на программирование:
Дан массив Report, содержащий k подряд идущих упорядоченных подпоследовательностей. Индекс начала каждой подпоследовательности – start[i] известен. Необходимо отсортировать массив Report по полю ключа путем слияния упорядоченных подпоследовательностей. Универсальная процедура слияния Merge<K, T> должна иметь параметры, задающие тип ключа и тип информационного поля элементов сортируемого массива.
8. Задача «Комплексные числа»
Тема: Построение класса
Во многих инженерных расчетах, в различных математических приложениях необходимо уметь работать с комплексными числами.
Задание на программирование
Создайте класс Complex_numbers, задающий тип данных – комплексные числа. Предусмотрите в этом классе возможность работы с комплексными числами в двух форматах:
z = x + i * y; z = r * ei*φ = r(cos φ + i * sin φ)
В классе должны быть предусмотрены арифметические операции над числами и операции сравнения на равенство. Класс должен допускать перегрузку знаков операций, обеспечивая возможность построения выражений над комплексными переменными, аналогично тому, как это делается для выражений с переменными арифметического типа.
Постройте решение, в котором этот класс используется для вычисления множества Мандельброта. Представьте графический образ построенного множества.
9. Задача «Полиномы»
Тема: Построение класса
Создайте класс Polinoms, задающий тип данных – полиномы.
В классе должны быть предусмотрены различные конструкторы, позволяющие задавать полином по точкам (полином Лагранжа), по корням полинома, по его коэффициентам. Должны быть предусмотрены операции над полиномами – сложение, вычитание, умножение, деление, вычисление значения полинома в заданной точке.
Постройте решение, в котором этот класс используется для работы с полиномами. Представьте графический образ используемых в решении полиномов.
10. Задача «Матрицы»
Тема: Построение класса
Создайте класс Matrix, задающий тип данных – матрицы.
В классе должны быть предусмотрены операции над матрицами – сложение, вычитание, возведение в степень (для квадратных матриц), умножение для прямоугольных матриц. Следует предусмотреть возможность выполнения этих операций в последовательном и параллельном варианте в зависимости от размера матриц.
Постройте решение, в котором этот класс используется для работы с матрицами.
11. Задача «Интерпретатор функций и Решатель уравнений»
Тема: Построение класса
Создайте классы Interpretator и Solver_Functions.
Класс Interpretator должен позволять вычислять значение функции, заданной аналитически – формулой, представленной строкой текста. Класс Solver должен позволять находить корни функции заданной аналитически.
Постройте решение, в котором эти классы используются для работы с функциями. Постройте графики этих функций.
12. Задача «Решатель систем линейных уравнений»
Тема: Построение класса
Создайте класс LinearSystem_Solver.
Класс должен позволять работать с матрицами, находить обратную матрицу, вычислять определитель, решать системы линейных уравнений. Постройте параллельные и последовательные версии методов класса.
Постройте решение, в котором этот класс используется для решения указанных задач.
13. Задача «Универсальный сортировщик»
Тема: Построение класса
Создайте класс UniversalSorter.
Класс UniversalSorter должен позволять сортировать записи, в которых поле ключа и информационное поле могут быть любого типа. На поле ключа накладывается естественное ограничение – тип должен допускать сравнение элементов,– быть потомком интерфейса IComparable. Включите в методы класса, по крайней мере, два метода сортировки – сортировку вставкой и быструю сортировку Хоара. Постройте последовательные и параллельные варианты этих методов.
Постройте решение, в котором этот класс используются для сортировки записей.
14. Задача «Требуется программист со знанием языка C#»
Программистская фирма «Шарп» объявила конкурс программистов для приема на работу. Каждый из претендентов должен заполнить подготовленную фирмой анкету. Анкета включает N бинарных свойств, таких, как например:
· Знает ли язык C#;
· Знает ли язык Python;
· Знает ли технологию ASP;
· Курит ли;
· Умеет ли работать в команде;
· Другие свойства.
Предполагается, что число вопросов в анкете N находится в интервале [20 – 50].
Задание на программирование
Создайте решение, позволяющее автоматизировать работу с анкетами и обработку запросов, поступающих от различных отделов фирмы. Каждый из отделов задает некоторый образец с указанием желательных и нежелательных свойств претендентов. Например, образец отдела «С» может включать знание С#, ASP, не курит, еще ряд свойств. Запросы на отбор претендентов могут быть такими, например, претендент обладает:
· теми и только теми свойствами, которые указаны в образце (идеальный претендент);
· всеми требуемыми положительными свойствами, но имеет нежелательные свойства;
· «k из n» положительных свойств;
· Другие аналогичные запросы.
Указание:
Постройте решение, основанное на работе со шкалами – перечислениями. Набор свойств задайте перечислением с атрибутом Flags. Запросы реализуйте, используя логические операции над объектами перечисления, содержательно задающих анкеты и образцы, представленные отделами.
15. Задача «Огни большого города»
В большом городе происходят самые разнообразные события. К сожалению, время от времени в городе происходят пожары. Сообщения о таких событиях поступают в городские службы – пожарную команду, милицию, скорую помощь, которые должным образом реагируют на событие.
Задание на программирование
Постройте решение, моделирующее в течение года возникновение пожаров в жизни города и то, как городские службы реагируют на это событие. Предполагается, что в городе N зданий, в каждом из которых в течение дня может возникнуть пожар с некоторой малой вероятностью p.
Указание:
Используйте механизм событий. Постройте класс, описывающий жизнь города и включающий событие «Пожар». Классы, описывающие городские службы, должны уметь получать уведомление о возникновении события и соответствующим образом обрабатывать это событие.
16. Задача «Фигуры, фигуры»
Как лепится снежная баба? Вначале создаем большой шар, потом сверху устанавливаем шар поменьше, затем еще один шар, добавляем нос морковкой, глазки, - получаем снежную бабу. Если мы умеем построить некоторые базисные графические примитивы, то из них можно построить сложную фигуру, используя такие операции над ними, как перемещение, масштабирование, окрашивание.
Задание на программирование
Создайте семейство классов, связанных отношением наследования. Классы этого семейства описывают геометрические фигуры - линии, дуги, эллипсы, окружности, прямоугольники, треугольники. Над этими объектами определены операции показа фигур на экране компьютера, их перемещение, масштабирование, окрашивание. Приложение должно позволять пользователю строить сложные фигуры из заданных примитивов.
Указание:
При построении семейства классов используйте механизм полиморфизма, включив, например, полиморфный метод Show – показа фигуры.
17. Задача «Управление процессами»
Постройте двух поточное приложение, позволяющее в интерактивном режиме управлять некоторыми процессами. В одном потоке должна работать бизнес – модель, в другом потоке – интерфейс, позволяющий управлять процессами бизнес- модели.
Например, постройте класс, моделирующий жизнь города, в котором происходят демографические процессы, процессы, отражающие активность бизнеса. В этом классе введите наблюдаемые и управляемые параметры для этих процессов. Наблюдаемые параметры модели должны быть доступны для показа в интерфейсе. Управляемые параметры должны позволять управлять текущими процессами в бизнес-модели.
18. Создать DLL с сервисным классом Matrix_SP для выполнения операций над матрицами - последовательными и параллельными алгоритмами.