Понятие алгоритма и его свойства

Автор работы: Пользователь скрыл имя, 05 Ноября 2013 в 17:57, лекция

Описание работы

Целью данной лекции является изучение основ алгоритмизации, уяснение понятия и этапов эволюции технологии программирования.

Содержание работы

Введение
1. Основы алгоритмизации
1.1 Понятие алгоритма и его свойства
1.2 Способы представления алгоритмов
2. Основы программирования
3. Понятие формализация

Файлы: 1 файл

Вычислительное программирование.doc

— 407.00 Кб (Скачать файл)

· ключевые слова;

· данные;

· выpажения и  т.д.

Операторы подpазделяются на исполняемые и неисполняемые. Неисполняемые опеpатоpы пpедназначены для описания данных и стpуктуpы пpогpаммы, а исполняемые -- для выполнения pазличных действий (напpимеp, опеpатоp пpисваивания, опеpатоpы ввода и вывода, условный оператор, операторы цикла, оператор процедуры и дp.).

6. Стандартные функции - заранее запрограммированные и встроенные в транслятор языка подпрограммы вычисления часто употребляемых функций.

В табл. 1.2 приведены  стандартные функций языка Turbo Pascal.

Таблица 1.2. Примеры стандартных математических функций

 

Название и  обозначение функции

Указатель функции

 

Абсолютная  величина (модуль)

| х |

abs(x)

 

Корень квадратный

 

sqrt(x)

 

Возведение  в квадрат

х2

sqr(х)

 

Натуральный логарифм

ln x

ln(x)

 

Экспонента

ex

exp(x)

 

Синус (угол в  радианах)

sin x

sin(x)

 

Косинус (угол в  радианах)

cos x

cos(x)

 

Арктангенс (главное значение в радианах)

arctg x

arctan(х)

 

Целая часть  числа

 

int(x), trunc(х)

 

Дробная часть  числа

 

frac(x)

 

Округленное до целого число. При х>=0 round(х) означает trunc(х+0.5), при x<0 - trunc(x-0.5)

 

round(х)

 

Число «пи»

 

Pi

 
       

В качестве аргументов функций можно использовать константы, переменные и выражения.

2. Основы программирования 
 
       Языки программирования служат самым разнообразным целям – от решения сложных математических задач и проведения экономико-математических расчетов до создания музыкальной партитуры и машинной графики. Попытки создания совершенного языка программирования предпринимается столько же лет, сколько существует само программирование. В результате этого поиска компанией Microsoft был разработан язык С#, соответствующий современным стандартам программирования и предназначенный для поддержки развития технологии .NET Framework. Этот язык представляет эффективный метод написания программ для современных компьютерных систем предприятий, которые используют операционную систему Windows и компоненты Internet. 
 
Компьютерные языки взаимосвязаны, а не существуют сами по себе. Каждый новый язык в той или иной форме наследует свойства ранее созданных языков, то есть осуществляется принцип преемственности. В результате возможности одного языка используются другими (например, новые характеристики интегрируются в уже существующий контекст, а старые конструкции языка удаляются). Так происходит эволюция компьютерных языков и совершенствуется искусство программирования. 
 
Язык С# не является исключением, он унаследовал много полезных возможностей от других языков программирования и напрямую связан с двумя наиболее широко применяемыми в мире компьютерными языками – C и C++, а также с языком Java. 
 
Хотя С# как язык программирования может изучаться изолировано, лучше рассматривать его во взаимосвязи с .NET Framework – средой, в которой он работает. Потому что, во первых, С# изначально разрабатывался компанией Microsoft для создания кода .NET Framework, во-вторых, .NET Framework определяет библиотеки, используемые языком С#. Поскольку они так тесно связаны, важно понимать общую концепцию .NET Framework и её значимость для C#. 
 
Язык С# использует две важные составляющие .NET Framework. Первая – это не зависящая от языка среда исполнения (Common Language Runtime, CLR), система, управляющая исполнением программы, и являющаяся частью технологии .NET Framework , которая позволяет программам быть переносимыми, поддерживает программирование с использованием нескольких языков и обеспечивает безопасность передачи данных. 
 
Вторая составляющая – библиотека классов .NET, которая дает программе доступ к среде исполнения, например, используется для ввода\вывода данных. Пока программа ограничена характеристиками, определенными библиотекой классов .NET, она может быть запущена везде, где поддерживается среда исполнения .NET.   
2.1.ПОСТАНОВКА ЗАДАЧИ 
Требовалось разработать программное приложение “Система складского учёта”, используя средства Microsoft Visual Studio .NET, а также SQL Server Express – для создания БД склада. База данных должна состоять из нескольких таблиц. В этих таблицах должна храниться следующая информация: 
- название товара; 
- номер товара на складе; 
- количество товара на складе; 
- дата прихода товара на склад; 
- дата расхода товара на складе. 

