Сборник заданий по методам программирования icon

Сборник заданий по методам программирования



НазваниеСборник заданий по методам программирования
страница1/15
Дата конвертации26.10.2012
Размер0.62 Mb.
ТипУчебно-методическое пособие
  1   2   3   4   5   6   7   8   9   ...   15

- -



СБОРНИК ЗАДАНИЙ ПО МЕТОДАМ ПРОГРАММИРОВАНИЯ


Учебно-методическое пособие





Москва 2005

Введение

Данное пособие является дополнением к курсу лекций Методы программирования. В соответствии с рассматриваемыми в курсе темами все задания разбиты на группы:

  • Структуры данных

  • Алгоритмы сортировки

  • Алгоритмы поиска

  • Алгоритмы исчерпывающего поиска

  • Алгоритмы поиска подстрок

  • Комбинаторные алгоритмы

  • Алгоритмы на графах


Целью заданий является:

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

  • их реализация на языке высокого уровня;

  • проведение серии экспериментов, подтверждающих теоретические оценки трудоемкости.

Описание задания содержит рекомендации, необходимую информацию или ссылки на нее. Дополнительные сведения об используемых математических понятиях и алгоритмах можно найти в [1-6]. Возможно два различных подхода к выдаче долгосрочных заданий:

  1. Несколько простых заданий, охватывающих все основные алгоритмы.

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

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

Задания повышенной сложности и требующие самостоятельного углубленного изучения ряда вопросов помечены (*).

СПИСОК ДОЛГОСРОЧНЫХ ДОМАШНИХ ЗАДАНИЙ


^

ТЕМА 1.Структуры данных

    1. Линейный список (в виде массивов)


Задача:

Создается структура данных линейный односвязный список с необходимым набором операций:

      • -создать пустой список;

      • -добавить элемент в список;

      • -добавить элемент после заданного;

      • - удалить элемент из списка;

      • - найти элемент в списке;

      • - сортировка элементов списка;

      • - добавить элемент в отсортированный список;

      • - просмотр всех элементов списка;

      • - просмотр всех элементов списка по циклу.

Под структуру данных выделяется непрерывный участок памяти.


Указания:

При работе с созданной структурой необходимо анализировать ситуацию, когда число элементов в списке превысит допустимое количество. В этой ситуации необходимо выделять дополнительно необходимое количество памяти, если это возможно.
Подробное описание линейного списка и работы с ним можно найти в [2,3,12].
    1. ^

      Линейный список (с помощью указателей)



Задача:

Создается структура данных линейный односвязный список с необходимым набором операций:

  • создать пустой список;

  • добавить элемент в список;

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

  • удалить элемент из списка;

  • найти элемент в списке;

  • сортировка элементов списка;

  • добавить элемент в отсортированный список;

  • просмотр всех элементов списка.

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


Указания:

При работе с созданной структурой необходимо в случае удаления элемента освобождать выделенную под его хранение память. Подробное описание линейного списка и работы с ним можно найти в [2,3,12].


    1. ^

      Умножение двух разреженных матриц



Определение. Матрица М размера n×m называется разреженной, если число ненулевых элементов не превосходит min(n,m).


Задача:

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


Указания:

Для хранения матриц используются линейные односвязные списки. С целью минимизации числа операций необходимо стремиться к уменьшению проходов по спискам. Можно, например, вначале транспонировать вторую матрицу. С помощью генератора случайных чисел создать 20 разреженных матриц. Для 10 произвольно взятых пар подсчитать число реально выполняемых операций при их умножении. Подробное описание можно найти в [8].


    1. ^

      Умножение двух многочленов, хранящихся в виде списков



Задача:

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


Указания:

Для хранения многочленов использовать линейные односвязные списки. С целью минимизации числа операций необходимо стремиться к уменьшению проходов по спискам. С помощью генератора случайных чисел создать 20 многочленов. Для 10 произвольно взятых пар подсчитать число реально выполняемых операций при их умножении. Подробное описание линейного списка, работы с ним и алгоритма умножения разреженных матриц можно найти в [2,3,8,12].


  1   2   3   4   5   6   7   8   9   ...   15



Похожие:

Сборник заданий по методам программирования iconДокументы
1. /CИСТЕМА ПРОГРАММИРОВАНИЯ НА МАКРОАССЕМБЛЕРЕ MS-DOS/A1P0.TXT
2. /CИСТЕМА...

Сборник заданий по методам программирования iconДокументы
1. /Страуструп - Язык программирования С++/CHAP000.TXT
2. /Страуструп...

Сборник заданий по методам программирования iconЛинейное программирование. Методы решения одношаговых задач оптимального управления
Методы решения таких задач получили название математического программирования. Простейшим случаем математического программирования...
Сборник заданий по методам программирования iconСборник заданий для лабораторных и семестровых работ
Учебное пособие предназначено для студентов всех специальностей, изучающих курс «Информатика»
Сборник заданий по методам программирования iconДокументы
1. /Задачи по численным методам.doc
2. /Э-БИЛЕТЫ...

Сборник заданий по методам программирования iconИнструкция по выполнению работы Экзаменационная работа по немецкому языку состоит из пяти разделов, включающих 48 заданий
Аудирование включает 15 заданий, из которых первое – на установление соответствия и 14 заданий с выбором правильного ответа. Рекомендуемое...
Сборник заданий по методам программирования iconФизика характеристика контрольных измерительных материалов единого государственного экзамена по физике в 2009 г
Экзаменационная работа по физике для егэ-2009 содержала 36 заданий: 25 заданий с выбором ответа (часть 1), 5 заданий с кратким ответом...
Сборник заданий по методам программирования iconИнструкция по выполнению работы Экзаменационная работа по английскому языку состоит из пяти разделов, включающих 48 заданий
Аудирование включает 15 заданий, из которых первое – на установление соответствия и 14 заданий с выбором одного правильного ответа...
Сборник заданий по методам программирования iconИнструкция по выполнению работы Экзаменационная работа по французскому языку состоит из пяти разделов, включающих 48 заданий
Аудирование включает 15 заданий, из которых первое – на установление соответствия и 14 заданий с выбором одного правильного ответа...
Сборник заданий по методам программирования iconМинистерство образования Российской Федерации
Тьюринга, теория рекурсивных функций. Также в пособие включены сведения, имеющие практическое применение в области программирования:...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов