Сараң алгоритмдерде шешім қабылдау

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

ШЖН – ОБ – 00109 – 2005
ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ

Қ. А. Ясауи атындағы Халықаралық қазақ – түрік университеті
Шымкент институты

Факультет: Физика – Математика
Кафедра: Ақпараттандыру

КУРСТЫҚ ЖҰМЫС

Тақырып: Сараң алгоритмді есептер шығаруда қолдану.
Пән: Информатиканың теориялық негіздері
Мамандығы: 050111 - Информатика

Орындаған: Тұрарбеков Мұхит.
Қабылдаған: Исатаева Ұлбосын.

ШЖН – ОБ – 00109 – 2005
ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ
Қ. А. Ясауи атындағы Халықаралық қазақ – түрік университеті
Шымкент институты

Факультет: Физика – Математика
Кафедра: Ақпараттандыру
Патенттік ізденіске
ТАПСЫРМА
Студент:: Тұрарбеков Мұхит тобы: 142-27
(аты-жөні)
Курстық жұмыстың тақырыбы: Сараң алгоритмді есептер шығаруда қолдану.
Ізденістің элементі
Ізденістің тереңділігі
Қарастырылатын мемлекетте
Классификатордың индексі
Ақпараттың дерек көзі

Ізденіс жұмыстың аяқталу мерзім
Курстық жұмыстың жетекшісі: Жақыпбекова Гүлнар (оқытушының аты – жөні, қызметі)
Студент: Тұрарбеков Мұхит.
ШЖН – ОБ – 00109 – 2005

Қ. А. Ясауи атындағы Халықаралық қазақ – түрік университеті
Шымкент институты

Факультет: Физика – Математика
Кафедра: Ақпараттандыру

Бекітемін
Кафедра меңгерушісі

2008 ж.
Студенттің курстық жұмысына
ТАПСЫРМА

(студенттің аты – жөні)

1. Жұмыстың тақырыбы:

2. Жұмыстың аяқталу уақыты:

3. Жұмысқа керек материалдар

4. Жұмыстың мазмұны (әдебиеттік және патенттік ізденісі, экспериментальдық бөлім, заттың шығу сипаттамасы, эксперименттің әдістемесі, экспериментальдық материалдарға талдау, қорытынды)
5. Кестелік және графикалық материалдардың тізімі
6.Әдебиеттер тізімі
7. Курстық жұмыстың орындалуы туралы график

Тарау (бөлім)

Мерзімі (ай)
Мерзімінің орындалуы, қолы

Берілген тапсырмалар
Алынған тапсырмалар
Теориялық бөлімі

Негізгі бөлімі

Қорытынды

Материалдардың талдауы

Алдын ала қорғау

Комиссияның алдында қорғау

8.Тапсырманың берілген уақыты
Курстық жұмыстың жетекшісі: Жақыпбекова Гүлнар
(оқытушының аты – жөні, қолы)
9.Тапсырманы алған студент: Тұрарбеков Мұхит
(студенттің аты – жөні)

ШЖН – ОБ – 00109 – 2005
Мазмұны

Кіріспе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 3
I-тарау . Сараң алгоритмдерде шешім қабылдау.
1.1 Сараң алгоритмдердің қолданушылық қасиеті ... ... ... ... ... ... 4
1.2 Сараң алгоритмде шешім қабылдау тәсілі ... ... ... ... ... ... ... ... . 6

II-тарау. Сараң алгоритмдерді қолдану шарттары.
2.1 Жалпы міндеттен жеке міндеттерді ажырату мүмкіндіктері ... 8
2.2 Міндеттер қарастырылатын шаралардың үздіксіздігі ... ... ... .. 12

Қорытынды ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 14
Әдебиеттер тізімі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 16

