Home

Information

ИНТУИТ:

Инженерия программного обеспечения

:

Structures and Algorithms for Computer Data Processing

: Information
[-]
Created: 01.02.2011 | Level: for all | Access: paid
Комплекс лекций с упражнениями для обучения моделированию задач на базе основных структур данных, алгоритмизации и программированию в среде MS Visual Studio 2010. Каждая тема содержит лекционный материал, примеры программных кодов, задания для аудиторной и самостоятельной работы.
Комплекс лекций с упражнениями для обучения программированию на языке С++, ориентированный на работу в среде MS Visual Studio 2010. Каждая тема имеет следующую структуру: название темы, цель, ключевые слова, теоретическая часть (необходимый для выполнения работы теоретический материал, который отражает основные положения лекции по соответствующей теме), примеры программных кодов в среде MS Visual Studio 2010, комплекс задач для аудиторной и самостоятельной работы (задачи представлены в порядке возрастания сложности).
Goal: Формирование алгоритмической и информационной культуры студентов при обучении программированию на языке С++ в среде MS Visual Studio 2010.
Prerequisites: Освоение обязательного минимума содержания предметной области Информатика и ИКТ для средней школы; алгоритмических основ языка программирования С++; курсов математического анализа и аналитической геометрии для высшей школы.

План занятий

LessonTitle <<Date
-
Lecture 1
7 minutes
 -
