Python тілінде бағдарламалау

Жұмыс түрі: Реферат
Тегін: Антиплагиат
Көлемі: 16 бет
Таңдаулыға:

Мазмұны
Кіріспе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .4
І.Негізгі бөлім ... ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..5
1.1. Python тілінде бағдарламалау ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ...5
1.2. Графтардағы қысқа жолды іздеу ... ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ...8
1.2. Дейкстра алгоритмі ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...10
1.2. Форд Беллман алгоритмі ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ... ..14
ІІ. Практикалық бөлім ... ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..15
2.1 Берілген тапсырманы шығару жолы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .15
2.2 Python тілінде жазылған код ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 18
Қорытынды ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 20
Пайдаланылған әдебиеттер ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...21

КІРІСПЕ

Оптимизацияның көптеген қолданбалы есептері графтағы тиімділеу есептері арқылы сипатталады. Бұнымен қатар, графтар теориясындағы есептер оптимизациялау есептерімен шешіледі. Осыған байланысты графтағы оптимизациялау есептерін зерттеу және оны шешу әдістерін білу қажеттілігі туады. Бұл есептерді шешкенде алгоритмдік ойлау қабілетті қажет етеді, ал бұл дегеніміз, қазіргі білім элементіне жатады. Жұмыста графтағы оптимизациялау есептерінің ішінде классикалыққа айналғандағы қарастырылған. Бұлар:
- оптималды жабатын ағашты табу есебі
- графтағы ең қысқа жолды табу есебі
- желілік графтағы кризистік жолды табу есебі
- графтағы максималды ағынды табу есебі

Графтағы оптимизациялау есептерінің бизнес - қосымшаларына:
- телекоммуникациялық провайдердің кабельдік желісін төсеу;
- қаладағы максималды адамдарды таситын транспорттық жүйені құру;
- автомобиль магистральдарындағы транспорттық ағымдарды реттеу.

І. НЕГІЗГІ БӨЛІМ

1.1. Python тілінде бағдарламалау

Python-бір мезгілде қарапайым және қуатты объектілі-бағытталған бағдарламалау тілі болып табылады. Ол, жоғары деңгейдегі деректер құрылымын қамтамасыз ететін, талғампаздық синтаксисі бар және динамикалық теруді пайдаланады, ол түрлі қосымшалар арқылы бірнеше платформаларында жұмыс істеу үшін арналған тамаша тіл. Python - бүкіл әлем бойынша түрлі мақсаттар -деректер базасын және сөз өңдеу үшін кең таралған әмбебап тіл,ойындарға интерпретатор қосу,және де GUI-ді бағдарламалау және жылдам прототип құру (RAD)үшін арналған тіл. Сонымен қатар Python-INTERNETжәне WEB қосымшаларын бағдарламалау үшін пайдаланылады. Python бай стандартты кітапханадан, және модульдердің бай жиынтығынан тұрады.Python мен қосымшалар ең танымал және үлкен фирмалар пайдаланып жазылған, мысалға алып қарайтын болсақ: IBM, Yahoo, Google.com, Hewlett Packard, Infoseek, НАСА, Red Hat, CBS MarketWatch, Microsoft.
Бұл тілде:
· Mailman - тарату тізімдерінің менеджері (Тарату тізімін басқару), жоба адресаттар тізімдерінің (GNU)ресми менеджері болған.
· Медуза - HTTP, FTP, NNTP, XML-RPC секілді сенімді өнімділігі жоғары TCP IP серверлер үшін арналған архитектура.
· Zope - кең танымалдылыққа ие болған бағдарлама-Web қосымшалар сервері (Web бағдарлама сервері).
Python - бұл сізге керек. Python қарапайым, бірақ ол құрылымдау және басқаға қарағанда үлкен бағдарламалар бойынша қолдау үшін әлдеқайда нақты программалау тілі болып табылады. Екінші жағынан, қателерді өңдеу үшін жақсы және өте жоғары стандарт тілдік табылатын, икемді массивтер және сөздіктер ретінде кіріктірілген жоғары деңгейдегі деректер түрлері бар бағдарлама.Көптеген нәрселер Python-да жасалады. Басқа қосымшаларда пайдалануға болады,модульдер ішінде бағдарламаны бөлуге мүмкіндік береді. Python-ды сіз өз бағдарламаларыныз үшін негіз ретінде, немесе тілді зерттеу мысалдар ретінде пайдалануға болады. Стандартты модульдер түрлі графикалық кітапхана файлдар, жүйе қоңыраулар, желілерге қосылу, тіпті интерфейстердің жұмыс істеу үшін құралдар ұсынады. Python -уақытты айтарлықтай аз жұмсау үшін берілген тіл.
Python бағдарламалау тілінің тарихы

