У нас можно недорого заказать курсовую, контрольную, реферат или диплом

«Задача коммивояжера» - Курсовая работа
- 37 страниц(ы)
Содержание
Введение
Выдержка из текста работы
Заключение
Список литературы

Автор: navip
Содержание
Глава 1. Математическая формулировка
задачи о коммивояжере…. стр. 3
§1. Постановка вопроса…. стр. 3
§2. Некоторые примеры…. стр. 6
§3. Необходимые сведения из теории графов…. стр. 14
§4. Построение полного графа задачи о коммивоя-
жере на основе анализа графа коммуникаций…. стр. 17
Глава 2. Методы решения задачи о коммивояжере… стр. 19
§1. Эвристические методы и методы Монте-Карло. стр. 19
§2. Сведение задачи о коммивояжере к задачам це-
лочисленного линейного программирования … стр. 21
§3.Решение задачи о коммивояжере методами дина-
мического программирования…. стр. 25
§4.Метод ветвей и границ…. стр. 27
Заключение …. стр. 36
Литература …. стр. 37
Введение
Первоначально задача возникла как чисто развлекательная, впоследствии она утратила этот характер и нашла многочисленные практические применения. Так часто бывает в истории науки. Решения многих задач, казавшихся поначалу развлечениями и головоломками, впоследствии послужили ключом для решения важных теоретических и практических вопросов. Укажем, например, на задачу кавалера Де–Мере1, которая была решена Паскалем2 и послужила толчком для возникновения одного из основных понятий теории вероятностей — понятия математического ожидания, или на игры типа игры в «орлянку», размышления над которыми привели Бореля3 к формулировке основной теоремы теории игр, являющейся в настоящее время главным инструментом при изучении конфликтных ситуаций. При этом, конечно, нужно иметь в виду, что выдающиеся ученые, занимаясь подобными задачами, предвидели фундаментальную роль научных теорий, кладущихся в основу их решения.
Задача о коммивояжере удивительно просто формулируется: коммивояжер, выходящий из какого-нибудь города, желает посетить (n-1) других городов и вернуться к исходному пункту. Известны расстояния между всеми этими городами. Требуется установить в каком порядке он должен посещать города, чтобы общее пройденное расстояние было минимальным.
Если несколько видоизменить постановку задачи и не требовать возвращения к исходному пункту, то получим незамкнутую задачу о коммивояжере. В последующем мы покажем, что эта новая постановка задачи без труда может быть сведена к первоначальной.
Простота постановки задачи о коммивояжере сочетается с чрезвычайной трудностью ее решения, причем трудности не принципиального, а вычислительного характера, так как легко указать прием, прямо ведущий к цели: перебрать все маршруты и взять из них наименьший. Принципиально это возможно, поскольку общее число мыслимых маршрутов является конечным числом. Но все дело в том, что ни одна, даже самая быстродействующая вычислительная машина не в состоянии осуществить этот перебор при сколько-нибудь значительном числе городов.
1 Задача Де-Мере заключается в следующем: два игрока условились сыграть ряд партий, выигравшим считается тот, кто первым выиграл S партий. Игра была прервана тогда, когда один из игроков выиграл a(a 2 Паскаль, Блез (1623—1661 гг.)— выдающийся французский математик и физик, автор большого числа работ по геометрии, теории чисел, теории вероятностей и т. д. В 1641 г. одним из первых сконструировал суммирующий автомат.
3 Борель, Эмиль (1871—1956 гг.)— французский математик, известен своими работами в области анализа, теории множеств и теории вероятностей.
В самом деле, выходя из первого города, коммивояжер может направиться в один из (n— 1) городов, откуда в один из (n-2) оставшихся городов и т. д., пока не останется один-единственный город, откуда он вышел. Таким образом, общее число вариантов, подлежащих просмотру, составляет (n— 1) (n —2) .2- 1 = (n— 1)! вариантов. С увеличением числа городов это число чрезвычайно быстро возрастает и уже при 15—20 городах достигает астрономических цифр. Пропорционально возрастает и время на перебор этих вариантов. Поэтому от полного перебора всех вариантов приходится с самого начала отказаться из-за невозможности уложиться в любое разумно назначенное время, а вот поиск методов (алгоритмов), позволяющих быстро находить оптимальный маршрут оказался чрезвычайно трудным.
О трудности отыскания таких алгоритмов говорит хотя бы тот факт, что за решение одного из контрольных вариантов задачи (для 33 городов) некая мыловаренная компания США установила премию в 10000 долларов. Только несколько человек угадали оптимальный маршрут, но и их ответы не были признаны решением, поскольку, помимо четких математических предписаний, допускалось применение не более 25 слов текста для обоснования догадки.
Надо заметить, что, учитывая предшествующий опыт неудачных попыток решения задачи, компания не очень сильно рисковала. Примерно такая же по размерам премия, установленная до этого за решение сходной задачи фирмой RAND-Corporation, так и осталась неприсужденной.
К настоящему времени предложено большое количество алгоритмов для решения задачи о коммивояжере. Наиболее интересные из них нами будут описаны, а пока мы рассмотрим несколько задач, математическая формулировка, которых совпадает с формулировкой задачи о коммивояжере.
Теперь сформулируем упрощенный, или как говорят наивный, вариант этой знаменитой задачи. Она была поставлена в 1934 г., и об нее, почти что как об Великую теорему Ферма, с тех пор обламывают зубы лучшие математики. В своей области (оптимизации дискретных задач) задача коммивояжера служит своеобразным полигоном, на котором испытываются все новые методы.
Наивная постановки задачи следующая.
Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2, 3, . . . , n и вернуться в первый город. Расстояния между всеми городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?
Чтобы, как говорят соискатели, обнаучить задачу, введем некоторые термины. Итак, города перенумерованы числами j= {1, 2, ., n}. Тур коммивояжера может быть описан циклической перестановкой t=(j1, j2, j3,., jn, j1), причем вce j1, j2, j3,., jn разные номера; повторяющийся в начале и конце j1 показывает, что перестановка зациклена. Расстояния между парами вершин cij образуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал
Выдержка из текста работы
Математическая формулировка
задачи о коммивояжере
§1. Постановка вопроса
Первоначально задача возникла как чисто развлекательная, впоследствии она утратила этот характер и нашла многочисленные практические применения. Так часто бывает в истории науки. Решения многих задач, казавшихся поначалу развлечениями и головоломками, впоследствии послужили ключом для решения важных теоретических и практических вопросов. Укажем, например, на задачу кавалера Де–Мере1, которая была решена Паскалем2 и послужила толчком для возникновения одного из основных понятий теории вероятностей — понятия математического ожидания, или на игры типа игры в «орлянку», размышления над которыми привели Бореля3 к формулировке основной теоремы теории игр, являющейся в настоящее время главным инструментом при изучении конфликтных ситуаций. При этом, конечно, нужно иметь в виду, что выдающиеся ученые, занимаясь подобными задачами, предвидели фундаментальную роль научных теорий, кладущихся в основу их решения.
Задача о коммивояжере удивительно просто формулируется: коммивояжер, выходящий из какого-нибудь города, желает посетить (n-1) других городов и вернуться к исходному пункту. Известны расстояния между всеми этими городами. Требуется установить в каком порядке он должен посещать города, чтобы общее пройденное расстояние было минимальным.
Если несколько видоизменить постановку задачи и не требовать возвращения к исходному пункту, то получим незамкнутую задачу о коммивояжере. В последующем мы покажем, что эта новая постановка задачи без труда может быть сведена к первоначальной.
Простота постановки задачи о коммивояжере сочетается с чрезвычайной трудностью ее решения, причем трудности не принципиального, а вычислительного характера, так как легко указать прием, прямо ведущий к цели: перебрать все маршруты и взять из них наименьший. Принципиально это возможно, поскольку общее число мыслимых маршрутов является конечным числом. Но все дело в том, что ни одна, даже самая быстродействующая вычислительная машина не в состоянии осуществить этот перебор при сколько-нибудь значительном числе городов.
1 Задача Де-Мере заключается в следующем: два игрока условились сыграть ряд партий, выигравшим считается тот, кто первым выиграл S партий. Игра была прервана тогда, когда один из игроков выиграл a(a 2 Паскаль, Блез (1623—1661 гг.)— выдающийся французский математик и физик, автор большого числа работ по геометрии, теории чисел, теории вероятностей и т. д. В 1641 г. одним из первых сконструировал суммирующий автомат.
3 Борель, Эмиль (1871—1956 гг.)— французский математик, известен своими работами в области анализа, теории множеств и теории вероятностей.
В самом деле, выходя из первого города, коммивояжер может направиться в один из (n— 1) городов, откуда в один из (n-2) оставшихся городов и т. д., пока не останется один-единственный город, откуда он вышел. Таким образом, общее число вариантов, подлежащих просмотру, составляет (n— 1) (n —2) .2- 1 = (n— 1)! вариантов. С увеличением числа городов это число чрезвычайно быстро возрастает и уже при 15—20 городах достигает астрономических цифр. Пропорционально возрастает и время на перебор этих вариантов. Поэтому от полного перебора всех вариантов приходится с самого начала отказаться из-за невозможности уложиться в любое разумно назначенное время, а вот поиск методов (алгоритмов), позволяющих быстро находить оптимальный маршрут оказался чрезвычайно трудным.
О трудности отыскания таких алгоритмов говорит хотя бы тот факт, что за решение одного из контрольных вариантов задачи (для 33 городов) некая мыловаренная компания США установила премию в 10000 долларов. Только несколько человек угадали оптимальный маршрут, но и их ответы не были признаны решением, поскольку, помимо четких математических предписаний, допускалось применение не более 25 слов текста для обоснования догадки.
Надо заметить, что, учитывая предшествующий опыт неудачных попыток решения задачи, компания не очень сильно рисковала. Примерно такая же по размерам премия, установленная до этого за решение сходной задачи фирмой RAND-Corporation, так и осталась неприсужденной.
К настоящему времени предложено большое количество алгоритмов для решения задачи о коммивояжере. Наиболее интересные из них нами будут описаны, а пока мы рассмотрим несколько задач, математическая формулировка, которых совпадает с формулировкой задачи о коммивояжере.
Теперь сформулируем упрощенный, или как говорят наивный, вариант этой знаменитой задачи. Она была поставлена в 1934 г., и об нее, почти что как об Великую теорему Ферма, с тех пор обламывают зубы лучшие математики. В своей области (оптимизации дискретных задач) задача коммивояжера служит своеобразным полигоном, на котором испытываются все новые методы.
Наивная постановки задачи следующая.
Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2, 3, . . . , n и вернуться в первый город. Расстояния между всеми городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?
Чтобы, как говорят соискатели, обнаучить задачу, введем некоторые термины. Итак, города перенумерованы числами j= {1, 2, ., n}. Тур коммивояжера может быть описан циклической перестановкой t=(j1, j2, j3,., jn, j1), причем вce j1, j2, j3,., jn разные номера; повторяющийся в начале и конце j1 показывает, что перестановка зациклена. Расстояния между парами вершин cij образуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал
L=L(t)=∑ cik*tk+1 (1)
где jn+1=jn, а суммирование ведется по k от 1 до n. Относительно математизированной формулировки задачи коммивояжера уместно сделать два замечания.
Во-первых, в наивной постановке сij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех i, j
cij ≥ 0, cii=∞ (2)
(последнее равенство означает запрет на петли в туре); симметричными, т.е. для всех i,j
cij =cji (3)
и удовлетворять неравенству треугольника, т.е. для всех i, j, k
cij + cij ≥ cjk (4)
В математической постановке говорится о произвольной матрице С. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2) —(4) не удовлетворяют. Особенно часто нарушается условие (3) (например, если сij — не расстояние, а плата за проезд: мы уже привыкли, что железнодорожный билет Харьков — Москва отличается по цене от билета Москва — Харьков). Поэтому мы будем различать два варианта задачи о коммивояжере— симметричную задачу, когда условие (3) выполнено и несимметричную в противном случае. Условия (2) и (4) по умолчанию мы будем считать выполненными.
Второе замечание касается числа всех возможных туров. В несимметричной задаче о коммивояжере туры t=(j1, j2, j3,., jn, j1) и t'=(j1, jn, ., j2, j1) имеют разную длину и должны учитываться оба. Разных туров очевидно (n-1)!
Зафиксируем на первом и последнем месте в циклической перестановке номер j1, а оставшиеся n-1 номеров переставим всеми (n-1)! возможными способами. В результате получим все несимметричные туры. А симметричных туров имеется в два раза меньше, ибо каждый засчитан как два раза: как t и как t'.
Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i,j) проведено, если сij = 0 (нулю, а не единице как обычно) и не проведено, если cij = 1. Тогда если существует тур длины 0, то он пройдет по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом (в орграфе — гамильтоновым контуром). Незамкнутый гамильтонов цикл (соответственно, контур) называется гамильтоновой цепью (соответственно, гамильтоновым путем).
В терминах теории графов симметричную задачу о коммивояжере можно сформулировать так:
Дана полная сеть с n вершинами, длина ребра (i,j) равна cij. Найти гамильтонов цикл минимальной длины.
В несимметричной задаче о коммивояжере вместо «цикл» говорят «контур», а вместо «ребра» — «дуги» или «стрелки».
Некоторые прикладные задачи формулируются как задача о коммивояжере, но в них нужно минимизировать длину не гамильтонова цикла (или контура), а гамильтоновой цепи (или гамильтонова пути). Такие задачи называются незамкнутыми. Некоторые модели сводятся к задаче о нескольких коммивояжерах.
§2. HЕKOTOРЫЕ ПРИМЕРЫ
1. Задача Гамильтона
Выдающийся английский математик и механик Гамильтон изобрел игру получившую в свое время широкое распространение. Игрушка представляет собой додекаэдр (правильный многогранник с 12 пятиугольными гранями и 20 вершинами). Считается, что этот додекаэдр приблизительно изображает земной шар. Пусть каждая из вершин изображает «столицу» одного из государств. Требуется, двигаясь по ребрам додекаэдра, обойти все «столицы», заходя в каждую из них один и только, один раз, и вернуться в исходный пункт (рис. 1). Каждый такой путь, если он существует, называется гамильтоновым контуром, или гамильтоновым циклом.
Нетрудно догадаться, что если гамильтонов маршрут существует, то его длина будет равна 20, если же такого маршрута нет, то длина пути обхода будет равна бесконечности. Поэтому, если используя эту матрицу в качестве входных данных, решить задачу о коммивояжере, то сразу же получается ответ на вопрос о том, возможен ли такой обход, и если он возможен, то одновременно с этим указывается и один из вариантов этого обхода.
Практически установлено, что для указанного додекаэдра существует несколько совершенно равноценных гамильтоновых циклов.
Если несколько усложнить задачу и каждому ребру поставить в соответствие некоторые, вообще говоря, не равные между собой числа, именуемые «расстояниями между соседними столицами», то решение задачи о коммивояжере должно привести к указанию, «как правило, одного-единственного маршрута.
2. Задача об обходе шахматной доски
Почти аналогично выглядит задача об обходе конем шахматной доски, рассмотренная еще Эйлером.
Перенумеруем все клетки шахматной доски и будем считать, что «расстояние» между двумя клетками равно единице, если конь может за один ход перескочить с одной из них на другую, и что это «расстояние» равно бесконечности в противоположном случае. Составив таким образом «матрицу расстояний» по типу таблицы 1.1 и считая, что конь первоначально стоит на поле а1, попробуем решить незамкнутую задачу о коммивояжере, В этом случае решением задачи о коммивояжере может быть либо L=63, либо L=∞ . Если окажется. что L= 63, то такой, обход возможен, и полученное решение укажет один из искомых вариaантов. Если же L = ∞, то обход невозможен. Надо сказать, что любители головоломок нашли пути решения не прибегая к помощи математики, и один из возможных вариантов такого обхода показан на рис. 3.
3. Сбор по тревоге
Рассмотрим еще одну задачу, в которой развлекательная сторона выражена менее резко, чем в двух предыдущих примерах. Задача выглядит следующим образом.
Пионеры одного звена проживают в разных местах города. Время на движение любого из них до всех других обозначим ti,j, где i и j — их порядковые номера. Для быстрого сбора звена установлен такой порядок: вожатый, получив сигнал тревоги, идет к одному из пионеров, извещает его о полученном сигнале, а сам направляется на место сбора звена. Этот пионер подобным же образом извещает другого и также направляется на место сбора, и так далее. Последний из пионеров, получив сигнал, прямо отправляется на пункт сбора. Спрашивается, как нужно составить эту цепочку, чтобы время сбора по тревоге всего звена было минимальным.
Сформулированная таким образом задача является задачей о кратчайшем n-звенном маршруте. Отличие этой задачи от незамкнутой задачи о коммивояжере состоит в том, что в последней пункт окончания маршрута не имеет значения, а в задаче о кратчайшем n-звенном маршруте заранее указаны как пункт старта, так и пункт финиша. В дальнейшем будет показано, что, как и незамкнутая задача о коммивояжере, эта тоже сводится к задаче о коммивояжере в общей постановке,
4. Проводка и энергоснабжение
Можно указать бесконечное множество задач, связанное с объездом ряда пунктов с какой-либо целью и возвращением в исходную точку, например, развозка почты, продуктов питания и т. п. Аналогичный характер носят задачи соединения этих пунктов кольцевыми линиями энергопередач, газоснабжения и т.п.
Рассмотрим, например, задачу подводки электроэнергии к рабочим местам. Отправляясь от одного полюса источника энергии, требуется подвести провод к n потребителям и затем замкнуть проводник на другом полюсе. При этом расстояние между точками можно определить по формуле
R(i,j)=[(xi –xj)2+(yi –yj)2+(zi –zj)2]1/2
(x,y,z— координаты места потребления энергии), если допустимо проведение соединяющей проводки напрямую от одной точки до другой, или же несколько более сложным образом, если проводку разрешается осуществлять с соблюдением некоторых ограничений (например, только по стенкам помещения и обязательно параллельно его ребрам). Так, кратчайшее расстояние между точками i и j, определяемое с учетом указанных правил, изображено на рис. 4. Оно складывается из отрезков ia, ab, bj.
Особое значение задачи подобного рода могут иметь при разработке технологии автоматического монтажа радиоаппаратуры.
5. Определение оптимальной последовательности обработки деталей.
Пусть у нас имеется два станка и совокупность различных деталей, каждая из которых должна быть последовательно обработана на этих станках (например, токарная обработка и фрезерование). Будем считать, что:
а) на каждом станке может обрабатываться не более одной детали;
б) начавшаяся обработка детали не прерывается вплоть до ее окончания;
в) время на переналадку станков при переходе на обработку следующей детали пренебрежимо мало.
Время обработки k-й детали на каждом из станков обозначим ak и bk. Спрашивается в каком порядке надо обрабатывать детали, чтобы вся их совокупность была обработана возможно быстрее?
Легко заметить, что какую бы последовательность мы ни выбрали, токарный станок простаивать не будет, обрабатывая одну деталь за другой. Простаивает фрезерный станок, и вот время-то его простоя с момента начала выполнения заказа, по существу, и требуется минимизировать.
Подобного рода задачи часто возникают при планировании работы многомашинных вычислительных комплексов, в которых каждая из машин предназначена для выполнения определенных операций в ходе решения задач. Например, можно представить себе такой двухмашинный комплекс, в котором одна из машин осуществляет проверку правильности составления программы, записанной в алгоритмическом языке, и ее трансляцию, а вторая осуществляет собственно решение.
Пусть у нас имеются две детали, подлежащие обработке. Путем непосредственного просмотра различных комбинаций величин a1, b1, a2, b2 можно установить, что в случае, если
min(a1, b2)< min(a2, b1),
в обработку сначала нужно пускать первую деталь. В противоположном случае, т.e. когда
min(a2, b1)< min(a1, b2),
в обработку следует сначала пускать вторую деталь.
Наконец, в случае, если
min(a2, b1)= min(a1, b2),
порядок, в котором детали пускаются в обработку, не сказывается на общей длительности обработки.
Оказывается, что и в более общем случае нескольких деталей i-я деталь должна обрабатываться ранее j-ой, детали если
min(ai, bj)≤ min(aj, bi). (1.1)
Если теперь поставить в соответствие каждой i-ой детали совершенно произвольную точку на плоскости и считать что расстояние между i-й и j-й точками равно 1, если соблюдается соотношение (1.1) и ri,j=∞ в противоположном случае, то получим некоторую «матрацу расстояний».
По аналогии с введенным понятием гамильтонова контура будем называть гамильтоновьм путем незамкнутый маршрут, соединяющий все точки. Оказывается, каждый гамильтонов путь обхода точек соответствует оптимальной последовательности обработки деталей. А задача отыскания гамильтоновых путей, как было отмечено в первых двух примерах, есть частный случай задачи о коммивояжере.
Составим небольшой численный пример.
Пусть дан набор деталей, каждая из которых требует следующих затрат времени на токарную обработку и фрезерование:
Заключение
Целью этой курсовой работы являлось рассмотрение методов решения одной из задач минимизации — задаче о коммивояжере, а также выяснение связи этой задачи с другими задачами линейного программирования.
Все известные методы решения задачи о коммивояжере делятся на точные, эвристические и приближенные. Из приближенных алгоритмов наиболее известен так называемый “деревянный алгоритм”, который достаточно прост и вместе с тем обладает сравнительно большой точностью (путь, указанный им может отличаться от оптимального не более чем в 2 раза). Известно, что существует огромное число алгоритмов решения задачи о коммивояжере (на сегодняшний день таких алгоритмов около 50), поэтому здесь подробно рассмотрена лишь небольшая их часть — те алгоритмы, которые дают точное решение задачи о коммивояжере.
Важность решения задачи о коммивояжере связана с тем, что многие явления в физике (особенно в кристаллографии) и проблемы экономики представляются математическими моделями, решение которых и есть решение задачи о коммивояжере. Необходимо заметить, что реальные жизненные ситуации обычно оказываются намного сложнее искусственных схем. Тем не менее, методы решения и этих упрощенных моделей во многих случаях могут подсказать пути отыскания лучшего из множества конкурирующих вариантов.
Список литературы
1. Ашманов М. Г. Линейное программирование. М., Наука, 1989.
2. Бондарев В. М., Качко Е. Г., Рублинецкий В. И. Основы программирования. Ростов-на-Дону, 1998.
3. Бурков Р. И. Комбинаторное программирование. М., Знание, 1977.
4. Гольдштейн Е. Г., Юдин Д. Б. Новые направления в линейном программировании. — М., 1966.
5. Карманов Э. Т. Математическое программирование. М., Наука, 1980.
6. Карп Р. М. Сводимость комбинаторных проблем. М., Мир, 1975.
7. Киржнер В. М., Рублинецкий В. И. О процедуре “иди в ближайший” в задаче коммивояжера. Харьков, 1973.
8. Дж. Литл, К. Мурти, Д. Суини, К. Кэрел. Алгоритм для решения задачи о коммивояжере. ─ “ Экономика и математические методы”, т.1, вып. 1, 1965.
9. Мудров В. И. Определение гамильтоновых путей кратчайшей длины в полном графе методами целочисленного программирования. — Техническая кибернетика, 1965, № 2.
10. Мудров В. И. Задача коммивояжера. М., Знание, 1969.
Тема: | «Задача коммивояжера» | |
Раздел: | Информатика | |
Тип: | Курсовая работа | |
Страниц: | 37 | |
Цена: | 1200 руб. |
Закажите авторскую работу по вашему заданию.
- Цены ниже рыночных
- Удобный личный кабинет
- Необходимый уровень антиплагиата
- Прямое общение с исполнителем вашей работы
- Бесплатные доработки и консультации
- Минимальные сроки выполнения
Мы уже помогли 24535 студентам
Средний балл наших работ
- 4.89 из 5
написания вашей работы
-
Дипломная работа:
Методика решения олимпиадных задач
46 страниц(ы)
ВВЕДЕНИЕ.3
ГЛАВА I. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО РЕШЕНИЮ ОЛИМПИАДНЫХ ЗАДАЧ ПО ИНФОРМАТИКЕ.4
1.1. Динамическое программирование.41.2. Перебор с возвратом.5РазвернутьСвернуть
1.3. Алгоритмы на графах.7
1.4. Вычислительная геометрия.10
1.5. Комбинаторные алгоритмы.14
ГЛАВА II. ОРГАНИЗАЦИЯ УЧЕБНОЙ ДЕЯТЕЛЬНОСТИ ПО РЕШЕНИЮ ЗАДАЧ .16
ГЛАВА III. БИБЛИОТЕКА ОЛИМПИАДНОЙ ИНФОРМАТИКИ.24
ЗАКЛЮЧЕНИЕ.29
СПИСОК ЛИТЕРАТУРЫ.30
ПРИЛОЖЕНИЕ.34
-
Дипломная работа:
Программный модуль формирования маршрутов транспортных средств на базе эволюционного алгоритма
68 страниц(ы)
ВВЕДЕНИЕ 3
ГЛАВА 1. ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ И МЕТОДЫ ИХ РЕШЕНИЯ 5
1.1 Обзор и анализ существующих задач маршрутизации 51.2 Методы решения задач маршрутизации 6РазвернутьСвернуть
1.3 Основные понятия эволюционного алгоритма 12
ГЛАВА 2. ПРОЕКТИРОВАНИЕ ПРОГРАММНОГО МОДУЛЯ 15
2.1 Постановка задачи маршрутизации 15
2.2 Применение операторов и процедур для эволюционного алгоритма 17
2.3 Проектирование программного модуля в программе BPwin 19
ГЛАВА 3. РАЗРАБОТКА ПРОГРАМНОГО МОДУЛЯ 23
3.1 Обзор и анализ существующих языков программирования 23
3.2 Техническое задание к программному модулю 26
3.3 Программная реализация разработанного эволюционного алгоритма 31
3.4 Вычислительный эксперимент 45
3.5 Анализ экономической эффективности 50
ЗАКЛЮЧЕНИЕ 66
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 67
-
Дипломная работа:
Программный модуль формирования маршрутов транспортных средств на базе генетического алгоритма
60 страниц(ы)
ВВЕДЕНИЕ 3
ГЛАВА 1. ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ ДЛЯ ПРОЦЕССА ОПТИМИЗАЦИИ МАРШРУТОВ 5
1.1 Значимость оптимизации маршрутов в логистических системах 51.2 Задачи и особенности транспортной логистики 6РазвернутьСвернуть
1.3 Способы решения задач маршрутизации 7
1.4 Основные понятия генетического алгоритма 12
1.5 Основные принципы работы генетического алгоритма. Операторы и процедуры генетического алгоритма 13
ГЛАВА 2. ПРОЕКТИРОВАНИЕ ПРОГРАММНОГО МОДУЛЯ ДЛЯ ПОСТРОЕНИЯ МАРШРУТОВ ТРАНСПОРТНЫХ СРЕДСТВ 17
2.1 Математическая модель задачи маршрутизации 17
2.2 Применение операторов и процедур генетического алгоритма 18
2.3 Техническое задание 22
2.4 Проектирование программного модуля для решения задачи
2.5 Маршрутизации в программе BPwin 25
ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ 29
3.1 Выбор языка программирования 29
3.2 Программная реализация 30
3.3 Руководство пользователя 33
3.4 Вычислительный эксперимент 35
3.5 Оценка эффективности работы разработанного алгоритма 36
3.6 Расчет экономической эффективности системы 40
ЗАКЛЮЧЕНИЕ 52
ЛИТЕРАТУРА 55
ПРИЛОЖЕНИЯ 58
-
Дипломная работа:
73 страниц(ы)
ВВЕДЕНИЕ 3
ГЛАВА I. ТЕОРЕТИКО-МЕТОДОЛОГИЧЕСКОЕ ОСНОВАНИЕ МОДЕЛИРОВАНИЯ В СИСТЕМЕ НАЧАЛЬНОГО ОБРАЗОВАНИЯ 8
1.1. Философский смысл понятий "модель" и "моделирование" 81.2. Роль и место действия моделирования в стандарте нового поколения для начальной школы 17РазвернутьСвернуть
1.3. Уровни моделирования содержания текстовых задач на движение в начальной школе 23
Выводы по главе I 31
ГЛАВА II. ЭКСПЕРИМЕНТАЛЬНАЯ РАБОТА ПО МОДЕЛИРОВАНИЮ СОДЕРЖАНИЯ ТЕСТОВЫХ ЗАДАЧ НА ДВИЖЕНИЕ В НАЧАЛЬНОЙ ШКОЛЕ 33
2.1. Программа по обучению учащихся моделированию содержания текстовых задач на движение 33
2.2. Этапы и содержание экспериментальной работы по осуществлению программы 39
2.3. Подведение итогов опытной работы и разработка методических рекомендаций для учителей по моделированию текстовых задач 43
Выводы по главе II 46
ЗАКЛЮЧЕНИЕ 48
ЛИТЕРАТУРА 50
ГЛОССАРИЙ ПО КАТЕГОРИАЛЬНОМУ АППАРАТУ 54
ГЛОССАРИЙ ПО ПЕРСОНАЛИЯМ 55
ПРИЛОЖЕНИЕ 1 56
ПРИЛОЖЕНИЕ 2 65
-
Дипломная работа:
Изучение текстовых задач на уроках математики в начальных классах
87 страниц(ы)
ВВЕДЕНИЕ…. 3
ГЛАВА I. ТЕОРЕТИКО-МЕТОДОЛОГИЧЕСКОЕ ОСНОВАНИЕ ИЗУЧЕНИЯ ТЕКСТОВЫХ ЗАДАЧ НА УРОКАХ МАТЕМАТИКИ В НАЧАЛЬНОЙ ШКОЛЕ.1.1.Роль и место текстовых задач в содержании в курсе математики в начальной школе…7РазвернутьСвернуть
1.2. Подходы к изучению текстовых задач в различных методических системах…. 17
1.3. Методическая система изучения текстовых задач в учебно-методическом комплексе «Школа России»….23
ГЛАВА II. ОПЫТНО-ПЕДАГОГИЧЕСКАЯ РАБОТА ПО ИЗУЧЕНИЮ ТЕКСТОВЫХ ЗАДАЧ ПРИ ИЗУЧЕНИИ КУРСА МАТЕМАТИКИ В НАЧАЛЬНОЙ ШКОЛЕ.
2.1. Инновационный проект по изучению текстовых задач в 4 классе основанное на УМК «Школа России»…40
2.2. Этапы и содержания опытно-экспериментальной работы по использованию современных подходов к изучению текстовых задач…. ….46
2.3. Подведение итогов опытной работы и разработка методических рекомендаций для учителей начальных классов…72
ЗАКЛЮЧЕНИЕ….78
ЛИТЕРАТУРА ….81
-
ВКР:
Обучение решению нестандартных задач по алгебре
94 страниц(ы)
Введение 3
1 Психолого-педагогические основы определения понятия «задача» 6
1.1 Различные подходы к определению понятия «задача» 61.2 Функции и классификация задач в обучении математике 10РазвернутьСвернуть
1.3 Обучение поиску решения задач 15
1.4 Структура решения задач 18
1.5 Нестандартные методы решения задач в школьном курсе математики 20
Выводы по главе 1 30
2 Функциональный метод решения нестандартных задач 31
2.1 Место изучения функциональной зависимости в школьном курсе математики 31
2.2 Решение задач с использованием свойств функций 32
2.3 Педагогический эксперимент 52
Выводы по главе 2 55
Заключение 59
Список использованной литературы 60
Приложения 63
Не нашли, что искали?
Воспользуйтесь поиском по базе из более чем 40000 работ
Следующая работа
Профессиональное самоопределение старшеклассников