ШЖН – ОБ – 00109 – 2005
Кіріспе
Сыртқы сорттау ретінде артқы жадқа орналасқан файлдар тізбегін сорттау түсініледі. Негізінен сыртқы сорттау БҚБЖ-де сұраныстар орындауда қолданылады. БҚБЖ-нің сұраныстардың өнімділігі қолданылатын әдістердің тиімділігіне қарай анықталады. Сыртқы сорттау әдістері сыртқы әдістері сыртқы жад үшін магниттік ленталар қолданыла бастаған кезеңде пайдаланылды. Ленталарда мәліметтер тізбектей сақталады. Бірақ магниттік дискі түрінде есте сақтау құрылғылары пайда болумен, әрбір информация блогына тікелей енуге мүмкіндік туады. Файлдар дискіге жолшалар мен секторлар бойынша жазылады. Сондықтан бір файл бірнеше бөліктен дискіге сақталуы мүмкін. Сондықтан мәліметтерді дискіге жазу және оқу бастигі ( головка ) көбірек қозғалысқа түседі. Қазіргі кезде файл блоктарын мүмкіндігінше дискіде бір-біріне жақын орналастыру жағдайлары қарастырылған яғни дискіні оптимациялау дефрагменацилау программалау кеңінен қолданылады. Сондықтан файлдық блоктары дискіде тізбектей орналасқанда ғана, бастиек ақырақ қозғалысқа түсіп, аз уақыт шығындайды. Қазіргі кезде БҚБЖ тек осындай файлдарды сорттайды.
Сыртқы сорттаудың жылдамдылығына жедел жадтың буфері өлшемі де ықпал етеді. Біз мүмкіндігінше операциялық жадтан аз орын талап ететін негізгі сырттай сорттау әдістерін қарастырамыз.
Курстық жұмыстың мақсаты – сараң алгоритмдер ұғымын ашып, рюгзяк туралы үздіксіз есеп шығару

ШЖН – ОБ – 00109 – 2005
Сараң алгоритм

Сараң алгоритм - алгоритм, жергілікті үйлесімді шешімдерді қабыл алуында болушы әрбір үйлесімді ақырғы шешімді сонымен қатар шешуге болады немесе рұқсат етеді .
Егер глобальды оптимальность практикалық әрқашан алгоритмды орын болады, ықшамдау басқа әдістеріне оны әдеттегі жоғары бағалайды, сондай-ақ динамикалық бағдарламалау сияқты http : ru . org wikipedia . wiki динамикалық _ бағдарламалау .
Алгоритмдер қасында дәл осындай ықшамдау көптеген мақсаттары салыстырмалы жылдам және қарапайым шешіледі. Жергілікті үйлесімді талдау сондай алгоритм әрбір адымда істейді, рұқсат ете, не үйлесімді қорытынды шешім сонымен қатар болады. Бірақ мынау әрқашан дәл осылай емес, бірақ ішін алгоритмдік мақсаттарды үлкен сандары сараң алгоритмдер үйлесімді шешімді нақты береді. Керек белгілеп қою, не сұрақ белгі мақсаттарды әрбір сыныбында сараң алгоритм қолданунышылығы туралы шешіледі, бірақ жалпы шешім негіздеуіне арналған матроид теориясы бар болады.
Сараң алгоритмдерді жұмыс схемасын қарап шығамыз нақтылыларды үлгілерде.
Мақсат мәлімдемелерді талдауы туралы
- дәрісхана жұмыстарының жеткізуіне мәлімдемелерді n тап осы әрбір мәлімдемеде бас көрсетілген және жұмыс соғысы (si және арналған fi). Мәлімдемені нөмірлерімен және j бірлескен, егер аралықтар [ si , fi ) және [ sj , fj ) емес (т. fi е . sj немесе fj si ). маќсат мәлімдемелерді талдауы туралы түзеледі, мәлімдемелерді дос- досымен бірге барынша көп сан теріп алу үшін.

