Программный алгоритм действий. Алгоритмы и программы. Анализ времени выполнения алгоритма

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

Свойства алгоритма:

-дискретность -последовательность решения (процесс) задач должен быть разбит на последовательность отдельных шагов.

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

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

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

-массовость - пригодность алгоритма для решения задач некоторого класса.

Способы записи алгоритма:

-словесный – способ на естественном языке.

-графический -описания алгоритма с помощью схем.

Процесс выполнения операций или групп операций

ввод исходных данных, вывод результата

Решение-выбор направления выполнения

Модификация-выполнение операций, меняющих команды или группы команд, изменяющих программ.

Соединители линий на одной странице.

Межстраничные соединители.

-язык программирования –удобен для ввода в комп-р.

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

Виды алгоритмов и основные принципы составления алгоритмов.

-Линейный – алгоритм, в кот-ом команды выполняются последовательно друг за другом в порядке их естественного следования независимо от каких-либо условий. S1, s2 , S3…Sn

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

· Полная условная конструкция (полное ветвление)

· Неполное условная конструкция

· Выбор из нескольких

-циклический – алгоритм, в кот-ом последовательность может выполняться более 1 раза.

· Цикл с параметром

· Цикл с предусловием. Может не выполниться ни разу. В теле цикла обязательно нах-ся оператор, к-ый изменяет значение переменной, входящей в блок Q.

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

Основные принципы алгоритмизации:

1. Выявить исходные данные, результаты и назначить им имена.

2. Метод решения задач.

3. Разбить метод решения задач на этапы.

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

5. В полученной схеме при любом варианте вычислений.

Предусмотреть выдачу результатов или сообщений об их отсутствии.

Обеспечить возможности после выполнение любой операции так или иначе перейти к блоку конец.

40.Основные алгоритмические структуры

Мы уже рассмотрели основные понятия программирования и переходим немного ближе к делу (но только ближе, программировать будем позже).

Рассмотрим основные структуры алгоритмов, а их шесть:

· Следование. Это последовательность блоков (или групп блоков) алгоритма. В программе следование представлено в виде последовательного выполнения операций

·
Разветвление. Данная алгоритмическая структура применяется в том случае, когда в зависимости от условия необходимо выполнить одно или другое действие

·
Обход. Эта структура является частным случаем разветвения, когда в одной из ветвей нет никаких действий.

·
Множественный выбор. Эта структура является обобщением раветвления, когда необходимо выполнить одно из нескольких действий в зависимости от значения переменной A.

ОТКРЫТЫЙ УРОК ПО МАТЕМАТИКЕ

«Алгоритм. Программа действий»

2 класс «Школа 2100»

Цели урока: 1. Доказать, что с помощью общего алгоритма, можно выполнять большое количество разных частных заданий; 2. Закрепить умение действовать по алгоритму, выполняя то или иное задание; 3. Закрепить умение различать алгоритмы разных видов: линейный, разветвленный, циклический; 4. На примере доказать присутствие действий по алгоритму в обычной жизни.

Задачи урока: 1. Решение различных видов заданий с помощью алгоритмов действий; 2. Обосновать выбор данного вида алгоритма.

ХОД УРОКА:

Организационный момент – проверка готовности к уроку, настрой на успех.

Проверка домашнего задания – составление алгоритма «Сбор портфеля в школу».

Математическая разминка:

Определить, сколько в числе 534 сотен, десятков и единиц? (В числе 534 – 5 сотен, 53 десятка, 534 единицы). Запишите это число в тетради разными способами.

(534 = 5 сот. 34 ед. = 53 дес. 4 ед. = 534 ед.)

Соберите число по сумме разрядных слагаемых и запишите его.

700 + 30 + 4 = (734) 500 + 6 = (506)

В ряду чисел найдите «лишнее» число и объясните свой выбор.

720, 540, 306, 50, 910, 300.

(Все числа, кроме 50 , - трехзначные; все числа, кроме 306 , - круглые; во всех числах, кроме 300 по одному нулю).

Итак, после небольшой разминки, вы готовы двигаться вперед? Чтобы ваш боевой настрой сохранился до конца урока, наш друг Совушка будет помогать его поддерживать. (Желаю успеха! У вас всё получится!)

Каждый день человек выполняет огромное количество разных дел. Он не должен ничего забыть. Как же не запутаться, не пропустить важного? Вы можете что-то посоветовать человеку, чтобы облегчить ему день? (Записать все свои дела по порядку в ежедневник (тетрадь, в которую записывают все свои ежедневные дела) и следовать им в течение дня).

Что напоминает вам этот совет? Если все действия проговорим по порядку, то что получим? (Алгоритм). А если мы запишем действияи посоветуем кому-нибудь воспользоваться этими записями, то что получим? (Программу действий). В чем отличие алгоритма от программы действий? (Алгоритм – это устный порядок действий, а программа действий – это записанный алгоритм).

Ну что ж, вы готовы назвать тему нашего урока? Чему же он будет посвящен? «Алгоритм. Программа действий». А с какой целью мы будем сегодня говорить об этом и выполнять задания? (Обратить внимание учащихся на цели урока).

Какие задачи мы перед собой ставим, чтобы добиться этих целей? (Обратиться к задачам урока).

Прежде, чем мы перейдем к выполнению наших задач, предлагаю вам вспомнить основные понятия, связанные с нашей темой. (На доске вывешены основные понятия: алгоритм, программа действий, блок-схема, виды алгоритмов:, - линейный, - разветвленный, - циклический).

Перейдем к первому заданию:

- вычислить сумму чисел 517 + 76 (593)

По какому алгоритму будем действовать? («Сложение в столбик с переходом через разряд»).

2 – сложить единицы;

3 – записать единицы под единицами и учесть переход через разряд;

4 – сложить десятки с учетом перехода через разряд;

5 – записать десятки под десятками и учесть переход через разряд

6 – сложить сотни с учетом перехода через разряд;

Действуя по общему алгоритму, мы можем вычислить сумму любых чисел. Докажем это. Самостоятельно вычислите сумму чисел 409 и 298 (707).

