Государственное учреждение образования

«Республиканский институт высшей школы»

Учреждение образования «Белорусский государственный

университет информатики и радиоэлектроники»

СБОРНИК

ТИПОВЫХ УЧЕБНЫХ ПРОГРАММ ДЛЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ ПО СПЕЦИАЛЬНОСТЯМ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
ОБЩЕНАУЧНЫЕ И ОБЩЕПРОФЕССИОНАЛЬНЫЕ ДИСЦИПЛИНЫ

Минск 2006

УДК 621.37/39+002.5(075.8)

С 23

В сборник включены типовые программы по общенаучным и общепрофессиональным дисциплинам: «Основы алгоритмизации и программирования», «Электронные приборы и устройства», «Метрология, стандартизация и сертификация», «Основы защиты информации», обязательные для изучения по специальностям информатики и радиоэлектроники.

УДК 621.37/39+002.5(075.8)

Министерством образования

Республики Беларусь

16.01.2006.

Регистрационный № ТД-I.001/тип.

по специальностям информатики и радиоэлектроники

Кафедрой вычислительных методов и программирования Учреждения образования «Белорусский государственный университет информатики и радиоэлектроники» (протокол № 1 от 26.09. 2005.);

Научно-методическим советом Учреждения образования «Белорусский государственный университет информатики и радиоэлектроники» (прото-
кол № 2 от 23.11.2005.)

СОГЛАСОВАНА С:

Председателем Учебно-методического объединения вузов Республики Беларусь по образованию в области информатики и радиоэлектроники;

Начальником Управления высшего и среднего специального

образования Министерства образования Республики Беларусь;

Первым проректором Государственного учреждения образования «Республиканский институт высшей школы»

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Типовая программа по дисциплине «Основы алгоритмизации и программирования» разработана для студентов высших учебных заведений по специальностям информатики и радиоэлектроники.

Целью изучения дисциплины является ознакомление с операционной системой ПЭВМ, усвоение понятия алгоритма его способов записи и основных свойств, изучение языка программирования высокого уровня типа Паскаль-СИ-…, получение практических навыков составления и отладки программ на персональных компьютерах, изучение основных базовых алгоритмов и закрепление навыков алгоритмизации на основе программирования алгоритмов на структурах данных и алгоритмов вычислительной математики.
МЕСТО КУРСА В ПОДГОТОВКЕ СПЕЦИАЛИСТА

Подготовка современного специалиста требует уверенного владения возможностями, предоставляемыми компьютерными технологиями. Изучение настоящей дисциплины на первом курсе обеспечивает начальную подготовку студентов навыкам работы на персональном компьютере и приемам программирования типовых алгоритмов. В подготовке специалиста информационного профиля большое внимание уделяется освоению алгоритмов работы со структурами данных – поиск и сортировка в массивах, динамических линейных и древовидных связанных списках. В инженерной подготовке специалиста радиоэлектронного профиля очень важно умение производить расчеты связанные с решением задач вычислительной математики, которые реализованы в целом ряде стандартных пакетов, таких, как например, MATHCAD, MATLAB и др.. Поэтому закрепление навыков программирования в данном курсе осуществляется на основе изучения и реализации в виде программ на языке высокого уровня основных алгоритмов на структурах данных и алгоритмов вычислительной математики. Раздел 1 обеспечивает базовую подготовку по программированию на языке высокого уровня. Раздел 2 предназначен для студентов информационных специальностей. Раздел 3 предназначен ля студентов радиоэлектронных специальностей. Раздел 4 является заключительным, имеет обзорный характер и освещает общие проблемы алгоритмизации и развитие технологии программирования.

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

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

• 
  современное состояние одного из алгоритмических языков высокого уровня;
  
• 
  основные динамические структуры данных и алгоритмы их обработки;
  
• 
  наиболее эффективные и часто используемые на практике вычислительные алгоритмы решения инженерных задач;
  
• 
  теоретические основы алгоритмизации и проектирования программ;
  

• 
  алгоритмизацию и программирование инженерных задач;
  

• 
  имеющееся программное обеспечение.
  

• 
  исходные и выходные данные решаемых задач и формы их представления; уметь использовать имеющееся программное обеспечение.
  

• 
  отладки программ.
  

Раздел 1. Основы алгоритмизации и возможности языков програмирования высокого уровня

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

Структура программы. Переменные и их основные базовые типы. Понятие оператора. Выполняемые и невыполняемые операторы. Программа как последовательность операторов. Пример программирования линейного алгоритма.

Понятие разветвляющегося алгоритма, схема его представления. Операторы реализующие разветвления. Примеры.

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

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

Адреса, указатели и ссылки. Типизированные и не типизированные указатели. Правила работы с динамической памятью. Функции работы с памятью. Динамические массивы.

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

Понятия строки, ее описание. Основные функции и процедуры обработки строк. Примеры алгоритмов обработки строк.

Понятие записи (структуры), ее описание и примеры использования для представления и обработки данных.

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

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

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

Понятие рекурсии. Условие окончания рекурсивного алгоритма. Деревья решений и их программирование. Решение задачи оптимального выбора.

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

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

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

Двоичные деревья. Алгоритмы формирования дерева. Операции над деревьями. Алгоритмы обхода дерева. Сбалансированные деревья. Алгоритм балансировки дерева.

Алгоритмы решения систем линейных алгебраических уравнений. Метод простой итерации. Метод Зейделя. Метод Гаусса, метод прогонки.

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

Формулы средних трапеций, Симпсона, Гаусса.

Методы дихотомии, простой итерации, Ньютона, Вегстейна, парабол.

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

Способы описания алгоритмов. Примитивы, синтаксис, семантика. Псевдокоды. Проблемы создания алгоритмов. Проблема универсального языка программирования. Проблема универсальной вычислительной машины. Машина Тьюринга. Теорема Гельдера. Тезис Черча-Тьюринга.

Требования к программному обеспечению (ПО). Нисходящее проектирование. Процедурное, декларативное, логическое и объектно-ориентированное программирование. Технологический цикл разработки ПО. Основные стадии и этапы разработки программного обеспечения ПО. Критерии качества ПО. Тестирование ПО.

Раздел 1. ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ

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

Раздел 2. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ НА СТРУКТУРАХ ДАННЫХ

1. 
   Программирование с использованием рекурсии.
   
2. 
   Программирование с использованием деревьев решений.
   
3. 
   Программирование алгоритмов поиска и сортировки в массивах данных.
   
4. 
   Алгоритмы поиска и сортировки линейных связанных списков.
   
5. 
   Программирование с использованием динамических древовидных структур данных. Дерево поиска. Построение сбалансированных бинарных деревьев. Поиск и сортировка на основе бинарных деревьев
   

Раздел 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ

1. 
   Составление и отладка программ реализации алгоритмов решения систем линейных алгебраических уравнений. Алгоритмы метода Гаусса, прогонки, квадратного корня, простой итерации, Зейделя.
   
2. 
   Составление и отладка программы по методам аппроксимации функций. Алгоритмы интерполяции и метода наименьших квадратов.
   
3. 
   Составление и отладка программ по формулам численного дифференцирования и интегрирования. Алгоритмы методов средних трапеций, Симпсона, Гаусса.
   
4. 
   Составление и отладка программ по методам решения нелинейных уравнений. Алгоритмы дихотомии, простой итерации, Ньютона, секущих, Вегстейна, квадратичной параболы.
   
5. 
   Составление программ нахождения минимума функции одной переменной. Алгоритмы методов золотого сечения, последовательного спуска, квадратичной и кубической параболы.