Пользователь  должен иметь следующие возможности при работе с данной программой: 
- оформлять приход товара на склад; 
- оформлять расход товара на складе; 
- просмотр статистики по приходу и отгрузки товара за определенный период времени.

 
2.2.АНАЛИЗ ЗАДАЧИ 
2.2.1.Добавление товара в список продукции, содержащейся на складе 
При добавлении товара должны изменяться только записи о  товаре, выбранном пользователем. Записи о других товарах, имеющих сходные с добавляемым название или индекс, должны остаться неизменными. С этой целью  операции с товаром производятся с использованием наименования и индекса товара, или значения поля id в записи о товаре, однозначно определяющем каждую запись. 
 
2.2.2.Удаление товара из списка продукции 
При удалении товара должен удаляться только товар, выбранный пользователем. Записи о других товарах, имеющих сходные с удаляемым название или индекс, должны остаться неизменными. С этой целью  операции с товаром производятся с использованием наименования и индекса товара, или значения поля id в записи о товаре, однозначно определяющем каждую запись. Если количество товара на складе меньше требуемого для удаления, количество товара становится равным 0, запись о товаре не удаляется. 
 
2.2.3. Получение статистических данных о товаре, его приходе и расходе за определенный период времени 
Статистические данные должны быть получены за определённый период времени. С этой целью пользователь должен иметь возможность ввести начальную и конечную даты отчётного периода (за который формируется статистические данные). Система должна различать, к какому периоду относятся данные, и в соответствии с этим выводить их.

 
2.2.4.СТРУКТУРНАЯ ОРГАНИЗАЦИЯ СИТЕМЫ 
2.2.4.1.Организация интерфейса пользователя 
Интерфейс пользователя включает в себя: 
1.Начальный экран программы 
 
 
 
Он служит для получения краткой информации о работе с программой, а также предоставляет возможность завершить работу программы. Сведения о работе с программой предоставляет экран, находящийся в центре формы. Кнопка «Выход» позволяет завершить работу программы. 
 
2.Форма оформления прихода товара на склад 
Она служит для ввода информации о товаре в БД «Склад». Для перехода на данную форму необходимо нажать левой кнопкой мыши на закладку “Приход”. Она находится в нижнем левом углу главного окна программы. Здесь мы вводим номер товара на складе, название товара и его количество. Чуть выше находится таблица, в которой отображается информация об имеющихся на складе товарах. 
 
 
 
3.Форма оформления расходов товара на складе 
Она служит для ввода информации о товаре, который следует списать на расход. Здесь, также как и на предыдущей форме, вводим номер товара на складе, его название и количество соответственно. При неверно заполненных данных на экран выдаётся сообщение об ошибке. Чуть выше находится таблица, в которой отображается информация о товарах на складе. 
  
 
4.Форма просмотра статистики 
Она предоставляет возможность просмотра статистики за определенный период времени. Пользователь выбирает начальную и конечную даты в полях, находящихся внизу главного окна программы, а затем нажимает кнопку «Собрать статистику». После чего на экране, находящемся чуть выше отображается полная статистика по приходу/расходу товаров за указанный срок. 
 
 
4.2.Модель БД 
 
Модель БД представлена в соответствии с рисунком, расположенном ниже. Она описывает отношения между таблицами «tovar», «prihod» и «rashod» составляющими БД «Склад». Таблицу «tovar» и таблицу «prihod» связывает отношение «один ко многим» т.е. одной записи в таблице «tovar» может соответствовать несколько записей в таблице «prihod», связанных по первичному ключу таблицы  «tovar» - «id». Таблицу «tovar» и таблицу «rashod» связывает отношение «один ко многим», связанных по первичному ключу таблицы  «tovar» - «id». В таблице «tovar» хранится информация о товаре, присутствующем на складе. Таблицы «prihod» и «rashod» хранится информация о поступлении и удалении товара со склада. 
 
2.3.РЕАЛИЗАЦИЯ КОМПОНЕНТОВ СИСТЕМЫ 
 