- вычислить разность чисел 724 – 235 (489)

По какому алгоритму будем действовать? («Вычитание трехзначных чисел с переходом через разряд»).

1 – записать числа столбиком разряд под разрядом;

2 – вычитаем единицы: если можем вычесть, вычитаем и записываем единицы под единицами, если не можем, занимаем 1 десяток и раскладываем его на 10 единиц плюс те единицы, которые уже есть и вычитаем единицы, записываем единицы под единицами;

3 – помним, что занимали 1 десяток, вычитаем десятки: если можем вычесть, вычитаем и записываем десятки под десятками, если не можем, занимаем 1 сотню и раскладываем ее на 10 десятков плюс те десятки, которые уже есть и вычитаем десятки, записываем десятки под десятками;

4 – помним, что занимали 1 сотню, вычитаем сотни и записываем сотни под сотнями; 5 – прочитать полученный результат.

Самостоятельно вычислите разность чисел 961 – 583 (378)

А теперь подтвердите свои умения и выполните сложение и вычитание «сказочных чисел»:

ΨӘ0 + Δ = (ΨӘΔ) Ω00 + ӨΛ = (ΩӨΛ)

ΥφΨ – φΨ = (Υ00) £0§ - £00 = (§)

Какие дополнительные правила помогут вам справиться с этим заданием?

(Если к любому числу прибавить 0, то получим то же самое число; если из любого числа вычесть то же самое число, то получим 0).

Изменился ли алгоритм ваших рассуждений при решении примеров со «сказочными числами»?

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

На доске приведены записи тех алгоритмов, которыми мы сейчас пользовались, но только уже не в устной форме, а в письменной, поэтому эти записи носят какое название? (Программы действий). Как называется такая запись программы действий? (Блок-схема).

Определите какой вид имеет блок-схема алгоритма сложения трехзначных чисел? (Линейный). Что такое линейный алгоритм? (Алгоритм, в котором все действия следуют друг за другом в определенном порядке. В некоторых случаях порядок действий можно изменять). Какой вид имеет блок-схема алгоритма вычитания трехзначных чисел? (Линейный, разветвленный, циклический). Что такое разветвленный алгоритм? (Алгоритм, содержащий условие и выбор действия). Что такое циклический алгоритм? (Алгоритм, в котором есть возврат к предыдущим действиям). Покажите на 2-ой схеме части каждого вида алгоритмов.

Блок-схема 1 алгоритма Блок-схема 2 алгоритма

ФИЗМИНУТКА

Мы встречаемся с алгоритмами не только при решении примеров. Приведите примеры заданий, в которых также удобно использовать алгоритм. (Уравнения). Проверим нашу гипотезу. Что такое гипотеза? (Научное предположение. Если предположение подтвердится, то оно становится правилом или законом. Если не подтвердится, то выдвигаем новую гипотезу).

Решаем уравнение. Что такое уравнение? (Равенство, в котором есть неизвестная величина, переменная). Что значит решить уравнение? (Найти такое значение переменной, при котором наше равенство будет верным).

Х + 241 = 729

Применяем алгоритм.

1 – смотрим на знак, чтобы определить целое и части;

2 – обозначаем целое и части и подписываем компоненты действия;

3 – определяем, чем является неизвестная величина;

4 – выбираем нужное правило;

5 – записываем способ решения;

6 – вычисляем;

7 – записываем результат;

8 – выполняем проверку.

К какому виду относится этот алгоритм? (К линейному). Опираясь на алгоритм, решаем уравнение.

1 слаг. 2 слаг. сумма

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

Но только ли в математике мы можем встретиться с действиями по алгоритму? Я предлагаю вам построить макет школы «Мир интеллекта», для которого нужен особый строительный материал, который отвечал бы строго определенным требованиям.

Соответствие нашего строительного материала необходимо проверять, пользуясь программой действий. (Работа с блоками Дьенеша).

У меня на столе лежат строительные блоки, но не все из них пригодны для нашей стройки. Нам потребуются только те блоки, которые пройдут отбор. В этом нам поможет программа действий «Архитекторы».

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

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

А теперь вернемся к нашим целям и задачам урока. (Проанализировать, добились ли мы каждой цели и выполнили ли поставленные задачи – ИТОГ УРОКА).

В качестве оценок за урок, мне бы хотелось вручить вам сертификаты и дипломы за участие в олимпиадах по математике и информатике.

Домашнее задание: составить алгоритм решения задач.

Спасибо за вашу работу на уроке. Урок окончен.

). Разработка программы с помощью такой системы программирования состоит из двух этапов: 1) создание в визуальном режиме элементов графического интерфейса программы; 2) разработка программного кода. Такой подход существенно облегчает создание программ, так как разработка графического интерфейса вручную (в процедурных языках) сложный и трудоёмкий процесс.

Первый шаг к пониманию важности изучения и знания алгоритмов это дать точное определение тому, что понимается под алгоритмом. Алгоритм в программировании- это понятная и точная последовательность действий , записанных на языке программирования.Согласно популярной книге Алгоритмы: построение и анализ (Кормен, Лейзерсон, Ривест, Штайн)"алгоритм (algorithm) - это любая корректно определенная вычислительная процедура, на вход (input) которой подается некоторая величина или набор величин, и результатом выполнения которой является выходная (output) величина или набор значений". Другими словами, алгоритмы похожи на дорожные карты для достижения четко определенной цели. Код, для вычисления членов последовательности Фибоначчи - это реализация конкретного алгоритма. Даже простая функция сложения двух чисел является алгоритмом, хотя и простым.

Для создания алгоритма (программы) необходимо знать:

полный набор исходных данных задачи (начальное состояние объекта);

цель создания алгоритма (конечное состояние объекта);

систему команд исполнителя (то есть набор команд, которые исполнитель понимает и может выполнить).

Полученный алгоритм (программа) должен обладать следующим набором свойств:

дискретность (алгоритм разбит на отдельные шаги - команды);

