2月 | 2013 | 情報工学とその周辺

['1301', '1332', '1334', '1352', '1377', '1379', '1414', '1417', '1514', '1515', '1518', '1605', '1606', '1661', '1662', '1712', '1719', '1720', '1721', '1722', '1762', '1766', '1780', '1801', '1802', '1803', '1805', '1808', '1810', '1812', '1813', '1814', '1815', '1816', '1819', '1820', '1821', '1822', '1824', '1826', '1827', '1833', '1834', '1835', '1847', '1852', '1860', '1861', '1865', '1866', '1867', '1868', '1870', '1871', '1878', '1879', '1881', '1882', '1883', '1884', '1885', '1888', '1890', '1893', '1896', '1898', '1899', '1911', '1914', '1916', '1919', '1921', '1924', '1925', '1926', '1928', '1929', '1930', '1934', '1937', '1939', '1941', '1942', '1944', '1945', '1946', '1949', '1950', '1951', '1952', '1954', '1956', '1959', '1961', '1963', '1964', '1967', '1968', '1969', '1972', '1973', '1975', '1978', '1979', '1980', '1982', '1983', '2001', '2002', '2003', '2004', '2009', '2052', '2053', '2056', '2107', '2108', '2109', '2120', '2127', '2128', '2131', '2151', '2168', '2170', '2174', '2175', '2181', '2193', '2196', '2198', '2201', '2204', '2206', '2207', '2211', '2212', '2215', '2217', '2220', '2229', '2264', '2267', '2269', '2270', '2281', '2282', '2284', '2286', '2288', '2290', '2292', '2301', '2305', '2309', '2317', '2322', '2327', '2331', '2353', '2359', '2371', '2372', '2378', '2395', '2398', '2413', '2418', '2432', '2433', '2440', '2450', '2453', '2462', '2466', '2491', '2501', '2502', '2503', '2531', '2533', '2540', '2572', '2579', '2580', '2590', '2593', '2594', '2597', '2599', '2602', '2607', '2613', '2651', '2659', '2660', '2662', '2664', '2670', '2674', '2676', '2678', '2681', '2685', '2687', '2692', '2695', '2698', '2715', '2726', '2729', '2730', '2733', '2734', '2737', '2749', '2753', '2760', '2764', '2768', '2772', '2784', '2791', '2792', '2801', '2802', '2809', '2810', '2811', '2812', '2815', '2871', '2874', '2875', '2897', '2899', '2908', '2910', '2914', '2915', '2918', '2922', '3001', '3002', '3003', '3004', '3022', '3023', '3028', '3034', '3036', '3048', '3050', '3064', '3076', '3086', '3087', '3088', '3091', '3092', '3097', '3098', '3099', '3101', '3103', '3104', '3105', '3106', '3107', '3109', '3110', '3116', '3141', '3148', '3151', '3153', '3156', '3159', '3167', '3201', '3202', '3204', '3205', '3225', '3228', '3231', '3258', '3302', '3313', '3315', '3321', '3333', '3341', '3349', '3360', '3366', '3371', '3382', '3391', '3395', '3396', '3397', '3398', '3401', '3402', '3405', '3407', '3408', '3421', '3431', '3433', '3434', '3436', '3443', '3501', '3512', '3513', '3514', '3521', '3524', '3526', '3529', '3551', '3553', '3569', '3577', '3580', '3591', '3593', '3606', '3607', '3608', '3620', '3626', '3627', '3630', '3632', '3635', '3636', '3639', '3640', '3656', '3657', '3659', '3660', '3662', '3708', '3715', '3724', '3730', '3738', '3762', '3769', '3770', '3774', '3817', '3834', '3861', '3864', '3865', '3877', '3878', '3880', '3893', '3941', '3946', '3950', '4003', '4004', '4005', '4007', '4008', '4021', '4022', '4023', '4027', '4028', '4031', '4041', '4042', '4043', '4044', '4045', '4046', '4047', '4061', '4062', '4063', '4064', '4078', '4088', '4091', '4092', '4095', '4097', '4098', '4099', '4100', '4109', '4112', '4114', '4116', '4118', '4151', '4182', '4183', '4185', '4186', '4187', '4188', '4201', '4202', '4203', '4204', '4205', '4206', '4208', '4212', '4215', '4216', '4217', '4218', '4220', '4221', '4228', '4229', '4231', '4238', '4271', '4272', '4282', '4283', '4295', '4301', '4307', '4310', '4312', '4319', '4321', '4324', '4326', '4331', '4337', '4340', '4343', '4344', '4346', '4350', '4362', '4401', '4403', '4404', '4410', '4452', '4461', '4471', '4502', '4503', '4506', '4507', '4508', '4512', '4514', '4516', '4519', '4521', '4523', '4527', '4528', '4530', '4531', '4534', '4536', '4538', '4539', '4540', '4541', '4543', '4544', '4547', '4548', '4549', '4550', '4551', '4553', '4554', '4555', '4559', '4568', '4569', '4574', '4577', '4578', '4581', '4611', '4612', '4613', '4614', '4617', '4619', '4620', '4626', '4631', '4633', '4634', '4641', '4651', '4653', '4658', '4661', '4665', '4666', '4668', '4671', '4674', '4676', '4678', '4679', '4680', '4681', '4684', '4687', '4689', '4694', '4696', '4704', '4708', '4711', '4714', '4716', '4718', '4719', '4722', '4724', '4725', '4726', '4728', '4732', '4733', '4739', '4743', '4745', '4746', '4762', '4767', '4768', '4775', '4776', '4779', '4799', '4801', '4812', '4820', '4825', '4826', '4839', '4848', '4901', '4902', '4911', '4912', '4914', '4917', '4919', '4921', '4922', '4924', '4927', '4928', '4951', '4956', '4958', '4963', '4967', '4968', '4971', '4973', '4975', '4977', '4985', '4989', '4992', '4994', '4996', '4997', '5002', '5007', '5009', '5011', '5012', '5013', '5015', '5017', '5018', '5019', '5020', '5101', '5105', '5108', '5110', '5121', '5122', '5142', '5185', '5186', '5187', '5191', '5192', '5195', '5196', '5201', '5202', '5204', '5208', '5210', '5214', '5218', '5232', '5233', '5234', '5261', '5262', '5269', '5288', '5301', '5302', '5310', '5331', '5332', '5333', '5334', '5337', '5344', '5351', '5352', '5363', '5367', '5384', '5391', '5393', '5401', '5406', '5408', '5410', '5411', '5413', '5423', '5440', '5444', '5445', '5449', '5451', '5453', '5457', '5463', '5464', '5471', '5476', '5480', '5481', '5482', '5486', '5491', '5541', '5563', '5602', '5612', '5631', '5632', '5658', '5659', '5702', '5703', '5706', '5707', '5711', '5713', '5714', '5715', '5726', '5727', '5738', '5741', '5801', '5802', '5803', '5805', '5807', '5809', '5812', '5815', '5819', '5821', '5851', '5857', '5901', '5902', '5909', '5911', '5912', '5915', '5923', '5929', '5930', '5932', '5936', '5938', '5942', '5943', '5946', '5947', '5949', '5951', '5957', '5958', '5959', '5974', '5975', '5976', '5981', '5988', '5991', '5992', '5998', '6005', '6013', '6054', '6101', '6103', '6104', '6113', '6118', '6135', '6136', '6138', '6140', '6141', '6146', '6151', '6201', '6203', '6205', '6208', '6210', '6217', '6218', '6222', '6247', '6250', '6262', '6268', '6269', '6272', '6273', '6274', '6277', '6278', '6282', '6287', '6291', '6293', '6298', '6301', '6302', '6305', '6306', '6309', '6310', '6315', '6316', '6317', '6319', '6326', '6328', '6330', '6331', '6332', '6333', '6335', '6339', '6340', '6345', '6349', '6351', '6355', '6358', '6361', '6362', '6363', '6366', '6367', '6368', '6369', '6370', '6371', '6373', '6375', '6376', '6378', '6379', '6381', '6383', '6390', '6393', '6395', '6406', '6407', '6409', '6412', '6413', '6417', '6418', '6419', '6420', '6428', '6430', '6436', '6440', '6444', '6445', '6448', '6454', '6455', '6457', '6459', '6460', '6461', '6462', '6463', '6465', '6470', '6471', '6472', '6473', '6474', '6479', '6480', '6481', '6482', '6485', '6486', '6489', '6490', '6498', '6501', '6502', '6503', '6504', '6505', '6506', '6507', '6508', '6513', '6517', '6581', '6584', '6586', '6588', '6590', '6592', '6594', '6617', '6620', '6622', '6630', '6632', '6640', '6641', '6644', '6645', '6651', '6652', '6674', '6675', '6676', '6678', '6701', '6702', '6703', '6704', '6706', '6707', '6715', '6718', '6723', '6724', '6727', '6728', '6730', '6731', '6737', '6741', '6742', '6744', '6745', '6751', '6752', '6753', '6754', '6755', '6756', '6758', '6762', '6763', '6767', '6768', '6770', '6771', '6773', '6779', '6788', '6789', '6791', '6794', '6796', '6798', '6800', '6801', '6803', '6804', '6806', '6807', '6809', '6815', '6816', '6817', '6820', '6823', '6839', '6841', '6844', '6845', '6849', '6850', '6853', '6855', '6856', '6857', '6858', '6859', '6860', '6861', '6866', '6869', '6875', '6877', '6883', '6885', '6900', '6901', '6902', '6905', '6910', '6911', '6914', '6915', '6923', '6924', '6925', '6926', '6927', '6929', '6935', '6937', '6938', '6941', '6947', '6951', '6952', '6954', '6958', '6961', '6963', '6965', '6966', '6967', '6971', '6973', '6976', '6981', '6985', '6986', '6988', '6989', '6995', '6996', '6997', '6999', '7003', '7004', '7007', '7011', '7012', '7013', '7102', '7105', '7122', '7148', '7150', '7161', '7164', '7201', '7202', '7203', '7205', '7211', '7212', '7220', '7222', '7224', '7226', '7230', '7231', '7236', '7238', '7239', '7240', '7241', '7242', '7243', '7244', '7245', '7246', '7248', '7250', '7251', '7256', '7259', '7260', '7261', '7262', '7266', '7267', '7269', '7270', '7272', '7274', '7276', '7277', '7278', '7280', '7282', '7283', '7294', '7296', '7305', '7309', '7312', '7313', '7414', '7416', '7420', '7421', '7427', '7433', '7438', '7442', '7445', '7447', '7448', '7451', '7453', '7455', '7456', '7459', '7463', '7466', '7476', '7480', '7481', '7482', '7483', '7494', '7504', '7506', '7508', '7512', '7513', '7514', '7516', '7517', '7518', '7520', '7522', '7524', '7532', '7537', '7541', '7545', '7550', '7552', '7554', '7558', '7561', '7581', '7591', '7594', '7595', '7599', '7600', '7601', '7606', '7607', '7608', '7609', '7611', '7613', '7615', '7616', '7619', '7628', '7630', '7631', '7637', '7640', '7649', '7701', '7702', '7709', '7714', '7715', '7717', '7718', '7721', '7723', '7728', '7729', '7730', '7731', '7732', '7733', '7734', '7735', '7739', '7740', '7741', '7744', '7745', '7751', '7752', '7756', '7762', '7769', '7775', '7817', '7819', '7821', '7822', '7825', '7832', '7838', '7840', '7844', '7846', '7860', '7862', '7864', '7867', '7868', '7873', '7874', '7885', '7893', '7897', '7898', '7905', '7908', '7911', '7912', '7913', '7914', '7915', '7916', '7917', '7921', '7925', '7936', '7937', '7942', '7943', '7944', '7947', '7949', '7951', '7952', '7955', '7956', '7958', '7961', '7962', '7966', '7968', '7970', '7971', '7972', '7974', '7976', '7979', '7981', '7984', '7987', '7988', '7990', '7994', '7995', '7999', '8001', '8002', '8005', '8007', '8008', '8011', '8012', '8013', '8014', '8015', '8016', '8018', '8020', '8022', '8025', '8028', '8029', '8031', '8032', '8035', '8036', '8037', '8038', '8043', '8050', '8051', '8052', '8053', '8056', '8057', '8058', '8059', '8060', '8061', '8065', '8068', '8070', '8074', '8075', '8078', '8081', '8084', '8086', '8087', '8088', '8089', '8090', '8091', '8093', '8095', '8096', '8097', '8098', '8101', '8103', '8111', '8113', '8114', '8127', '8129', '8130', '8131', '8132', '8133', '8136', '8137', '8140', '8141', '8142', '8150', '8151', '8153', '8154', '8155', '8158', '8159', '8160', '8165', '8166', '8168', '8170', '8173', '8174', '8175', '8178', '8179', '8181', '8182', '8184', '8185', '8194', '8196', '8200', '8201', '8203', '8207', '8214', '8217', '8218', '8219', '8227', '8229', '8233', '8237', '8242', '8245', '8248', '8251', '8252', '8253', '8255', '8260', '8263', '8266', '8267', '8270', '8273', '8274', '8276', '8278', '8279', '8281', '8282', '8283', '8289', '8291', '8303', '8304', '8306', '8308', '8309', '8316', '8324', '8325', '8327', '8331', '8332', '8333', '8334', '8336', '8337', '8338', '8339', '8341', '8342', '8343', '8344', '8345', '8346', '8349', '8350', '8354', '8355', '8356', '8358', '8359', '8360', '8361', '8362', '8363', '8364', '8366', '8367', '8368', '8369', '8374', '8377', '8379', '8381', '8382', '8383', '8385', '8386', '8387', '8388', '8390', '8392', '8393', '8394', '8395', '8396', '8397', '8399', '8409', '8410', '8411', '8415', '8418', '8423', '8424', '8425', '8439', '8473', '8511', '8512', '8515', '8518', '8519', '8521', '8522', '8524', '8527', '8529', '8530', '8536', '8537', '8541', '8542', '8543', '8544', '8545', '8550', '8551', '8558', '8562', '8563', '8566', '8570', '8572', '8584', '8585', '8586', '8591', '8593', '8595', '8600', '8601', '8604', '8609', '8613', '8614', '8616', '8617', '8622', '8624', '8628', '8630', '8692', '8697', '8698', '8703', '8706', '8707', '8713', '8714', '8725', '8729', '8742', '8750', '8766', '8771', '8772', '8793', '8795', '8801', '8802', '8803', '8804', '8806', '8815', '8818', '8830', '8833', '8835', '8840', '8841', '8842', '8848', '8860', '8864', '8869', '8870', '8871', '8875', '8876', '8877', '8879', '8880', '8881', '8895', '8897', '8904', '8905', '8907', '8915', '8918', '8923', '8933', '8934', '8944', '8999', '9001', '9003', '9005', '9006', '9007', '9008', '9009', '9010', '9014', '9020', '9021', '9022', '9031', '9037', '9039', '9041', '9042', '9044', '9045', '9047', '9048', '9058', '9062', '9064', '9065', '9066', '9067', '9068', '9069', '9070', '9072', '9074', '9075', '9076', '9081', '9086', '9101', '9104', '9107', '9110', '9113', '9115', '9119', '9130', '9132', '9201', '9202', '9232', '9301', '9302', '9303', '9304', '9305', '9306', '9310', '9312', '9324', '9351', '9358', '9364', '9366', '9368', '9369', '9370', '9375', '9380', '9381', '9401', '9404', '9409', '9412', '9413', '9422', '9430', '9432', '9433', '9435', '9437', '9449', '9470', '9474', '9475', '9477', '9479', '9501', '9502', '9503', '9504', '9505', '9506', '9507', '9508', '9509', '9511', '9513', '9531', '9532', '9533', '9534', '9536', '9543', '9600', '9601', '9602', '9603', '9605', '9607', '9613', '9616', '9619', '9621', '9622', '9627', '9628', '9632', '9633', '9671', '9672', '9675', '9678', '9681', '9682', '9684', '9692', '9697', '9704', '9706', '9715', '9716', '9717', '9719', '9722', '9726', '9728', '9729', '9731', '9735', '9739', '9740', '9742', '9743', '9744', '9746', '9747', '9749', '9755', '9757', '9759', '9760', '9763', '9766', '9783', '9787', '9788', '9790', '9792', '9793', '9795', '9810', '9828', '9830', '9831', '9832', '9842', '9843', '9850', '9854', '9861', '9869', '9880', '9882', '9883', '9887', '9889', '9896', '9900', '9902', '9928', '9930', '9932', '9934', '9938', '9945', '9946', '9948', '9956', '9957', '9962', '9963', '9972', '9974', '9979', '9982', '9983', '9984', '9987', '9989', '9990', '9991', '9993', '9994', '9997']

