Реферат: Программа дисциплины по кафедре Прикладная математика т информатика алгоритмические языки и программирование

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

Тихоокеанский государственный университет



Утверждаю

Проректор по учебной работе

______________ С.В. Шалобанов

«_____» ________________200___ г.



Программа дисциплины

по кафедре Прикладная математика т информатика


АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ И ПРОГРАММИРОВАНИЕ


Утверждена научно-методическим советом университета для направления подготовки Информатика и вычислительная техника


Хабаровск 2006 г.


Программа разработана в соответствии с требованиями государственного образовательного стандарта, предъявляемыми к минимуму содержания дисциплины и в соответствии с примерной программой дисциплины, утвержденной департаментом образовательных программ и стандартов профессионального образования с учетом особенностей региона и условий организации учебного процесса Тихоокеанского государственного технического университета.


Программу составил (и)

к.ф.-м.н., доцент Вихтенко Э.М.


Программа рассмотрена и утверждена на заседании кафедры

протокол № ____ от «____»_________________2006 г.


Завкафедрой _________. д.ф.-м.н., профЗарубин АГ. «___»____________2006 г


Программа рассмотрена и утверждена на заседании УМК и рекомендована к изданию

протокол № ____ от «____»_________________2006 г.


Председатель УМКС ___________ «____»___________2006 г.


Декан ФММиПУ_______________ «___»_______________2006 г. Син А.З.

^ Цель и задачи дисциплины

Цели дисциплины

Целью дисциплины «Алгоритмические языки и программирование» является изучение и освоение базовых понятий, методов и приемов программирования, применяемых на всех основных этапах жизненного цикла программы. Дисциплина является базовой в программистском образовании для направления подготовки Прикладная математика


^ Задачи дисциплины:

сформировать взгляд на программирование как на систематическую научно-практическую деятельность, носящую массовый характер (производство программ заданного качества в заданные сроки);

сформировать базовые теоретические понятия (возможно, на элементарном уровне), лежащие в основе процесса конструирования программ, в том числе:

заложить основы разработки надёжных программ, акцентируя внимание как на методах аналитической верификации и разработке корректных программ, так и на технике (технологии) их испытания (тестирования и отладки);

заложить в основу конструирования и использования сложных (динамических) структур данных модель (парадигму) абстрактного типа данных, с последующим переходом к объектно-ориентированному подходу;

дать навыки технологии разработки корректных программ, (относительно) инвариантные к используемому языку программирования высокого уровня и опирающиеся на универсальную модель вычислительной машины;

научить реализации корректных программ на выбранном рабочем языке программирования с учётом особенностей его конкретной реализации на персональной ЭВМ (конкретной системы программирования);

продемонстрировать теоретически и на практике целесообразность и возможность конструктивного использования базовых теоретических понятий, методов и приемов (абстрактных схем) программирования;

сформировать начальные представления и знания об анализе сложности алгоритмов и программ.


Требования к уровню освоению содержания дисциплины

В результате изучения дисциплины студенты должны

(а) Знать:

способы постановки и спецификации задач для решения на ПЭВМ;

основные современные методы и средства разработки корректных структурированных алгоритмов и программ;

технологию работы на персональной ЭВМ (ПЭВМ), правила и приемы диалоговой работы на ПЭВМ при программировании типовых задач;

положения объектно-ориентированного программирования;

способы записи и документирования алгоритмов и программ;

способы испытания и отладки программ.

(б) Уметь:

самостоятельно осуществлять постановку и спецификацию задачи для решения на ПЭВМ;

самостоятельно составлять, отлаживать, тестировать и документировать программы для персональных ЭВМ;

доказывать корректность ключевых фрагментов составленных алгоритмов и программ.

(в) Иметь представление о

методах и проблемах доказательства правильности программ;

анализе некоторых задач и алгоритмов;

проблемах оптимизации программ;

абстрактных типах данных (на примерах), их спецификации, представлении и реализации в конкретном языке;

основных понятиях объектно-ориентированного программирования и их реализации в конкретной системе программирования;