однозначность (каждая команда определяет единственно возможное действие исполнителя);

понятность (все команды алгоритма входят в систему команд исполнителя);

результативность (исполнитель должен решить задачу за конечное число шагов).

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

Некоторые алгоритмы, к примеру, для вычисления последовательности Фибоначчи, являются интуитивно понятными и относятся к врожденным навыкам логического мышления и решения задач. Тем не менее, большинству из нас будет не лишним изучить и сложные алгоритмы, чтобы в будущем можно было использовать их в качестве строительных блоков для более эффективного решения логических задач. В действительности можно удивиться, узнав как много сложных алгоритмов используется людьми при проверке электронной почты или прослушивании музыки. В этой статье представлены некоторые основные идеи анализа алгоритмов с практическими примерами, иллюстрирующими важность изучения алгоритмов.

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

Анализ времени выполнения алгоритма

Одним из наиболее важных аспектов алгоритма является его скорость. Часто бывает легко придумать алгоритм решающий задачу, но если алгоритм слишком медленный, то он возвращается на доработку. Поскольку точная скорость алгоритма зависит от того где запускается алгоритм, а также деталей реализации, компьютерные специалисты обычно говорят о времени выполнения относительно входных данных. Например, если вход состоит из N целых чисел, то алгоритм может иметь время выполнения пропорциональное N 2 , что представляется как O(N 2). Это означает, что если вы запустите реализацию алгоритма на компьютере с входом размером в N, то это займет C*N 2 секунд, где C-некоторая константа, которая не меняется с изменением размера входа.

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

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

Обозначение	Описание	Примечания
	Начало и конец алгоритма
	Ввод и вывод данных.	Вывод данных иногда обозначают иначе:
	Действие	В вычислительных алгоритмах так обозначают присваивание
	Развилка	Развилка - компонент, необходимый для реализации ветвлений и циклов
	Начало цикла с параметром
	Типовой процесс	В программировании - процедуры или подпрограммы
	Переходы между блоками

Приведем пример описания алгоритма суммирования двух величин в виде блок-схемы:

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

Сортировка

Сортировка является хорошим примером алгоритма, который часто используется программистами. Самый простой способ отсортировать группу элементов это начать с удаления наименьшего элемента из группы, и поставить его первым. Затем удаляется второй по величине элемент и ставится вторым и т.д. К сожалению, время работы этого алгоритма составляет O(N 2), а это означает, что потребуется количество времени пропорциональное количеству элементов в квадрате. Если бы нам пришлось сортировать млрд. элементов, то этот алгоритмы бы потребовал 10 18 операций. Если считать что обычные настольные ПК делают примерно 10 9 операций в секунду, то потребуются годы чтобы закончить сортировку этого млрд. элементов.

К счастью существует ряд более совершенных алгоритмов, например, быстрая сортировка (quicksort), пирамидальная сортировка (heapsort) и сортировка слияния(mergesort). Эти алгоритмы имеют время выполнения O(N * Log(N)). Таким образом, число операций необходимых для сортировки млрд. элементов сокращается до таких разумных пределов, что даже самый дешевый настольный ПК способен провести такую сортировку. Вместо млрд. в квадрате операций (10 18) эти алгоритмы требуют только 10 млрд. операций (10 10), т.е. в 100 млн. раз быстрее.

Кратчайший путь

Алгоритмы поиска кратчайшего пути из одной точки в другую исследуются уже на протяжении многих лет. Примеров прикладного применения этих алгоритмов предостаточно, однако для простоты изложения будем придерживаться следующей постановки: требуется найти кратчайший путь из точки А в точку Б в городе с несколькими улицами и перекрестками. Существует много разных алгоритмов для решения этой задачи и все они со своими преимуществами и недостатками. Прежде чем мы углубимся в их изучение, давайте рассмотрим время выполнения простого алгоритма перебором. Если алгоритм рассматривает каждый возможный путь от А до Б (который не образует циклов) он вряд ли закончится при нашей жизни, даже если А и Б находятся в маленьком городке. Время выполнения этого алгоритма является экспоненциальным, что обозначается как O(C N) для некоторого C. Даже для малых значений C, C N становится астрономическим числом, когда N принимает умеренно большое значение.

Один из самых быстрых алгоритмов для решения этой задачи имеет время выполненияO(E+V*Log(V)), где E число дорожных сегментов, а V число пересечений. Алгоритм займет около 2 секунд времени, для поиска кратчайшего пути в городе из 10000 пересечений и 20000 дорожных сегментов (обычно бывает около 2 дорожных сегментов на одно пересечение). Этот алгоритм известен как алгоритм Дейкстры, он является довольно таки сложным и требует использования структуры данных очередь с приоритетом (priority queue). Однако в некоторых случаях даже такое время выполнения является слишком медленным (взять например нахождение кратчайшего пути от Нью-Йорка до Сан-Франциско - в США есть миллионы пересечений), в таких случаях программисты пытаются улучшить время выполнения с помощью так называемой эвристики. Эвристика - это приближенное значение чего-то, что имеет отношение к задаче. В задаче поиска кратчайшего пути, например, может оказаться полезным знать, как далеко находится точка от пункта назначения. Зная это можно разработать более быстрый алгоритм (например алгоритм поиска А* в некоторых случаях работает значительно быстрее чем алгоритм Дейкстры). Такой подход не всегда улучшает время выполнения алгоритма в наихудшем случае, но в большинстве реальных приложений алгоритм начинает работать быстрее.

Приближенные алгоритмы

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

На самом деле есть немало важных задач, для которых известные на сегодня алгоритмы выдают оптимальный результат слишком медленно. Наиболее известная группа из этих задач называется NP (non-deterministic polynomial). Если задача называется NP-полной или NP-трудной, то это означает, что никто не знает достаточно хорошего способа для получения оптимального решения. Кроме того, если кто-то разработает эффективный алгоритм для решения одной NP-трудной задачи, то этот алгоритм можно будет применить ко всем NP-трудным задачам.

