Разработка системы задач (алгоритмы-программы) по дискретной математике

    Дисциплина: Программирование
    Тип работы: Курсовая
    Тема: Разработка системы задач (алгоритмы-программы) по дискретной математике

    Вятский Государственный Гуманитарный Университет
    Кафедра прикладной математики
    Курсовая работа по информатике
    Тема: Разработка системы упражнений и задач (алгоритмы-программы) по дискретной математике.
    Выполнил:Студент 4 курса
    факультета информатики
    Лепешкин Антон Геннадъевич
    Проверила: Ашихмина Татьяна Викторовна
    Киров 2004
    Содержание.
    TOC \\o \"1-3\" \\h \\z \\u
    Содержание.
    PAGEREF _Toc90286509 \\h
    Введение.
    PAGEREF _Toc90286510 \\h
    Глава 1 Теоретический материал.
    PAGEREF _Toc90286511 \\h
    Перебор с возвратом.
    PAGEREF _Toc90286513 \\h
    Поиск данных.
    PAGEREF _Toc90286514 \\h
    Логарифмический(бинарный) поиск
    PAGEREF _Toc90286515 \\h
    Методы сортировки.
    PAGEREF _Toc90286516 \\h
    Сортировка слияниями.
    PAGEREF _Toc90286517 \\h
    Быстрая сортировка Хоара.
    PAGEREF _Toc90286518 \\h
    Графы.
    PAGEREF _Toc90286519 \\h
    Представление графа в памяти компьютера
    PAGEREF _Toc90286520 \\h
    Достижимость
    PAGEREF _Toc90286521 \\h
    Кратчайшие пути.
    PAGEREF _Toc90286522 \\h
    Алгоритм Дейкстры
    PAGEREF _Toc90286523 \\h
    Алгоритм Флойда (кратчайшие пути между всеми парами вершин).
    PAGEREF _Toc90286524 \\h
    Глава 2 Система задач и упражнений.
    PAGEREF _Toc90286525 \\h
    Классификация задач.
    PAGEREF _Toc90286526 \\h
    Комнаты музея.
    PAGEREF _Toc90286527 \\h
    Пират в подземелье.
    PAGEREF _Toc90286528 \\h
    Диспетчер и милиция.
    PAGEREF _Toc90286529 \\h
    Задача о футболистах.
    PAGEREF _Toc90286530 \\h
    Задача о семьях.
    PAGEREF _Toc90286531 \\h
    Метро.
    PAGEREF _Toc90286532 \\h
    Роботы.
    PAGEREF _Toc90286533 \\h
    Вожатый в лагере
    PAGEREF _Toc90286534 \\h
    Егерь.
    PAGEREF _Toc90286535 \\h
    Игра «Найди друга».
    PAGEREF _Toc90286536 \\h
    Приложение.
    PAGEREF _Toc90286537 \\h
    PAGEREF _Toc90286538 \\h
    PAGEREF _Toc90286539 \\h
    PAGEREF _Toc90286540 \\h
    PAGEREF _Toc90286541 \\h
    PAGEREF _Toc90286542 \\h
    PAGEREF _Toc90286543 \\h
    PAGEREF _Toc90286544 \\h
    PAGEREF _Toc90286545 \\h
    PAGEREF _Toc90286546 \\h
    PAGEREF _Toc90286547 \\h
    Заключение.
    PAGEREF _Toc90286548 \\h
    Литература
    PAGEREF _Toc90286549 \\h
    Введение.
    Несмотря на то, что для решения задач в основном используются общие методы, все-таки мышление каждого конкретного человека немного отличается от мышления других людей, если он
    обладает достаточной базой знаний. Таким образом, при решении задач «начиная с нуля» можно зайти в тупик, если выбрать неверный путь решения задачи. В данном курсовом проекте мы
    разработаем собственную классификацию задач, позволяющую определить наиболее подходящий способ решения, чтобы облегчить процесс моделирования и составления алгоритма и предотвратить
    выбор неверного способа, также рассмотрим данную классификацию с точки зрения методики преподавания информатики.
    выбор неверного способа. В этом заключается актуальность данного курсового проекта.
    Цель:
    Разработать собственную классификацию для задач по дискретной математике. Для достижения этой цели были поставлены следующие задачи:
    Разработать собственную систему задач и упражнений по дискретной математике.
    Определить способы решения данных задач, используя теоретический материал курса дискретной математики.
    Составить алгоритм – программу для каждой задачи, реализующий выбранный способы решения.
    Разработать систему критериев классификации данной системы задач.
    Глава 1 Теоретический материал.
    Перебор с возвратом.
    Общая схема
    Даны N упорядоченных множеств U1 U2,..., Un (N - известно), и требуется построить вектор А=(а1 а2, ..., а
    ), где a1
    U1, a2
    U2, ..., a
    , удовлетворяющий заданному множеству условий и ограничений.
    Начало
    Выборы для А1
    Выборы для А2 при А1
    Выборы для А3 при данных А1 и А2
    В алгоритме перебора вектор А строится покомпонентно слева
    направо. Предположим, что уже найдены значения первых (к-1)
    компонент, A=(a1, a2, ..., a
    ), ?, ..., ?), тогда заданное множество
    условий ограничивает выбор следующей компоненты а
    некоторым
    множеством S
    k. Если Sk[ ] (пустое), мы вправе выбрать в
    качестве а
    наименьший элемент
    перейти
    выбору
    \"^выборы п«я»,
    (к+1) компоненты и
    так
    далее.
    Однако
    Jfcv
    при данном а,
    если условия
    условия
    а,, ^иаз
    таковы, что Sk оказалось пустым, то мы возвращаемся к выбору
    (к-1) компоненты, отбрасываем
    и выбираем в качестве нового a
    (k-1) тот элемент S
    (k-i), который непосредственно следует за только что отброшенным. Может оказаться, что для нового
    (k-1)
    условия задачи допускают непустое Sk, и тогда мы пытаемся снова выбрать элемент а
    к. Если невозможно выбрать
    (k-1)
    , мы возвращаемся еще на шаг назад и выбираем новый элемент а
    (к-2) и так далее.
    Графическое изображение - дерево поиска. Корень дерева (0 уровень) есть пустой вектор. Его сыновья суть множество кандидатов для выбора а1 и,
    в общем случае, узлы k-го уровня являются кандидатами на выбор а
    к при условии, что а1, а2, ..., a
    (k-1) выбраны так, как указывают предки этих узлов. Вопрос о том, имеет ли задача решение, равносилен вопросу, являются ли какие-нибудь узлы дерева решениями. Разыскивая все
    решения, мы хотим получить все такие узлы.
    Рекурсивная схема реализации алгоритма,
    procedure
    Backtrack
    кт
    begin
    else begin
    for a
    Si do Васк
    аск(вектор| | a,i+l); {| | - добавление к вектору компоненты}
    end; end;
    Оценка временной сложности алгоритма. Данная схема реализации перебора приводит к экспоненциальным алгоритмам. Действительно, Пусть все решения имеют длину N, тогда исследовать
    требуется порядка | Si| *| S2| *...*| SN| узлов дерева. Если значение S; ограничено некоторой константой С, то получаем порядка C
    N узлов.
    Поиск данных.
    Логарифмический(бинарный) поиск
    Логарифмический (бинарный или метод деления пополам) по­
    иск данных применим к сортированному множеству элементов
    1 а
    2 а
    размещение которого выполнено на смежной па­
    мяти. Для большей эффективности поиска элементов надо, чтобы
    пути доступа к ним стали более короткими, чем просто последова­
    тельный перебор. Наиболее очевидный метод: начать поиск со
    среднего элемента, т.е. выполнить сравнение с элементом а.
    Результат сравнения позволит определить, в какой половине по­
    следовательности а
    2,...,
    ,,...,
    п продолжить поиск,
    применяя к ней ту же процедуру, и т.д. Основная идея бинарного
    поиска довольно проста, однако «для многих хороших програм­мистов не одна попытка написать правильную программу закон­чилась неудачей». Чтобы досконально разобраться в алгоритме,
    лучше всего представить данные а
    х а
    2 а
    п в виде двоичного
    дерева сравнений, которое отвечает бинарному поиску.
    Двоичное дерево называется деревом сравнений , если для лю­
    бой его вершины (корня дерева или корня поддерева) выполняет­
    ся условие:
    {Вершины левого поддерева}{Вершины
    правого поддерева
    Рис
    Пример
    дерева
    сравнений
    отвечающего
    бинарному
    поиску среди
    сортированных
    элементов
    : 3,5,7,9,12,19,27,44
    Т.о. бинарный поиск – это сравнение эталона х, которое осуществляется с элементом, расположенным в середине массива и в зависимости от результата сравнения (больше или меньше)
    дальнейший поиск проводится в левой или правой половине массива.
    Используется, когда имеется какая-либо инф...

    Забрать файл

    Похожие материалы:


ПИШЕМ УНИКАЛЬНЫЕ РАБОТЫ
Заказывайте напрямую у исполнителя!


© 2006-2016 Все права защищены