2.3.1.Подробное описание функций и процедур приложения 
exitButton_Click(object sender, EventArgs e) – закрывает приложение;

 
mainForm_Load(object sender, EventArgs e) - вызывает метод this.tovarTableAdapter.Fill(this.sCLADDataSet.tovar), который выбирает все данные из таблицы товар и заполняет ими  sCLADDataSet.tovar. При этом в связанном с ним DataGridView  отображаются данные из таблицы товар;

  
prihodButton_Click(object sender, EventArgs e) - вызывает процедуру  updatePrihod для обновления данных после  внесения товара в базу данных; 
updatePrihod(string name, string nomer, int colvo) – принимает в виде входных параметров название товара – name, индекс товара – nomer и вносимое количество товара -  colvo.

 Если количество  вносимого товара меньше 0, отображает  предупреждение и завершается.  Затем, вызывая tovarTableAdapter.GetDataBy4(name, nomer), определяет, существует ли такой  товар на складе. Если не существует (tempTable.Rows.Count < 1), то вставляет информацию о товаре в таблицу склада (tovarTableAdapter.InsertQuery(name, nomer, colvo)), определяет id вставленной записи и использует его для вставки записи в таблицу прихода (int id = (Int32)tovarTableAdapter.ScalarQuery()           
prihodTableAdapter.InsertQuery(id, DateTime.Today, colvo)), затем вызывается this.tovarTableAdapter.Fill(this.sCLADDataSet.tovar) для обновления записей, демонстрируемых в DataGridView. Если записи о товаре уже существуют в таблице, тогда определяется значение id для этой записи (int id = (Int32)tempTable.Rows[0]["id"];), вызывается запрос для обновления информации в базе данных (tovarTableAdapter.UpdateQuery(colvo, id);), в базу данных вставляется информация о приходе (prihodTableAdapter.InsertQuery(id, DateTime.Today, colvo);) и вызывается  this.tovarTableAdapter.Fill(this.sCLADDataSet.tovar) для обновления записей, демонстрируемых в DataGridView;  
 
private 
 
void 
 
rashodButton 

Click 

object 
 
sender 
,  
EventArgs 
 

) - вызывает процедуру  updateRashod для обновления данных после  удаления товара; 
 
updateRashod 

string 
 
name 
,  
string 
 
nomer 
,  
int 
 
colvo 
) - принимает в виде входных параметров название товара – name 
, индекс товара – nomer 
и удаляемое количество товара -  colvo. Если количество удаляемого товара меньше 0, отображает предупреждение и завершается. Затем, вызывая tovarTableAdapter.GetDataBy4(name, nomer), определяет, существует ли такой товар на складе. Если не существует (tempTable.Rows.Count < 1), то вызывает сообщение об ошибке и заканчивает работу. В противном случае определяется значение id для записи об этом товаре (int id = (Int32)tempTable.Rows[0]["id"];), 
и его количество на складе(int count = (Int32)tempTable.Rows[0]["kolvo"];). Если количество оформляемого для расхода товара меньше, чем количество на складе, то число товара на складе сократится до нуля (if (count < colvo) colvo = count; tovarTableAdapter.UpdateQuery1(colvo, id);). В таблицу расходов заносится информация о расходе (rashodTableAdapter.InsertQuery(id, DateTime.Today, colvo);) . После всего вызывается  this.tovarTableAdapter.Fill(this.sCLADDataSet.tovar) для обновления записей, демонстрируемых в DataGridView;  
statButton_Click(object sender, EventArgs e) - вызывает процедуру  private void getStat(DateTime start, DateTime finish), собирающую статистику; 
showError 
() - метод для показа ошибки, вызывает  MessageBox с текстом ошибки; 
 
getStat 

DateTime 
 
start 
,  
DateTime 
 
finish 
) -  метод для получения статистических данных, принимает в качестве параметров даты начала и конца отчётного периода;  
 
В начале работы определяются данные о товарах

(DataTable tempTable = tovarTableAdapter.GetDataBy6();).

 Затем в  цикле для каждой полученной  записи в statTextBox выводятся данные о товаре – название, индекс и т.д. Потом определяется, есть ли данные о приходе и расходе такого товара за отчётный период

 (rashodTable = rashodTableAdapter.GetDataBy1((Int32)tempTable.Rows[i]["id"], start, finish); 
prihodTable = prihodTableAdapter.GetDataBy1((Int32)tempTable.Rows[i]["id"], start, finish);). Если такие данные существуют, то они выводятся в statTextBox. Так происходит для каждой записи о товаре, находящейся в таблице «тovar». 
showWarning() – метод, выполняющийся в случае, если пользователь пытается ввести нулевое количество товара. 

 

 
2.3.2.Структура БД 
2.3.2.1. Таблица  
prihod 
Таблица prihod состоит из 3 полей: 
- tovar_id (хранит номер товара); 
- data_prihoda (хранит дату прихода товара на склад); 
- kolvo (хранит количество товара на складе). 
 
 

2.3.2.2. Таблица  
rashod 
Таблица rashod состоит из 3 полей: 
- tovar_id (хранит номер товара); 
- data_rashoda (хранит дату расхода товара на склад); 
- kolvo (хранит количество товара на складе). 
 
 

 