технологии производства программ.

^ Объем дисциплины и виды учебной работы

Наименование
По учебным планам основной траектории обучения

С максимальной трудоемкостью

С минимальной трудоемкостью
Общая трудоемкость дисциплины
По ГОС

По УП

260

272




Изучается в семестрах

12



Виды итогового контроля по семестрам
Зачет

Экзамен

Курсовой проект (КП)

Курсовая работа (КР)

^ Виды итогового контроля самостоятельной работы без отчетностей

Расчетно-графические работы (РГР)

Реферат (РФ)

Домашние задания (ДЗ)


12

2


12




^ Аудиторные занятия:

Всего

В том числе: лекции (Л)

Лабораторные работы (ЛР)

Практические занятия (ПЗ)



68

51

34



Самостоятельная работа
Общий объем часов (С2)

В том числе: на подготовку к лекциям

на подготовку к ЛР

на подготовку к ПЗ

на выполнение КП

на выполнение КР

на выполнение РГР

на написание РФ

на выполнение ДЗ

на экзаменационную сессию


119


17

34

34


34




^ Содержание дисциплины


Введение

Предмет дисциплины и ее задачи. Содержание и форма проведения занятий. Связь с другими дисциплинами учебного плана специальности.


Тема 1. Основные задачи разработки, анализа и верификации программ

1.1. Этапы и проблемы решения задач на ПЭВМ. Решение задач на ПЭВМ. Основные этапы и проблемы конструирования программ. Постановка задачи и спецификация. Разработка алгоритма решения задачи. Характеристики алгоритма, его свойства, запись алгоритма в виде блок-схемы. Программа как продукт.

1.2. ^ Верификация и анализ алгоритмов и программ. Пример разработки, верификации и анализа алгоритма. Алгоритм Евклида для нахождения НОД двух чисел. Разработка и запись алгоритма в виде блок-схемы. Метод математической индукции и его применение в доказательстве правильности алгоритма. Метод индуктивных утверждений. Проблемы верификации программ. Цели и методы верификации программ. Аналитическая верификация (доказательство корректности) и испытание программы. Конструктивный подход: конструирование и верификация. Автоматизация верификации программ. Оценка сложности алгоритмов (на примерах).


Тема 2. Общие сведения о языке и системе программирования

2.1. Общая характеристика языка. Основные объекты программы. Классификация действий и данных. Программа на языке программирования: синтаксис и семантика. Пример программы: структура программы, описание переменных, присваивание.

2.2. ^ Система программирования. Проект как совокупность программного кода и экранных форм. Инспектор свойств объектов. Компоненты системы. Трансляция программ (компиляция и интерпретация). Выполнение программы. Системы поддержки процесса подготовки и выполнения программ.


Тема 3. Представление данных. Концепция типов данных. Стандартные типы

3.1. Тип данных как совокупность значений и действий. Принцип строгой типизации. Номенклатура простых типов языка. Скалярные типы. Порядковые типы. Предописанные типы.

3.2. Целые числа без знака и со знаком. Принципы представления в памяти. Множество значений, допустимые операции.

3.3. Вещественные числа. Принципы представления в памяти. Свойства машинной арифметики. Машинное эпсилон. Примеры. Множество значений, допустимые операции.

3.4. Символьный тип. Множество значений, предописанные функции. Особенности реализаций. Способы использования символьного типа в программах.

3.5. Логический тип. Множество значений, операции. Особенности логических выражений в языке программирования, приоритет операций.


Тема 4. Основные управляющие структуры и их реализация

4.1. Основные управляющие структуры программирования. Составной оператор.

4.2. Условный оператор. Оператор множественного выбора.

4.3. Операторы цикла с предусловием и с постусловием: сходство, различие, преобразования. Цикл с параметром.


Тема 5. Процедуры и функции

5.1. Метод последовательных уточнений (пошаговой декомпозиции) и концепция подпрограммы (модуля) в программировании. Локальные и глобальные переменные, область действия