Хорошим примером NP-трудной задачи является задача коммивояжёра. Продавец хочет посетить N городов, и он знает, сколько времени занимает перемещение из одного города в другой. Вопрос в том насколько быстро он сможет посетить все города? Самый быстрый из известных алгоритмов для решения этой задачи является слишком медленным - и многие считают, что так будет всегда - поэтому программисты ищут достаточно быстрые алгоритмы, дающие хорошее решение, но часто не оптимальное.

Случайные алгоритмы

Еще один подход, применяемый для решения некоторых задач, заключается в том, чтобы сделать алгоритм случайным. Данный подход не улучшает время алгоритма в худшем случае, но довольно часто хорошо работает в среднем случае. Алгоритм быстрой сортировки является хорошим примером использования рандомизации. В худшем случае, алгоритм быстрой сортировки сортирует группу элементов за O(N 2), где N количество элементов. Если в этом алгоритме использовать рандомизацию, то шансы на худший случай становятся незначительно малыми, и в среднем случае алгоритм быстрой сортировки работает за время O(N*Log(N)). Другие алгоритмы даже в худшем случае гарантируют время работы O(N*Log(N)), однако они медленнее в среднем случае. Хотя оба алгоритма имеют время работы пропорциональное N*Log(N), алгоритм быстрой сортировки имеет более меньший постоянный коэффициент (constant factor) - т.е. он требует C*N*Log(N), в то время как другие алгоритмы требуют более 2*C*N*Log(N) операций.

Другой алгоритм, использующий случайные числа ищет медиану для группы чисел и его время работы в среднем случае составляет O(N). Это намного быстрее по сравнению с алгоритмом, который сортирует числа и выбирает среднее, и работает за O(N*Log(N)). Существуют детерминированные алгоритмы (не случайные) которые позволяют найти медиану за время O(N), однако случайный алгоритм проще для понимания и часто работает быстрее этих детерминированных алгоритмов.

Основная идея алгоритма поиска медианы это выбрать среди чисел случайное, и посчитать, сколько чисел в группе меньше чем выбранное число. Допустим, есть N чисел, K из них меньше или равно выбранному числу. Если K меньше чем половина N, тогда мы знаем что медиана это (N/2-K)-е число которое больше чем случайно выбранное число, так что мы отбрасываем K чисел меньших или равных случайному числу. Теперь допустим мы хотим найти (N/2-K)-е наименьшее число, вместо медианы. Алгоритм такой же, мы просто случайно выбираем число и повторяем описанные шаги.

Сжатие

Еще один класс алгоритмов предназначен для сжатия данных. Этот алгоритм не имеет ожидаемого результата (как например, алгоритм сортировки), но вместо этого делается оптимизация по некоторым критериям. В случае сжатия данных, алгоритм (например, LZW) пытается сделать так чтобы данные занимали как можно меньше байтов, но в то же время, чтобы можно было распаковывать их до первоначальной формы. В некоторых случаях этот тип алгоритмов использует те же методы что и другие алгоритмы, что приводит к хорошему результату, но неоптимальному. Например, JPG и MP3 сжимают данные таким образом, что конечный результат получается более низкого качества, чем оригинал, однако и размер меньше. MP3 сжатие не сохраняет каждую особенность оригинального аудио файла, но пытается сохранить достаточно деталей, чтобы обеспечить приемлемое качество и в то же время значительно сократить размер файла. Формат JPG следует тому же принципу, но детали существенно отличаются, т.к. целью является сжатие изображения, а не аудио.

Зачем нужно знать всякие алгоритмы

Чтобы использовать алгоритмы должным образом, важно знать все упомянутые типы алгоритмов. Если вам придется разрабатывать важную часть программного обеспечения, то вы должны быть в состоянии оценить скорость работы вашего алгоритма. Точность вашей оценки зависит от того насколько вы владеете анализом времени исполнения алгоритмов. Кроме этого, необходимо знать детали алгоритмов, что позволит предсказывать особые случаи, в которых программа не будет работать быстро, или будет давать неприемлемые результаты.

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

В качестве примера можно рассмотреть, как работают сетевые коммутаторы. Коммутатор имеет N подключенных к нему кабелей, и принимает пакет данных, поступающих по этим кабелям. Коммутатор должен сначала проанализировать пакеты, а затем отправить их обратно по правильному кабелю. Коммутатор также как и компьютер работает в дискретном режиме - пакеты отправляются дискретными интервалами, а не непрерывно. Быстрый коммутатор стремится послать, как можно больше пакетов в течение каждого интервала иначе они накопятся и коммутатор "упадет". Цель алгоритма отправлять максимальное количество пакетов в течение каждого интервала, а также обеспечить порядок, при котором пакеты, пришедшие раньше других отправлялись тоже раньше других. В этом случае оказывается, что для решения этой задачи подходит алгоритм известный как "stable matching", хотя на первый взгляд это может быть не очевидно. Такие связи между задачей и решением можно обнаружить только с помощью уже имеющихся алгоритмических знаний.

Реальные примеры

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

Существуют десятки примеров применения сложных алгоритмов, но обсудим две задачи, решение которых требует таких же навыков, как для решения некоторых задач на TopCoder. Первая задача известна как задача о максимальном потоке, а вторая связана с динамическим программированием - методом который часто позволяет решать задачи с казалось бы невозможной молниеносной скоростью.

Алгоритм поиска максимального потока

Задача поиска максимального потока состоит в том, чтобы посредством имеющейся сети наилучшим образом переместить что-то из одного места в другое. Конкретно такая проблема впервые возникла в 1950-х в связи с железнодорожными путями Советского Союза. США хотели знать, как быстро Советский Союз может подвозить материалы к государствам-сателлитам в Восточной Европе через свою сеть железных дорог.

Кроме того США хотели знать какую часть рельсов можно наиболее легко уничтожить чтобы отрезать государства-сателлиты от остальной части Советского Союза. Оказалось, что эти две задачи тесно связаны и что решение задачи поиска максимального потока также решает задачу о минимальном разрезе, что, в конечном счете, позволит выяснить самый дешевый способ отрезать Советский Союз от своих спутников.