2.3.2.3.Таблица  
tovar 
Таблица tovar состоит из 3 полей: 
- nomer (хранит номер товара); 
- name (хранит название товара); 
- kolvo (хранит количество товара на складе).

 
 

 
2.4.КОРОТКАЯ ИНСТРУКЦИЯ ПО РАЗВЕРТЫВАНИЮ 
Сначала необходимо скопировать папку «КУРСОВОЙ ПРОЕКТ – СИСТЕМА СКЛАДСКОГО УЧЁТА» на жёсткий диск. В этой папки находится приложение и база данных. Открываем SQL Server Management Studio Express, после чего щёлкаем правой кнопкой мыши по папке Databases. Выбираем в выпадающем меню пункт attach. 

 
 
 
Появляется окно, в котором необходимо выбрать файл Sclad.mdf.  
 
 
 
Теперь копируем файлы Conf.exe (...\КУРСОВОЙ ПРОЕКТ - СИСТЕМА СКЛАДСКОГО УЧЁТА\ПРОГРАММА\Conf \Conf\bin\Debug), Sclad.exe и Sclad.exe.config (\КУРСОВОЙ ПРОЕКТ - СИСТЕМА СКЛАДСКОГО УЧЁТА\ПРОГРАММА\Sclad\Sclad\bin\Debug) в одно и тоже место. Запускаем файл Conf.exe. В появляющемся окне указываем имя компьютера и нажимаем кнопку ОК. Программа готова к работе, после чего можно запускать файл Sclad.exe. 
 
3. Формализация понятия алгоритма

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

Один из возможных  путей формализации состоит в  том, чтобы подобрать понятия, уже  известные в математике, и для  которых уже разработан формализм. Одним из таких понятий-претендентов является функция. Действительно, на первый взгляд между функцией и алгоритмом есть много общего. У функции есть область определения, у алгоритма есть область применимости; у функции есть область допустимых значений, у алгоритма есть определенное множество результатов.

Рассмотрим взаимосвязь  между функцией и алгоритмом. Сразу отметим, что основные свойства этой взаимосвязи мы будем здесь приводить без доказательства. Тому есть как минимум две причины. Первая - у читателя не предполагается знания необходимого математического аппарата; вторая - это увело бы нас в сторону от основной цели - формализации понятия алгоритма.

Определение: Говорят, что алгоритм А вычисляет функцию f(x), если:

Существует взаимно  однозначное соответствие j между  областью определения f(х) и областью применимости А;

Для любого х из области  определения f верно: f(x)= А(j(x))

В этом случае функция f(x) называется вычислимой функцией.

Определение: Говорят, что Алгоритм А разрешает множество М относительно множества Х, где МÌХ, если:

Для любого х из множества  М верно, что А(х) = “истина”;

Для любого у из Х, но у не принадлежит М, А(у) =“ложь”.

В этом случае говорят, что  множество М разрешимое.

Примеры разрешающих  алгоритмов - признаки делимости на 2, на 3, на 5. Эти алгоритмы разрешают  множество натуральных чисел, кратных 2 (соответственно 3 либо 5), относительно всего множества натуральных чисел.

Определение: Говорят, что алгоритм А перечисляет множество В если область применимости А есть множество натуральных чисел N, а совокупность результатов есть множество В.

В этом случае В называется перечислимым множеством. Другими словами, в перечислимом множестве все элементы занумерованы целыми числами. Любой элемент в перечислимом множестве может быть найден по его номеру.

Изучение свойств вычислимой функции, а стало быть и алгоритма, показало, что:

Область применимости любого алгоритма - перечислимое множество; Следствие: алгоритмы не могут работать на множестве вещественных чисел.

Функция f(x) вычислима  тогда и только тогда, когда перечислим ее график, т.е. множество {(x, f(x))} перечислимо.

Множество MÌX разрешимо относительно множества X, когда M и X\M перечислимы.

Отсюда видно, что понятие алгоритма  не сводимо к понятию функции. Множество функций мощнее множества  алгоритмов.

Самое важное различие между этими  понятиями для нас состоит  в том, что алгоритм определяет некоторый процесс, который мы называем вычислительным. Понятие функции не предполагает и не определяет никакого процесса. Функция представляется в виде “черного ящика”, на вход которого подали аргументы и на выходе получили результат. Как этот результат был получен - умалчивается. Понятие алгоритма наоборот прежде всего сфокусировано на процессе вычисления результата. Алгоритм определяет именно то, как по аргументам вычислить результат. Итак, понятие функции, как оно есть в математике, нам не подходит, нужно строить формализацию, специально для алгоритма.

Информация о работе Понятие алгоритма и его свойства