ШЖН – ОБ – 00109 – 2005
Сараң алгоритмді ертіп әкелеміз, тап осы мақсатты шешуші Мыналар жанында ойлаймыз, болмаса мәлімдемелер аяқталады. Уақыттарыны мына түрде реттелген
Activity - Selector ( s , f )
1 n length [ s ]
?{1}
3 j ?1
4 for i ?2 to n
5 do if si fj
?{ i }
7 j i
Осы алгоритмге кіру үшін бас сілемдері және жұмыстарды аяқтылары береді. Жиыны таңдалған мәлімдемелерді нөмірлерінен түзеледі, соңғы мәлімдеме j – нөмірі. Сараң алгоритм мәлімдемені іздейді, басталушының аяғы ертерек емес j - ана, содан соң табылған мәлімдемені қосады, ал j оның нөмірі иемденеді.
Алгоритм үшін жұмыс істейді (nlogn + n), е. т. сорттау қосамыз сұрыптау. Әрбір адымда ең жақсы шешім шығады. Көрсетеміз, жиыныда ең жақсы жағдайлар жиынтығы болып шығады.
Дәлел. Көріп қаламыз, барлық мәлімдемелер аяғы уақыттарының кему сызығы мен сорттап шығарылған. Мәлімдеме нөмір 1, айқын, ең жақсы жағдайлар жиынтығына кіреді (егер жоқ, онда оған ең жақсы жағдайлар жиынтығында ең ерте мәлімдемені ауыстыруға болатын, мынаның одан нашар болмайды). Мәлімдеменің барлық лақтырып тастап, біріншінің қарсы келетіндер, мәлімдемелердің аз санымен негізгі мақсатты аламыз. Үйлесімді шешімге индукциямен келеміз, ұқсас бейнемен ойлай.
ШЖН – ОБ – 00109 – 2005
Сараң алгоритм қолданушылығы
Жалпы оқиғада айтуға болмайды, болады сараң алгоритм арқасында нақтылы мақсатқа сәйкес үйлесімді шешім алу. Бірақ екі ерекшелік бар, мінездемелер мақсаттарға арналған,сараң алгоритмдер арқасында шешіледі: сараң таңдау принципі және қасиет - үшін .
Сараң таңдау принципі
Сөйлейді, ықшамдау мақсатына сараң таңдау принципін қолдануға болатын, егер жергілікті үйлесімді таңдауларды жүйелілігі глобальды үйлесімді шешімді берсе. Мынада динамикалық бағдарламалауды сараң алгоритмдерді негізгі айырмашылығы түзеледі: барлық түрлерді зардабы лезде екіншісінде жалғасады.
Іспен көрсету үшін, сараң алгоритм ең жақсы жағдайлар жиынтығын береді, дәлел өткізуге талаптану керек,алгоритм ұқсас мақсат дәлеліне мәлімдемелерді таңдауы туралы. Біз алдымен көрсетеміз, сараң таңдау бірінші адымда үйлесімді шешімге жол жаппайды:сараң таңдаумен басқа, келісілген үшін-шешімдер бар және одан нашар емес біріншісі. Біз сонан соң көрсетеміз, тапсырмадан кейін, көрінген сараң таңдаудан кейін негізгі ұқсас бірінші адымда. Индукциямен ереді, сараң таңдаулар сондай жүйелілігі үйлесімді шешім береді.

Мынау қасиет томға сөйлейді, үйлесімді шешімді тапсырмадан кейін барлық мақсаттарды асырайды. Үйлесімді шешімдерге мысалы, мақсатта мәлімдемелерді таңдауды көріп қалуға болады, егер мәлімдемелерді-үйлесімді терімі, 1, нөмір мәлімдеме ұстаушы анау ?= \{1}- мәлімдемелерді үйлесімді терімі үшін мәлімдемелері аз жиындары ?, ана мәлімдемелерден құрылушыны білуге болады.

ШЖН – ОБ – 00109 – 2005
Сараң алгоритм немесе динамикалық бағдарламалау

Динамикалық бағдарламалау аралық ерекшелік және сараң алгоритммен арқа қоржын туралы мақсат үлгісінде нақтылы мысал келтіруге болады, оның дискреттік және толассыз қалыптастыруында. Толассыз мақсат сараң әдіспен шешіледі, дискреттік жіңішке және динамикалық шешім көбірек талап етеді.
Дискреттік мақсат арқа қоржын туралы. Ұры сараң әрең өтті, заттар қайсысында сақталады n. Әрбір зат доллардан vi тұрады және килограм wi ауыр тартиды. Ұры барынша көп сомада тауарды алып кетуді қалайды, бірақ ол килограм көбірек W көтере алмайды (барлық бүтін санды). Арқа қоржынға тиісті қою ?
Толассыз мақсат арқа қоржын туралы. Қазір ұры тауарларды уатуға біледі және арқа қоржынға салу оларды тек қана бөлімді, ал міндеті тұтас емес. Әдеттегі дискреттік мақсатта сөйлеу жүреді, алтындарды әр түрлі сынау кесектерінде, ал толассызды-алтынмен құмда.
Бос арқа қоржын бола, толассыз мақсат оқиғасында заттарды салыстырмалы құнын есептейміз, барынша толыққып содан соң ең қымбат затты аламыз, содан соң екінші құнмен және т. т. соған дейін, соңғы зат білуге келіп жатқанда, оқиғада дискреттік мақсатты, аналарды түсініктермен пайдаланады, біз бірінші затты алдымен қоямыз, бірақ қазір бізге анағұрлым арқа қоржын жатқызу байлауды астына емес ең қымбаттарымен (аласы да емес килограмды) заттарды қандай біз дәл осылай $220 табыс кіргіземіз орнына алынғандарды алгоритммен $160.