Первый эффективный алгоритм для поиска максимального потока был придуман учеными Фордом и Фалкерсоном. Алгоритм впоследствии был назван алгоритмом Форда - Фалкерсона и является одним из наиболее известных алгоритмов в области компьютерной науки. В последние 50 лет алгоритм претерпел ряд улучшений, что сделало его быстрее (правда, некоторые из этих улучшений устрашают своей сложностью).

Поскольку задача была четко поставлена, обнаружилось множество различных применений. Алгоритм напрямую связан с Интернетом, где важно транспортировать максимум данных из одной точки в другую. Задача также возникает во множестве бизнес-процессов, и является важной частью исследования операций. Например, если есть N сотрудников и N задач, которые должны быть сделаны, но не каждый сотрудник может справиться с каждой задачей, то поиск максимального потока выдаст решение, как назначить N сотрудников на задачи таким образом, чтобы каждая задача была выполнена при условии что это возможно. Задача Graduation из TopCoder SRM 200является хорошим примером задачи на поиск максимального потока.

Сравнение последовательностей

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

Например, рассмотрим последовательности "AABAA" и "AAAB". Для преобразования первой последовательности во вторую самое простое, что нужно сделать это удалить B в середине и изменить последнюю A на B. Этот алгоритм имеет множество применений, включая некоторые задачи связанные с ДНК и обнаружением плагиата. Однако многие программисты используют его в основном для сравнения версий одного и того же файла с исходным кодом. Если элементы последовательности это строки в файле, тот этот алгоритм позволяет узнать какие строки надо удалить, вставить, изменить чтобы преобразовать одну версию файла в другую.

Без динамического программирования приходится перебирать экспоненциальное число преобразований, чтобы перейти от одной последовательности к другой. Однако динамическое программирование сокращает время выполнения алгоритма до O(N*M), где N и M количество элементов в двух последовательностях.

Заключение

Сколько существует различных задач, столько существует и различных алгоритмов для их решения. Тем не менее есть большая вероятность того что задача которую вы пытаетесь решить в некотором смысле похожа на другую задачу. Развивая глубокое понимание широкого диапазона алгоритмов, вы сможете выбрать верный алгоритм и применить его для решения задачи. Кроме того решение задач в соревнованиях на TopCoder поможет вам отточить свои навыки в этой области. Многие из этих задач кажутся искусственными и не реалистичными, но они требуют такого, же набора алгоритмических знаний который требуется каждый день в реальном мире.

Программирование

Задача

1.Действие

2. Процесс

3 АЛГОРИТМ инструкцией.

4. ПРОГРАММОЙ

Нижний уровень компилятор или интерпретатор .

Компилятор

Интерпретатор

Входные данные (устройство ввода) -> Память (программа)(внутренние данные) -> <-> Процессор.

Две главные компоненты ЭВМ:

1) ПАМЯТЬ данными

Емкость (размер);

2) ПРОЦЕССОР

Представление данных в памяти ЭВМ. Понятие переменной, константы, типа, диапазона значений.

В алгоритмах и программах данные встречаются в виде констант и переменных.

КОНСТАНТА - это постоянная величина, которая определяется своим значением.

ПЕРЕМЕННАЯ - величина, значение которой может меняться в процессе вычислений.

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

Тип константы определяется формой ее записи. Тип переменной определяется множеством значений, которые она может принимать.

Основными типами, применяемыми в машинных алгоритмах, являются цел , вещ , лог и лит .

Значениями целых переменных являются числа: 0, 1, -1, 2, -2,..., которые в памяти машины представляются точно.

Значениями вещественных переменных являются действительные числа, записываемые в виде десятичных дробей: 0.5, 1.2*10^6. Вещественные числа в памяти представлены с округлением.

Значениями логических переменных являются логические значения: истина (1) и ложь (0).

Значениями литерных переменных являются литеры или цепочки литер из определенных алфавитов - русского, латинского и тп: "упчк!!!11", "х=".

При размещении в памяти машины каждой константе и переменной выделяется отдельный участок памяти. Имя переменной является адресом этого участка.

Каждая инструкция программы также занимает участок памяти, длина которого зависит от вида инструкции.

В силу ограниченности участка, где размещаются переменные и константы, невозможно размещение и формирование чисел и литерных цепочек сколь угодно большой величины. Поэтому для каждой вычислительной машины и ЯП сущ. величины максцел - макс целое число, минвещ, максвещ и макслит. Вычисления, результаты которых выходят за пределы этих диапазонов, приводят к возникновению исключительных ситуаций в машине.

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

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

Требования к качеству программного продукта. Основные критерии качества.

Необходимым условием массового производства и внедрения программных систем является организация промышленного производства этих систем. Следовательно, должна существовать технология программирования, т.е. способ проведения процесса производства программ, обеспечивающий планирование, разработку и сдачу программных систем в срок. К программам должны предъявляться требования как к промышленному продукту, который могут использовать вне организации-разработчика и которому должно быть обеспечено тиражирование, внедрение, обслуживание в эксплуатации и развитие.

К программному продукту предъявляются слудующие требования:

1. Работоспособность - возможность выполнения программы на имеющейся машине.

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

3. Надежность - отсутствие отказов при выполнении программы даже для неправильно закодированных или недопустимых данных.

4. Эффективность - минимальность времени получения решения задачи в целом, включая как время выполнения программы, так и время разработки программы и данных, тестирования и отладки.

5. Документированность - наличие инструкции по пользованию и описаний внутренней логики программы.

6. Мобильность - независимость программы от конкретной реализации.

7. Эргономичность - программа позволяет минимизировать усилия пользователя по подготовке исходных данных, обработке данных и оценке полученных результатов.

8. Читабельность - программа должна быть понятной.

Постановка задачи.