What is algorithm?

Algorithm: well-defined computational procedure. it has input and output such as some values. it is composed of a sequence of computational steps.

Correctness: for every input instance, the algorithm halts with the correct output.

Correct algorithm solves the given computational problem.

What is data structure?

Data Structure: a way to store and organize data in order to facilitate access and modifications.

No single data structure works well for all purposes.

Various techniques of algorithm design and analysis

Order notation
Minimum spanning trees (MST)
Maximum flow in a network
Divide-and-conquer
Dynamic Programming (DP)
Amortized analysis

etc.

Hard problems

NP-complete: the subset of computational problems.
1) no efficient algorithm for this type of problem has ever been found, and nobody has ever proven that an efficient algorithm for one cannot exist. (In other words, no one knows whether or not efficient algorithm exist for NP-complete problem.)
2) this problem has remarkable property that if an efficient algorithm exists for any one of them, then efficient algorithms exist for all of them. (!)
3) several NP-complete problems are similar to problems for which we know efficient algorithms.

E.g. Traveling-salesman problem
To deliver goods to several address, we want to know the shortest overall distance traveled by car. => This is NP-complete (no efficient algorithm exists! However under some assumptions, we can use approximate algorithms.)

Efficiency

Different algorithms devised to solve the same problem often differ dramatically in their efficiency. (=> Discuss Order notation)
Difference of efficiency can be much more significant than differences than differences due to hardware and software.

E.g. Time complexity
Two algorithms for sorting. if n items given as input, computational time of each algorithm are
1) Insertion sort: $c_1 n^2$
2) Merge sort: $c_2 n{\rm log}n$
where $c_1, c_2$ are constant.
Although insertion sort usually runs faster than merge sort for small input size, the input size $c$ becomes large enough, merge sort’s advantage of ${\rm log}n$ vs. $n$ .

Algorithms are at the core of most technologies.
Skilled programmers with the knowledge of algorithms.

情報工学とその周辺

Connecting dots.

月別アーカイブ: 2013年2月

良い進捗報告に必要なもの

東証一部上場会社 1699社コードリスト (2013.02.24現在)

[Algorithms] Algorithms and Data Structure

[latex]テーブルのキャプションの文字”表”を”図”に変更する方法