ШЖН – ОБ – 00109 – 2005
Хаффмена кодтары
Хабар қысуы жанында Хаффмена кодтары тез қолданылады. Бұлар сараң алгоритмнің көмегі жанында кодтар салуға болады, Хаффменмен ұсынылған болатын.
Біз онан әрі кодтар тек қана анықтап қараймыз, қайсылары биттарды екі жүйелілігінен, таныстырушы әртүрлі символдар емес басқа бір префикспен кодтар келмейді.Кодты-Көріп қалу үшін, хабар жүзеге асыратын бұрынғы бір мағыналы қалыпқа келуі, бар болады емес жаманырақ префиксті код.
Хабардың кодтау жанында әрбір символ өз кодына ауыстырылады. Үшін-кодтарды кодпен ашу үшін бір мағыналы орындалады, сол жағында және оңда. Кодпен ашу процесін нәтижелі іске асыру үшін, ыңғайлы түрге код туралы хабарды қажетті сақтау. Мысалы; қайсысы кодталған символдарға талапқа сай болады: екілік ағашты жапырақтар түрінде кодқа ұсынуға болады. Ал ағаш шығыны жолы кодталған символға дейін биттарды жүйелілік кодтайтынға анықтайды:солға бұрылу-0, оңға-1 береді.
Үйлесімді кодқа екілік ағаш әрқашан талапқа сай болады, қайсыда-шын, емен жапырақпен болатын, екеулерінің балалары болады. Мынау томға қорытындыға келу жеңіл қасиет рұқсат етеді, файлға арналған үйлесімді-код ағашы, қайсыда-жиындарында символдарды барлығы қолданады және олар тек қана, жапырақтарды, тегіс асырайды, әрбір символға біреуін емен және тегіс ?1 түйін, емес жапырақтармен болатындарды.
Биттарды саны разы жеңіл табу, қажетті файл кодтауына арналған, егер біз ағашын білсек, лайықты-кодқа. F мейлі [ c ] белгілейді (c)-тереңдікті ағашта жапырақ лайықты (биттарды жүйелілік ұзындығын, c кодтайтын). аламыз, файл кодтауына арналған қажетті
( )=? c C f [ c ] ( c )
ШЖН – ОБ – 00109 – 2005
Хаффмен сараң алгоритмін ертіп әкелеміз, салған үйлесімді префиксный Хаффменн. код-коды мыналар жанында болжаймыз, үшін-символыны ? f оның жиілігін берілген [c]. сонымен қатар алгоритмде приоритеттерімен кезек қолданылады, оларды ағып келіп қосылуына арналған ең азы жиіліктермен екі объекті табуға рұқсат етеді.
Huffman ( )
1 n ?
А
3 for i ?1 to n -1
4 do z Allocate - Node ()
5 x left [ z ]? Extract - Min ( )
6 y right [ z ]? Extract - Min ( )
7 f [ z ]? f [ x ]+ f [ y ]
8 Insert ( , z )
9 return Extract - Min ( )
Ағаш - кодтарды үйлесімді алгоритм салады. Үшін мынаны циклда орындалады x екі шыңы кезегінен сұрыптау және y наменьшими мен жиіліктермен (f [x] және f [y] сәйкесті), қайсылар ауыстырылады біреуінің z шыңын f жиілігімен [x]+ f [y] және x балаларымен және y.
Алгоритм үшін жұмыс істейді (nlogn) символдарды n әліппеге арналған. Не есептей, кезегі екілік үймелер түрінде іске асырылған, біз арналған инициализациясын орындай аламыз (n), ал әрбір операцияны арналған үйменің үстінде (logn).