Python программалау тілі 1980 жылы ойластырылған, және оның құру Нидерландыда математика және информатика орталығында Гидо ван Россумның көмегімен 1989жылдың желтоқсанынан бастады. Python тілі операциялық жүйені ерекшелеп өңдеу және өзара іс-қимыл қабілетті бағдарламалау тілінде Ван Rossum негізгі авторы Python-мен осы күнге дейін тілді дамытуға қатысты шешім қабылдауда маңызды рөл атқаруын жалғастыруда. Python 2.0 нұсқасы 16 қазан, 2000 жылғы шығарды, және көптеген жаңа ірі мүмкіндіктерді қамтитын болды,осындай толық қоқыс жинау және Unicode қолдау ретінде қолданылды. Алайда, барлық өзгерістер ең маңызды тіл дамыту және оның құру неғұрлым мөлдір процесіне көшу процесінде өзгеруі болды.Ал Python-ның 3.0 алғашқы нұсқасы тестілеуден ұзақ уақыт өткеннен кейін 2008 жылы і желтоқсанда шығарылды. Бұл жаңа редакцияда мүмкіндіктердің көбі Python 2.6 және Python 2.7 сыйысымды.
Негізгі және аралық нұсқалардың уақыты:
· Python 1.0-Қаңтар 1994
· Python 1.5 - 31 желтоқсан 1997
· Python 1.6-5 қыркүйек 2000
· Python 2.0 - 16 қазан 2000
· Python 3.1-27 маусым 2009
· Python 3.2-20 ақпан, 2011
· Python 3.3-29 қыркүйек, 2012
· Python 3.4-16 наурыз, 2014
Салыстырмалы түрде кеш пайда болған Python программалау тілдерінің түрлі әсерінен құрылды:
· ABC - операторлар тобы үшін шегініс, жоғары деңгейдегі деректер құрылымын (картасы) (Python шын мәнінде ABC жобалау кезінде жасалған қателердi түзету әрекеті ретінде құрылды);
· Modula-3 - пакеттер, модульдер басқа функцияларынды пайдалана отырып, бірлесіп әрекет ету.(бұл да Common Lisp әсер) ;
· C, C ++ - кейбір синтаксистік конструкциялар ( Гидо ван Rossum жазғандай - Python үшін C бағдарламашылар арасында наразылық туғызып қалмас үшін ол, С конструкциясыныңбасқаша дизайнын пайдаланды);
· Smalltalk - объектілі-бағытталған бағдарламалау;
· Lisp - функционалдық бағдарламалау кейбір ерекшеліктері (lambda, map, reduce, filter және баскалары);
· Fortran - күрделі арифметикалық массивтер тілімі;
· Miranda - тізім-өрнек;
· Java - logging, unittest, threading модульдері (модуль бастапқы мүмкіндіктерінің бөлігі іске асырылмаған) xml.sax стандартты кітапхана және ерекшеліктерді іске асыру,және де @ декораторын қолдану үшін.
Бейімделген Python және барлық дерлік белгілі платформа жұмыс істейді - ККП-дан мэйнфреймов. Microsoft Windows үшін порттары, барлық дерлік нұсқалары (FreeBSD және Linux қоса алғанда) UNIX, Plan 9, Mac OS және Mac OS X, Iphone OS 2.0 немесе одан жоғары, Palm OS, OS 2, Amiga, HaikuOS, AS 400, тіпті OS бар 390, Windows Mobile, Symbian және Android. Платформаның ескіруі тілге көмек беруін тоқтатады. Мысалы, 2,6 Windows 95, Windows 98 және Windows ME [18] қолдау төмендеді. Алайда, бұл платформаларында, сіз Python алдыңғы нұсқасын пайдалануға болады - қазіргі уақытта қатты (олардың жүзеге түзетулер үшін) 2,3-ден Python нұсқасын қолдайды. Осылайша, барлық негізгі платформалардан көптеген жүйелердің айырмашылығы Python осы нақты платформа технологияларды (мысалы, Microsoft COM DCOM) қолдау бар. Сонымен қатар, Python В.М. Java арнайы нұсқасы бар - Jython, Java қолдайтын кез келген жүйесінде іске қосу үшін интерпретаторы беретін, Java сыныптар осылайша Python тікелей пайдаланылуы үшін тіпті жазылуы мүмкін. IronPython және Python.Net -Сондай-ақ, кейбір жобалар платформасында Microsoft .NET, негізгі біріктіруді қамтамасыз етеді.
Python-ның түрлері мен деректер құрылымы
Python-ның айнымалы түрі тек бағдарламаны орындау кезінде анықталады, динамикалық теруді қолдайды. Сондықтан оның орнына айнымалы тағайындау шамамен айтуға жақсы кейбір атымен міндетті күші құндылықтар. Python-ның кірістірілген түрлері: логикалық, жолды, Unicode-жолды, бүтін, еркін-дәлдігін, қалқымалы нүктелі нөмірін, комплекс санды, және басқалар. Python-ның жаңа түрін қосу, сіз класс (класс) жазыңыз, немесе (мысалы, C -жазылған) кеңейту модулінің жаңа түрін анықтауға болады. Сыныптар мұралық (бір және бірнеше) және метобағдарламалық әрекетті қолдайды.Ең кіріктірілген түрлері мұралық болып есептелінеді. Барлық нысандар сілтеме және атом болып бөлінеді. Атом бойынша INT және long күрделі және кейбір басқалар болады. Атом заттарды тағайындау кезінде ғана объектіге анықтамалық көрсеткіш үшін көшіріледі, ал олардың мәні көшіріледі, сондықтан бірдей мәнді тағайындау кезінде екі айнымалы қолданылады. Анықтамалық нысандар өтпелі және даусыз болып табылады. Айнымалы - Мысалы, жолдар және луын өзгермейтін және тізімдер, сөздіктер және басқа да көптеген нысандар болып табылады. Python жылы Tuple, шын мәнінде, өзгеріссіз тізімі болып табылады. Көптеген жағдайларда, луын жылдам тізімдері сондықтан сіз ретін өзгертуді жоспарлап болмаса, оларды пайдалану үшін үздік болып табылады.
Lisp және Прологта сияқты, Python интерпретаторы операторлар пернетақтадан енгізіледі, онда интерактивті режим, дереу орындалады бар, және нәтижесі (REPL) көрсетіледі. Бұл режим бастаушы ғана емес, қызықты, бірақ сондай-ақ, сіз басты бағдарлама оны пайдаланар алдында интерактивті кез келген аймақ кодын тексеру, немесе жай ғана функцияларын үлкен жиынтығы бар калькулятор ретінде пайдалануға болады деп есептейді тәжірибелі бағдарламашылар.
Интерактивті режимде PDB () (көмек үшін деп аталатын) көмек жүйесі қол жетімді. Анықтамалық жүйесі олар құжаттама жолдың қамтамасыз етілді, тек егер модульдермен функциялар үшін жұмыс істейді.