Lecture 2
48 minutes
Типы данных в языке С++
В лекции рассматриваются понятие типов данных в языках программирования, приводится классификация типов данных в С++, излагаются особенности представления базовых типов и операций над ними, рекомендации и правила выполнения операции преобразования базовых типов в С++.
Contents
    		-
    Lecture 3
    27 minutes
    Подставляемые (встраиваемые) функции. Перегрузка функций
    В лекции рассматриваются понятия, объявление и использование в программах подставляемых и перегруженных функций в С++, механизмы выполнения подстановки и перегрузки функций, рекомендации по повышению эффективности программ за счет перегрузки или подстановки функций.
    Contents
      		-
      Lecture 4
      33 minutes
      Рекурсивные функции
      В лекции рассматриваются понятие, определения и виды рекурсии, рекурсивные функции, этапы решения задач рекурсивными способами через разработку рекурсивной триады, приводятся примеры решения задач рекурсивными способами.
      Contents
        		-
        Тест 1
        24 minutes
        		 -
        Lecture 5
        29 minutes
        Производные типы. Тип указатель: указатели на объекты
        В лекции рассматриваются определение и виды указателей, способы объявления, инициализация указателей на объекты, методы доступа к данным через указатели, размещение указателей и адресуемых ими объектов в памяти, операции над указателями.
        Contents
          		-
          Lecture 6
          23 minutes
          Тип указатель: указатели на функции
          В лекции рассматриваются определение указателя на функцию, способы объявления, адресуемость и обращение к функции через указатель, передачу фактических параметров указателю на функцию, использование указателя на функцию в качестве параметра функции.
          Contents
            		-
            Lecture 7
            26 minutes
            Решение задач с использованием указателей
            В лекции рассматриваются определение, реализация одиночного и многочисленного перенаправления с помощью указателей, определение, способы объявления, разработка и вызов функций с переменным числом параметров, дается обзор типичных ошибок, связанных с некорректным использованием указателей.
            Contents
              		-
              Тест 2
              24 minutes
              		 -
              Lecture 8
              28 minutes
              Символьные данные и строки
              В лекции рассматриваются понятия и определения символьных данных и строк, сходство и отличия их внутреннего представления, способы объявления, инициализация строк, методы доступа к элементам строк, определение размера строк, различные способы организации ввода/вывода символьных данных и строк.
              Contents
                		-
                Lecture 9
                28 minutes
                Функции для работы со строками
                В лекции рассматриваются библиотечные функции, предназначенные для работы со строками, и особенности их выполнения, приведены примеры использования таких функций при решении задач.
                Contents
                  		-
                  Lecture 10
                  19 minutes
                  Решение задач на обработку строк
                  В лекции рассматриваются понятие, способы объявления, инициализация указателей на строки, применение функций обработки строк при решении типовых задач, особенности выполнения стандартных функций в контексте представления строк и указателей на строки.
                  Contents
                    		-
                    Тест 3
                    24 minutes
                    		 -
                    Lecture 11
                    41 minute
                    Массивы: одномерные массивы
                    В лекции рассматриваются понятие и виды массивов в языках программирования, определение, объявление, инициализация, способы генерации и вывод одномерных массивов, расположение в памяти элементов массивов, связь между указателями и массивами.
                    Contents
                      		-
                      Lecture 12
                      22 minutes
                      Одномерные массивы: задачи поиска, замены и перестановок элементов массива
                      В лекции рассматривается классификация типовых задач на обработку одномерных массивов, приводятся примеры алгоритмизации задач поиска, замены и перестановок в одномерных массивах.
                      Contents
                        		-
                        Lecture 13
                        27 minutes
                        Одномерные массивы: задачи сортировок элементов массива
                        В лекции рассматриваются понятие и виды сортировок массивов, критерии оценки трудоемкости выполнения алгоритмов сортировок одномерных массивов, приводятся примеры реализации простых сортировок.
                        Contents
                          		-
                          Lecture 14
                          33 minutes
                          Двумерные массивы: задачи поиска, замены и суммирования элементов двумерного массива
                          В лекции рассматриваются понятие, определение, объявление, инициализация, генерация и вывод двумерных массивов, расположение в памяти элементов массивов, связь между указателями и двумерными массивами, типовые алгоритмы поиска, замены и суммирования в двумерных массивах.
                          Contents
                            		-
                            Lecture 15
                            21 minute
                            Двумерные массивы: задачи сортировок и перестановок в двумерных массивах
                            В лекции рассматриваются типовые задачи на обработку двумерных массивов, приводятся примеры алгоритмизации задач сортировок и перестановок в двумерных массивах.
                            Contents
                              		-
                              Тест 4
                              24 minutes
                              		 -
                              Lecture 16
                              34 minutes
                              Структуры
                              В лекции рассматриваются определения, способы объявления, инициализация структур, методы доступа к данным структуры, размещение структур и определение их размера в памяти, массивы структур.
                              Contents
                                		-
                                Lecture 17
                                28 minutes
                                Структуры и указатели
                                В лекции рассматриваются определения, способы объявления, инициализация указателей на структуры, ограничения на использование указателей как типов элементов структур, методы доступа к данным структуры через указатели, использование указателей на структуры как параметров и значений функций.
                                Contents
                                  		-
                                  Lecture 18
                                  28 minutes
                                  Объединения
                                  В лекции рассматриваются определения, способы объявления, объединений как частного случая структур, методы доступа к данным объединения, размещение объединений и определение их размера в памяти, использование объединений при объявлении переменных с изменяемой структурой.
                                  Contents
                                    		-
                                    Lecture 19
                                    25 minutes
                                    Битовые поля
                                    В лекции рассматриваются определение, объявление и размещение в памяти битовых полей, методы доступа к битовым полям, приемы использования битовых полей для побитового анализа данных.
                                    Contents
                                      		-
                                      Тест 5
                                      24 minutes
                                      		 -
                                      Lecture 20
                                      45 minutes
                                      Стандартные файлы и функции по работе с ними
                                      В лекции рассматриваются понятия и определения файлов и потоков, классификация файлов, стандартные функции по работе с файлами, основные алгоритмы работы с файлами, приводятся примеры решения задач на организацию ввода-вывода и обработку данных в файлах.
                                      Contents
                                        		-
                                        Lecture 21
                                        21 minute
                                        Обработка файлов в потоковом режиме
                                        В лекции рассматриваются понятие потокового режима при работе с файлами, потоки как типы данных, библиотечные функции ввода-вывода в потоковом режиме, примеры решения задач на обработку данных из файлов.
                                        Contents
                                          		-
                                          Lecture 22
                                          40 minutes
                                          Прямой доступ к данным файла
                                          В лекции рассматриваются понятие, особенности, способы организации и функции ввода-вывода в файлы на нижнем уровне, отличия низкоуровневого и потокового ввода-вывода в файлы, примеры, иллюстрирующие низкоуровневый обмен данными в файлах.
                                          Contents
                                            		-
                                            Lecture 23
                                            30 minutes
                                            Работа с элементами файлов
                                            В лекции рассматриваются особенности организации файлового ввода-вывода в С++ в потоковом и стандартном режимах, основные типы задач редактирования элементов файлов, способы алгоритмизации задач исключения, вставки и замены в файлах, приводятся примеры решения типовых задач.
                                            Contents
                                              		-
                                              Lecture 24
                                              32 minutes
                                              Решение задач на обработку файлов
                                              В лекции рассматриваются функции библиотеки классов потокового ввода-вывода, примеры реализации алгоритмов решения задач на обработку файлов.
                                              Contents
                                                		-
                                                Тест 6
                                                24 minutes
                                                		 -
                                                Lecture 25
                                                33 minutes
                                                Распределение памяти. Динамическое выделение памяти
                                                В лекции рассматриваются определения, распределение, способы выделения и освобождения динамической памяти, взаимодействие указателей и участков динамической памяти.
                                                Contents
                                                  		-
                                                  Lecture 26
                                                  28 minutes
                                                  Одномерные динамические массивы
                                                  В лекции рассматриваются определение, объявления, инициализация одномерных динамических массивов, способы выделения и освобождения динамической памяти под одномерный массив, доступ к элементам одномерного динамического массива.
                                                  Contents
                                                    		-
                                                    Lecture 27
                                                    28 minutes
                                                    Двумерные динамические массивы
                                                    В лекции рассматриваются определение, объявления, инициализация двумерных динамических массивов, способы и этапы выделения и освобождения динамической памяти под двумерный массив, доступ к элементам двумерного динамического массива.
                                                    Contents
                                                      		-
                                                      Lecture 28
                                                      37 minutes
                                                      Решение задач на динамические массивы
                                                      В лекции рассматриваются преимущества и недостатки управления динамической памятью, типичные ошибки при работе с динамической памятью, организация проверки выделения памяти, многомерные динамические массивы, приемы представления, чтения и записи динамических массивов.
                                                      Contents
                                                        		-
                                                        Тест 7
                                                        24 minutes
                                                        		 -
                                                        Lecture 29
                                                        31 minute
                                                        Динамические структуры данных
                                                        В лекции рассматриваются определение, способы объявления, инициализация динамических структур, методы доступа к данным динамических структур, размещение их в памяти, преимущества и недостатки использования динамических структур в программах.
                                                        Contents
                                                          		-
                                                          Lecture 30
                                                          47 minutes
                                                          Динамические структуры данных: однонаправленные и двунаправленные списки
                                                          В лекции рассматриваются определения и виды списков, структура, способы объявления однонаправленных и двунаправленных списков, основные операции над элементами списков, приводятся примеры решения задач с использованием однонаправленных и двунаправленных списков.
                                                          Contents
                                                            		-
                                                            Lecture 31
                                                            27 minutes
                                                            Динамические структуры данных: очередь и стек
                                                            В лекции рассматриваются определения стека и очереди как частных случаев линейных списков, структура, способы объявления стеков и очередей, основные операции над их элементами, приводятся примеры решения задач с использованием стеков и очередей.
                                                            Contents
                                                              		-
                                                              Lecture 32
                                                              35 minutes
                                                              Динамические структуры данных: бинарные деревья
                                                              В лекции рассматриваются определения, свойства и виды деревьев, элементы, характеристики и способы объявления деревьев в программах, основные операции над элементами деревьев, понятие и виды обходов деревьев, приводятся примеры реализации основных операций над бинарными деревьями в виде рекурсивных функций.
                                                              Contents
                                                                		-
                                                                Lecture 33
                                                                42 minutes
                                                                Решение задач на динамические структуры данных
                                                                В лекции рассматриваются определения, способы объявления, инициализация и особенности использования при решении задач циклических списков, деков, красно-черных деревьев, приводятся примеры решения задач на обработку кольцевых списков, деков, красно-черных деревьев.
                                                                Contents
                                                                  		-
                                                                  Тест 8
                                                                  24 minutes
                                                                  		 -
                                                                  Lecture 34
                                                                  41 minute
                                                                  Алгоритмы обработки данных
                                                                  В лекции рассматривается понятие ресурсной эффективности алгоритмов посредством анализа асимптотических функций временной и емкостной сложности, приводится классификация алгоритмов на основе функции временной сложности, рассматриваются общие методы оценки трудоемкости алгоритмов.
                                                                  Contents
                                                                    		-
                                                                    Lecture 35
                                                                    44 minutes
                                                                    Рекурсия и рекурсивные алгоритмы
                                                                    В лекции рассматриваются основные понятия рекурсии в контексте разработки алгоритмов с помощью рекурсивной триады, дается представление о ресурсной эффективности и о методе оценки рекурсивных алгоритмов через подсчет вершин рекурсивного дерева.
                                                                    Contents
                                                                      		-
                                                                      Lecture 36
                                                                      38 minutes
                                                                      Решение задач на использование рекурсивных алгоритмов
                                                                      В лекции рассматриваются опорные схемы решения задач рекурсивными способами, приводятся примеры разработки рекурсивных функций с помощью опорных схем.
                                                                      Contents
                                                                        		-
                                                                        Lecture 37
                                                                        38 minutes
                                                                        Алгоритм перебора с возвратом
                                                                        В лекции рассматривается общее и частное решения переборных задач, организация возвратной рекурсии, трудоемкость алгоритмов возвратной рекурсии, приводится пример решения задачи о расстановке ферзей на шахматной доске методом рекурсии с возвратом.
                                                                        Contents
                                                                          		-
                                                                          Тест 9
                                                                          24 minutes
                                                                          		 -
                                                                          Lecture 38
                                                                          32 minutes
                                                                          Алгоритмы поиска в линейных структурах
                                                                          В лекции рассматриваются определение и классификация алгоритмов поиска в линейных структурах данных, описания и примеры реализаций алгоритмов последовательного поиска, поиска с барьером, бинарного поиска, приводится оценка трудоемкости алгоритмов поиска в линейных структурах.
                                                                          Contents
                                                                            		-
                                                                            Lecture 39
                                                                            56 minutes
                                                                            Алгоритмы хеширования данных
                                                                            В лекции рассматриваются определение и виды хеширования, методы разрешения коллизий в хеш-таблицах, основные алгоритмы хеширования, приводятся примеры программной реализации открытого и закрытого хеширования.
                                                                            Contents
                                                                              		-
                                                                              Lecture 40
                                                                              30 minutes
                                                                              Алгоритмы поиска в тексте
                                                                              В лекции рассматриваются основные понятия и алгоритмы, используемые в задачах поиска в тексте и приводятся примеры реализации основных алгоритмов поиска в тексте.
                                                                              Contents
                                                                                		-
                                                                                Lecture 41
                                                                                48 minutes
                                                                                Алгоритмы поиска на основе деревьев
                                                                                В лекции рассматриваются определение и виды деревьев поиска, приемы снижения трудоемкости поиска в древовидных структурах, приводятся описания алгоритмов поиска в двоичных упорядоченных, случайных и сбалансированных в высоту (АВЛ) деревьях, приводятся примеры программной реализации бинарного дерева поиска и АВЛ-дерева.
                                                                                Contents
                                                                                  		-
                                                                                  Lecture 42
                                                                                  40 minutes
                                                                                  Алгоритмы сжатия данных
                                                                                  В лекции рассматриваются основные понятия и алгоритмы сжатия данных, приводятся примеры программной реализации алгоритма Хаффмана через префиксные коды и на основе кодовых деревьев.
                                                                                  Contents
                                                                                    		-
                                                                                    Тест 10
                                                                                    24 minutes
                                                                                    		 -
                                                                                    Lecture 43
                                                                                    51 minute
                                                                                    Алгоритмы сортировки массивов. Внутренняя сортировка
                                                                                    В лекции рассматриваются определение и классификация алгоритмов сортировок массивов, в частности, быстрых сортировок, изучаются параметры, характеризующие трудоемкость алгоритмов сортировок, рассматриваются описания и примеры программных кодов следующих алгоритмов быстрых сортировок: бинарная пирамидальная сортировка, сортировка слиянием, сортировка Шелла и сортировка Хоара.
                                                                                    Contents
                                                                                      		-
                                                                                      Lecture 44
                                                                                      32 minutes
                                                                                      Алгоритмы сортировки массивов. Внешняя сортировка
                                                                                      В лекции рассматриваются определение и классификация алгоритмов внешних сортировок, понятия фаз и путей в алгоритмах внешних сортировок, приводятся описания и реализации алгоритмов внешней сортировки слиянием и естественной сортировки.
                                                                                      Contents
                                                                                        		-
                                                                                        Lecture 45
                                                                                        33 minutes
                                                                                        Алгоритмы на графах. Алгоритмы обхода графа
                                                                                        В лекции рассматриваются основные понятия из теории графов, модели представления графов, на основе которых приводятся описания и реализации алгоритмов поиска в глубину и в ширину.
                                                                                        Contents
                                                                                          		-
                                                                                          Lecture 46
                                                                                          40 minutes
                                                                                          Алгоритмы на графах. Алгоритмы нахождения кратчайшего пути
                                                                                          В лекции рассматриваются постановка задачи и описание алгоритмов нахождения кратчайшего пути в графах, приводятся программные реализации алгоритмов Дейкстры, Флойда и переборного алгоритма.
                                                                                          Contents
                                                                                            		-
                                                                                            Lecture 47
                                                                                            54 minutes
                                                                                            Решение задач на использование алгоритмов обработки данных
                                                                                            В лекции даются общие рекомендации по решению задач повышенной сложности, рассматривается примеры программной реализации задач обработки данных, которые решаются с помощью алгоритмов сортировок, обходов графа и сжатия данных.
                                                                                            Contents
                                                                                              		-
                                                                                              Тест 11
                                                                                              24 minutes
                                                                                              		 -
                                                                                              Lecture 48
                                                                                              2 hours 21 minute
                                                                                              Задания
                                                                                              Contents
                                                                                                		-
                                                                                                Lecture 49
                                                                                                		 -
                                                                                                5 hours
                                                                                                		 -