5.2. Описание процедур и функций. Формальные и фактические параметры. Способы передачи параметров. Параметры-значения, параметры-переменные, параметры-константы, процедуральные параметры.

5.3. Процедуры и программирование действий с массивами. Массивы в качестве параметров процедур и функций. Процедуры и функции как инструмент определения и реализации действий с массивами. Особенности использования многомерных массивов и их компонент в качестве параметров процедур и функций. Примеры обработки матриц с использованием процедур. Открытые массивы.


Тема 6. Типы данных пользователя.

6.1. Описание типов данных пользователя.

6.2. Перечисляемый тип: определение типа, константы, переменные, операции, предописанные функции, реализация ввода и вывода.

6.3. Диапазонный тип. Базовый тип. Определение диапазон ного типа. Операции и предописанные функции. Примеры использования.


Тема 7. Обработка структурированных типов данных

7.1. Массив как составной тип данных. Определение типа. Определение переменных. Логическая структура массивов. Доступ к элементам массива (адресация). Примеры работы с массивами.

7.2. Тип данных запись. Определения. Синтаксис и семантика. Примеры использования. Оператор присоединения with. Записи с вариантами. Рекомендации по применению.

7.3. Тип множество. Определение типа. Конструкторы множеств. Операции над множествами. Примеры использования. Особенности реализации.

7.4. Строки. Определение, операции над строками. Представление строк (с явной длиной, с символом ограничителем). Реализация типовых операций над строками.

7.5. Указатели. Ссылочные и идентифицированные (динамические) переменные. Действия над ссылками и динамическая память. Применение ссылочных переменных при программировании. Определяемые рекурсивные типы данных. Цепное представление последовательностей. Программирование основных операций.

7.6. Работа с файлами. Определение файлов и файловых переменных. Базовые операции с файлами. Текстовые файлы. Типизированные файлы. Типовые действия, особенности работы с разными типами файлов.


Тема 8. Приемы программирования некоторых задач

8.1. Линейный и бинарный поиск. Задача поиска элемента массива. Линейный поиск. Варианты решения. Доказательство корректности. Общая схема линейного просмотра. Задача поиска места элемента в упорядоченном массиве. Спецификация задачи. Разработка корректной программы бинарного поиска. Анализ алгоритма бинарного поиска. Дерево бинарного поиска. Оптимальность алгоритма бинарного поиска. Оптимизация программы бинарного поиска. Быстрый вариант с развертыванием цикла.

8.2. ^ Рекурсия в программировании. Рекурсивные определения и рекурсивные функции. Рекурсивные алгоритмы. Выполнение рекурсивных алгоритмов: подготовка трассы, стек (магазин). Анализ рекурсивных алгоритмов. Рекуррентные уравнения. Соотношение время-память для рекурсивных алгоритмов. Рекурсивные процедуры и функции в языке программирования. Приемы рекурсивного программирования (нисходящая и восходящая рекурсия, накапливающие параметры). Примеры: простая рекурсия, программы с несколькими рекурсивными вызовами, косвенная рекурсия (взаимно- рекурсивные подпрограммы). Преобразование рекурсивных программ в итеративные (“избавление” от рекурсии). Примеры.

8.3. ^ Программирование линейных списков. Линейный однонаправленный список (Л1-список) как абстрактный тип данных. Функциональная спецификация Л1-списка. Ссылочная реализация Л1-списка в связанной памяти. Представление и реализация Л1-списка на языке программирования. Разновидности линейных списков: циклические, двунаправленные (Л2-

списки). Примеры.


^ Тема 9. Элементы объектно-ориентированного программирования

Основные идеи объектно-ориентированного программирования. Объектовый тип и экземпляр объектового типа. Данные и методы объекта. Инкапсуляция. Наследование. Полиморфизм. Пример программы.


Тема 10. Графические объекты.

10.1. Создание элементарных графических изображений. Компьютерная анимация

10.2. Компоненты для включения средств деловой графики: построение графиков функций.


Заключение

Основные тенденции и направления развития методов и языков программирования на ПЭВМ. Инструментальная поддержка и автоматизация конструирования программ.
^ Разделы дисциплины и виды занятий и работ