1.2. Графтардаығы қысқа жолды іздеу.

Графтардағы қысқа жолды іздеу әдістері графтар теориясының негізгі классикалық есептерінің бірі болып табылады. Графтардағы қысқа жолды іздеу есебі дегеніміз - графтағы жолды құрайтын қабырғалар салмақтарының қосындысы минималданатын екі нүктенің (төбенің) арасындағы ең қысқа жолды іздеу есебі болып табылады.
Қысқа (қарапайым, жай) тізбекті геодезиялық тізбек деп те атайды. Қысқа жол туралы есептің әртүрлі қойылу жағдайлары бар. Графтағы қысқа жолды іздеу есебі бағытталған, бағытталмаған немесе аралас графтар үшін анықталуы мүмкін. Бұл жұмыста қарапайым түрде бағытталмаған граф үшін есептің қойылуы қарастырылады. Бағытталған немесе аралас графтар үшін қосымша түрде қабырғалардың бағыттары ескерілуі керек.
Графтағы қысқа жолды іздеу есебіне ұқсас болатын есептегіш геометриядағы евклидтік қысқа жолды іздеу есебі, коммивояжер есебі, канадалық саяхатшы есебі, сызықтық программалау есептері т.б. бар. Қарастырылып отырған есептің әртүрлі қойылуларына сәйкес графтағы қысқа жолды іздеу есебін шешудің көптеген алгоритмдері белгілі. Олардың ішінен Дейкстра, Флойд-Уоршелл, Беллман-Форд, Джонсон, Ли (толқындық алгоритм), Килдала алгоритмдерін атауға болады. [1]
Сипатталатын алгоритм Дейкстра алгоритмі деп аталады. Дейкстра алгоритмі 1959 жылы нидерландтық оқымысты Эдсгер Дейкстраның ойлап тапқан графтардағы алгоритмі. Бұл алгоритм көмегімен қажетті ақпараттар берілген жағдайда теріс салмақты (теріс мәнді) қабырғалары жоқ графтардың бір төбесінен басқа төбелеріне дейінгі ең қысқа ара қашықтық табылады. Мысалы, сол кезде қажетті ақпараттар берілген жағдайда осы алгоритмді пайдаланып, бір қаладан басқа қалаларға барудың тиімді жолдар тізбегін анықтауға, кай елге мұнайды экспортқа шығару тиімділігін анықтауға мүмкіндік болды. Алгоритм программалауда, және көптеген технологияларда, мысалы OSPF және ІS-ІSмаршруттау хаттамаларында кең түрде қолданылады (OSPF - ағылшынша Open Shortest Path First - каналдың (link-state technology) жағдайын бақылау технологиясына негізделген және қысқа жолды табу үшін Дейкстра алгоритмін (Dijkstra's algorithm) қолданатын динамикалық маршруттау хаттамасы. IS-IS - қосылыстар жағдайына негізделген маршруттау хаттамасы, алынған ақпаратты алып қор жасақтайды, мұнда да ең тиімді маршрутты есептеу үшін Дейкстра алгоритмі қолданылады).
Бұл алгоритмнің бірнеше үлгілері (нұсқалары) бар. Дейкстра (1) алгоритмінің ең қысқа жолдың ұзындығын ғана емес жолдың өзін де анықтайтын қосымша қасиеті бар. Бұл ең қысқа жолдың әрбір төбесі үшін жолдың алдыңғы төбесін көрсетіп отыратын көрсеткіш көмегімен жүзеге асырылады. Сонымен, егер А мен В-ның арасындағы ең қысқа жолдың ұзындығы табылса, онда ең қысқа жолдың бойымен кері бағытта В-дан А-ға қарай қозғала отырып, жолдың өзін табуға болады. Мынадай теореманы тұжырымдаймыз.
Теорема. Егер a = v1 және b = v n болғанда v1 , v2 ,.., vi , vi+1 , ... , vj ,vj+1 ,..., vn - а мен b төбелері арасындағы ең қысқа жол (ара қашықтық) болса, онда бұл жолдың i v және j v төбелерінің арасындағы vi ,vi+1 ,...,vj бөлігі де vi және vj төбелерінің арасындағы ең қысқа жол болады.
Дейкстра (1) алгоритмі. Дейкстраның бірінші алгоритмінің тұжырымдамасын, одан соң оның қолданылу жағдайларын қарастырамыз. Алгоритмге сәйкес v1 төбесінен vn төбесіне дейінгі ең қысқа ара қашықтық іздестіріледі. v1 төбесінен басталады және v1 төбесінен бастап онымен ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.