ШЖН – ОБ – 00109 – 2005
Хаффмен алгоритмінің дұрыстығы
Іспен көрсетеміз, мақсатқа арналған үйлесімдіде-код туралы орындалады сараң таңдау принципі және қасиет-үшін тапсырмадан кейін. Лемманы ертіп әкелеміз, көрсетушіні, қомағай таңдауды принцип орындалған.
Лемма 1
Әліпбесінде мейлі кез келген символы ма? f жиілігін болады [c]. x, y мейлі ? -екі символ ең азы жиіліктермен. Үйлесімді арналған сол уақытта болады префиксный код, биттарды қайсы жүйеліліктері , x кодтайтын және y, бірдей ұзындықты және соңғы битта тек қана айырады.
Дәлел. T. Ағаш - кодтарыны көрсетеміз өз бетімен үйлесімді қарап шығамыз, не мынау дәл осылай ағаш өзгертуге болады, жапырақтар үшін, x лайықты және y, ағайындармен болар еді, егер олар сондай болу ертерек. Мынау және тап осы лемманы іспен көрсетеді.
Ағаштары көршілес жапырақтарды буына қарап шығамыз, орнында болғанды түбірді барынша көп ара қашықтығында. Символдар, орналасады бұларды жапырақтарда (b және c), аз жиіліктер емес болады, немен x және y. есептеуге болады, f [ x ]? f [b] және f [y]? f [ ]. Ағашымен екі операцияны онан әрі іске асырамыз: b символдары және x орындармен ауыстырамыз (алынған ағаш ат қоямыз ?), ал c символдары және y содан соң (қазір көрсетеміз алынған ағаш T ?). Ат қоямыз, ағашы ? Үйлесімді сонымен қатар келеді. Үшін мынаны керек іспен көрсету, ( ( ( ?)( құн-функциясы). Асуы жанында ? екі тек қана құн функциясында алмастырады қосылғандарды: f [ b ] ( b )+ f [ x ] ( x ) f ауыстырылады [ b ] ?( b )+ f [ x ] ?( x ), f е . т . [ b ] ( x )+ f [ x ] ( b ). аламыз
( ( ?)= f [ b ] ( b )+ f [ x ] ( x )? f [ b ] ( x )? f [ x ] ( b )=( f [ b ]? f [ ( ( x ))?0.
ШЖН – ОБ – 00109 – 2005
Ұқсас дәлелдейміз ( ( ?), аламыз ( ( ?), және ағашы сондықтан ба? Сонымен қатар үйлесімді.
Қазір тапсырмадан кейін орындалған қасиет-үшін, ал ?-әліппе, болып шығады, егер x және y лақтырып тастау және арналған кодты ағаштар қарап шығамыз z. Жаңа символын қосу, x қайсыларды және y ағайындармен келеді. Аламыз, не арналған кодты ағаш бір арналған әрбір ағашқа талапқа сай болады ? алшы, егер x шыңдары және y алып тастау, ал оларды жалпы әке-шешені z. символы кодымен есептеу арналған мына ағашқа ма? Екі талапқа сай болады кодтыларды C. арналған ағашты
Әрбір символды артынан ? F жиілігін оны бекітеміз [c]. символдарға арналған ? z басқа ( f [ z ]= f [ x ]+ f [ y ]), сондай жиілікті ғой, не және C. Лемманы қисынға келтіруге қазір болады.
Лемма 2
Құнны дос лайықтыларды ?( суреттелген сәйкестік жанында ) f мөлшеріне құйып алады [ x ]+ f [ y ].
Дәлел. Мәлім, ( c )= ?( x ) барлықтарға арналған ? ( ( y )= ?( z )+1. аламыз
F [ x ] ( x )+ f [ y ] ( y )=( f [ x ]+ f [ y ])( ?( z )+1)= f [ z ] ?( z )+( f [ x ]+ f [ y ]).
( ( ?)+ f [ x ]+ f [ y ].
Теорема
Үйлесімді Хаффмен сараң алгоритмі салады префиксті код.
Дәлел. Сондай арасында үйлесімді кодты ағаштар іздеуге болады, қайсыларды екі ең сиректерді символды ( x және y ) ағайындармен келеді (леммамен 1). Оларға әліппеге арналған ағаштар талапқа сай болады ?, X қайсыда және y z . құйылєан егер есептеу, f [
ШЖН – ОБ – 00109 – 2005
z ]= f [ x ]+ f [ y ], анау леммамен 2 бізге әліппесіне арналған үйлесімді кодты ағаш табуға қалады ?, ал екі бала z шыңға содан соң қосу, x символдармен таңбалағандарды және y .
Сараң алгоритмдердің теориялық негіздері (матроиды)
Сараң алгоритм (Greedy algorithm)
- Берілген жиын барынша көп салмақ ішкі жиын іздеп табу қиыстыру ықшамдау алгоритмі, қайсы жазылып қойылған-салмақ элементтеріне. Сараң алгоритм дұрыс шешімді береді, егер негізгі жиындар матроид бар http : iis . pco . su nsk . grapp sl _ html m . . Сараң алгоритмдерге графаларда көптеген алгоритмдерді жатады, мысалы , Краскала алгоритмдары http : iis . pco . su nsk . grapp sl _ html a . жјне прима http : iis . pco . su nsk . grapp sl _ html a . ең азы салмақ каркасы іздеп табу
Мысал
Тиінді майдалау
1=1 a 2... an . a адамгершілігімен жүйе-мемлекет ақша Тапсырма. ақшалардан түзеледі талап етеді ақшаларды ең азы мүмкін санымен сомасын беру .
Мына мақсат шешім сараң алгоритмі сондай. An адамгершіліктері аќшалардыѕ еѕ їлкен мїмкін саны алады :. сондаймен єой бейнемен аламыз , ќаншалар аз номинал аќшалары керек , жјне д . т .
Тап осы маќсаттардыѕ артынан ќомаєай алгоритм їйлесімді шешімді јрќашан емес береді . Мысалы , соманы 10 тиындардыѕ аќшалармен 1,5 жјне 6 коп . ќомаєай алгоритм ўсаќтайды дјл осылай :6 коп .-1 шт .,1 коп .-4 шт ., сол уаќытта дўрыс шешім -2 аќшалар 5 тиындардыѕ . Јйткенмен , барлыќ наќты аќшаларды жїйелерде ќомаєай алгоритм дўрыс жауапты береді .

ШЖН – ОБ – 00109 – 2005
Сараң алгоритмнің түрлері
Хаффмана алгоритмі
Краскала алгоритмі
Прима алгоритмі
Радо - Эдмондсо - жалпы екі сараѕ болып табылады . алгоритмы
Краскала алгоритмі
Алгоритмі примасы

Бірлестік порталы
Форум

Жаѕа тїзетудіѕ
Жаѕа беттіѕ
Мјлімет
Садаќа етудіѕ
Іздеу

Маќсат . Аќша 1=1 a 2... an . a адамгершілігімен жїйе - мемлекеттер аќшалардан тїзеледі Требуется аќшалардыѕ еѕ азы мїмкін санымен сомасын беру .
Мына маќсат шешім ќомаєай алгоритмы сондай . An адамгершіліктері аќшалардыѕ еѕ їлкен мїмкін саны алады :.

ШЖН – ОБ – 00109 – 2005
сондаймен єой бейнемен аламыз , ќаншалар аз номинал аќшалары керек , жјне д . т .
Тап осы маќсаттардыѕ артынан ќомаєай алгоритм їйлесімді шешімді јрќашан емес береді . Мысалы , соманы 10 тиындардыѕ аќшалармен 1,5 жјне 6 коп . ќомаєай алгоритм ўсаќтайды дјл осылай :6 коп .-1 шт .,1 коп .-4 шт ., сол уаќытта дўрыс шешім -2 аќшалар 5 тиындардыѕ . Јйткенмен , барлыќ наќты аќшаларды жїйелерде ќомаєай алгоритм дўрыс жауапты береді.
Хаффман алгоритм. ( Huffman англ . )- оптималды префикстеліп кодталєан жеке минимальды алфавиттен тўратын сараѕ алгоритм .1952 Ќазіргі таѕда кґптеген программалардыѕ берілгенін сыєу їшін пайдаланылады. ж Массачусет технологиялыќ институтыныѕ докторы Дэвид Хафман көмегімен істелінген .
Шеннона - Фано алгоритмыныѕ айырмашылыєына , їйлесімді јрќашан Хаффмана алгоритмы ќалады жјне m екінші ќайтара јліпбилеріне арналєан 2 екімен кґбірек символдармен .
мынау кодтау әдісі түзеледі екіні негізгі кездерді:
Үйлесімді кодты аєаш ќўруы .
Елестету құру код - символ салєан аєаш негізінде . Ўстау
1 алгоритм
Орындау 2 үлгісі
3 сілтеме
4 әдебиет

ШЖН – ОБ – 00109 – 2005
Алгоритм
Подсчитываются негізгі мјтінде алєашќы әліппе символдарыныѕ кґріну ыќтималдыќтары ... жалғасы

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