№
^ Раздел дисциплины
Л

ЛР

ПЗ

РГР

ДЗ

С2



Этапы и проблемы решения задач на ПЭВМ

*




*












Общие сведения о языке и системе программирования

*

*















Представление данных. Концепция типов данных. Стандартные типы

*




*

*









Основные управляющие структуры и их реализация

*

*

*

*









Процедуры и функции

*

*

*

*









Типы данных пользователя

*

*




*









Обработка структурированных типов данных

*

*

*

*









Приемы программирования некоторых задач

*

*

*

*









Элементы объектно-ориентированного программирования

*

*

*

*









Графические объекты

*

*




*









Заключение

*

















^ Лабораторный практикум


Используемое оборудование. Лабораторные занятия проводятся в аудитории, оснащенной современными персональными компьютерами. Количество компьютеров должно соответствовать количеству студентов на занятии (1 компьютер на 1 студента). На компьютерах должна быть установлена операционная система Windows 9x/XP/NT и интегрированная система программирования. Может быть использована любая из версий языка, выбранного кафедрой для преподавания.


Целью лабораторного практикума является выработка и закрепление навыков самостоятельного составления, отладки и тестирования программ на языке программирования.


^ Оценка результатов работы. В ходе выполнения задания для поставленной задачи составляется и отлаживается программа. Результат работы оценивается в процессе тестирования на наборе контрольных примеров, предложенных как самим студентом-разработчиком, так и преподавателем, проводящем занятие.


^ Задания для лабораторных работ включают в себя ряд задач по теме занятия. Количество и общий объем приведенного списка лабораторных работ превышает объем часов, отводимых на выполнение лабораторных работ по учебному плану. При разработке рабочей программы из приведенного списка выбираются необходимые работы. Количество заданий в каждой работе также может быть изменено.

Ниже приведены примеры заданий для одного варианта.


Лабораторная работа 1^ . ЗНАКОМСТВО СО СРЕДОЙ ПРОГРАММИРОВАНИЯ. РАЗРАБОТКА ПРОГРАММ ЛИНЕЙНОЙ СТРУКТУРЫ

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



Задание 2. Составить программу pешения задачи.

Пассажирский поезд, двигаясь равномерно, за 10 мин прошел путь 15 км. Вычислить скорость поезда ( в м/с и км/ч )

Задание 3. Составить программу решения задачи.

Сторона ромба равна a, меньшая диагональ L. Найти большую диагональ.

Задание 4. Составить пошаговую словесную запись алгоритма. По данному алгоритму составить программу.

Известно, что К-тый день года это n-тый день в неделе (например, 321 день года это 3-тий день в неделе, т.е. среда). Найти номер дня недели, с которого начинался этот невисокосный год.

Время выполнения: 2 часа


Лабораторная работа 2^ . УСЛОВНЫЕ ОПЕРАТОРЫ

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

2. Составить программу для определения подходящего возраста для вступления в брак, используя следующее правило: возраст девушки равен половине возраста мужчины плюс 7, возраст мужчины соответственно определяется как удвоенный возраст девушки минус 14.

3. Используя только условный оператор, вычислить значение выражения

z=||x+1|-|y+x||

4. Составить алгоритм и написать программу решения задачи.

Определить количество положительных чисел среди чисел a, b, c, d.

Время выполнения: 2 часа


Лабораторная работа 3. ЦИКЛЫ

1. Разъяснить выполнение программы, указать тело цикла, вид цикла, параметр, начертить блок-схему. Переписать программу на другой язык.

10 t=1

20 print t,t*t

30 t=t+2

40 if t<=10 then 20

50 end

2. Вычислить для заданного n указанное выражение.



3. Вывести на печать номер и значение первого отрицательного члена последовательности

4. Разложить число на простые множители.

Время выполнения: 4 часа


^ Лабораторная работа 4. МАССИВЫ

1. Использовать одномерные массивы, ввод и вывод элементов массива организовать в строку, отделяя элементы друг от друга пробелами.