2. Анализ задачи и составление спецификации программы - на этом этапе проводится анализ задачи, уточняется ее постановка и разрабатываются требования, предъявляемые к программе. Создается полное и точное описание программы, называемое ее спецификацией. Уточняются обычно четыре основных момента: вход/выход данные, метод и аномалии. Спецификация задачи – документ. Служит заданием на разработку программы (из нее разработчик программы должен извлечь все, что ему нужно знать о стоящей перед ним задаче); является частью соглашения между заказчиком программы и ее разработчиком, описанием задачи, которое приемлемо для заказчика, не обязательно сведущего в программировании; она должна использоваться для проверки готовой программы (решает ли разработанная программа поставленную задачу).

3. Проектирование алгоритма и структур данных и проектирование тестов - на этом этапе формируется общая структура программы. Фундаментальным подходом к разработке программ и программных систем является нисходящее проектирование. В основе нисходящего проектирования лежит идея постепенного раскрытия деталей проектируемой программы по мере движения от общей цели, сформулированной на самом верхнем уровне в условии задачи, к уровню объектов, выраженных в терминах, "понятных ЭВМ". Алгоритм записывается метаязыком, предназначенным для описания внутренней логики программы, а также для фиксации проектных решений по организации вычислений.

4. Кодирование алгоритма на языке программирования - на этом этапе алгоритм переводится с метаязыка на язык программирования.

5. Отладка (включая тестирование), предупреждение ошибок - цель этого этапа - получение корректной программы, т.е. программы, в которой отсутствуют ошибки проекта (ошибки, которые могут возникнуть, которые могут возникнуть на всех этапах разработки программы, в т.ч. и ошибки, появляющиеся из-за несоответствия требований заказчика и действий исполнителя). Методика отладки: визуальный контроль, синтаксический контроль, контроль структурированности программы, тестирование.

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

Исполнение программы.

Первые 4 этапа выполняются последовательно. Пятый этап распределяется по всем этапам - каждый завершается составлением документации.

Технология - это совокупность методов, а также правил и порядка их применения, которые обеспечивают производство в срок качественного продукта.

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

Технология структурного программирования:

1. Нисходящее проектирование алгоритмов и данных.

2. Строгая последовательность этапов программирования.

3. Выполнение требований к качеству продукта.

Ввод данных

Для ввода исходных данных чаще всего используется процедура ReadLn:

ReadLn(A1,A2,...AK);

Процедура производит чтение К значений исходных данных и присваивает эти значения переменным А1, А2, ..., АК.

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

Значения исходных данных могут отделяться друг от друга пробелами и нажатием клавиш табуляции и Enter.

Не допускается разделение вводимых чисел запятыми!

<оператор #1>;
<оператор #2>;
<оператор #3>;
. . .

Until <условие>

Читается так: "Выполнять оператор #1, оператор #2. : до выполнения условия".

Цикл ПОКА:

while - это цикл, в котором условие стоит перед телом. Причем тело цикла выполняется тогда и только тогда, когда условие true ; как только условие становится false , выполнение цикла прекращается.

While имеет формат:

while < условие> do <оператор 1>; {Пока … делай ….}

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

21. Реализация параметрического цикла в языке Паскаль. Синтаксис и семантика, ограничения при использовании.

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

Операторы цикла используются для многогратного повторения входящих в состав операторов. В языке Турбо паскаль различают операторы цикла типа арифметической прогрессии (оператор цикла со счетчиком FOR) с шагом +1 или -1 и операторы цикла итерационного типа (While и Repeat)

Оператор цикла типа арифметической прогрессии используется, если заранее известно количество повторений цикла и шаг изменния параметра цикла +1 или -1.

For <параметр цикла>:=<выражение1>to <выражение 2> do <оператор(тело цикла>; - шаг изменения параметра цикла +1

Downto - -1

Var f1:text

assign(f1,"file.txt");

reset(f1);

Процедура ввода массива может иметь разную степень универсальности

1) инициализация файлов и ввод длины массива происходит в главной программе;

(как в приведенном ниже примере); а ввод массива – в процедуре;

{вход: f – имя ф.п.,n – длина массива; выход: X - массив}

Procedure Input1_mas (var f: text; n: ind; var X: mas);

2) инициализация файлов происходит в главной программе, а ввод длины массива и самого массива – в процедуре;

{вход: f – имя ф.п.,выход:n – длина массива; X - массив}

Procedure Input2_mas (var f: text; var n:ind; var X: mas);

3) в главной программе вводятся внешние имена файлов, а инициализация файлов и ввод длины массива и самого массива – в процедуре;

{вход: Namef – внешнее имя файла,выход:n – длина массива; X - массив}

Procedure Input3_mas (Namef: str8; var n: ind; var X: mas);

4) в процедуре выполняются все операции: вводятся внешние имена файлов, инициализация файлов и ввод длины массива и самого массива

{вход: -- ,выход:n – длина массива; X - массив}

Procedure Input4_mas (var n: ind; var X: mas);

Так как фактический (реальный) массив определяется внешним именем файла Namef и длиной n массива, то именно этими переменными желательно управлять в главной программе. С этой точки зрения наиболее предпочтителен следующий вариант:

5) в главной программе вводятся внешние имена файлов и длины массива, а инициализация файлов и ввод самого массива – в процедуре;

{вход: Namef – внешнее имя файла,n – длина массива; выход: X - массив}

Procedure Input5_mas (Namef: str8; n: ind; var X: mas);

Базовые понятия пpогpаммиpования. Действие, пpоцесс, алгоритм, программа.

Программирование - это способ решения задач с помощью ПК.

Задача - это вопрос, на который нужно ответить, или требование, которое нужно выполнить, опираясь на те условия и учитывая те ограничения, которые указаны в задаче.

1.Действие -совершается неким объектом и приводит к опр результату(характер, время)

Самое важное понятие - ДЕЙСТВИЕ. Действие совершается над объектом и приводит к определенному результату. Если действие можно разложить на составные части, то оно называется ПРОЦЕССОМ. Если нет - это элементарное действие.

2. Процесс – действие, которое возможно разложить на элементарные действия.

Последовательное(одно за другим) параллельное(одновременно)