-
Курсовая работа:
61 страниц(ы)
Введение
Глава I. Суфражистское движение в Англии
1. Первые женские политические группы в Великобритании2. Эммелин Панкхерст – глава Женского союзаРазвернутьСвернуть
3. Лига за избирательные права женщин
4. Независимая лейбористская партия
5. Женский социально-политический союз
Глава II. Проведение социологического опроса по выявлению избирательной активности среди женщин и мужчин, провести сравнительный анализ.
Заключение
Литература
Прложение
-
Дипломная работа:
Средства и методы воспитания выносливости
45 страниц(ы)
ВВЕДЕНИЕ 3
ГЛАВА I. ОБЗОР ЛИТЕРАТУРНЫХ ИСТОЧНИКОВ 5
1.1 Общая характеристика выносливости 5
1.2 Этапы развития выносливости 101.3 Методы развития общей и специальной выносливости у бегунов на средние дистанции 15РазвернутьСвернуть
1.4 Воспитание выносливости в зонах различной мощности 18
ГЛАВА II. ЦЕЛИ, ЗАДАЧИ, МЕТОДЫ, ОРГАНИЗАЦИЯ ИССЛЕДОВАНИЯ 22
2.1 Цель и задачи исследования 22
2.2 Методы исследования 23
2.3 Организация исследования 26
ГЛАВА III. РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ 30
3.1 Результаты исследования 30
3.2 Обсуждение результатов 34
ВЫВОДЫ 36
СПИСОК ЛИТЕРАТУРЫ 38
ПРИЛОЖЕНИЕ 41
-
Курсовая работа:
Развитие художественного вкуса будущих дизайнеров средствами образовательной среды
38 страниц(ы)
ВВЕДЕНИЕ….…3
Глава I. Дизайн как категория эстетической деятельности и художественная коммуникация….6
1.1. Понятия дизайн и дизайнер…61.2. Виды и функции дизайна….…9РазвернутьСвернуть
Глава II. Эстетический и художественный вкус: сущность, значение и формирование…12
2.1. Определение понятия эстетический вкус….….…12
Глава Ш. Формирование эстетического вкуса и роль художественной культуры в процессе подготовки дизайнеров….18
3.1. Формирование эстетического вкуса студентов в образовательном процессе….18
3.2. Развитие художественного вкуса будущих дизайнеров….….22
ЗАКЛЮЧЕНИЕ….31
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ….….….34
-
Дипломная работа:
Музыкальное самообразование взрослых на основе музыкально-компьютерных технологий
76 страниц(ы)
ВВЕДЕНИЕ .3
ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МУЗЫКАЛЬНОГО САМООБРАЗОВАНИЯ У ВЗРОСЛЫХ 8
1.1. Самообразование на основе музыкального искусства 81.2. Музыкально-компьютерные технологии как основа музыкального самообразования взрослых 24РазвернутьСвернуть
Выводы по главе 1 37
ГЛАВА 2. УСЛОВИЯ МУЗЫКАЛЬНОГО САМООБРАЗОВАНИЯ ВЗРОСЛЫХ НА ОСНОВЕ МУЗЫКАЛЬНО-КОМПЬЮТЕРН ТЕХНОЛОГИЙ 39
2.1. Формы музыкального самообразования взрослых 39
2.2. Педагогический эксперимент и его результаты 54
Выводы по главе 2 66
ЗАКЛЮЧЕНИЕ 68
СПИСОК ЛИТЕРАТУРЫ 70
ПРИЛОЖЕНИЕ А 75
ПРИЛОЖЕНИЕ Б 76
-
Дипломная работа:
Гендерные различия влияние школьной тревожности на успеваемость подростков
190 страниц(ы)
Введе-ние_ 3
Глава I. Теоретические аспекты проблемы гендерных различий
1.1. Анализ исследований отечественных и зарубежных психологи по проблеме гендерных разли-чий_71.2. Гендерные различия и социализа-ция_18РазвернутьСвернуть
1.3. Ограничение, накладываемые традиционной женской и мужской ролью_21
1.4. Гендер в разных культурах_27
Глава II. Теоретические аспекты проблемы школьной тревожности и ее влияние на успеваемость
2.1. Анализ исследований отечественных и зарубежных психологи по проблеме тревожности _30
2.2. Зависимость тревожности от психических свойств личности _34
2.3. Изучение природы тревожности и уровни тревожности _41
2.4. Причины тревожности и их последствия у школьников _45
1.5. Внешние и внутренние источники тревожности _54
1.6. Психологические особенности учебной деятельности
подростков _66
Выводы _73
Глава III. Эмпирические исследование гендерных различий тревожности и ее влияние на успеваемость школьников
3.1.Общая характеристика выборки и методов исследования_75
3.2Анализ результатов исследова-ния_80
Вы-вод_95
Заключе-ние_97
Литература _100
Приложение _105
-
Контрольная работа:
24 страниц(ы)
Введение 3
1. Регистрация документов и журнальная система регистрации документов 4
2. Карточная система регистрации 123. Автоматизированные системы регистрации 15РазвернутьСвернуть
Заключение 23
Список литературы 24
-
Курсовая работа:
Становление юридической терминологии в языке деловой письменности xviii века
28 страниц(ы)
ВВЕДЕНИЕ…. 3
ГЛАВА I. Юридический язык в системе современного официально-делового стиля
1. Понятие и функции официально-делового стиля… 52. Стилевые и языковые черты официально-делового стиля…. 6РазвернутьСвернуть
3. Понятие и функции юридического подстиля и языка права…. 7
4. Характерные черты языка права… 9
5. О терминологии языка права … 10
ГЛАВА II. Исторические сведения об общественно-политическом строе и правовой системе Российского государства XVIII в.
1. Становление административно-полицейских и судебных органов…. 12
2. Особенности законодательной системы при Петре I и Екатерине II… 13
3. Развитие институтов гражданского, уголовного и процессуального права в XVIII в. … 13
ГЛАВА III. Особенности функционирования юридической терминологии в языке деловой письменности XVIII в.….… 17
ЗАКЛЮЧЕНИЕ….… 25
СПИСОК ЛИТЕРАТУРЫ… 26
-
Дипломная работа:
90 страниц(ы)
ВВЕДЕНИЕ 3
ГЛАВА 1. ОБЗОР ЛИТЕРАТУРЫ 7
1.1. Полимерный гидрогель 17
1.1.1. Полиакриламид и акриламид 27
1.1.2. Влияние гидрогеля на растения 311.2. Характеристика использованных видов 33РазвернутьСвернуть
1.2.1. Chlorella vulgaris Beijer 33
1.2.2. Eustigmatos magnus (B. Petersen) Hibberd 34
1.2.3. Scotiellopsis rubescens Vinatzer 35
1.2.4. Nostoc sp. (Cyanobacteria) 36
1.3. Сельскохозяйственные культуры 37
ГЛАВА 2. МАТЕРИАЛЫ И МЕТОДЫ ИССЛЕДОВАНИЯ 42
2.1. Характеристика гидрогеля 42
2.2. Методика культивирования микроводорослей и цианобактерий 42
2.3. Методика подсчета клеток в камере Горяева и определения плотности биомассы с помощью фотоэлектроколориметра 44
2.4. Методика проращивания и определения всхожести семян Triticum aestivum L. и Secale cereale L 47
2.5. Методика проведения исследования 48
2.6. Методика оценки жизнеспособности проростков 50
ГЛАВА 3. РЕЗУЛЬТАТЫ И ИХ ОБСУЖДЕНИЕ 52
ВЫВОДЫ 82
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 84
-
Дипломная работа:
98 страниц(ы)
Введение 3
Глава 1. Деятельность психолого-педагогических центров по сопровождению детей с детским церебральным параличом1.1. Психолого-физиологические особенности детей с детским церебральным параличом 7РазвернутьСвернуть
1.2. Практический опыт по сопровождению детей с детским церебральным параличом 24
1.3. Инклюзивное образование, как реализация права 28
Выводы по I главе 33
Глава 2. Особенности произносительной стороны речи у детей дошкольного возраста с детским церебральным параличом
2.1. Методика обследования произносительной стороны речи у дошкольников с детским церебральным параличом 36
2.2. Анализ констатирующего эксперимента 41
Выводы по II главе 43
Глава 3. Организация психолого-педагогического сопровождения детей с детским церебральным параличом
3.1. Опыт работы Государственного бюджетного учреждения Республики Башкортостан Западный межрайонный центр «Семья» 46
3.2. Программа коррекции речи детей с детским церебральным параличом.49
3.3. Результаты диагностического исследования произносительной стороны речи у дошкольников с детским церебральным параличом 57
Выводы по III главе 60
Заключение 62
Список литературы 67
Приложение
-
Дипломная работа:
77 страниц(ы)
1. ВВЕДЕНИЕ 3
ГЛАВА 1. ЭМБЛЕМА В РИТОРИЧЕСКОЙ КУЛЬТУРЕ 6
1.1 Эмблема и эмблематический образ 6
2.2. Эмблема в эстетике барокко 101.3. Эмблематика и риторика в эстетике классицизма 16РазвернутьСвернуть
Выводы по главе 1 22
ГЛАВА 2. ЭМБЛЕМАТИЧЕСКИЕ ОБРАЗЫ В ЛИТЕРАТУРЕ: XVII ВЕК И СОВРЕМЕННОСТЬ 23
2.1 Эмблематические образы и их роль в баснях Ж. де Лафонтена 23
2.2 Эмблематические образы как приём стилизации 35
в романе П. Киньяра 35
Выводы по главе 2 41
ГЛАВА 3. ИНТЕРАКТИВНЫЕ МЕТОДЫ ОБУЧЕНИЯ ФРАНЦУЗСКОМУ ЯЗЫКУ НА ПРИМЕРЕ РАБОТЫ С ТЕКСТАМИ Ж. ДЕ ЛАФОНТЕНА 42
3.1 Техника «медленного чтения» 42
3.2 От визуальной картины к словесной: креативные задания на материале эмблематических образов (иллюстрация, шарады, описания-загадки) 48
3.3 Инсценировка басен Ж.де Лафонтена 54
Выводы по главе 3 57
ЗАКЛЮЧЕНИЕ 58
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 60
ПРИЛОЖЕНИЕ 64