Даны числа а1,...,аn. Найти среднее геометрическое и среднее арифметическое чисел.

2. Дан одномерный массив. Поменять местами наибольший и наименьший элементы массива.

3. Сортировка одномерного массива выбором: отыскивается максимальный (минимальный) элемент и переносится в конец массива; затем этот метод применяется ко всем элементам, кроме последнего.

4. Даны квадратные матрицы A и B порядка n. Получите матрицу AB - BA.

Время выполнения: 4 часа


Лабораторная работа 5. ПРОЦЕДУРЫ И ФУНКЦИИ

1. Описать процедуру SumDigit(N,S), находящую сумму цифр S целого числа N (N — входной, S — выходной параметр). Используя эту процедуру, найти суммы цифр пяти данных чисел.

2.  Описать нерекурсивную функцию NOD2(A,B) целого типа, находящую наибольший общий делитель (НОД) двух натуральных чисел A и B, используя алгоритм Евклида: НОД(A,B) = НОД(B mod A,A), если A <> 0;     НОД(0,B) = B. С помощью этой функции найти наибольшие общие делители пар A и B, A и C, A и D, если даны числа A, B, C, D.

3. Описать функцию NMin(A,N)1|NMax(A,N)2 целого типа, находящую номер минимального1|максимального2 элемента массива A (массив состоит из N вещественных чисел). С помощью этой функции найти номера минимальных1|максимальных2 элементов массивов A, B, C размера NA, NB, NC соответственно.

4. Описать процедуру NMinmax(A,N,NMin,NMax), находящую номера минимального и максимального элемента массива A из N вещественных чисел. Выходные параметры: NMin (номер минимального элемента) и NMax (номер максимального элемента). С помощью этой процедуры найти номера минимальных и максимальных элементов массивов A, B, C размера NA, NB, NC соответственно.

Время выполнения: 6 часов


Лабораторная работа 6^ . ДАННЫЕ СТРОКОВОГО ТИПА

В предложении все слова сдвинуть циклически на k букв (например, k=2, слово ПРОБА станет ОБАПР).

Удалить из предложения все слова «поле».

Время выполнения: 2 часа


Лабораторная работа 7^ . СТРУКТУРИРОВАННЫЕ ТИПЫ ДАННЫХ (ЗАПИСИ)

Дано расписание движения самолетов. Расписание представляет собой массив записей. Каждая запись содержит информацию об одном рейсе в виде:

номер рейса;

тип самолета;

конечный пункт назначения;

список дней вылета через запятую;

время вылета;

время прилета;

цена билета.

Определить наиболее подходящий рейс в заданный город, улетающий, желательно, в определенный день и в определенное время (например, рейс в Москву в понедельник в 8 утра).

Время выполнения: 4 часа


Лабораторная работа 8^ . ДИНАМИЧЕСКИЕ СПИСКИ

В работе во всех вариантах используются односвязные списки, информационная часть которых – целое число. Требуется создать список и выполнить задания варианта. Для создания списка и вывода его на форму написать отдельные процедуры. Создание списка может быть выполнено по схеме:

1. «Введите количество элементов в списке» (N – количество элементов);

2. «Введите элементы списка».

В процедурах обработки списка по варианту количество элементов N не использовать!

1. Определить количество пар соседних элементов, в которых большее число находится слева от меньшего.

2. В списке из каждой группы подряд идущих равных элементов оставить только один.

3. Разработать алгоритм включения и исключения записей в сортированный односвязный список.

Время выполнения: 4 часа


Лабораторная работа 9. ФАЙЛЫ

1.  Даны два файла вещественных чисел с именами Name1 и Name2, элементы которых упорядочены по возрастанию. Объединить эти файлы в новый файл с именем Name3, сохранив упорядоченность элементов.

2.  Дан текстовый файл с именем NameT. Подсчитать число повторений в нем строчных русских букв ("а"–"я") и создать строковый файл с именем NameS, элементы которого имеют вид: "<буква>–<число повторений данной буквы>". Буквы, отсутствующие в тексте, в файл не включать. Строки упорядочить по возрастанию кодов букв.