ПРОЦЕССОРОМ наз. исполнитель, который выполняет элементарные действия согласно инструкциям (человек, автомат, ЭВМ).

3 . Каждое действие можно описать с помощью языка или системы формул. АЛГОРИТМ - это описание процесса, т.е. описание последовательности элементарных действий, приводящих к определенному результату. Каждое элементарное действие наз. инструкцией.

4. ПРОГРАММОЙ называется алгоритм, который написан на языке, понятном вычислительной машине. Различие между общим алгоритмом и программой машины состоит в том, что в последней правила поведения должны быть уточнены до мельчайших подробностей и она должна быть составлена в точном соответствии с правилами записи, определенными для используемой машины.

Существует несколько уровней ЯП. Нижний уровень - внутренний язык машины (машинный код: 0 и 1). Программа на ЯП высокого уровня может быть введена в машину, но не может быть выполнена. Программа, которая переводит (транслирует) программу с языка высокого уровня на внутренний язык машины, называется транслятор: компилятор или интерпретатор .

Компилятор - программа, которая транслирует код с языка высокого уровня на язык машины: сначала перевод, потом выполнение программы (Паскаль).

Интерпретатор переводит каждое действие и тут же выполняет, пооператорно (Basic).

2. Функциональная структура ЭВМ. Основные устройства ЭВМ, их функциональные характеристики.

Входные данные (устройство ввода) -> Память (программа)(внутренние данные) -> Выходные данные (устройство вывода). К памяти две стрелки <-> Процессор.

Две главные компоненты ЭВМ:

1) ПАМЯТЬ (запоминающее устройство). В памяти в закодированном виде содержатся объекты, над которыми производятся действия. Эти закодированные объекты наз. данными . Основные характеристики памяти:

Емкость (размер);

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

2) ПРОЦЕССОР - это устройство, которое выполняет 2 основные функции:

Производит действия над данными;

Управляет последовательностью действий в программах.

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

Т.о. память играет роль "камеры хранения" для процессора, причем она используется как для хранения программы, так и для хранения данных.

Внутренние данные, обрабатываемые программой, состоят из входных, выходных и промежуточных данных.

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

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

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

Алгоритм? набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы.

Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкций, от которых они зависят. Независимые инструкции или инструкции, ставшие независимыми из-за завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система.

Алгоритм означает точное описание некоторого процесса, инструкцию по его выполнению. Разработка алгоритма является сложным и трудоемким процессом. Алгоритмизация? это техника разработки (составления) алгоритма для решения задач на ЭВМ. Блок-схема обобщенного алгоритма работы программы представлена на рисунке 3.9.

Рисунок 3.9 - Блок-схема алгоритма работы программы

Для записи алгоритма решения задачи применяются следующие изобразительные способы их представления:

· словесно-формульное описание;

· блок-схема (схема графических символов);

· алгоритмические языки;

· операторные схемы;

· псевдокод;

Разработка программного продукта

Со времени появления платформы.NET (примерно в 2001 г.) среди библиотек базовых классов появился API по имени Windows Forms, представленный в основном сборкой System.Windows.Forms.dll. Инструментальный набор Windows Forms предоставляет типы, необходимые для построения графических пользовательских интерфейсов для настольных компьютеров, создания специализированных элементов управления, управления ресурсами (например, строками и значками) и выполнения других задач, возникающих при программировании для пользовательских компьютеров. Имеется и дополнительный API по имени GDI+ (представленный сборкой System.Drawing.dll), который предоставляет дополнительные типы, позволяющие программисту генерировать двухмерную графику, взаимодействовать с сетевыми принтерами и обрабатывать графические данные .

Windows Forms (и GDI+) применяются в платформе.NET 4.0 и, видимо, будут существовать еще некоторое время (возможно, длительное) в составе библиотеки базовых классов. Правда, после выхода.NET 3.0 компания Microsoft выпустила совершенно новый инструментальный API под названием Windows Presentation Foundation (WPF) .

Несомненно, наиболее важным пространством имен Windows Forms является System.Windows.Forms. Типы из этого пространства имен можно разбить на следующие крупные категории :

· Базовая инфраструктура. Это типы, представляющие базовые операции программ, которые используют Windows Forms (Form и Application), и различные типы, предназначенные для взаимодействия с устаревшими элементами ActiveX, a также для взаимодействия с новыми специальными элементами управления WPF;

· Элементы управления. Эти типы применяются для создания графических пользовательских интерфейсов (наподобие Button, MenuStrip, ProgressBar и DataGridView), все они являются производными от базового класса Control. Элементы управления допускают настройку на этапе проектирования и видимы (по умолчанию) во время выполнения;

· Компоненты. Это типы, которые не порождены от базового класса Control, но все-таки могут предоставлять программам Windows Forms визуальные возможности (например, ToolTip и ErrorProvider). Многие компоненты (к примеру, Timer и System.ComponentModel.BackgroundWorker) не видимы во время выполнения, но все-таки допускают настройку на этапе проектирования;

· Окна стандартных диалогов. В Windows Forms имеется несколько заготовленных диалоговых окон для распространенных операций (например, OpenFileDialog, PrintDialog и ColorDialog).

В мире Windows Forms тип Form представляет любое окно в приложении, включая главное окно самого верхнего уровня, дочерние окна приложений с многодокументным интерфейсом (multiple document interface ? MDI), а также модальные и немодальные диалоговые окна. Тип Form содержит множество возможностей, унаследованных от классов-предков, а также из реализуемых им многочисленных интерфейсов.

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

Для создания нового проекта в Visual Studio выберем «New»-«Project», в появившемся окне выберем «Windows Form Application» и заполним предложенные поля.

Для передачи запроса SQL серверу и возврату результата в виде набора строк (запросы на выборку) был реализован метод «GetSQLData», представленный ниже.

В качестве параметра метод принимает строку-запрос, в качестве возвращаемого значения имеет тип «DataTable» ? таблицу данных.

public static DataTable GetSQLData(string query)

DataSet ds = new DataSet();

myConnection.Open();

catch (Exception e1)

