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

«Задача коммивояжера» - Курсовая работа
- 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 работ
Следующая работа
Профессиональное самоопределение старшеклассников




-
Дипломная работа:
31 страниц(ы)
Введение …. 3
Глава 1. Понятие и основные признаки экстремизма . 6
Глава 2. Религиозно-политический экстремизм, социально-экономические и политические причины его проявления …. 11Глава 3. Государственная поддержка традиционного ислама как важный фактор профилактики экстремизма и терроризма в исламской среде (на примере Челябинской области) . 20РазвернутьСвернуть
Заключение …. 29
Список использованной литературы . 31
-
Дипломная работа:
58 страниц(ы)
Введение…. 3
ГЛАВА I. Средства художественной выразительности как объект лингвостилистических исследований1.1. Понятие лингвостилистических средств и их виды….5РазвернутьСвернуть
1.2. Взгляды ученых на классификацию стилистических выразительных средств…13
1.3. Роль лингвостилистических средств в реализации авторского замысла….16
Выводы по главе 1.
ГЛАВА II. Роль лингвостилистических средств в романе Николаса Спаркса «Дневник памяти»
2.1. Стилистические приемы как способ интерпретации сущности герое в литературе…. 21
2.2. Особенности художественного текста – личный дневник…. 23
2.3. Лингвостилистические средства в романе Николаса Спаркса «Дневник памяти»….27
Выводы по главе 2.
ГЛАВА III. Методика работы с текстом на уроках английского языка в средней школе.
3.1. Общие принципы работы с текстом на уроке английского языка…. 36
3.2. Методическая разработка внеклассного мероприятия по теме «Авторские приемы в создании образов в художественном произведении (на примере романа Н. Спаркса «Дневник памяти “The Notebook”))…41
Выводы по главе 3.
Заключение…49
Список используемой литературы
Приложение -
Контрольная работа:
Решения задач на Pascal Записи
15 страниц(ы)
4.4. Лабораторная работа 4
Тема: Записи
Вариант Задания
1 1. Распечатать список учеников, фамилии которых начинаютсяна букву В, с указанием даты их рождения.РазвернутьСвернуть
2 1. Из данного списка спортсменов распечатать сведения о тех
из них, кто занимается плаванием. Указать возраст, сколько
лет они занимаются спортом.
2. В таблице хранятся следующие данные об учениках:
фамилия, имя, отчество, рост, масса. Вычислить, каков
средний рост учеников, рост самого высокого и самого
низкого учеников.
3 1. Вычислить средний балл учеников класса, если известны оценки каждого ученика по математике, русскому языку и физике. Распечатать список учеников, имеющих средний балл выше среднего в классе.
2. На аптечном складе хранятся лекарства. Сведения о лекарствах содержатся в специальной ведомости: наименование лекарственного препарата, количество, цена, срок хранения (в месяцах). Выяснить сколько стоит самый дорогой и самый дешевый препарат; сколько препаратов хранится на складе
4 1. Распечатать фамилии рабочих бригады, начинающиеся с букв А и С, с указанием их месячной зарплаты.
2. Распечатать фамилии тех учеников класса, которые являются троечниками по итогам года. Также указать, насколько их средний балл отличается от среднего балла хорошиста с самым низким средним баллом среди хорошистов.
5
6 1. Распечатать список учеников музыкальной школы, которые учатся играть на скрипке. Указать также, сколько лет они занимаются музыкой и принимали ли участие в каких- либо конкурсах.
2. Распечатать список автомобилей, участвовавших в гонках (указать марку, время прохождения трассы, фамилию гонщика ). Кто пришел к финишу первым и последним?
8 1. Распечатать фамилии тех учеников, которые не получили ни одной тройки за последнюю четверть. В каких классах учатся эти ученики? Каков их средний балл?
2. В таблице хранятся следующие данные об учениках: фамилия, имя, отчество, рост, масса. Сколько учеников могут заниматься в баскетбольной секции, если рост баскетболиста должен быть больше 170 см?
9 1. Распечатать список тех учителей школы, которые преподают математику и информатику, указать стаж их работы и недельную нагрузку.
2. Даны результаты переписи населения, которые хранятся в памяти ЭВМ. Напечатать фамилии, имена и подсчитать общее число жителей женского пола, родившихся после 1990 г.
.
11 1. Распечатать анкетные данные учеников, участвовавших в олимпиаде по информатике и заработавших не менее 30 баллов.
2. Распечатать список учеников музыкальной школы, которые учатся играть на скрипке. Указать также, кто из них играет на каком либо другом инструменте и владеет английским языком.
12 2. Составить программу назначения стипендии студентам по результатам сессии, используя следующие правила:1) если все оценки 5, назначается повышенная стипендия; 2) если все оценки 4 и 5, назначается обычная стипендия; 3) если есть оценка 3, то стипендия не назначается. В результате работы программы должны быть напечатаны два списка фамилий (назначенных на повышенную и обычную стипендию)
15 2. Среди работников данного предприятия найти тех троих, чья заработная плата за месяц самая высокая по предприятию, а также распечатать список тех, кто проработал на предприятии менее 3 лет, с указанием их фамилии, зарплаты, стажа работы и должности.
-
Дипломная работа:
103 страниц(ы)
Введение 3
1. Аналитический обзор осуществления землеустроительных работ в Российской Федерации 6
1.1. Зарождение и становление землеустройства как отдельного вида регулирования земельных отношений 61.2. Развитие и проведение землеустройства в 1911 – 1990 гг. 11РазвернутьСвернуть
1.3. Современная земельная реформа и ее влияние на проведение землеустройства 21
2. Теоретические основы проведения землеустройства 29
2.1. Основные направления землеустройства и его организация 29
2.2. Нормативно-правовое регулирование осуществления землеустройства в Российской Федерации 36
2.3. Практика осуществления землеустройства 39
3. Анализ проведения землеустроительных работ по установлению границ земельного участка линейного объекта (на примере автодороги «Волоколамское шоссе км 20.6 – 35.5») 50
3.1. Цель и общие правила проведения землеустроительных работ в отношении линейных объектов 50
3.2. Характеристика исходных данных на обследуемую территорию 56
3.2.1. Особенности проведения землеустройства линий электропередач 58
3.2.2. Особенности проведения землеустройства трубопроводов 59
3.2.3. Особенности проведения землеустройства железных дорог 60
3.2.4. Особенности проведения землеустройства автомобильных дорог 62
3.3. Землеустроительные работы и состав землеустроительного дела по установлению границ полосы отвода автодороги «Волоколамское шоссе км 20.6 – 35.5» (на примере одного участка) 67
4. Расчет стоимости землеустроительных работ по объекту «Волоколамское шоссе» 84
5. Меры безопасности при производстве топографо-геодезических работ на автодорогах 93
Заключение 100
Библиографический список 103 -
Дипломная работа:
Воспитание выносливости у лыжников 15-16 лет, занимающихся в секции
56 страниц(ы)
ВВЕДЕНИЕ 3
ГЛАВА I. СОВРЕМЕННОЕ СОСТОЯНИЕ ИЗУЧАЕМОЙ ПРОБЛЕМЫ ПО ТЕМЕ ИССЛЕДОВАНИЯ 5
1.1 Общее понятие о выносливости и ее характеристика 51.2 Средства и методы воспитания выносливости у лыжников 15-16 лет, занимающихся в секции 15РазвернутьСвернуть
1.3 Возрастные особенности юношей 15-16 лет 26
ВЫВОДЫ ПО ПЕРВОЙ ГЛАВЕ 31
ГЛАВА II. МЕТОДЫ И ОРГАНИЗАЦИЯ ИССЛЕДОВАНИЯ 33
2.1. Методы исследования 33
2.2. Организация исследования 35
ГЛАВА III. РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ И ИХ ОБСУЖДЕНИЕ 36
3.1. Разработанный комплекс упражнений, направленный на воспитание выносливости у лыжников 15-16 лет, занимающихся в секции 36
3.2. Результаты исследования 37
3.3. Обсуждение результатов исследования 41
ВЫВОДЫ 46
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 48
-
Задача/Задачи:
10 страниц(ы)
Задача 1.
Асинхронный трехфазный двигатель с короткозамкнутым ротором типа 4A100S4 имеет следующие паспортные данные: напряжение U = 220/380В, номинальная мощность Pн = 3 кВт, частота вращения nн = 1434 об/мин, К.П.Д. = 82,0%, коэффициент мощности cos = 0,83, кратность пускового тока α = 6,0 перегрузочная способность двигателя λ= 2,4, кратность пускового момента β = 2,0.Определить, номинальный и пусковой токи двигателя при соединении обмотки статора в треугольник и звезду. Построить механическую характеристику не менее чем по 6 расчетным точкам. Возможен ли пуск нагруженного двигателя, если подводимое напряжение на 10% ниже номинального и если пуск производится путем переключения обмоток статора со звезды на треугольник от сети с напряжением 220В?РазвернутьСвернуть
-
Дипломная работа:
Исследование психофизиологических аспектов профессиональной деятельности офисных работников
105 страниц(ы)
Введение 3
Глава 1. Теоретические основы изучения особенностей двигательной активности офисных работников1.1. Понятие профессиональной гиподинамии, сидячего образа жизни, офисной работы, уровней физической активности 10РазвернутьСвернуть
1.2. Влияние физической активности на состояние здоровье человека, в том числе в процессе профессиональной деятельности, негативные эффекты гиподинамии 14
1.3. Социально-экономические факторы, сопутствующие недостаточной физической активности 22
Глава 2. Меры профилактики профессиональной гиподинамии, нейтрализации вызванных ею негативных последствий
2.1. Политика международных органов системы здравоохранения по вопросам предупреждения гиподинамии 32
2.2. Зарубежный опыт профилактики профессиональной гиподинамии. .43
2.3. Пути и способы решения проблем недостаточной физической активности офисных работников 49
2.4. Производственная физическая культура (гимнастика) 58
Глава 3. Опытно-экспериментальная работа по выявлению причин и условий, формирующих недостаток физической активности офисных работников
3.1. Методы и процесс исследования 70
3.2. Итоги опытно-экспериментальной работы по выявлению причин и условий, формирующих недостаток физической активности офисных работников 73
Заключение 78
Литература 80
Приложения 88 -
Дипломная работа:
Особенности изучения раздела «лексика» в 1 классе
62 страниц(ы)
ВВЕДЕНИЕ…3
ГЛАВА I. ЛИНГВИСТИЧЕСКИЕ ОСНОВЫ ИЗУЧЕНИЯ РАЗДЕЛА «ЛЕКСИКА» В НАЧАЛЬНОЙ ШКОЛЕ
1.1 Лексика русского языка как система….71.2 Методика работы над многозначными числами….16РазвернутьСвернуть
1.3 Психолого-педагогические основы развития речи младших школьников.19
Выводы по I главе….27
ГЛАВА II. ОПЫТНО-ПЕДАГОГИЧЕСКАЯ РАБОТА ПО ТЕМЕ ИССЛЕДОВАНИЯ
2.1 Анализ программ и учебников по русскому языку в аспекте активизации речи учащихся многозначных слов….….28
2.2 Система работы сформированности универсальных учебных действий по теме «Лексика»…32
2.3 Анализ результатов опытно-педагогической работы….38
Выводы по II главе….43
ГЛАВА III. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ
3.1 Методические рекомендации для учителей начальных классов в процессе обучения раздела «Лексика» в 1 классе….44
ЗАКЛЮЧЕНИЕ….57
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ….….59
-
Дипломная работа:
79 страниц(ы)
СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ 4
ВВЕДЕНИЕ 5
ГЛАВА 1. ПАТОГЕНЕЗ РАССЕЯННОГО СКЛЕРОЗА (ОБЗОР ЛИТЕРАТУРЫ) 81.1. Рассеянный склероз 8РазвернутьСвернуть
1.2. Роль Th17-клеток в иммунопатогенезе рассеянного склероза 14
1.3. Транскрипционный фактор RORYt и дифференциации Th17 клеток 21
1.4. Рецепторы глутамата и их участие в функционировании иммунных клеток при рассеянном склерозе 26
ГЛАВА 2. МАТЕРИАЛЫ И МЕТОДЫ ИССЛЕДОВАНИЯ 31
2.1. Материалы исследования 31
2.1.1. Объект исследования 31
2.1.2. Клинико-демографическая характеристика доноров 31
2.1.3. Перечень использованных реактивов 32
2.2. Методы исследования 34
2.2.1. Забор крови/биоматериала 34
2.2.2. Выделение лимфоцитов периферической крови 34
2.2.3. Культивирование лимфоцитов периферической крови 35
2.2.4. Иммунофенотипирование лимфоцитов 36
2.2.5. Внутриклеточное иммуноцитохимическое окрашивание цитокина IL-17A 36
2.2.6. Выделение суммарной РНК 37
2.2.7. Синтез комплиментарной ДНК (кДНК) с помощью РНК-зависимой ДНК-полимеразы 37
2.2.8. Количественная полимеразная цепная реакция с обратной транскрипцией (ОТ-ПЦР) в режиме реального времени 38
2.2.9. Методы статистического анализа результатов исследования 40
ГЛАВА 3. РЕЗУЛЬТАТЫ И ИХ ОБСУЖДЕНИЯ 41
3.1. Влияние (+)-МК801 на содержание CD4+ Т-клеток у здоровых доноров и доноров - больных рассеянным склерозом
3.2. Эффект блокады NMDA-рецепторов на содержание IL-17-продуцирующих CD4+ Т-клеток у здоровых доноров и доноров - больных рассеянным склерозом
3.3. Влияние (+)-MK801 на экспрессию гена транскрипционного фактора RORYt, специфичного для Th17 клеток, у здоровых и больных рассеянным склерозом доноров
ГЛАВА 4. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ИСПОЛЬЗОВАНИЮ РЕЗУЛЬТАТОВ ВЫПУСКНОЙ КВАЛИФИКАЦИОННОЙ РАБОТЫ В ШКОЛЬНОМ КУРСЕ «БИОЛОГИЯ» 41
4.1. Значение биологического образования 41
4.2. Анализ программ и учебников по реализации материалов ВКР в школе 43
4.3. Разработка урока по теме: «Иммунитет. Нарушения иммунной системы
человека. Вакцинация» для 8 класса 47
4.4. Применение логико-смысловой модели в образовательном процессе (педагогические методы) 53
ЗАКЛЮЧЕНИЕ 57
ВЫВОДЫ 58
СПИСОК ЛИТЕРАТУРЫ 59
ПРИЛОЖЕНИЕ 75
-
Дипломная работа:
Коррекция письменной речи у детей младшего школьного возраста
57 страниц(ы)
Введение 3
Глава 1. Развитие и изучение письменной речи у детей младшего школьного возраста 6
1.1. Нейропсихологические, психологические и психолингвистические аспекты развития письменной речи 61.2. Нарушения письменной речи у детей младшего школьного возраста 11РазвернутьСвернуть
1.3. Изучение детей с нарушениями письменной речи 17
Выводы по 1 главе 26
Глава 2. Изучение и коррекция нарушений письма у детей младшего школьного возраста 29
2.1. Организация экспериментальной работы и методы исследования нарушений письма у детей младшего школьного возраста 29
2.2. Исследование нарушений письменной речи у детей младшего школьного возраста и качественно-количественный анализ результатов 31
2.3. Методические рекомендации по коррекции письменной речи у детей младшего школьного возраста 35
Выводы по главе 2 41
Заключение 43
Список литературы 44
Приложения 47