Время выполнения: 4 часа


Лабораторная работа 10^ . РЕКУРСИВНЫЕ АЛГОРИТМЫ

1. Описать рекурсивную функцию NOD2(A,B) целого типа, находящую наибольший общий делитель (НОД) двух натуральных чисел A и B, используя алгоритм Евклида: НОД(A,B) = НОД(B mod A,A), если A <> 0;     НОД(0,B) = B. С помощью этой функции найти наибольшие общие делители пар A и B, A и C, A и D, если даны числа A, B, C, D.

2. Используя рекурсивные процедуры (функции), решить задачу получения всех перестановок из N элементов.

Время выполнения: 6 часов


Лабораторная работа 11.^ СОРТИРОВКА И ПОИСК В ПОСЛЕДОВАТЕЛЬНОСТИ ДАННЫХ

1. Реализовать сортировку выбором, простыми обменами (пузырьком), вставками, быструю сортировку одномерного массива.

2. Дана действительная матрица. Упорядочить строки матрицы

а) по неубыванию значений первых элементов строки;

б) по невозрастанию сумм элементов строки.

Время выполнения: 6 часов.


Лабораторная работа 12^ . ЭЛЕМЕНТЫ ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПРОГРАММИРОВАНИЯ

Выполнить умножение двух длинных целых чисел. Число х назовем длинным, если -10100 < x< 10100. Описать класс «длинное целое число»

Время выполнения: 6 часов


Лабораторная работа 13. ГРАФИКА

1. Исследовать область определения и построить графики функций



2. Построить спираль вокруг начала координат с n витками и внешним радиусом r.

3. Построить области пересечения двух прямоугольников; двух окружностей; окружности и прямоугольника.

Время выполнения: 6 часов


Лабораторный практикум и

его взаимосвязь с содержанием лекционного курса


№ п/п

№ раздела

лекции


Наименование лабораторной работы

1

2, 3

Разработка программ линейной структуры

2

3, 4.1

Условные операторы

3

3, 4.2, 6

Циклы

4

5

Процедуры и функции

5

7.1, 6

Массивы

6

7.4, 6

Данные строкового типа

7

7.2, 6

Структурированные типы данных (записи)

8

7.5, 6, 8.3

Динамические списки

9

7.6, 6

Файлы

10

8.2

Рекурсивные алгоритмы

11

8.1

Сортировка и поиск в последовательности данных

12

9

Элементы объектно-ориентированного программирования

13

10

Графика


^ Практические занятия


Схемы алгоритмов. Базовые структуры алгоритмов

Задание: составить алгоритмы решения задач, начертить блок-схемы.

Примеры задач: нахождение площади треугольника по трем сторонам; решение квадратного уравнения; метод половинного деления для решения уравнения f(x)=0.

Время выполнения задания: 2 часа


^ Алгоритмы обработки последовательностей

Задание: составить алгоритмы решения задач нахождения суммы, максимального (минимального) элементов последовательности.

Время выполнения задания: 2 часа


^ Алгоритмы сочетания цикла и ветвления

Обработка числовой и символьной последовательностей

Задание: составить алгоритмы решения задач

Примеры задач: определить, есть ли в последовательности символов символ «*»; вычислить среднее арифметическое отрицательных элементов последовательности

Время выполнения задания: 2 часа


^ Алгоритмы обработки массивов: сортировка, поиск, вставка элемента, удаление элемента

Задание: составить алгоритмы решения типовых задач, связанных с обработкой массивов

Время выполнения задания: 2 часа


^ Алгоритмы обработки записей

Задание: составить алгоритмы решения типовых задач, связанных с обработкой записей (база данных)

Время выполнения задания: 2 часа


^ Алгоритмы обработки данных с использованием подпрограмм с параметрами

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

Примеры задач: функция проверки простоты числа; процедура перевода числа из десятичной в двоичную систему – с рекурсией и без нее; факториал – с рекурсией и без нее; операции с массивами.

Время выполнения задания: 4 часа


