Учебно-методическии комплекс дисциплины «Структуры и алгоритм обработки данных» (стр. 1 )

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени ШАКАРИМА г. СЕМЕЙ
Документ СМК 3 уровня	УМКД	УМКД 042-39. 1.ХХ/03- 2013
УМКД Учебно-методические материалы по дисциплине «Структуры и алгоритм обработки данных»	Редакция №____от_____

УЧЕБНО-МЕТОДИЧЕСКИИ КОМПЛЕКС

ДИСЦИПЛИНЫ

«Структуры и алгоритм обработки данных»

для специальности 5В011100 – «Информатика »

УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ

Семей

2013

СОДЕРЖАНИЕ

Глоссарий Лекции Практические и лабораторные занятия Курсовая работа (проект) Самостоятельная работа студента ГЛОССАРИИ

Оформляется в соответствии с пунктом 6.3.1 настоящей документированной процедуры

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

Алгоритм линейной структуры (следова­ние)  – алгоритм, в котором все действия выполняются последовательно друг за другом

Ветвление  – схема, в которой предусмотрено разветвление указанной последовательности действий на два направления в зависимости от итога провер­ки заданного условия

Итерация  – повторение последовательности операторов, включающим проверку условия в начале каждого прохода цикла

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

Язык программирова­ния  –        система обозначений для точного описания алгоритмов для ЭВМ

Транслятор  – программа, осуществляющая перевод текстов с одного языка на другой

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

Интерпретатор  – программный продукт, выполняющий предъявленную программу пу­тем одновременного ее анализа и реализации предписанных ею дейст­вий

Уровень языка про­граммирования  – смысловая емкость его конструкций и его ориентация на программиста-человека

Алфавит языка про­граммирования –  набор символов, с помощью которого могут быть образованы величи­ны, выражения и операторы данного языка

       Программирование  –        процесс определения последовательности инструкций, которые дол­жен выполнить компьютер для решения определенной задачи

       Синтаксическая диа­грамма  – направленный граф для описания синтаксиса языка, в соответствии с которым строится синтаксически правильная программа

       Константа  – элемент  данных,  сохраняющий  неизменное значение в течение всего времени выполнения программы

Переменная  – объект,  имеющий фиксированное имя, фиксированный тип и изменяю­щееся в зависимости от применяемых действий значение

Идентификатор  – последовательность символов,  начинающаяся с буквы, для наименова­ния объектов

Тип данных  – множество значений,  которые может принимать переменная  и сово­купность операций, выполняемых с этими данными

Стандартные типы данных  – изначально определенные типы данных, встроенные в ЭВМ

Целый тип (INTEGER) – элементы подмножества целых чисел

Вещественный тип (REAL) – элементы подмножеств вещественного типа

Логический тип (BOOLEAN) – одно из двух истиностных значений, обозначаемых предопределенными именами false и true

Символьный (литер­ный) тип  – элементы конечного и упорядоченного множества символов

Скалярные перемен­ные  – переменные, имеющие в качестве текущего значения только одну вели­чину

Структурированная переменная  – переменная, состоящая из нескольких элементов или компонент, на которую можно ссылаться как на единый объект

Выражение  – совокупность операций и операндов

Оператор присваива­ния  – оператор,  присваивающий переменной или имени функции значение выражения, стоящего справа от знака присваивания 

       Составной оператор  – последовательность произвольных операторов программы, заключен­ная в операторные скобки (BEGIN-END)

       Условный оператор  – оператор с ключевыми словами IF-THEN-ELSE для программирова­ния алгоритмов разветвляющейся структуры

Оператор выбора  – оператор для программирования алгоритмов с множественным выбо­ром (CASE-OF-ELSE-END).

Оператор повторений WHILE-DO  – оператор для программирования алгоритмов циклической структуры с предпроверкой условия

Метка  – произвольный идентификатор, позволяющий именовать некоторый опе­ратор программы и таким образом ссылаться на него

Оператор перехода  – оператор передачи управления соответствующему меченному оператору (GOTO)

Данные - это значения или наборы значений, описывающие любую информацию, которую можно обработать на персональном компьютере.

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

Физическая структура данных - это схема размещения или хранения структуры в памяти компьютера (последовательность ячеек памяти).

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

Очередь - это линейный список с доступом только в начале и в конце списка. Элементы вставляются в конец списка и удаляются из начала (первый пришел - первый ушел).

Очередь приоритетов - это список типа очередь; при удалении объекта из списка определяется элемент с наивысшим приоритетом.

Файл  - это последовательность байтов, приравниваемая к потоку (последовательность байтов, перемещаемая от одного устройства к другому). Прямой доступ осуществляется только к дисковому файлу.

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

Дерево  - это  структура данных, в которой  все  элементы происходят от одного  источника,  называемого  корнем. Каждый  элемент, за исключением корня, имеет единственного предка.

Пирамида - это особая версия дерева, в котором самый маленький (большой) элемент всегда занимает корневой узел.

Множество - эта структура данных,  которая находит  применение, когда  данные  являются неупорядоченными и каждый элемент данных является единственным в своем роде, уникальным.

Граф - это структура данных, задающая набор вершин и  набор связей, соединяющих вершины.

Сеть - это особая  форма графа, которая присваивает вес каждой связи.

ЛЕКЦИИ

Лекция №1

Тема: Введение. Анализ алгоритмов. Сортировка и поиск. Анализ алгоритмов. Время выполнения программ. Алгоритмы сортировки массивов. Сортировка посредством выбора. Сортировка обменом (сортировка методом пузырька).

Цель: ввести основные понятия. Познакомить с видами сортировок.

Широкое распространение идей структурного программирования в последние 20-30 лет оказало большое влияние на теорию и практику программирования и привело к пересмотру роли типа и структуры данных при разработке соответствующих алгоритмов и программ. В связи с этим в последние десятилетия в учебных планах целого ряда ведущих отечественных и зарубежных университетов, проводящих подготовку специалистов в области программного обеспечения ЭВМ, появилась новая самостоятельная дисциплина – «типы и структуры данных».

Данная дисциплина является фундаментальным разделом компьютерной науки (Computer Science) информатики, который по своей сути закладывает начальные основы, без которых в настоящее время не представляется возможным подготовка высококвалифицированных специалистов в области информационных технологий и соответствующего программного обеспечения.

Идейное содержание данного курса является независимым от языка программирования, однако все примеры приведены на языке С++, в котором сочетаются простота трактовки и наглядность представления структур данных.

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

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

Данные – это значения или наборы значений, описывающие любую информацию, которую можно обработать на персональном компьютере.

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

Логическая или математическая модель организации данных называется структурой данных.

Различают следующие понятия: «логическая структура данных» и «физическая структура данных».

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

Физическая структура данных – это схема размещения или хранения структуры в памяти компьютера (последовательность ячеек памяти).

Всю совокупность данных можно разделить:

- на данные статической структуры;

- на данные динамической структуры.

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

Данные динамической структуры – это данные, внутреннее строение которых формируется по определенному закону, но количество элементов, их взаиморасположение и взаимосвязи могут динамически изменяться во время выполнения программы.