Таврійський національний університет ім. В. І. Вернадського

“Затверджую”

Проректор з навчальної роботи

_________________ Тимохін О.М.

МОДУЛЬНИЙ КОНТРОЛЬ

Програмування

_________________________________________________________________________________

Факультет математики і інформатики

Кафедра застосовної математики

Мета та завдання дисципліни, її місце в навчальному процесі: Вивчення принципів розробки сучасного програмного забезпечення, розвиток алгоритмічного мислення. Освоєння та аналіз існуючих алгоритмів розв`язання прикладних задач; освоєння та реалізація обчислювальних схем алгоритмів; освоєння методів оцінки ефективності розроблених алгоритмів; освоєння сучасних мов програмування та засобів розробки ПЗ

Студент повинен знати: Основні базові алгоритми, що використовуються при розробці алгоритмів розв’язку задач за допомогою ЕОМ

Студент повинен вміти: Розробляти програми розв’язку задач з застосуванням отриманих знань.

Робоча програма складена

Робоча програма затверджена на засіданні кафедри прикладної математики, протокол №2_

«_15__» _09_____2010 р. Зав. кафедрою Чехов В.М.________________

Схвалено методичною комісією _____________________ ФМИ_ ______________________

(протокол № 2 від 20 ____ 10 _____ 2010 р.

Голова __ _ _ Старков

Модульный контроль № 1 (семестр 1)

Неймановская архитектура ЭВМ

· Понятие об архитектуре ЭВМ.

· Неймановская архитектура ЭВМ. Устройство ввода-вывода. Запоминающее устройство. Устройство управления. Арифметико-логическое устройство.

· Прерывания, защита памяти, управление памятью. Мультизадачный и мультипрограммный режимы.

Алгоритмы и их основные свойства.

· Понятие об алгоритме.

· Свойства алгоритмов

· Алгоритмы вычислительные, информационные, управляющие.

· Способы описания алгоритмов.

· Блок-схемы.

· Пример записи алгоритма в виде блок-схемы.

Разработка алгоритмов.

Алгоритмические языки. Типы величин.

· Понятие об алгоритмическом языке С.

· Алфавит языка. Синтаксис и семантика языка программирования.

· Синтаксические диаграммы.

· Основные типы величин. Целый, действительный, булевский и символьный типы.

Выражения языка С. Операторы языка С.

· Характеристика языка С.

· Алфавит С.

· Служебные слова.

· Идентификаторы. Изображения. Знаки операций. Разделители.

· Структура программы. Метки, константы, переменные, подпрограммы-функции.

· Система типов языка С.

· Оператор присваивания.

· Оператор процедуры.

· Простейший ввод-вывод.

· Оператор перехода.

· Составной оператор.

· Условный оператор. Оператор варианта switch.

· Операторы цикла.

Программы, основанные на рекуррентных соотношениях. Некоторые простые программы и алгоритмы.

· Конструкция while(cond)op;

· Вычисление НОД

· Вычисление факториала целого числа.

· Вычисление рядов.

Массивы: определение, описание. Простейшие алгоритмы работы с массивами:

· ввод- вывод массивов

· суммирование

· поиск наибольшего (наименьшего) элемента в массиве

· алгоритмы поиска в массиве;

· алгоритмы обработки матриц: нормы матриц, след матрицы, транспонирование матриц; сложение и умножение матриц, умножение вектора на матрицу;

· включение и исключение элементов массива

· преобразование матрицы в одномерный массив.

Модульный контроль №2(семестр 1)

Обработка символьных данных. Библиотечные средства символьной обработки.

· Данные типа строка литер.

· Стандартные и функции для работы со строками.

Комбинированный тип данных - записи.

· Понятие записи. Поля записей.

Файловый тип данных

· Понятие файла в C. Описание файлов.

· Элементарные операции над файлами:

открытие-закрытие файлов

форматированный ввод - вывод

перемещения по файлу

специальные операции(дозапись и перезапись данных).

· Текстовые файлы.

Задачи:

1. Написать программу, заполняющую однонаправленный список случайными числами.

2. Написать программу, заполняющую двунаправленный список последовательными натуральными числами.

3. Рекурсия на примере задачи нахождения наибольшего и наименьшего элемента в массиве.

4. Написать программу сортировки обменом.

5. Написать программу сортировки вставками.

6. Написать программу сортировки выбором.

Модульный контроль № 3(семестр 2)

Питання:

Функции.

· Понятие подпрограммы. Назначение подпрограмм.

· Общая структура подпрограмм.

· Тело подпрограммы. Область действия имен. Глобальные и локальные данные

· Механизм передачи параметров. Формальные и фактические параметры. Механизмы связи различных видов параметров.

· Предварительное описания подпрограмм(прототипированиеы).

· Рекурсия. Примеры рекурсивных алгоритмов. Достоинства и недостатки рекурсивных алгоритмов.

· Передача в качестве параметра имени функцииы.

.

Ссылочный тип данных

· Определение ссылочного типа данных

· Операция взятия адреса

· Доступ к переменной по указателю

· Статические и динамические переменные

· Создание и удаление динамических переменных

· Примеры использования указателей

Задачи

1. Даны числа A₁, B₁, C₁, A₂, B₂, C₂. Напечатать координаты точки пересечения прямых, описываемых уравнениями

A₁*X + B₁*Y + C₁ = 0

A₂*X + B₂*Y + C₂ = 0

либо сообщить, что эти прямые совпадают, не пересекаются либо вообще не существуют.

2. Написать программу проверки, является ли заданное число простым.

1. Написать программу перевода числа из десятичной системы в систему с заданным основанием.
2. Написать программу сложения двух длинных чисел.
3. Написать программу умножения длинного числа на короткое.
4. Написать программу нахождения наибольшего общего делителя N заданных чисел.
5. Виртуальные методы на примере иерархии графических объектов.
6. Написать программу, находящую все простые числа в заданном диапазоне.
7. Написать программу умножения двух многочленов, заданных своими
8. Написать программу, формирующую упорядоченный массив из двух заданных упорядоченных массивов.
9. Написать программу, отыскивающую седловую точку в заданной матрице.

1. Написать программу нахождения площади выпуклого многоугольника, заданного вершинами.

2. Используя методы объектно-ориентированного программирование, создать объект Вектор и реализовать метод умножения вектора на число.

3. Написать программу решения системы двух линейных уравнения с двумя неизвестными.

4. Написать программу, реализующую список с помощью динамических записей.

Програми, основані на рекурентних відношеннях. Деякі прості програми и алгоритми.

· Конструкція while(cond)op;

· Знаходження НЗД

· Обчислення факторіалу натурального числа.

· Знаходження суми ряду.

Масиви: поняття, оголошення. Прості алгоритми роботи з масивами:

· введення - виведення масивів

· знаходження суми елементів масиву.

· пошук найбільшого (найменшого) елемента в масиві

· алгоритми пошуку в масиві;

· алгоритми роботи з матрицями: норми матриць, слід матриці, транспонування матриць; додавання та добуток матриць, добуток вектора на матрицю;

· включення та исключение элементов массива

· преобразование матрицы в одномерный массив.

Обработка символьных данных. Библиотечныее средства символьной обработки.

· Данные типа строка литер.

· Стандартные и функции для работы со строками.

Комбинированный тип данных - записи.

· Понятие записи. Поля записей.

Файловый тип данных

· Понятие файла в C. Описание файлов.

· Элементарные операции над файлами:

открытие-закрытие файлов

форматированный ввод - вывод

перемещения по файлу

специальные операции(дозапись и перезапись данных).

· Текстовые файлы.

Задачи

1. Сортировка слиянием. Сложность алгоритма.

2. Рекурсия на примере задачи нахождения наибольшего и наименьшего элемента в массиве.

3. Написать программу сортировки обменом.

4. Написать программу сортировки вставками.

5. Написать программу сортировки выбором.

6. Сортировка слиянием. Сложность алгоритма.

7. Написать программу проверки, является ли заданное число простым.

8. Написать программу перевода числа из десятичной системы в систему с заданным основанием.

9. Написать программу сложения двух длинных чисел.

10. Написать программу умножения длинного числа на короткое.

11. Написать программу нахождения наибольшего общего делителя N заданных чисел.

12. Виртуальные методы на примере иерархии графических объектов.

13. Написать программу, находящую все простые числа в заданном диапазоне.

14. Написать программу умножения двух многочленов, заданных своими

15. Написать программу, формирующую упорядоченный массив из двух заданных упорядоченных массивов.

16. Написать программу, отыскивающую седловую точку в заданной матрице.

17. Написать программу нахождения площади выпуклого многоугольника, заданного вершинами.

18. Используя методы объектно-ориентированного программирование, создать объект Вектор и реализовать метод умножения вектора на число.

19. Написать программу решения системы двух линейных уравнения с двумя неизвестными.

20. Написать программу, реализующую список с помощью динамических записей.

21. Виртуальные методы на примере иерархии графических объектов.

Модульний контроль № 4 (семестр 2)

Вопросы

Функции.

· Понятие подпрограммы. Назначение подпрограмм.

· Общая структура подпрограмм.

· Тело подпрограммы. Область действия имен. Глобальные и локальные данные

· Механизм передачи параметров. Формальные и фактические параметры. Механизмы связи различных видов параметров.

· Предварительное описания подпрограмм(прототипированиеы).

· Рекурсия. Примеры рекурсивных алгоритмов. Достоинства и недостатки рекурсивных алгоритмов.

· Передача в качестве параметра имени функции.

.

Ссылочный тип данных

· Определение ссылочного типа данных

· Операция взятия адреса

· Доступ к переменной по указателю

· Статические и динамические переменные

· Создание и удаление динамических переменных

· Примеры использования указателей

Стеки и очереди.

· Определение стека

· Программный стек.

· Включение элемента в стек

· Извлечение элемента из стека

· Очереди, включение элемента в очередь, исключение элемента из очереди.

Основные операции над списками

Простые и списки

· Исключение и включение элементов

· Алгоритм поиска в односвязном списке

· Поиск с включением. Использование барьера.

· Объединение 2-х списков в один.

· Копирование списков.

· Разбиение списков на 2 и более.

Задачи:

1. Написать программу, заполняющую однонаправленный список случайными числами.

2. Написать программу, заполняющую двунаправленный список последовательными натуральными числами.

3. Написать программу, реализующую стек с помощью массива.

4. Бесскобочная запись арифметических выражений. Деревья арифметических выражений.

5. Написать программу, реализующую стек с помощью динамических записей.

6. Написать программу, реализующую очередь с помощью массива.

7. Рекурсивный алгоритм получения всех перестановок элементов множества.

8. Написать программу, реализующую очередь с помощью динамических записей.

9. Не рекурсивный алгоритм получения всех перестановок элементов множества.

10. Написать программу, реализующую заданное множество, состоящее из букв латинского алфавита, в виде битового вектора.

11. Написать программу динамического выделения памяти под трехмерный массив.

12. Написать программу, обхода бинарного дерева в инфиксном порядке.

13. Написать программу, создающую списки смежности для графа, заданного ребрами. Списки смежности хранить в массиве.

14. Написать программу, определяющую, принадлежит ли заданное число последовательности Фибоначчи.

15. Написать программу, создающую списки смежности для графа, заданного ребрами. Списки смежности хранить с помощью динамических записей.

16. Написать функцию удаления элемента з двонаправленного списка.

17. Написать программу определения, содержится ли заданное число в заданном массиве, за логарифмическое время.

18. Написать процедуру, определяющую, принадлежит ли заданный путь заданному графу.

19. Написать процедуру удаления элемента двунаправленного списка, заданного динамическими записями.

Модульный контроль № 5(семестр 3)

Основные операции над списками

Двунаправленные списки

· Исключение и включение элементов

· Алгоритм поиска в односвязном списке

· Поиск с включением. Использование барьера.

· Объединение 2-х списков в один.

· Копирование списков.

· Разбиение списков на 2 и более.

· Топологическая сортировка.

Деревья, представление деревьев, основные операции над ними.

· Определение структуры дерева и основные понятия, связанные с деревьями

· Бинарные деревья

· Построение дерева с равномерно распределенными узлами

· Обход бинарного дерева

· Дерево поиска

· Поиск по дереву с включением

· Удаление из дерева поиска

· Сбалансированные деревья

· Включение в сбалансированное дерево с соблюдением сбалансированности

· Удаление из сбалансированного дерева

· В-деревья

Модульный контроль № 6(семестр 3)

Алгоритмы сортировки массивов

· Понятие о сортировке массивов.

· Сортировка простым выбором.

· Сортировка простым включением.

· Сортировка методом пузырьков.

· Сортировка методом двоичного деления.

· Шейкер-сортировка.

· Сортировка включениями с убывающими приращениями.

· Сортировка с помощью дерева.

· Сортировка с разделением.

Сортировка файлов

· Простое слияние.

· Естественное слияние.

· Сбалансированное многофазное слияние.

· Многофазная сортировка

Формальное описание языков программирования: РБНФ, синтаксические диаграммы

· Определение и структура языка

· Синтаксис и семантика

· Нормальные формы Бэкуса-Наура.

· Синтаксические диаграммы.

Примеры задач:

1. N натуральных чисел являются элементами двунаправленного списка L. Вычислить

X₁*X_n + X₂*X_n-1... + X_n*X₁.

2. N натуральных чисел являются элементами двунаправленного списка L. Вычислить

(X₁ + X_n)*(X₂ + X_n-1)*...*(X_n + X₁).

3. Считалка. Даны натуральные числа m и n. Предполагается, что n человек встают в круг и получают номера, считая про­тив часовой стрелки, 1, 2, 3,... n. Затем, начиная с перво­го, также против часовой стрелки отсчитывается m-й человек (поскольку люди стоят по кругу, то за n-м человеком стоит первый). Этот человек выходит из круга, после чего, начиная со следующего, снова отсчитывается m-й человек и так до тех пор пока из всего круга не останется один человек. Опреде­лить его номер.

4. Дан файл, содержащий некоторое количество слов. Вывести слова, являющиеся палиндромами (одинаково читается как сле­ва направо, так и справа налево).

5. Используя двунаправленный список, содержащий символы и их шифры, зашифровать текст, содержащийся в файле. 6. Создать двунаправленный список список и разместить в нем случайным образом данные о колоде из 36 карт. Сократить спи­сок, убрав из него шестерки.

7. Каталог книг, содержащихся в библиотеке, представлен в виде двунаправленного списка. Написать программу, обрабаты­вающую такой каталог (включение, исключение книг, поиск нуж­ной книги).

8. Последовательность камней домино представить в виде дву­направленного списка, заполненного произвольным образом. Исключить все дубли, вывести результат.

9. Создать двунаправленный список и разместить в нем в оп­ределенном порядке данные о колоде игральных карт. Разрабо­тать программу, проводящую перемешивание колоды карт путем сдвига и перестановки ее частей. Результаты перемешивания вы­вести на печать.