^ Алгоритмы обработки данных с использованием текстовых файлов для исходных и выходных данных, типизированных файлов для хранения внутренних данных

Задание: составить алгоритмы решения задач с использованием файлов

Примеры задач: чтение из файла, запись в файл, сортировка файла и др.

Время выполнения задания: 4 часа


^ Алгоритмы построения графика функции. Мультипликация

Задание: масштабирование графиков; использование разных принципов создания «движущихся» изображений; таймер; графические компоненты

Время выполнения задания: 4 часа


^ Алгоритмы обработки данных с использованием динамических списков

Задание: составить алгоритмы решения типовых задач работы со списками

Примеры задач: создание списка, вывод списка, поиск в списке, вставка и удаление элементов списка

Время выполнения задания: 4 часа


^ Алгоритмы обработки данных с использованием объектов, динамических и виртуальных методов

Задание: освоить основные приемы работы с объектами (классами)

Примеры задач: описание объекта, создание и уничтожение объекта, использование наследования и полиморфизма

Время выполнения задания: 4 часа


^ Алгоритмы обработки данных с использованием указателей

Задание: решение задач с использованием указателей как параметров функций; с использованием массива указателей на функции

Время выполнения задания: 4 часа


Практические занятия и их

взаимосвязь с содержанием лекционного курса


№ п/п

№ раздела

лекции


Наименование лабораторной работы

1

2, 3, 4

Схемы алгоритмов. Базовые структуры алгоритмов

2

2, 3,4, 6

Алгоритмы обработки последовательностей

3

2, 3,4, 6

Алгоритмы сочетания цикла и ветвления

Обработка числовой и символьной последовательностей

4

5

Алгоритмы обработки данных с использованием подпрограмм с параметрами

5

7.1, 6

Алгоритмы обработки массивов: сортировка, поиск, вставка элемента, удаление элемента

6

7.2, 6

Алгоритмы обработки записей

7

7.6, 6

Алгоритмы обработки данных с использованием файлов

8

7.5, 6, 8.3

Алгоритмы обработки данных с использованием динамических списков

9

5, 7.5, 6, 8.3

Алгоритмы обработки данных с использованием указателей

10

9

Алгоритмы обработки данных с использованием объектов, динамических и виртуальных методов

11

10

Алгоритмы построения графика функции. Мультипликация

^ Расчетно-графическая работа

Цель РГР: совершенствование и дальнейшее закрепление навыков самостоятельного составления, отладки, тестирования и документирования программ на языке программирования.

Объем пояснительной записки: 7-10 листов.

Содержание пояснительной записки:

титульный лист;

постановка задачи;

блок-схемы основных модулей;

контрольные (тестовые примеры) – не мене 5 шт.;

список использованных источников.

Время выполнения РГР: 10 часов


Расчетно-графическая работа 1

Задание: Разработать алгоритм, составить программу решения поставленной задачи. Разработать набор тестовых примеров и провести тестирование. Основные модули алгоритма оформить в виде блок-схем.

Дан порядок двух квадратных матриц Т и С – число n. Матрица Т задается своим внешним видом, матрица С вводится с клавиатуры. Необходимо получить матрицы Т и С и обработать их в соответствии с заданием.

Пример задания матрицы T (n=4):

10

4

3

1

11

9

5

2

15

12

8

6

16

14

13

7

Найти k1– количество различных чисел ниже побочной диагонали матрицы С и k2 – количество аналогичных чисел для Т. Если k1
В программе должны быть использованы только 3 глобальные величины – n, T, C.


^ Расчетно-графическая работа 2

Задание: Разработать алгоритм, составить программу решения поставленной задачи. Разработать набор тестовых примеров и провести тестирование.

Дано натуральное число N и пары вещественных чисел (xi, yi), i = 1, 2, …, N. Каждая пара (xi, yi) является координатами точки на плоскости.

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

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


^ Домашние задания


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

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

Источниками информации служат основная и дополнительная литература, а также материалы лекционных и лабораторных занятий.


Темы для домашних заданий.

