Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное
учреждение высшего профессионального образования
Кубанский государственный технологический университет
(ФГБОУ ВПО КубГТУ )
Факультет компьютерных технологий и автоматизированных систем
Кафедра ИСП
КУРСОВАЯ РАБОТА
По дисциплине «Дискретная математика»
На тему: «Задачи и алгоритмы дискретной математики»
Выполнил студент группы 12-КБ-ПИ1 Дискант Александр Александрович
(Ф.И.О.)
Руководитель работы _________к.т.н., доцент_____________ Е.А. Симоненко
(подпись, дата, расшифровка подписи)
Защищён __________________ Оценка______________________
(дата)
Члены комиссии _____________________________________ Е.А. Симоненко
(подпись, дата, расшифровка подписи)
________________________________________________________ А.Г. Волик
(подпись, дата, расшифровка подписи)
(подпись, дата, расшифровка подписи)
Краснодар
2013
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное
учреждение высшего профессионального образования
Кубанский государственный технологический университет
(ФГБОУ ВПО КубГТУ)
Факультет компьютерных технологий и автоматизированных систем
Кафедра ИСП
УТВЕРЖДАЮ
Зав. кафедрой ИСП
профессор Л.А. Видовский
«___» 2013 г.
ЗАДАНИЕ
на курсовую работу
Студенту Дискант А.А группы 12-КБ-ПИ-1 2 курса
факультета Компьютерных технологий и автоматизированных систем
направление 230700.62 Прикладная информатика
Тема работы: "Задачи и алгоритмы дискретной математики"
Содержание задания: Разработать Windows-приложение, для решения задач и алгоритмов дискретной математики
(коротко раскрыть основной смысл задания на курсовую работу)
Объём курсовой работы:
а) пояснительная записка 17 стр.;
б) программа.
Рекомендуемая литература Скиена С. Алгоритмы. Руководство по разработке. Фленов М.Е. Библия C#.
Срок выполнения проекта: с «2» сентября 2013г. по «21» декабря 2013г.
Срок защиты: «21» декабря 2013г.
Дата выдачи задания: «2» сентября 2013г.
Дата сдачи работы на кафедру: с «2» декабря 2013г. по «21» декабря 2013г.
Руководитель работы __________________________________Е.А. Симоненко
(подпись)
Задание принял студент _________________________________А.А. Дискант
(подпись)
Реферат
Пояснительная записка к курсовой работе 17 страниц, 3 рисунка, 5 источников, 2 приложения.
MICROSOFT VISUAL STUDIO 2010, ФОРМА, STRING, LABEL, BUTTON, UNICODE, TOOLSTRIP, MENUSTRIP, COMBOBOX, CHECKBOX
В данной курсовой работе рассмотрены вопросы решения по задачам и алгоритмам дискретной математики. Были рассмотрены такие темы как: «Топологическая сортировка» и «Цепные дроби».
Основными моментами проведённого исследования были:
Проделанная работа даст представление о способах решения приведенных задач и их наглядной реализации.
Введение 5
1 Нормативные ссылки 7
2 Постановка задачи 8
3 Описание входных и выходных данных 9
4 Технология разработки приложения 10
5 Описание программы 11
6 Руководство пользователя 14
Список используемых источников 18
Приложение А Листинг программы 19
Топологическая сортировка упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин.
При помощи топологической сортировки строится корректная последовательность выполнения действий, всякое из которых может зависеть от другого: последовательность прохождения учебных курсов студентами, установки программ при помощи пакетного менеджера, сборки исходных текстов программ при помощи Makefile'ов.
Можно построить список отображения объектов в изометрической проекции зная парные порядковые отношения между объектами (какой из двух объектов должен быть прорисован раньше).
Цепная дробь (или непрерывная дробь) это математическое выражение, где a0 есть целое число и все остальные an натуральные числа (положительные целые). Любое вещественное число можно представить в виде цепной дроби (конечной или бесконечной). Число представляется конечной цепной дробью тогда и только тогда, когда оно рационально. Число представляется периодической цепной дробью тогда и только тогда, когда оно является квадратичной иррациональностью.
В данной пояснительной записке использованы ссылки на следующие стандарты.
ГОСТ Р 50739-95 Средства вычислительной техники. Защита от несанкционированного доступа к информации. Общие технические требования
ГОСТ 2.105-95 Общие требования к текстовым документам
ГОСТ 2.301-68 Единая система конструкторской документации. Форматы
ГОСТ 7.32-2001 СИБИД. Отчет о научно-исследовательской работе. Структура и правила оформления
ГОСТ 7.1-2003 СИБИД. Библиографическая запись. Библиографическое описание документа. Общие требования и правила составления
ГОСТ 7.80-2000 СИБИД. Библиографическая запись. Заголовок. Общие требования и правила составления
ГОСТ 19.701-90 СТД. (ИСО 5807-85) ЕСПД. Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения
ГОСТ 34.601-90 Информационная технология. Комплекс стандартов на автоматизированные системы. Автоматизированные системы. Стадии создания
ОК 015-94 (МК002-97) Общероссийский классификатор единиц измерения
МР КубГТУ 4.4.3-2004 СМК. УМД. Выпускные квалификационные работы
Необходимо написать программу реализующую топологической сортировки и вычисления цепных дробей, используя C#.
Используя язык высокого уровня С#, создать приложение, позволяющее обычному пользователю справиться с такой задачей, как вычисление цепной дроби. Для облегчения использования приложения, разработать доступный пользователю интерфейс, содержащий следующие средства:
Чтобы создать приложение, следует:
Обработка значений происходит так:
static double Function(int x, int n, int max)
{
if (n == max) return n + x;
if (n == 1) return x * 1.0 / (n + x * 1.0 / Function(x, n + 1, max));
return n + (x * 1.0 / Function(x, n + 1, max));
}
Задается числитель и знаменатель:
int n=50, ch=0, zn=0;
int[] h = new int[n];
int[] z = new int[n];
int[] v = new int[n];
Console.WriteLine("Введите числитель: ");
ch= Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Введите знаменатель: ");
zn=Convert.ToInt32(Console.ReadLine());
Console.Clear();
Console.Write("Значение дроби: {0}/{1} = ( ", ch, zn);
Подсчет и запись в консоли цепной дроби происходит следующим образом:
for (int i=0; i<n; i++)
{
h[0] = ch;
z[0] = zn ;
if (z[i] == 0) break;
else
{
v[i] = h[i] / z[i];
Console.Write(v[i]+" ");
z[i + 1] = h[i] - z[i] * v[i];
h[i + 1] = z[i];
}
}
Console.Write(")");
Console.ReadKey();
}
}
}
Обход графа с целью топологической сортировки:
public static void DFS(int u, int[,] c, int[,] g, int n)
{
int t = 0;
for (int i = 0; i < n; i++)
{
if (g[u, i] == 1 && c[u, i] == 0)
{
Покраска вершины в серый цвет, это означает, что вершина посещена.
c[u, i] = 1; //grey
t = u;
u = i;
i = t;
DFS(u, c, g, n);
}
if (g[u, i] == 1 && c[u, i] == 1)
{
Покраска в черный цвет.
c[u, i] = 2; //black
Console.WriteLine("(" + (u+1) + ", " + (i+1) + ")");
t = u;
if(i<n-1)
u = i+1;
i = t;
DFS(u, c, g, n);
}
}
}
Массив вершин и цветов:
int n = 4, u = 0;
int[,] g = new int[n, n];
int[,] c = new int[n, n];
Матрица смежности графа.
g[0, 0] = 0; g[0, 1] = 0; g[0, 2] = 0; g[0, 3] = 1;
g[1, 0] = 0; g[1, 1] = 0; g[1, 2] = 0; g[1, 3] = 1;
g[2, 0] = 0; g[2, 1] = 0; g[2, 2] = 0; g[2, 3] = 1;
g[3, 0] = 1; g[3, 1] = 1; g[3, 2] = 1; g[3, 3] = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
Console.Write(g[i, j] + " ");
Console.WriteLine();
}
Console.WriteLine();
DFS(u, c, g, n);
Console.ReadKey();
}
}
}
Для работы с программой по решению задач и алгоритмов дискретной математики необходимо иметь минимальные требования, указанные ниже.
Компьютер:
Программное обеспечение:
Как пользоваться программой:
Рисунок 1 Окно программы топологической сортировки
Рисунок 2 Окно программы вычисления цепных дробей
Рисунок 3 Пример вычисления цепной дроби
Заключение
В ходе выполнения курсовой работы были изучены следующие вопросы:
Достоинствами данной программы являются:
Недостатками данной программы являются:
Была составлена программа для топологической сортировки графа, а также для вычисления церных дробей. После проведённых тестов, был сделан вывод, что программы работают корректно, следовательно, поставленная задача выполнена.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace цеп
{
class Program
{
static double Function(int x, int n, int max)
{
if (n == max) return n + x;
if (n == 1) return x * 1.0 / (n + x * 1.0 / Function(x, n + 1, max));
return n + (x * 1.0 / Function(x, n + 1, max));
}
static void Main(string[] args)
{
int n = 50, ch = 0, zn = 0;
int[] h = new int[n];
int[] z = new int[n];
int[] v = new int[n];
Console.WriteLine("Введите числитель: ");
ch = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Введите знаменатель: ");
zn = Convert.ToInt32(Console.ReadLine());
Console.Clear();
Console.Write("Значение дроби: {0}/{1} = ( ", ch, zn);
for (int i = 0; i < n; i++)
{
h[0] = ch;
z[0] = zn;
if (z[i] == 0) break;
else
{
v[i] = h[i] / z[i];
Console.Write(v[i] + " ");
z[i + 1] = h[i] - z[i] * v[i];
h[i + 1] = z[i];
}
}
Console.Write(")");
Console.ReadKey();
}
}
}
Приложение Б Листинг программы
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
public static void DFS(int u, int[,] c, int[,] g, int n)
{
int t = 0;
for (int i = 0; i < n; i++)
{
if (g[u, i] == 1 && c[u, i] == 0)
{
c[u, i] = 1; //grey
t = u;
u = i;
i = t;
DFS(u, c, g, n);
}
if (g[u, i] == 1 && c[u, i] == 1)
{
c[u, i] = 2; //black
Console.WriteLine("(" + (u+1) + ", " + (i+1) + ")");
t = u;
if(i<n-1)
u = i+1;
i = t;
DFS(u, c, g, n);
}
}
}
static void Main(string[] args)
{
int n = 4, u = 0;
int[,] g = new int[n, n];
int[,] c = new int[n, n];
g[0, 0] = 0; g[0, 1] = 0; g[0, 2] = 0; g[0, 3] = 1;
g[1, 0] = 0; g[1, 1] = 0; g[1, 2] = 0; g[1, 3] = 1;
g[2, 0] = 0; g[2, 1] = 0; g[2, 2] = 0; g[2, 3] = 1;
g[3, 0] = 1; g[3, 1] = 1; g[3, 2] = 1; g[3, 3] = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
Console.Write(g[i, j] + " ");
Console.WriteLine();
}
Console.WriteLine();
DFS(u, c, g, n);
Console.ReadKey();
}
}
}