SqlDataAdapter dataAdapter = new SqlDataAdapter(comm);

ds = new DataSet();

dataAdapter.Fill(ds);

MessageBox.Show("Error");

myConnection.Close();

catch (Exception e3)

return ds.Tables;

Для передачи запроса SQL серверу без возврата результата (запросы на вставку, изменение и удаление) был реализован метод «SetSQLData», представленный ниже. В качестве параметра метод принимает строку-запрос и не имеет возвращаемого типа значения.

public static void SetSQLData(string query)

SqlConnection myConnection = new SqlConnection(Config.ConnectionString);

myConnection.Open();

catch (Exception e1)

MessageBox.Show(e1.ToString());

SqlCommand comm = new SqlCommand(query);

comm.CommandType = System.Data.CommandType.Text;

comm.Connection = myConnection;

comm.ExecuteNonQuery();

myConnection.Close();

catch (Exception e3)

MessageBox.Show(e3.ToString());

Для того, чтобы пользователю не приходилось вводить строку подключения к базе данных также необходимо создать класс и файл конфигурации, которые хранили бы и позволяли изменять настройки приложения. Для этих целей были созданы соответственно класс «Config» и файл конфигурации «App.config»

public static string ConnectionString = GetParam("ConnectionStringSql");

public string Connection

return ConnectionString;

ConnectionString = value;

public static string GetPathTo(string ParamName)

return Application.StartupPath +

ConfigurationManager.OpenExeConfiguration(ConfigurationUserLevel.None).AppSettings.Settings.Value;

Переменная «Connection» этого класса является строкой для соединения с сервером. При запуске она инициализируется из файла настроек при помощи метода «GetParam», представленного ниже.

public static string GetParam(string ParamName)

return ConfigurationManager.OpenExeConfiguration(ConfigurationUserLevel.None).AppSettings.Settings.Value;

«App.config» - XML-файл, содержаний переменные и их явно или неявно указываемые значения. Текст сформированного xml-документа пользовательских настроек приведен ниже.

connectionString="Valid Connection String;" />

Обработчики различных событий элемента создаются на вкладке «Events». К примеру, событие «OnClick» - «нажатие на кнопку». После двойного клика на необходимое событие откроется код формы с объявленным обработчиком, в который необходимо добавить код для обработки возникающего события.

Добавим в обработчик события «OnClick» следующий код для вызова другой формы приложения:

private void button1_Click(object sender, EventArgs e)

NewTest obj = new NewTest();

obj.ShowDialog();

Подобным образом мы будем вызывать все формы приложения. Для считывания выборки в таблицу нашей формы добавим в ее код метод «Load_Tables».

listView1.Items.Clear();

DateTime d = new DateTime();

for (int i = 1; i < dt.Columns.Count; i++)

listView1.Items.Add(item);

Строка «query» в данном методе это запрос на выборку к базе данных. Теперь можно приступать к проектированию и реализации других форм приложения.

Добавить форму в текущий проект можно из контекстного окна «Solution Explorer», или через меню «Project»-«Add Windows Form». В появившемся окне вводим имя создаваемой формы и жмем «Add».

Задачи для этих элементов на данной форме будут следующими:

1. GroupBox - группировка схожих полей для ввода или выбора информации;

2. TextBox - поле для ручного ввода информации, которая после будет использоваться в запросах;

3. Label - подсказка пользователю о значении того или иного поля а также данных, которые необходимо ввести;

4. Button - подтверждение действия пользователем, считываемое системой.

В случае выбора того или иного элемента «RadioButton» («Ученик» или «Преподаватель»), будут разблокированы поля для ввода данных студента или преподавателя соответственно. По нажатию на кнопку «Начать работу» осуществляется авторизация.

Следующая форма приложения - форма добавления и изменения данных теста.

Данные из полей «Наименование», «Количество вопросов» и «Преподаватель» считываются и, при помощи запроса на вставку в методе «SetSQLData» класса «Connection» отправляются SQL-серверу.

В случае успеха или неудачи пользователю будет выведено соответствующее сообщение.

При загрузке формы наши выпадающий список «Преподаватель» (элемент «ComboBox») должен быть проинициализирован и заполнен некоторым набором значений, которые сможет выбирать пользователь. Для этого добавим в код формы метод «LoadComboboxes», код которого приведен ниже.

private void LoadComboboxes()

query = "Select Преподаватель from Преподаватели";

DataTable dt = Connection.GetSQLData(query);

comboBox1.DataSource = dt;

comboBox1.DisplayMember = "Преподаватель";

MessageBox.Show("Ошибка загрузки справочника <Преподаватели>");

Следующая форма приложения - отчет «Результаты тестирования». Добавляем форму, как было описано ранее, размещаем на форме элемент «ListView» и придаем форме следующий вид.

Данный отчет группирует все попытки зарегистрированных учеников успешно пройти тестирование при помощи системы. Для считывания полученной от SQL сервера таблицы добавим в код формы приведенный ниже метод.

private void Load_Tables(string query)

listView1.Items.Clear();

DataTable dt = Connection.GetSQLData(query);

foreach (DataRow row in dt.Rows)

DateTime d = new DateTime();

ListViewItem item = new ListViewItem(row.ToString());

for (int i = 1; i < dt.Columns.Count; i++)

if (i == dt.Columns.Count - 1)

d = Convert.ToDateTime(row[i]);

item.SubItems.Add(d.ToShortDateString());

item.SubItems.Add(row[i].ToString());

listView1.Items.Add(item);

Следующая форма - форма тестирования знаний. Элемент «DateTimePicker» размещен на форме для возможности точного слежения за временем начала и окончания сдачи теста. Данный элемент скрыт от пользователя и не отображается.

Для работы изменения вопросов и ответов теста добавим еще одну форму и придадим ей следующий вид.

Аналогичным путем были созданы и реализованы остальные формы автоматизированной системы тестирования знаний по дисциплине «Русский язык». Более подробно функционал программы представлен в разделе «Руководство пользователя» и в приложении «Листинг кода программы».