1. Системы счисления. Задание: решение задач на перевод чисел из одной системы счисления в другую, выполнение арифметических операций (6 часов).

2. Составление и решение задач разного типа. Задание: подготовка к выполнению лабораторных работ, разработка алгоритмов и составление тестовых примеров для поставленных задач (28 часов).


^ Контроль знаний студентов


Входной контроль знаний студентов

Входной контроль остаточных знаний проводится в форме анкетирования. Курс Алгоритмические языки и программирование базируется на понятиях, изучаемых в предшествующих естественнонаучных дисциплинах математика и информатика средней общеобразовательной школы.

Вопросы входного контроля:

1. Что изучает информатика?

2. По каким признакам и сколько поколений вычислительной техники

выделяют в истории ее развития?

3. Какие устройства могут входить в состав ПК?

4. Дайте определение алгоритма.

5. Какие основные формы представления алгоритмов существуют?

6. Какие типы алгоритмов(вычислительных процессов) Вы знаете?

7. Какие основные системы счисления Вы знаете?

8. Каковы единицы измерения количества информации?

9. О каких языках программирования Вам известно?

10. Каковы этапы решения задач с помощью ПК?

11. Что такое программа?

12. Какие программы называются прикладными?

13. Что такое редактор текстов?

14. Что такое база данных?

15. Что такое электронная таблица?

16. Что такое операционная система?


Текущий контроль осуществляется в процессе выполнения студентами заданий лабораторных работ и проводится в форме собеседования преподавателя со студентом по теме занятия.

Кроме того, в течение семестра предусмотрен ряд проверочных работ, целью которых является определение уровня усвоения студентом учебного материала.

^ Примеры вопросов промежуточного контроля знаний (вопросы и их количество может меняться):

1. Логическое выражение

(N mod 10 mod 2=0) or (N div 10 mod 10 mod 2=0) or (N div 100 mod 2=0)

должно принимать значение TRUE тогда и только тогда, когда истинно высказывание

в трехзначном натуральном числе все цифры четные;

в трехзначном натуральном числе одна цифра четная;

в трехзначном натуральном числе две цифры четные;

в трехзначном натуральном числе хотя бы одна цифра четная;

в трехзначном натуральном числе нет четных цифр.


2. Ошибку “Structure too large” (структура превышает максимально допустимый объем статической памяти) вызовет описание

type Vector=array[-3000..1000] of byte; var c: array [1..10] of Vector;

var T: file of string;

type A=record S:string; a,b,c: array[10..20] of real; end;

var M: array[1..5,1..8] of A;

var K:array[-3000,4000] of string[9];

var S:array[-1000..10000] of string[2]


3. Имеется описание

Type Dn=(pn, vt, sr, cht, ptn, sb, vs); Mn=set of Dn; var V: Mn;

и фрагмент программы

V:=[pn..ptn]-[sr,ptn..vs]*[pn,sr];

После исполнения этого фрагмента переменная имеет значение

[pn..vs]; 2) [sr,ptn]; 3) [pn,vt,cht,pt]; 4) []; 5) [pn..ptn]


4. В приведенном фрагменте программы (N типа Longint, N>0)

P:=1;

While p<=n do

Begin

Left:=N div (P*10)*(P*10);

Right:=N mod P;

K:=((N mod (P*10) div P+1) mod 10)*P;

N:=Left+K+Right;

P:=P*10;

End

натуральное число N изменяется по следующему правилу:

не изменяется;

в каждый разряд прибавляется 1;

из каждого разряда вычитается 1;

в каждый разряд прибавляется 1, если значение в разряде не 9, иначе заменяется на нуль;

каждая девятка в десятичной записи числа заменяется на нуль.


5. Цикл с постусловием выполняется так:

выполняется тело цикла, изменяется параметр цикла, проверяется условие продолжения выполнения цикла;

выполняется тело цикла, проверяется условие продолжения выполнения цикла;

изменяется параметр цикла, проверяется условие продолжения выполнения цикла, выполняется тело цикла;

тело цикла выполняется N раз;

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