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

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

Литература:
• Кнут Д. Искусство программирования. т.1,2,3,4. Третье издание. Вильямс, 2010. (1968, 1969, 1973, 2005)
• Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. - ИД
Вильямс, 2003.
• Вирт Н. Алгоритмы + структуры данных = программы. – Невский диалект,
2008. (1985)
• Вирт Н. Алгоритмы и структуры данных. – Невский диалект, 2008. (1989)
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение
и анализ. - Вильямс, 2010.
• Каррано Ф., Причард Дж. Абстракция данных и решение задач на
C++. Стены и зеркала, 3-е издание. – Вильямс, 2003. (2002)
• Кубенский А.А. Структуры и алгоритмы обработки данных. Объектноориентированный подход и реализация на С++. – БХВ-Петербург, 2004.
• Гудрич М., Томасия Р. Структуры данных и алгоритмы в Java. – Минск:
Новое знание, 2003. (2001)

2. Цели и задачи курса

Цель – научиться технике конструирования и формулирования
алгоритмов, описывающих некоторые типовые процессы
обработки данных.
Задачи:
1.
2.
3.
4.
5.
6.
Алгоритмы и структуры данных взаимосвязаны.
Использовать приемы, не зависящие от конкретных приложений.
Язык инструмент, а не самоцель.
Абстрактные типы данных и структуры данных — не одно и то же.
От сложного к простому через рекурсию.
Оценка эффективности алгоритмов – составная часть компьютерного
решения задач.

3. Структура курса (1 часть)

Указатели
Динамические структуры данных
Абстрактные типы данных
(стеки, очереди, деревья)
Рекурсия
Управление памятью
Эффективность алгоритмов

4. Структура курса (2 часть)

Хеш-таблицы
Сортировка
Поиск
Комбинаторные алгоритмы

5. Основные понятия - память

Фон-Неймановская
архитектура
Однородность памяти
Куча
Область кода
Область данных
(статическая)
Память программы
Область данных
(динамическая)
Свободная память
(куча)

6. Основные понятия - данные

тип данных - множество значений, которые может принимать переменная
int a;
// объявление переменной a целого типа
float b;
// объявление переменной с плавающей запятой
char d = 's';
// инициализация переменной типа char
структура данных - набор переменных, возможно, различных типов данных,
объединенных определенным образом (способ организации данных)
struct str_name
{
int member_1;
float member_2;
};
Абстрактный тип данных - это тип данных, который предоставляет
для работы с его элементами определённый набор функций.
class Stack
{ …………………
void Push(int i);
int Pop();
bool isEmpty();
………………….
};

7. Основные понятия - алгоритм

Алгоритм - точная конечная последовательность действий,
обеспечивающая получение требуемого результата из заданных
исходных данных.
Основные свойства алгоритмов:
1. Дискретность
2. Определенность (детерминированность)
3. Результативность
4. Массовость
5. Эффективность
Начало
m;n;
Алгоритм Евклида.
Найти наибольший общий
делитель для целых m>n.
r=m%n;
m=n;n=r;
Нет
r==0
Да
n;
Конец